My software development journey
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 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…
Given an integer how do we check if it is a power of 2?For example 1, 2, 4, 8, 16, 32, 64, 128, 256,… are integral powers of 2.There are several methods to check if a number is a power of 2.Method#1: Using repeated division If you repeatedly divide the number by 2 (without any…
Given an integer, how do we count the number of set (1) bits?For example the number 37 has 3 set bits in it’s binary representation (0010 0101) Method#1: Simple In this method we perform & operation between the number and 1 to get the last bit (Least Significant Bit or LSB). If it is 1…
We have an array that contains only 0, 1 and 2. We have to write a program to sort this array.For example if the input array is [2,0,1,2,1,0,0,2], the output should be[0,0,0,1,1,2,2,2].As the first thought, we can very well use well known sorting algorithms like Quick sort, or Merge sort or Heap sort. But that…
Given an array of numbers, how do we find the element which appears most number of times? In statistics this element is called mode.A simple solution is to count the frequency of all the elements in the array and select the one with maximum frequency. The outer loop selects an element, and the inner loop…
Given an array which contains some duplicate entries, How do we find the element which appears first and is also repeated.For example let us consider the array [10, 78, 45, 39, 22, 45, 78, 61].The element 78 is repeated and it appears before all such repetitive elements. Note that, though two entries of 45 is…