My software development journey
Given a string, how do we reverse the words inside the string? For example if the input string is “this is a test” the output should be “test a is this”. The algorithm is simple. This can be done in two steps. The first step is to reverse the entire string. In the second step…
Given a string and a character, Write a function to remove all instances of the character and return the modified string. One easy method is to iterate through each character of the string, Once a restricted character is seen, we move all the characters appearing after it by one position. This approach involves a lot…
Counting sort as its name indicates sort a list of integers by counting the occurrence each number appearing in the list. This is possible when the range of integers (particularly small) is given. Unlike comparison based sorting algorithms which run in O( n log n) time in the worst case, Counting sort runs O(n) time.…
Given an array of positive and negative values. We have to find the maximum sum a sub-array can have. For example the the array {-1, 7, -2, 4, -3, -9, 2} has a maximum sum of 9 which corresponds to the sub-array {7, -2, 4}. To solve this problem, we take two variables to keep…
Given an array of numbers which contains all the numbers in pairs expect one element. We have to find that unique element. For example in the array [7,3,8,1,3,4,7,1,8] 4 is the unique element and all the remaining elements occur in pairs. This is actually a specific case of more generic problem discussed in the my…
Given a set of numbers, how do we generate its power set? For example for the set {1,2} the power set is given below. { {}, {1}, {2}, {1,2} } A power set is nothing but all the possible subsets of a given set. If a set contains N elements, it’s power set contains 2N…
Given an array of numbers which indicates the prices of stocks for a period of time. We have to find the two values in the array such that their difference is maximum and also the greater value must appear later than smaller value. In another way, we have to find the buying and selling price…
Given a Binary Search Tree (BST), How do we find the Lowest Common Ancestor (LCA) of the given two nodes? For example in the following BST, the LCA of 5 and 8 is 7 because it is the nearest ancestor common to both the nodes. Let us assume that the LCA(5,7) is 7 itself (…
Given a matrix of size M x N which contains only 0s and 1s, How do we find the largest square sub-matrix which contains all 1s. For example in the following example, highlighted portion indicates a 3×3 square sub-matrix with all 1s. 1 0 0 1 1 0 0 1 1 1 1 1 0…
How do we write a program to print the binary representation of an integer?For the sake of simplicity, let us assume that the integer takes 32 bits. The integer 367 is represented in binary as follows.0000 0000 0000 0000 0000 0001 0110 1111Iterative Method:In this method we extract the bit at each of the 32…