Given an n x n square matrix, find sums of all sub-squares of size k x k

Problem:
Given an n x n square matrix, find sums of all sub-squares of size k x k where k is smaller than or equal to n.
Examples:

Input:
n = 5, k = 3
arr[][] = { {1, 1, 1, 1, 1},
            {2, 2, 2, 2, 2},
            {3, 3, 3, 3, 3},
            {4, 4, 4, 4, 4},
            {5, 5, 5, 5, 5},
         };
Output:
       18  18  18
       27  27  27
       36  36  36


Input:
n = 3, k = 2
arr[][] = { {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9},
         };
Output:
       12  16
       24  28

Solution:
Pre-process the matrix by calculating sums of all vertical strips of size 1 x k. Note that you can use the "rolling window" approach to calculate subsequent sums in the same column in O(1) time.
Then use the calculated sums and, again, the rolling window approach to calculate the k x k squares' sums.


Complexity:

time - O(n^2)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/given-n-x-n-square-matrix-find-sum-sub-squares-size-k-x-k/

Find next greater number with same set of digits

Problem:
Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.

Solution:
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976″, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976″. The smallest digit greater than 4 is 6.

III) Swap the above found two digits, we get 536974 in above example.

IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.

Optimizations:
1) We can use binary search in step II instead of linear search.
2) In step IV, instead of doing simple sort, we can apply some clever technique to do it in linear time. Hint: We know that all digits are linearly sorted in reverse order except one digit which was swapped.

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.geeksforgeeks.org/find-next-greater-number-set-digits/

Reverse alternate levels of a binary tree

Problem:
Given a Binary Tree, reverse the alternate level nodes of the binary tree.

Given tree: 
               a
            /     \
           b       c
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
       h  i j  k l  m  n  o 

Modified tree:
          a
            /     \
           c       b
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
      o  n m  l k  j  i  h

Solution:

A simple solution is to do following steps.
1) Access nodes level by level.
2) If current level is odd, then store nodes of this level in an array.
3) Reverse the array and store elements back in tree.

A tricky solution is to do two inorder traversals. Following are steps to be followed.
1) Traverse the given tree in inorder fashion and store all odd level nodes in an auxiliary array. For the above example given tree, contents of array become {h, i, b, j, k, l, m, c, n, o}

2) Reverse the array. The array now becomes {o, n, c, m, l, k, j, b, i, h}

3) Traverse the tree again inorder fashion. While traversing the tree, one by one take elements from array and store elements from array to every odd level traversed node.
For the above example, we traverse ‘h’ first in above array and replace ‘h’ with ‘o’. Then we traverse ‘i’ and replace it with n.

Note that the solution works for complete binary trees only. Perhaps it could be modified to work with incomplete trees too, by storing "empty" elements in the array on step #1.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/reverse-alternate-levels-binary-tree/

Find running median from a stream of integers

Problem:
Given that integers are read from a data stream. Find median of elements read so for in efficient way.

Solution:
We can use a max heap on left side to represent elements that are less than effective median, and a min heap on right side to represent elements that are greater than effective median.

After processing an incoming element, the number of elements in heaps differ at most by 1 element (because we re-balance the heaps if needed). When both heaps contain same number of elements, we pick average of heaps root data as effective median. When the heaps are not balanced, we select effective median from the root of heap containing more elements.


NOTE: Finding running median from a stream of data is a tough problem, and finding an exact solution with memory constraints efficiently is probably impossible for the general case. On the other hand, if the data has some characteristics we can exploit, we can develop efficient specialized solutions. For example, if we know that the data is an integral type, then we can use counting sort, which can give you a constant memory constant time algorithm. Heap based solution is a more general solution because it can be used for other data types (doubles) as well. And finally, if the exact median is not required and an approximation is enough, you can just try to estimate a probability density function for the data and estimate median using that.

Complexity:

time - O(1)
space - O(n) or O(1)

Links and credits:
http://stackoverflow.com/questions/10657503/find-running-median-from-a-stream-of-integers

Maximum and minimum of an array using minimum number of comparisons

Problem:
Find maximum and minimum of an array using minimum number of comparisons.

Solution:
http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

