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/

Find heavy ball

Problem:
9 identical balls. one ball is heavy. find the heavy ball with only 2 measurements ........ dead easy.

Solution:
this is super easy. split the ball into three groups with 3 balls each. pick two groups out to measure if they are equal weight. this way, you could find out which group contains the heavy ball. Then from this particular group, you could pick two to do one more measurement, this way, you find out the heavy ball

Complexity:

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

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

Circular right shift by n

Problem:
Given an integer array. Perform circular right shift by n.
Give the best solution.

Solution:

O(n)/O(1):

void reverse(int A[], int start, int end)
{
 while(start < end)
  swap(A[start++], A[end--]);
}

//shift A[0…sz-1] by n (n>0)
void shiftArray(int A[], int sz, int n)
{
 n = n%sz;
 reverse(A, 0, sz-1);
 reverse(A, 0, n-1);
 reverse(A, n, sz-1);
 return;
}

But the above solution performs too many swaps. There's an alternative O(n)/O(1) solution that swaps each element only once. We start with the first element at index 0 and put it to its final position (at index [n % length]). The former element at index [0 + n % length] will now be saved in a temporary variable. Now, on the next loop iteration we put the temporary element to its final position (at index [(n + n) % length]) and similarly store the element from that new position to a temporary variable. We continue the process until we put an element at index 0, after which the array is rotated. As an example, consider the following example with an array of 5 elements that needs to be shifted by 3:

1 2 3 4 5

Shift it by 3:

x 2 3 1 5 - 4
x 4 3 1 5 - 2
x 4 3 1 2 - 5
x 4 5 1 2 - 3
3 4 5 1 2

Each line above represents the state of the array on each iteration of the loop. A number after the '-' sign is the temporary storage used for an element currently being shifted. The 'x' represents a position that doesn't contain a valid data and needs to be filled last. So, the loop would look like this:

int i = 0;
int temp = array[0];
do {
   int k = i + n % length;
   int t = array[k];
   array[k] = temp;
   temp = t;
   i = (i + n) % length;
} while (i != 0);
// Finally, fill the index 0:
array[0] = temp;

Complexity:

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

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

Find elements with sum equal to the sum of their indexes

Problem:
Write a method which takes an array input and returns true if the sum of any two elements is equal to the sum of the corresponding indices. Like if for an array the sum of values at any two indices i and j is equal to the sum of i and j.

Solution:
Since we know we are looking for pairs where x+y = A[x] + A[y], by simple algebra, you can also look for x-A[x] = A[y]-y

public static ArrayList<ArrayList<Integer>> findSums(int[] A) {
  // Look for pairs where  x - A[x] == A[y] - y
  ArrayList<ArrayList<Integer>> soln = new ArrayList<ArrayList<Integer>>();
  HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();
  
  for (int x = 0; x < A.length; x++) {
   h.put(x-A[x],x);
  }
  
  for (int y = 0; y < A.length; y++) {
   if (h.containsKey(A[y]-y)) {
    int x = h.get(A[y]-y);
    if (y != x) {
     ArrayList<Integer> pair= new ArrayList<Integer>();
     pair.add(x);
     pair.add(y);
     soln.add(pair);
    }
   }
  }
  
  return soln;
}

Complexity:

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

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

LCA or Lowest Common Ancestor of a Binary Tree

Problem:
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

E.g.:

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

In this tree, an LCA for 6 and 4 is 5. For 5 and 4 it is 5,too. For 7 and 1 it is 3. And so on.

Solution:
A Bottom-up Approach:
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Complexity:

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

Links and credits:
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

Min number of slaves to find poison

Problem:
There is a king, who has got 1000 bottles of Rum with him, of which One bottle contains poison. And he has any number of slaves. He has got 1 hour to decide which bottle contains Poison, and any slave who even takes a sip of the poison, dies within an hour. How many least number of slaves does the king need to use, to make out which bottle contains poison.

Solution:
The answer is still 10. (2 power 10 = 1024) List numbers until 1000 in binary format vertically. Each 1 represents a slave and with the combination of slaves you can find the poisoned rum.
8 = 2 power 3. So three slaves

Eg:          1 2 3 4 5 6 7 8
Slave 1:     0 0 0 1 1 1 1 0
Slave 2:     0 1 1 0 0 1 1 0
Slave 3:     1 0 1 0 1 0 1 0

from the above combination you can find the rum bottle based on which slaves died

Complexity:

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

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

Search in a matrix sorted by rows and columns

Problem:
Search in a row wise and column wise sorted matrix

Solution:
Assuming both sorted in strictly increasing order:

M[row][column] < M[row+1][column] and M[row][column] < M[row][column+1]

Start from the top-right corner of the matrix. If the matrix element is larger than the target, move to the column on the left; if smaller, move to the row below.

Complexity if O(#rows + #columns)

public Position searchSortedMatrix(int x, int[][] M) {
 if (M.length==0 || M[0].length==0) return Position(-1,-1);
 int row = 0, column = M[0].length-1, curVal;
 while (row<M.length && column>=0) {
  curVal = M[row][column];
  if (curVal == x) return Position(row,column);
  if (curVal > x) column--;
  else row++;
 }
 return Position(-1,-1);
}

Note that binary search won't work because the element being searched can be located virtually anywhere, so we can't choose the "right" row or column beforehand.


There's also a divide and conqure solution exist:
1) Find the middle element.
2) If middle element is same as key return.
3) If middle element is lesser than key then
….3a) search submatrix on lower side of middle element
….3b) Search submatrix on right hand side.of middle element
4) If middle element is greater than key then
….4a) search vertical submatrix on left side of middle element
….4b) search submatrix on right hand side.

If given a n x n matrix, the time complexity of the divide and conqure solution is O(n^1.58) (follows from a recurrence: T(n) = 3T(n/2) + O(1), see geeksforgeeks link for details).

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=6448780970819584
http://www.geeksforgeeks.org/divide-conquer-set-6-search-row-wise-column-wise-sorted-2d-array/