1. Linear: 1 + 2*(n - 2)
2. Divide and conqure: 1.5*n - 2 (if n is a power of 2, otherwise more comparisions are required)
3. Compare in pairs: also ~1.5*n.

Complexity:

time - O(n)
space - O(1) or O(log n) (for method #2)

Links and credits:
http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

Longest Common Subsequence

Problem:
Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.

Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Solution:
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).

If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

Since there's overlapping subproblems, we can use dynamic programming to solve this problem.

// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;
  
   // Following steps build L[m+1][n+1] in bottom up fashion. Note 
   // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
  
       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
  
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
    
   // L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1]
   return L[m][n];
}

To print the LCS using the matrix L[][]:

1) The value L[m][n] contains length of LCS. Create a character array lcs[] of length equal to the length of lcs plus 1 (one extra to store \0).

2) Traverse the 2D array starting from L[m][n]. Do following for every cell L[i][j]
…..a) If characters (in X and Y) corresponding to L[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS and decrease both i and j.
…..b) Else compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.

   // Following code is used to print LCS
   int index = L[m][n];
 
   // Create a character array to store the lcs string
   char lcs[index+1];
   lcs[index] = '\0'; // Set the terminating character
 
   // Start from the right-most-bottom-most corner and
   // one by one store characters in lcs[]
   int i = m, j = n;
   while (i > 0 && j > 0)
   {
      // If current character in X[] and Y are same, then
      // current character is part of LCS
      if (X[i-1] == Y[j-1])
      {
          lcs[index-1] = X[i-1]; // Put current character in result
          i--; j--; index--;     // reduce values of i, j and index
      }
 
      // If not same, then find the larger of two and
      // go in the direction of larger value
      else if (L[i-1][j] > L[i][j-1])
         i--;
      else
         j--;
   }
 
   // Print the lcs
   cout << "LCS of " << X << " and " << Y << " is " << lcs;

Complexity:

time - O(nm)
space - O(nm)

Links and credits:
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
http://www.geeksforgeeks.org/printing-longest-common-subsequence/

Count all possible groups of size 2 or 3 that have sum as multiple of 3

Problem:
Given an unsorted integer (positive values only) array of size ‘n’, we can form a group of two or three, the group should be such that the sum of all elements in that group is a multiple of 3. Count all possible number of groups that can be generated in this way.

Input: arr[] = {3, 6, 7, 2, 9}
Output: 8
// Groups are {3,6}, {3,9}, {9,6}, {7,2}, {3,6,9},
//            {3,7,2}, {7,2,6}, {7,2,9}


Input: arr[] = {2, 1, 3, 4}
Output: 4
// Groups are {2,1}, {2,4}, {2,1,3}, {2,4,3}

Solution:

The idea is to see remainder of every element when divided by 3. A set of elements can form a group only if sun of their remainders is multiple of 3. Since the task is to enumerate groups, we count all elements with different remainders.

1. Hash all elements in a count array based on remainder, i.e, 
   for all elements a[i], do c[a[i]%3]++;
2. Now c[0] contains the number of elements which when divided
   by 3 leave remainder 0 and similarly c[1] for remainder 1 
   and c[2] for 2.
3. Now for group of 2, we have 2 possibilities
   a. 2 elements of remainder 0 group. Such possibilities are 
      c[0]*(c[0]-1)/2
   b. 1 element of remainder 1 and 1 from remainder 2 group
      Such groups are c[1]*c[2].
4. Now for group of 3,we have 4 possibilities
   a. 3 elements from remainder group 0.
      No. of such groups are c[0]C3
   b. 3 elements from remainder group 1.
      No. of such groups are c[1]C3
   c. 3 elements from remainder group 2.
      No. of such groups are c[2]C3
   d. 1 element from each of 3 groups. 
      No. of such groups are c[0]*c[1]*c[2].
5. Add all the groups in steps 3 and 4 to obtain the result.

// Returns count of all possible groups that can be formed from elements
// of a[].
int findgroups(int arr[], int n)
{
    // Create an array C[3] to store counts of elements with remainder
    // 0, 1 and 2.  c[i] would store count of elements with remainder i
    int c[3] = {0}, i;
 
    int res = 0; // To store the result
 
    // Count elements with remainder 0, 1 and 2
    for (i=0; i<n; i++)
        c[arr[i]%3]++;
 
    // Case 3.a: Count groups of size 2 from 0 remainder elements
    res += ((c[0]*(c[0]-1))>>1);
 
    // Case 3.b: Count groups of size 2 with one element with 1
    // remainder and other with 2 remainder
    res += c[1] * c[2];
 
    // Case 4.a: Count groups of size 3 with all 0 remainder elements
    res += (c[0] * (c[0]-1) * (c[0]-2))/6;
 
    // Case 4.b: Count groups of size 3 with all 1 remainder elements
    res += (c[1] * (c[1]-1) * (c[1]-2))/6;
 
    // Case 4.c: Count groups of size 3 with all 2 remainder elements
    res += ((c[2]*(c[2]-1)*(c[2]-2))/6);
 
    // Case 4.c: Count groups of size 3 with different remainders
    res += c[0]*c[1]*c[2];
 
    // Return total count stored in res
    return res;
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.geeksforgeeks.org/count-possible-groups-size-2-3-sum-multiple-3/

Jump game

Problem:
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution:

bool canJump(int A[], int n) {
    int reach = 1;
    for (int i = 0; i < reach && reach < n; ++i)
        reach = max(reach, A[i] + i + 1);
    return reach >= n;
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/232/jump-game

Replace each element with its Next Larger Element on the right

Problem:
Given an Array, replace each element in the Array with its Next Element(To its RHS) which is Larger than it. If no such element exists, then no need to replace.
Ex:

i/p: {2,12,8,6,5,1,2,10,3,2}
o/p:{12,12,10,10,10,2,10,10,3,2}

Solution:

Naive solution is O(n^2) as it requires two nested loops.

A more optimal solution is to traverse the array from the right and put all elements in a BST, replacing each element in the array with its immediate in-order successor in the BST. This will take O(n log n) time to complete and require O(n) space.

The best solution also requires O(n) space but runs in O(n) time. We traverse the array from the left and keep pushing elements' indexes to a stack, ensuring that all the elements in the stack are always stored in decreasing order. Once the order is not decreasing, we pop the element from the stack (remember, it's an index) and replace the corresponding element in the array with an element currently being processed in the main loop:

void ReplaceNextLargest ( int * Arr, int N ) {
    stack<int> stk;
    stk.push(0);

    for( int idx = 1; idx < N; idx++ ) {
        while( !stk.empty() && (Arr[idx] > Arr[stk.top()]) ) {
            Arr[stk.top()] = Arr[idx];
            stk.pop();
        }
        stk.push(idx);
    }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=6311825561878528
http://www.geeksforgeeks.org/next-greater-element/

Find number of ways to go n steps with 1 or 2 steps

Problem:
Frog can jump 1 or 2 steps write the code to find out number of ways to go up to n steps.

Solution:

The number of ways to jump to n steps is the n-th Fibonacci number!

F[n] = F[n-1] + F[n-2]; 
F1 = 1; F2 = 2;

Example:

F[3] = F[2] + F[1]
1 1 1 part of F[2]
2 1 part of F[2]
1 2 part of F[1]

F[2]
1 1 
2

F[1]
1

Complexity:

time - O(n)
space - O(1) (for iterative approach)

Links and credits:
http://www.careercup.com/question?id=5950229446656000

Inorder traversal of binary tree w/o recursion

Problem:
Inorder traversal of binary tree w/ recursion

Solution:

/* Iterative method using stack */
Inordertraversal(struct btree *root)   
{
 while(1)
 {   
  while( root )
  {
   push(root);
   root = root->left;
  }
  if(Isstackempty(S))
   return;
  printf( S(top)->data);
  root = pop(S);
  root = root->right;
 }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5198302274387968

Sort n numbers in range from 0 to n^2 – 1 in linear time

Problem:
Given an array of numbers of size n. It is also given that the array elements are in range from 0 to n2 – 1. Sort the given array in linear time.

Examples:
Since there are 5 elements, the elements can be from 0 to 24.
Input: arr[] = {0, 23, 14, 12, 9}
Output: arr[] = {0, 9, 12, 14, 23}

Since there are 3 elements, the elements can be from 0 to 8.
Input: arr[] = {7, 0, 2}
Output: arr[] = {0, 2, 7}

Solution:
The idea is to use Radix Sort. Following is standard Radix Sort algorithm.

Do following for each digit i where i varies from least significant digit to the most significant digit: Sort input array using counting sort (or any stable sort) according to the i’th digit.

Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for decimal system, b is 10. Since n2-1 is the maximum possible value, the value of d would be O(\log_b(n)). So overall time complexity is O((n+b)*\log_b(n)). Which looks more than the time complexity of comparison based sorting algorithms for a large k. The idea is to change base b. If we set b as n, the value of O(\log_b(n)) becomes O(1) and overall time complexity becomes O(n).

arr[] = {0, 10, 13, 12, 7}

Let us consider the elements in base 5. For example 13 in
base 5 is 23, and 7 in base 5 is 12.
arr[] = {00(0), 20(10), 23(13), 22(12), 12(7)}

After first iteration (Sorting according to the last digit in 
base 5),  we get.
arr[] = {00(0), 20(10), 12(7), 22(12), 23(13)}

After second iteration, we get
arr[] = {00(0), 12(7), 20(10), 22(12), 23(13)}

How to sort if range is from 1 to n2?
If range is from 1 to n n2, the above process can not be directly applied, it must be changed. Consider n = 100 and range from 1 to 10000. Since the base is 100, a digit must be from 0 to 99 and there should be 2 digits in the numbers. But the number 10000 has more than 2 digits. So to sort numbers in a range from 1 to n2, we can use following process.
1) Subtract all numbers by 1.
2) Since the range is now 0 to n2, do counting sort twice as done in the above implementation.
3) After the elements are sorted, add 1 to all numbers to obtain the original numbers.

How to sort if range is from 0 to n^3 -1?
Since there can be 3 digits in base n, we need to call counting sort 3 times.


PS. Note: the counting sort for the radix sort for base n requires O(n) memory. We could try to use a bit-set for sorting if all the numbers are unique.

Complexity:

time - O(n)
space - O(n) (for counting sort)

Links and credits:
http://www.geeksforgeeks.org/sort-n-numbers-range-0-n2-1-linear-time/

Find minimum range that includes an element from every array

Problem:
There are many sorted arrays. Find a minimum range, so that in each array there's at least one integer within this range.

Solution:
Do a "merge" operation (kind of) by maintaining a priority queue of minimum elements from each array. The range of the whole queue is the range of the current interval. Iterate over all elements until one of the arrays is exhausted and choose the minimum range. The priority queue guarantees that there's at least one element from each array present. The fact that the queue is sorted allows as to quickly retrieve the current min and max elements and therefore determine the current range. It's best to maintain the heap using a BST - all operations (including getMax/Min) will take O(log M), where M is the number of input arrays.
Example:

input {0,10,255} {2 , 11 , 257} {4,12,258} 

Let's take the first element from each array and push them into priority queue. 

step 0:  queue: [0,2,4]  range:0-4 
step 1:  pop 0 from queue , push next element to 0 from first array 
queue: [2,4,10] range: 2-10 
step2:  pop 2 , push 11 
queue: [4,10,11] range: 4-11 
step3:  pop 4 , push 12 
queue: [10,11,12] range: 10-12 <----- minimal range 

etc...

Complexity:

time - O(n log n) (we iterate once and maintain a heap)
space - O(M), where M - the number of arrays

Links and credits:
http://www.careercup.com/question?id=5103437989543936

Generate 1 and 0 with equal probability

Problem:
Given a function “f” in which 0 occurs with probability 0.4 and 1 occurs with probability 0.6. Using function “f” deduce a new function “f1” such that both 0 and 1 occurs with probability 0.5.

Solution:
Run the function f() two times. The possible outcomes are

00 with probability 0.4*0.4

11 with probability 0.6*0.6

01 with probability 0.4*0.6

10 with probability 0.6*0.4

Notice that the probabilities for 01 and 10 are the same. So create a new function f1() such that

f1():
   first = f()
   second = f()
   if (first == 0 and second == 0) or (first == 1 or second == 1):

      discard and run again
   else: 
      if first == 0 and second == 1: return 0
      else: return 1

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://www.geeksforgeeks.org/amazon-interview-set-64-campus-sde/