Integer to Roman

Problem:
Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solution:

public String intToRoman(int num) {
    int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    StringBuilder res = new StringBuilder();
    int i=0;
    while (num>0) {
        int times = num / nums[i];
        num -= nums[i]*times;
        for (; times>0; times--) {
            res.append(symbols[i]);
        }
        ++i;
    }
    return res.toString();
}

Complexity:

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

Links and credits:
http://discuss.leetcode.com/questions/194/integer-to-roman

Reverse Nodes in k-Group

Problem:
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:
It's easy to reverse the whole linked list (i.e. consider k === list length). Now, the definition of the "whole list" is only a matter of how we define its head and tail. We should just traverse the original list and treat each k-group as a separate list and reverse it one by one until we reach a group of size less than k.

ListNode *reverseKGroup(ListNode *head, int k) {
    if (!head || k <= 1) return head;

    ListNode dummy(0);
    dummy.next = head;
    ListNode *pre = &dummy;

    int i = 0;
    while (head) {
        i++;
        if (i % k == 0) {
            pre = reverse(pre, head->next);                
            head = pre->next;
        } else {
            head = head->next;   
        }
    }

    return dummy.next;
}

ListNode *reverse(ListNode *pre, ListNode *next) {
    ListNode *last = pre->next;
    ListNode *cur = last->next;
    while (cur != next) {
        last->next = cur->next;
        cur->next = pre->next;
        pre->next = cur;

        cur = last->next;
    }
    return last;
}

Complexity:

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

Links and credits:
http://discuss.leetcode.com/questions/206/reverse-nodes-in-k-group

Median of Two Sorted Arrays

Problem:
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution:

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int total = m + n;
    if (0 == total % 2) {
        return (FindKth(A, m, B, n, total/2) + FindKth(A, m, B, n, total/2 + 1)) / 2;
    } else {
        return FindKth(A, m, B, n, total/2 + 1);
    }
}

double FindKth(int A[], int m, int B[], int n, int k) {
    if (m > n) return FindKth(B, n, A, m, k);
    if (0 == m) return B[k-1];
    if (0 == n) return A[k-1];
    if (1 == k) return min(A[0], B[0]);

    int aMid = min(k/2, m);
    int bMid = k - aMid;
    if (A[aMid-1] < B[bMid-1]) {
        return FindKth(A + aMid, m - aMid, B, n, k - aMid);
    } else {
        return FindKth(A, m, B + bMid, n - bMid, k - bMid);
    }
}

Complexity:

time - O(log n)
space - O(log n) (for recursion stack; could be optimized to O(1) using iterative approach)

Links and credits:
http://discuss.leetcode.com/questions/142/median-of-two-sorted-arrays

Find the k-th Smallest Element in the Union of Two Sorted Arrays

Problem:
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

Solution:

O(m + n): Merge the arrays and return the k-th element. Also requires O(m+n) memory.

O(k): Maintain two indexes for each array and perform the merge procedure w/o actually merging the arrays. I.e. just traverse them both and return the k-th element.

O(log m + log n): Given i and j as indexes in A and B respectively, the smallest of A[i] and B[j] is the element that we search for if  i+j = k-1 AND the element (say, A[i]) satisfies B[j-1] < A[i] < B[j] (or vice versa for B[j].) And since the arrays are sorted, we can perform "binary searches" on them, or rather divide them by half. See Links for the code.

O(log k): This is similar to the previous method, but is done by maintaining the "left" and "right" borders of the smallest subarray of size 2*k in an array that would have been the result of merging the arrays. We do not perform the actual merge operation, we only do binary searches on the bottom parts of the arrays:

int findKthInSortedArrays(int A[], int B[], int k) {
    if (A == null)  A = new int[0];
    if (B == null)  B = new int[0];
    int nA = A.length;
    int nB = B.length;
    if (nA == 0 && nB == 0) return Integer.MIN_VALUE;

    int l = k - Math.min(k, nB);
    int r = Math.min(k, nA);

    while(l <= r) {
        int i = l + (r - l) / 2;
        int j = k - i;

        int a_i = (i < nA) ? A[i] : Integer.MAX_VALUE;
        int a_i_prev = (i > 0) ? A[i-1] : Integer.MIN_VALUE;
        int b_j = (j < nB) ? B[j] : Integer.MAX_VALUE;
        int b_j_prev = (j > 0) ? B[j-1] : Integer.MIN_VALUE;

        if (a_i >= b_j_prev && b_j >= a_i_prev) {
            return Math.max(a_i_prev, b_j_prev);
        }

        if (a_i < b_j_prev) {
            l = i + 1;
        } else {
            r = i - 1;
        }
    }

    return Integer.MIN_VALUE;
}

Complexity:

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

Links and credits:
http://discuss.leetcode.com/questions/136/find-the-k-th-smallest-element-in-the-union-of-two-sorted-arrays

Palindrome Number

Problem:
Determine whether an integer is a palindrome. Do this without extra space.

Solution:
First, compare the first and last digit. If they are not the same, it must not be a palindrome. If they are the same, chop off one digit from both ends and continue until you have no digits left, which you conclude that it must be a palindrome.

Now, getting and chopping the last digit is easy. However, getting and chopping the first digit in a generic way requires some thought.

bool isPalindrome(int x) {
    if (x < 0) return false;
    int div = 1;
    while (x / div >= 10) {
        div *= 10;
    }
    while (x != 0) {
        int l = x / div;
        int r = x % 10;
        if (l != r) return false;
        x = (x % div) / 10;
        div /= 100;
    }
    return true;
}

Complexity:

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

Links and credits:
http://discuss.leetcode.com/questions/181/palindrome-number

Regular Expression Matching

Problem:
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

 bool isMatch(const char *s, const char *p)
Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

1. If the next character of p is NOT '*', then it must match the current character of s. Continue pattern matching with the next character of both s and p.
2. If the next character of p is '*', then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p... Until we could not match any more characters.

bool isMatch(const char *s, const char *p) {
    assert(s && p);
    if (*p == '\0') return *s == '\0';

    // next char is not '*': must match current character
    if (*(p+1) != '*') {
        assert(*p != '*');
        return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
    }
    // next char is '*'
    while ((*p == *s) || (*p == '.' && *s != '\0')) {
        if (isMatch(s, p+2)) return true;
        s++;
    }
    return isMatch(s, p+2);
}

Complexity:

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

Links and credits:
http://discuss.leetcode.com/questions/175/regular-expression-matching

Optimal solution (that grep, awk, and other tools use):
http://swtch.com/~rsc/regexp/regexp1.html

Binary Tree Zigzag Level Order Traversal

Problem:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Solution:
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level's order (whether it is left->right or right->left).

You pop from stack currentLevel and print the node's value. Whenever the current level's order is from left->right, you push the node's left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level's order is from right->left, you would push the node's right child first, then its left child. Finally, don't forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

void printLevelOrderZigZag(BinaryTree *root) {
    stack<BinaryTree*> currentLevel, nextLevel;
    bool leftToRight = true;
    currentLevel.push(root);
    while (!currentLevel.empty()) {
        BinaryTree *currNode = currentLevel.top();
        currentLevel.pop();
        if (currNode) {
            cout << currNode->data << " ";
            if (leftToRight) {
                nextLevel.push(currNode->left);
                nextLevel.push(currNode->right);
            } else {
                nextLevel.push(currNode->right);
                nextLevel.push(currNode->left);
            }
        }
        if (currentLevel.empty()) {
            cout << endl;
            leftToRight = !leftToRight;
            swap(currentLevel, nextLevel);
        }
    }
}

Complexity:

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

Links and credits:
http://discuss.leetcode.com/questions/52/binary-tree-zigzag-level-order-traversal

Print Left View of a Binary Tree

Problem:
Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side. Left view of following tree is 12, 10, 25.

          12
       /     \
     10       30
            /    \
          25      40

Solution:
The left view contains all nodes that are first nodes in their levels. A simple solution is to do level order traversal and print the first node in every level.

The problem can also be solved using simple recursive traversal. We can keep track of level of a node by passing a parameter to all recursive calls. The idea is to keep track of maximum level also. Whenever we see a node whose level is more than maximum level so far, we print the node because this is the first node in its level (Note that we traverse the left subtree before right subtree).

Note: the same procedure can be used to get the "right view" of a tree if we first traverse the right sub-tree in the recursive algorithm.

// Recursive function to print left view of a binary tree.
void leftViewUtil(struct node *root, int level, int *max_level)
{
    // Base Case
    if (root==NULL)  return;
 
    // If this is the first node of its level
    if (*max_level < level)
    {
        printf("%d\t", root->data);
        *max_level = level;
    }
 
    // Recur for left and right subtrees
    leftViewUtil(root->left, level+1, max_level);
    leftViewUtil(root->right, level+1, max_level);
}
 
// A wrapper over leftViewUtil()
void leftView(struct node *root)
{
    int max_level = 0;
    leftViewUtil(root, 1, &max_level);
}

Complexity:

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

Links and credits:
http://www.geeksforgeeks.org/print-left-view-binary-tree/

Print Postorder traversal from given Inorder and Preorder traversals

Problem:
Given Inorder and Preorder traversals of a binary tree, print Postorder traversal.

Example:

Input:
Inorder traversal in[] = {4, 2, 5, 1, 3, 6}
Preorder traversal pre[] = {1, 2, 4, 5, 3, 6}

Output:
Postorder traversal is {4, 5, 2, 6, 3, 1}

Trversals in the above example represents following tree

         1
      /     \   
     2       3
   /   \      \
  4     5      6

Solution:
A naive method is to first construct the tree, then use simple recursive method to print postorder traversal of the constructed tree. We can print postorder traversal without constructing the tree.

1. The pre[0] is the root of the tree --> 1
2. The in[] represents the tree as:
   
   { { left-sub-tree } ;  root ;   { right-sub-tree } }
   
   So the index of the root at in[] is the length of the left sub-tree --> 3
3. The (in[].length - rootIndex - 1) is the length of the right sub-tree --> 2
4. The pre[] represents the tree as:
   
   { root ;   { left-sub-tree } ;  { right-sub-tree } }
   
   Since we know the lengths of the sub-trees from steps #2 and #3, we can proceed recursively as follows:
   
   leftIn[] = in[ 0 .. (rootIndex-1) ] = { 4, 2, 5 }
   leftPre[] = pre[ 1 .. (rootIndex-2) ] = { 2, 4, 5 }
   
   rightIn[] = in[ (rootIndex+1) .. (length-1) ] = { 3, 6 }
   rightPre[] = pre[ (rootIndex+1) .. (length-1) ] = { 3, 6 }
   
   Recursion ends when the lengths of the in[] and pre[] become equal to 1.

int search(int arr[], int x, int n)
{
    for (int i = 0; i < n; i++)
      if (arr[i] == x)
         return i;
    return -1;
}
 
// Prints postorder traversal from given inorder and preorder traversals
void printPostOrder(int in[], int pre[], int n)
{
   // The first element in pre[] is always root, search it
   // in in[] to find left and right subtrees
   int root = search(in, pre[0], n);
 
   // If left subtree is not empty, print left subtree
   if (root != 0)
      printPostOrder(in, pre+1, root);
 
   // If right subtree is not empty, print right subtree
   if (root != n-1)
      printPostOrder(in+root+1, pre+root+1, n-root-1);
 
   // Print root
   cout << pre[0] << " ";
}

Complexity:

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

Links and credits:
http://www.geeksforgeeks.org/print-postorder-from-given-inorder-and-preorder-traversals/

Find the equilibrium position of an array

Problem:
write a code to find the equilibrium position of the array.

given an array: 3,-3,8,6,-1,-5

equilibrium position should be 2(element 8) sum of lower index(3+-3)=sum of higher index(6+(-1)+(-5))

Solution:
For any index i, if we know the sum of items 0..i, we can find the sum of items i+1..n-1 by subtracting it from the sum of all elements. So:
1. Find the total sum of the array
2. For each element in the array
2.a. keep contSum, which is the sum up to the point in the array
2.b. if the (sum - A[i] - contSum) == contSum, return index (This is the point where the leftSum and the rightSum equals)
3. Return -1 if not found

public static int equilibriumIndex(int[] A) {
 int sum = 0;
 int i = 0;
 for (i = 0; i < A.length; i++) 
  sum += A[i];
  
 int contSum = 0;
 for (i = 0; i < A.length; i++) {
  if ( (sum - A[i] - contSum) == contSum) return i;
   
  contSum += A[i];
 }
  
 return -1; // not found
}

Complexity:

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

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

Find a missing number

Problem:
Given you an array of 100 Elements with one number missing, how will you find the missing number?

Ex.: Array 1 to 100 with 55 missing.

Solution:
Just do sum of all the numbers from 1 to 100 : (n * (n+1))/2 and find sum of all the elements from actual array. Just take the difference and you will get missing number.
If numbers start with n > 1, then normalize them by subtracting n-1.

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=23092662
See also: Find two missing numbers

Calculate (x^y)%z without pow()

Problem:
Calculate (x^y)%z without pow().

Solution:
The question here is how we can reduce the complexity... if we compute the x^y by normal method the complexity is O(y)... to reduce the complexity we can use binary weighted power computation method in which complexity is O(logy)..

ans=1;
square=x;
if(y==0)
    return 1;
while(y!=0)
{
    if(y%2)
        ans=ans*square;
    square=(square*square)%z;
    y=y/2;
    if(ans>z)
        ans=ans%z;
}
return ans;

Complexity:

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

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

Find tree height

Problem:
A tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes that node with id k is the root. For ex:

3 3 3 -1 2
0 1 2 3 4

In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4.

Given such an array, find the height of the tree.

Solution:
A straightforward approach is to find the root, then find all its children, etc. (i.e. perform a BFS), and find out the maximum depth. This is a O(n^2) solution, although it requires only O(1) memory.

Using dynamic programming we can do this in O(n) time using O(n) memory:

public int countDepth(int[] tree) {
    int[] height = new int[tree.length];
    for (int i = 0; i < tree.length; i++)
        height[i] = -1;
    int maxHeight = -1;
    for (int i = 0; i < tree.length; i++) {
        if (height[i] == -1)
            maxHeight = max(maxHeight, findHeight(i, height, tree));
    }
    return maxElement(height);
}

private int findHeight(int i, int[] height, int[] tree) {
    if (height[i] != -1)
        return height[i];
    if (tree[i] == -1) {
        height[i] = 0;
    else
        height[i] = 1 + findHeight(tree[i], height, tree);
    return height[i];
}

Complexity:

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

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

Generate integer from 1 to 7 with equal probability

Problem:
Given a function foo() that returns integers from 1 to 5 with equal probability, write a function that returns integers from 1 to 7 with equal probability using foo() only. Minimize the number of calls to foo() method. Also, use of any other library function is not allowed and no floating point arithmetic allowed.

Solution:
If we somehow generate integers from 1 to a-multiple-of-7 (like 7, 14, 21, …) with equal probability, we can use modulo division by 7 followed by adding 1 to get the numbers from 1 to 7 with equal probability.

Consider

5*foo() + foo() - 5

This expression generates numbers 1..25 with equal probability. Now, if we only accept numbers 1..21 and return i%7+1, then we get numbers 1..7 with equal probability. If the above expression returns a number >= 22, then ignore it and run the procedure once again until a proper number is returned.

int my_rand() // returns 1 to 7 with equal probability
{
    int i;
    i = 5*foo() + foo() - 5;
    if (i < 22)
        return i%7 + 1;
    return my_rand();
}

Complexity:

time - O(1), but really unpredictable, depends on the behavior of foo()
space - O(1)

Links and credits:
http://www.careercup.com/question?id=22457666
http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/
ARRAY: http://stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17

Find square root of an integer without using built in functions

Problem:
Find square root of an integer without using built in functions.

Solution:
Provided we don't know or can't recall any math: square roots of integer numbers are "sorted" in a way that the grater the number, the greater its square root is. So we can use binary search starting with the interval (0; n) and set x = (n - 0) / 2, continuing dividing the interval until we get | x*x - n | < epsilon, where the epsilon is some very small number (e.g. 0.0000000001).

Complexity:

time - O( ??? ) - I'd speculate something like O (log n / epsilon). log n comes from using the binary search, and obviously, the higher the required precision, the longer the search takes, hence the (1 / epsilon) multiplier.
space - O(1)

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

Populating Next Right Pointers in Each Node

Problem:
Given a binary tree

struct TreeLinkNode {
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.

Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Solution:

public void connect(TreeLinkNode root) {

    TreeLinkNode leftWall = root;
    while (leftWall != null) {

        TreeLinkNode across = leftWall;
        while (across != null) {
            if (across.left != null) {
                across.left.next = across.right;
            }

            if (across.right != null && across.next != null) {
                across.right.next = across.next.left;
            }

            across = across.next;
        }
        leftWall = leftWall.left;
    }
}

Complexity:

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

Links and credits:
http://discuss.leetcode.com/questions/7/populating-next-right-pointers-in-each-node

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

Problem:
Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
Examples:

  Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
  Output: 6  (j = 7, i = 1)

  Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
  Output: 8 ( j = 8, i = 0)

  Input:  {1, 2, 3, 4, 5, 6}
  Output: 5  (j = 5, i = 0)

  Input:  {6, 5, 4, 3, 2, 1}
  Output: -1

Solution:

/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;
 
    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);
 
   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);
 
    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);
 
    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }
 
    return maxDiff;
}

Complexity:

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

Links and credits:
http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/

Find the path traversed by a KNIGHT

Problem:
Find the path traversed by a KNIGHT to reach the destination from source in a 8x8 chess broad...
**you will be given the starting position and ending position

Solution:
From any position, a knight can go in 4 different directions. Thus, we do a BFS (using a queue), keeping a set of visited positions. Once we get to the target point, we're done.

Complexity:

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

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

Pyramid of glasses

Problem:
There are some glasses with equal volume 1 litre. The glasses kept as follows:

                           1
           2   3
        4    5    6
      7    8    9   10

You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..
If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd - 1/2 litre

Solution:
In this problem the rates at which glasses get filled in are rational numbers, whose numerators form the binomial coefficients and denominators are powers of 2 - specifically 2 raised to the power of level at which glasses are present.

A litre of water (overflowed from previous level) gets distributed among the glasses at each level as follows:

level 0: 1
level 1: 1/2  1/2
level 2: 1/4  2/4  1/4
level 3: 1/8  3/8  3/8  1/8
level 4: 1/16  4/16  6/16  4/16  1/16

The above distribution pattern provides with a partial progress towards the actual algorithm that finds the amount of water in jth glass of ith row. The algorithm gets tricky because all the glasses at a level might not be completely filled yet, before water starts getting filled up in levels below (albeit, in an inverted triangle fashion).

----------------------------------------------------------------------------
The above observation apart, a DP-like algorithm below(that remembers quantities in glasses of the previous row) to find out the amount of water in jth jug of ith row can solve the problem.

0. For each glass, maintain 2 variables - the amount of water it holds and the amount of water it overflows.
1. For a glass at index i in the given row, look up two glasses in the previous row at index i-1 & i. (Boundary cases of indices need to be checked though)
2. The inflow into the current glass = half of outflow of glass in the previous row at i-1 + half of outflow of glass in the previous row at index i
3. Based on the inflow, volume held in the current glass = min(1, inflow) and the overflow at the current glass = inflow - volume held by the current glass
4. Repeat steps 1 to 3 until we reach the required glass.

An implementation in java goes like the below:

import java.util.Scanner;
import java.util.regex.Pattern;

class GlassStatus {
 float heldVolume;
 float overflownVolume;
}

public class GlassPyramid {

 static int ipRowNum, ipGlassNum, ipVolume;
 public static float computeWaterAt(float volume, int level, GlassStatus[] previousRows) {

  if (volume <= 0)
   return 0;
  
  GlassStatus[] rows = new GlassStatus[level + 1];
  float overflow1 = 0, overflow2 = 0, inflow = 0, tempVol = 0;
  
  for (int i = 0, prev = i-1, next = i; i <= level; i++, prev++, next++) {
   
   rows[i] = new GlassStatus();
   
   if (prev < 0) {
    overflow1 = 0;
   } else {
    overflow1 = previousRows[prev].overflownVolume/2;
   }
   
   if (next >= level) {
    overflow2 = 0;
   } else {
    overflow2 = previousRows[next].overflownVolume/2;
   }
   if (level == 0) {
    inflow = volume;
   } else {
    inflow = overflow1 + overflow2;
   }
   
   tempVol += rows[i].heldVolume = Math.min(1, inflow);
   rows[i].overflownVolume = inflow - rows[i].heldVolume;    
  }
  
  if (level == ipRowNum) {
   return rows[ipGlassNum].heldVolume; 
  } else {
   return computeWaterAt(volume - tempVol, level + 1, rows);
  }
 }

 public static void readInput() {
  Scanner scanner = new Scanner(System.in);
  scanner.useDelimiter(System.getProperty("line.separator"));
  Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
  scanner.useDelimiter(delimiters);
  
  System.out.println("Input row#:");
  ipRowNum = scanner.nextInt();
  
  System.out.println("Input glass#:");
  ipGlassNum = scanner.nextInt();
  
  System.out.println("Input volume:");
  ipVolume = scanner.nextInt();
    
 }
 
 public static void main(String[] args) {
  readInput();
  System.out.println("Volume in the glass=" + computeWaterAt(ipVolume, 0, new GlassStatus[] {}));
 }

}

Complexity:

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

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

Construct a binary tree from inorder and preorder traversals

Problem:
Construct a BST from inorder and preorder traversal string

Solution:

Let us consider the below traversals:

Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

                 A
               /   \
             /       \
           D B E     F C

We recursively follow above steps and get the following tree.

         A
       /   \
     /       \
    B         C
   / \        /
 /     \    /
D       E  F

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
  static int preIndex = 0;
 
  if(inStrt > inEnd)
     return NULL;
 
  /* Pick current node from Preorder traversal using preIndex
    and increment preIndex */
  struct node *tNode = newNode(pre[preIndex++]);
 
  /* If this node has no children then return */
  if(inStrt == inEnd)
    return tNode;
 
  /* Else find the index of this node in Inorder traversal */
  int inIndex = search(in, inStrt, inEnd, tNode->data);
 
  /* Using index in Inorder traversal, construct left and
     right subtress */
  tNode->left = buildTree(in, pre, inStrt, inIndex-1);
  tNode->right = buildTree(in, pre, inIndex+1, inEnd);
 
  return tNode;
}

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=21296665
http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
http://discuss.leetcode.com/questions/148/construct-binary-tree-from-preorder-and-inorder-traversal

Find all combinations summing up to a given target

Problem:
In a given array a = {1, 7, 3, 4, 5, 6, 2} Print the indices of all the combinations which lead to a given sum called target. For e.g. if the method is
Void PrintAllSumCombos(int[] arr, int target) - and the array shown above is passed with sum target = 7, then the output should be:

0, 3, 6
0, 5
1
2, 3
4, 6

Note: For simplicity, You may assume the array does not contain any negative numbers and also consider same set of indices with a different order as identical - for e.g. if 2, 3 is already printed, ignore 3, 2 as they are one and the same.

Solution:
A simple  and straightforward solution is to examine all possible combinations recursively, and print those that sum up to the target:

void PrintAllSumCombos(int arr[], int target,int start,int taken[],int count) {
   if (target==0) {
      for (int i =0;i<count;i++) {
         cout << taken[i] << " ";
      }
      cout << "\n";
      return ;
   }
   if (target ==-1 || start > 7) {
      return ;
   }
   for(int i=start; i < 7 ;i++) {
      taken[count]=i;
   }
}
int main() {
   int a[7]={1, 7, 3, 4, 5, 6, 2};
   int b[7];
   PrintAllSumCombos(a, 7,0,b,0) ;

   return 0;
}

However, there must exist a more efficient dynamic programming solution. Basic idea: examine each element of the array. Drop those that are greater than the target (because all the elements are non-negative). Also drop all elements equal to the target and print their indexes (tricky part if we should account for zeroes, but this is doable - just don't drop the elements that are equal to the target then). Now we're left with items that are less than the target. We must now produce all possible pairs, remembering the indexes of the pair elements, calculate their sum and perform the same procedure as for single elements (dropping/printing the pairs as necessary). So we end up with a list of pairs with sums less than the target. Continue this until the list is empty. The worst case time complexity of this algorithm is still O(n ^ 2), however, in average case it must be more efficient because we examine less and less elements on each step due to dropping those that are too large.

Complexity:

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

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

Check if a binary tree is symmetric

Problem:
Check if a given binary tree is symmetric.

Solution:

public boolean recurseSymmetry(Node<AnyType> left, Node<AnyType> right ){
   if(left == null || right == null) return left==right;
   else 
      return left.value == right.value &&
             recurseSymmetry(left.left, right.right) &&
             recurseSymmetry(left.right, right.left);
}

Complexity:

time - O(n)
space - O(n) (for recursion stack)

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

Rank of a permutation

Problem:
Given a word consisting of letters, different words can be formed using all the letters in the word. Find the rank of input word in sorted list of all possible words.

Eg.
ABAB = 2
QUESTION = 24572

Program should use no more than 1GB memory and run within 500 milliseconds. Maximum input length = 25 and input word will contain atleast 2 different letters.

Solution:
From http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation :

A particular ranking of a permutation associates an integer with a particular ordering of all the permutations of a set of distinct items. For our purposes the ranking will assign integers 0..(n! − 1) to an ordering of all the permutations of the integers 0..(n − 1).

For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank:

  PERMUTATION      RANK
  (0, 1, 2, 3) ->  0
  (0, 1, 3, 2) ->  1
  (0, 2, 1, 3) ->  2
  (0, 2, 3, 1) ->  3
  (0, 3, 1, 2) ->  4
  (0, 3, 2, 1) ->  5
  (1, 0, 2, 3) ->  6
  (1, 0, 3, 2) ->  7
  (1, 2, 0, 3) ->  8
  (1, 2, 3, 0) ->  9
  (1, 3, 0, 2) -> 10
  (1, 3, 2, 0) -> 11
  (2, 0, 1, 3) -> 12
  (2, 0, 3, 1) -> 13
  (2, 1, 0, 3) -> 14
  (2, 1, 3, 0) -> 15
  (2, 3, 0, 1) -> 16
  (2, 3, 1, 0) -> 17
  (3, 0, 1, 2) -> 18
  (3, 0, 2, 1) -> 19
  (3, 1, 0, 2) -> 20
  (3, 1, 2, 0) -> 21
  (3, 2, 0, 1) -> 22
  (3, 2, 1, 0) -> 23

Algorithms exist that can generate a rank from a permutation for some particular ordering of permutations, and that can generate the same rank from the given individual permutation (i.e. given a rank of 17 produce (2, 3, 1, 0) in the example above).

One use of such algorithms could be in generating a small, random, sample of permutations of n items without duplicates when the total number of permutations is large. Remember that the total number of permutations of n items is given by n! which grows large very quickly: A 32 bit integer can only hold 12!, a 64 bit integer only 20!. It becomes difficult to take the straight-forward approach of generating all permutations then taking a random sample of them.

Code in Java:

  public static BigInteger getRank(int[] permutation)
  {
    int n = permutation.length;
    BitSet usedDigits = new BitSet();
    BigInteger rank = BigInteger.ZERO;
    for (int i = 0; i < n; i++)
    {
      rank = rank.multiply(BigInteger.valueOf(n - i));
      int digit = 0;
      int v = -1;
      while ((v = usedDigits.nextClearBit(v + 1)) < permutation[i])
        digit++;
      usedDigits.set(v);
      rank = rank.add(BigInteger.valueOf(digit));
    }
    return rank;
  }
 
  public static int[] getPermutation(int n, BigInteger rank)
  {
    int[] digits = new int[n];
    for (int digit = 2; digit <= n; digit++)
    {
      BigInteger divisor = BigInteger.valueOf(digit);
      digits[n - digit] = rank.mod(divisor).intValue();
      if (digit < n)
        rank = rank.divide(divisor);
    }
    BitSet usedDigits = new BitSet();
    int[] permutation = new int[n];
    for (int i = 0; i < n; i++)
    {
      int v = usedDigits.nextClearBit(0);
      for (int j = 0; j < digits[i]; j++)
        v = usedDigits.nextClearBit(v + 1);
      permutation[i] = v;
      usedDigits.set(v);
    }
    return permutation;
  }

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=21500666
http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation
http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms/1506337#1506337

Find increasing 3-tuple (sub-sequence)

Problem:
You given an array:
3, 2, 1, 6, 5, 4, 9, 8, 7
you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array.
Answer can have multiple tuples, you have to find any one.
In this array, answer will be 3, 6, 9

Solution:

1. Simple. Time complexity = O(n ^ 2)
• Create an array of indexes, and sort the original array keeping track of the indexes in the second array. Now go through the sorted array and for each element try to find a pair of grater elements whose indexes are increasing. Complexity: time = O(n log n) + O(n ^ 2) = O(n ^ 2), space = O(n)
• Alternatively, traverse the original array starting from the second element and consider it to be the middle of the 3-tuple. Try to find a smaller element at indexes [0..i) and a greater element at (i..n]. Complexity: time = O(n ^ 2), space = O(1)
• As suggested in a comment, the following BST solution won't work for "3, 1, 2, 4".
  Or, build a BST from the original array. Then find an element having two consecutive right children. They are grater than one another due to the BST property, and they are located one after another in the original array because we added them in this order in the BST. Complexity: time = O(n ^ 2) [worst] + O(n) = O(n ^ 2), space = O(n)
2. Advanced.
   Search for Longest Increasing Subsequence and stop after finding three elements of the tuple. Time complexity = O(n log n), space = O(n)

From Wikipedia:

Denote the sequence values as X[1], X[2], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:

M[j] — stores the position k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range k ≤ i (note we have j ≤ k ≤ i here, because j represents the length of the increasing subsequence, and k represents the position of its termination. Obviously, we can never have an increasing subsequence of length 13 ending at position 11. k ≤ i by definition).

P[k] — stores the position of the predecessor of X[k] in the longest increasing subsequence ending at X[k].

In addition the algorithm stores a variable L representing the length of the longest increasing subsequence found so far.

Note that, at any point in the algorithm, the sequence

X[M[1]], X[M[2]], ..., X[M[L]]

is nondecreasing. For, if there is an increasing subsequence of length i ending at X[M[i]], then there is also a subsequence of length i-1 ending at a smaller value: namely the one ending at X[P[M[i]]]. Thus, we may do binary searches in this sequence in logarithmic time.

The algorithm, then, proceeds as follows.

L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L
     such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)

The result of this is the length of the longest sequence in L. The actual longest sequence can be found by backtracking through the P array: the last item of the longest sequence is in X[M[L]], the second-to-last item is in X[P[M[L]]], etc. Thus, the sequence has the form

..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].

Another explanation for the above dynamic programming solution:
In general, we have set of active lists of varying length. We are adding an element A[i] to these lists. We scan the lists (for end elements) in decreasing order of their length. We will verify the end elements of all the lists to find a list whose end element is smaller than A[i] (floor value).

Our strategy determined by the following conditions,

1. If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.

2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].

3. If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.

Note that at any instance during our construction of active lists, the following condition is maintained.

“end element of smaller list is smaller than end elements of larger lists”.

It will be clear with an example, let us take example from wiki {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

A[0] = 0. Case 1. There are no active lists, create one.
0.
----------------------------------------------------------
A[1] = 8. Case 2. Clone and extend.
0.
0, 8.
----------------------------------------------------------

A[2] = 4. Case 3. Clone, extend and discard.
0.
0, 4.
0, 8. Discarded
----------------------------------------------------------

A[3] = 12. Case 2. Clone and extend.
0.
0, 4.
0, 4, 12.
----------------------------------------------------------

A[4] = 2. Case 3. Clone, extend and discard.
0.
0, 2.
0, 4. Discarded.
0, 4, 12.
----------------------------------------------------------

A[5] = 10. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 10.
0, 4, 12. Discarded.
----------------------------------------------------------

A[6] = 6. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 6.
0, 2, 10. Discarded.
----------------------------------------------------------

A[7] = 14. Case 2. Clone and extend.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------------------------

A[8] = 1. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2. Discarded.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------------------------

A[9] = 9. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Discarded.
----------------------------------------------------------

A[10] = 5. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 5.
0, 2, 6. Discarded.
0, 2, 6, 9.
----------------------------------------------------------

A[11] = 13. Case 2. Clone and extend.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------------------------

A[12] = 3. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 5. Discarded.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------------------------

A[13] = 11. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Discarded.
----------------------------------------------------------

A[14] = 7. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9. Discarded.
0, 2, 6, 9, 11.
----------------------------------------------------------

A[15] = 15. Case 2. Clone and extend.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <-- LIS List
----------------------------------------------------------

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=21602662
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Find Nth number in x2x3x5 sequence

Problem:
Following sequence is given:
1,2,3,4,5,6,8,9,10,12,15,16,18,20,24
In this sequence, each number is multiple of 2,3 or 5 only.
This sequence does not contain 7 & 14 as these number has sequence 7 as multiple.
So, if you are given N find the Nth number of this sequence.

Solution:
A dynamic programming solution (assume the sequence starts with 2):

1. Maintain a counter, that is initialized to 1 and start from an initial value v, say 2. 
2. Keep incrementing the value v and check if it is divisible by 2 or 3 or 5. 
3. If divisible, check if the corresponding quotient of v/2 or v/3 or v/5 is present in the solutions to subproblems, that are already computed. If yes increment the counter. 
4. Return value v when the counter becomes N.

void findN(int N) {
    HashMap<Integer, Integer> DPMap = new HashMap<Integer, Integer>();
    int temp = 2, i = 1;
    DPMap.put(1, 1);
    DPMap.put(2, 2);

    while (i < N) {
        temp++;
        if ((temp % 2 == 0 && DPMap.containsKey(temp / 2))
                || (temp % 3 == 0 && DPMap.containsKey(temp / 3))
                || (temp % 5 == 0 && DPMap.containsKey(temp / 5)))
        {
            i++;
            DPMap.put(temp, temp);
        }
    }
    System.out.println("The required number = " + temp);
}

Complexity:

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

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

Synchronize two clocks

Problem:
There is a clock at the bottom of the hill and a clock at the top of the hill. The clock at the bottom of the hill works fine but the clock at the top doesn’t. How will you synchronize the two clocks. Obviously, you can’t carry either of the clocks up or down the hill! And you have a horse to help you transport yourself. And, the time required for going up the hill is not equal to the time required to go down the hill.

Solution:
Let h1 be the time required to climb up to the top of the mountain on the horseback and h2 be the time required to climb down to the bottom on the horseback.

Let p1 and p2 be times required for the person to climb up and climb down on foot.

The person has to make four different kinds of round-trips and measure the round trip times.

1. Climb up and climb down on horseback. The round trip time would be: h1 + h2 = t1 (t1 is measured accurately using the clock at the bottom)
2. Climb up and climb down on foot. The round trip time would be: p1 + p2 = t2
3. Climb up on horseback and climb down on foot. The round trip time would be: h1 + p2 = t3
4. Climb up on foot and climb down on horseback. The round trip time would be: p1 + h2 = t4

Now we have four equations and four unknowns:
h1 + h2 = t1
p1 + p2 = t2
h1 + p2 = t3
p1 + h2 = t4

(t1 to t4 are measured values and hence are known). Solving the system of linear equations gives the values of h1, h2, p1 & p2.

Now start from the bottom of the hill, record the time, call it t, using the clock at the bottom and climb up either on horseback or on foot.

Once you reach the top, correct the clock's time at the top to be either t + h1(if you have climbed up the hill on horseback) or t + p1(if you have climbed up the hill on foot).

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

Remove every kth element (Josephus problem)

Problem:
There are n nodes in a circle and you will start removing every kth node from it until there is only one node left.

Design a datastructure which will allow above in O(n) time

Solution:
This is known as a Josephus problem. A solution is as follows: after removing kth element we end up with (n-1) elements left, and should then remove a kth element starting with the (k+1) element from the original sequence. Obviously, if we do that on the actual data structure, we'll need O(n^2) operations. So instead we should use modular arithmetic and simply find out the index of a remaining element. This can be done in O(n) time as follows:

def josephus(n, k):
   if n ==1:
     return 1
   else:
     return ((josephus(n-1,k)+k-1) % n)+1

This can also be implemented as a loop w/o recursion.
The answer to the original question is: a simple array will do.

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=20318662
http://en.wikipedia.org/wiki/Josephus_problem

Find the most frequent non-empty subarray

Problem:
Given an array of ints, find the most frequent non-empty subarray in it. If there are more than one such sub-arrays return the longest one/s.
Note: Two subarrays are equal if they contain identical elements and elements are in the same order.

For example: if input = {4,5,6,8,3,1,4,5,6,3,1}
Result: {4,5,6}

Solution:
The idea is to use a suffix array to easily identify repeated subarrays.

Suffix array is actually a 2D array. The suffix array for the given array {4,5,6,8,3,1,4,5,6,3,1} would be as below. Here, each element of the array itself is an array.

{4,5,6,8,3,1,4,5,6,3,1}
{5,6,8,3,1,4,5,6,3,1}
{6,8,3,1,4,5,6,3,1}
{8,3,1,4,5,6,3,1}
{3,1,4,5,6,3,1}
{1,4,5,6,3,1}
{4,5,6,3,1}
{5,6,3,1}
{6,3,1}
{3,1}
{1}

After sorting the suffix array, you'd get:
{8,3,1,4,5,6,3,1}
{6,8,3,1,4,5,6,3,1}
{6,3,1}
{5,6,8,3,1,4,5,6,3,1}
{5,6,3,1}
{4,5,6,8,3,1,4,5,6,3,1}
{4,5,6,3,1}
{3,1,4,5,6,3,1}
{3,1}
{1,4,5,6,3,1}
{1}

Checking for matching subarrays is easily done in a suffix array by comparing the prefixes. If you traverse the above sorted array and compare adjacent elements for similarity you'd see the prefix [4,5,6] is occurring maximum number(=2) of times and is also of maximum length. There are other subarrays as well, like [6], [5,6],[3,1] and [1] that are occurring 2 times, but they are shorter than the subarray [4,5,6], which is our required answer.

Complexity:

time - Θ(n) (to construct the suffix array)
space - O(n^2) (might probably avoid making copies of data, and only use indexes to the original array)

Links and credits:
http://www.careercup.com/question?id=20963685
http://en.wikipedia.org/wiki/Suffix_array

Given a string find the largest substring which is palindrome

Problem:
Given a string find the largest substring which is palindrome.

Solution:
Test if a substring is a palindrome starting from its potential "center":

int longestPalindromicSubstring(char* str)
{
 int len = strlen(str);
 int maxLength = 1;
 int start = 0;
 int low, high;
 
 for(int i = 1; i < len; i++)
 {
  // Find longest even length palindrome with
  // center points as i-1 and i
  low = i-1;
  high = i;
  while(low >= 0 && high < len && str[low] == str[high])
  {
   if(high - low + 1 > maxLength)
   {
    start = low;
    maxLength = high - low + 1;
   }
   low--;
   high++;
  }
  
  // Find longest odd length palindrom with
  // center point as i
  low = i-1;
  high = i+1;
  while(low >= 0 && high < len && str[low] == str[high])
  {
   if(high - low + 1 > maxLength)
   {
    start = low;
    maxLength = high - low + 1;
   }
   low--;
   high++;
  }
 }
 
 printf("Longest Palindromic Substring is: ");
 for(int i = start; i <= start + maxLength - 1; i++)
 {
  printf("%c", str[i]);
 }
 
 return maxLength;
}

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=20351666
O(n) algorithm (Manacher's Algorithm) is discussed at http://discuss.leetcode.com/questions/178/longest-palindromic-substring

Count bits in an integer

Problem:
Count the no. of 1's in an integer.

Solution:

Solution #1: The most straightforward approach is to check each bit one by one. Here is the code,

int count1(int n)
{
    int count=0;

    while(n)
    {
        if(n&1)
            count++;

        n = n>>1;
    }

    return count;
}

Solution #2: The below code is an efficient version which improves the average time.
This code is faster because on each iteration it always clears the LSB of the number.

int count2(int n)
{
    int count=0;

    while(n)
    {
        count++;
        n = n&(n-1);
    }

    return count;
}

Complexity:

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

Links and credits:
http://puddleofriddles.blogspot.ru/2012/03/count-bits-in-integer.html

Find number of coins summing up to a given sum

Problem:
Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

Example:
Given coins with values 1, 3, and 5.
And the sum S is set to be 11.

Solution:
First of all we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. We then go to sum 1. First, we mark that we haven't yet found a solution for this one (a value of Infinity would be fine). Then we see that only coin 1 is less than or equal to the current sum. Analyzing it, we see that for sum 1-V1= 0 we have a solution with 0 coins. Because we add one coin to this solution, we'll have a solution with 1 coin for sum 1. It's the only solution yet found for this sum. We write (save) it. Then we proceed to the next state - sum 2. We again see that the only coin which is less or equal to this sum is the first coin, having a value of 1. The optimal solution found for sum (2-1) = 1 is coin 1. This coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with the help of only 2 coins. This is the best and only solution for sum 2. Now we proceed to sum 3. We now have 2 coins which are to be analyzed - first and second one, having values of 1 and 3. Let's see the first one. There exists a solution for sum 2 (3 - 1) and therefore we can construct from it a solution for sum 3 by adding the first coin to it. Because the best solution for sum 2 that we found has 2 coins, the new solution for sum 3 will have 3 coins. Now let's take the second coin with value equal to 3. The sum for which this coin needs to be added to make 3 , is 0. We know that sum 0 is made up of 0 coins. Thus we can make a sum of 3 with only one coin - 3. We see that it's better than the previous found solution for sum 3 , which was composed of 3 coins. We update it and mark it as having only 1 coin. The same we do for sum 4, and get a solution of 2 coins - 1+3. And so on.

Set Min[i] equal to Infinity for all of i
Min[0]=0

For i = 1 to S
For j = 0 to N - 1
   If (Vj<=i AND Min[i-Vj]+1<Min[i])
   Then Min[i]=Min[i-Vj]+1

Output Min[S]

Complexity:

time - O(S*N)
space - O(S)

Links and credits:
http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

Modify bits x...y in an integer

Problem:
given two integers and two bit positions. Set the first integer between the two bit positions to be that of the second integer.

Solution:
The trickiest part is to calculate the mask:

int replace_bits(int a, int b, int x, int y) 
{ 
    int mask = ((1 << (y - x + 1)) - 1) << x; 
    // Clear a and replace with that of b 
    return ((a & ~mask) | (b & mask)); 
}

Complexity:

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

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

Calculate ceiling (y / x) w/o using % (modulo)

Problem:
given y bytes and you can transfer only x bytes at once..give a mathematical expression having only + - / * which gives the number of iterations to copy y bytes. ( dont try giving modulo operator answers )

Solution:

ceiling(y / x) = (y + (x - 1)) / x

In order to prove correctness you need to check two case sets:
1. y % x == 0 => addition of x-1 doesn't affect the result, so it is y/x (which is ok)
2. y % x > 0 => addition of x-1 increments result with 1 (which is ok because we need another copy for the remaining y % x bytes).

Complexity:

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

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

Print a decimal number in binary form

Problem:
Print a decimal number in binary form. eg: number=10 or 2.22 or 0.876 ....
Required to print only four number after decimal point.

Solution:
Subsequently divide the integer part by two, and then multiply the fractional part by two.

def dec2bin(number):
    ## integer part:
    int_number = int(number)
    int_bin_str = ''
    while int_number != 0:
        (int_number, remainder) = divmod(int_number, 2)
        int_bin_str = str(remainder) + int_bin_str

    ## fractional part
    frac_number = number - int(number)
    frac_bin_str = ''
    count = 0
    while( count < 4):
        frac_bin_str += str(int(2.0 * frac_number))
        frac_number  = 2*frac_number - int(2*frac_number)
        count += 1

    return int_bin_str+"."+frac_bin_str

## MAIN ##
print dec2bin(10)
print dec2bin(2.22)
print dec2bin(0.876)

Complexity:

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

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

Find subarray with given sum

Problem:
Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

Solution:
Initialize a variable curr_sum as first element. curr_sum indicates the sum of current subarray. Start from the second element and add all elements one by one to the curr_sum. If curr_sum becomes equal to sum, then print the solution. If curr_sum exceeds the sum, then remove trailing elemnents while curr_sum is greater than sum:

int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of first element
       and starting point as 0 */
    int curr_sum = arr[0], start = 0, i;
 
    /* Add elements one by one to curr_sum and if the curr_sum exceeds the
       sum, then remove starting element */
    for (i = 1; i <= n; i++)
    {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > sum && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }
 
        // If curr_sum becomes equal to sum, then return true
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d", start, i-1);
            return 1;
        }
 
        // Add this element to curr_sum
        if (i < n)
          curr_sum = curr_sum + arr[i];
    }
 
    // If we reach here, then no subarray
    printf("No subarray found");
    return 0;
}

Complexity:

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

Links and credits:
http://www.geeksforgeeks.org/find-subarray-with-given-sum/

Inorder Tree Traversal without recursion and without stack (Morris Traversal)

Problem:
Traverse a binary tree without using stack and recursion.

Solution:
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left

void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;
 
  if(root == NULL)
     return; 
 
  current = root;
  while(current != NULL)
  {                 
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;      
    }    
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;
 
      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }
             
      /* Revert the changes made in if part to restore the original 
        tree i.e., fix the right child of predecssor */   
      else 
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;      
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}

Complexity:

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

Links and credits:
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
http://www.careercup.com/question?id=6154593645887488

Find the majority number in a given sequence of numbers

Problem:
Find the majority number in a given sequence of numbers (a number that occurs more than N/2 times where N is the count of numbers in the sequence). Don't maintain a map of all occurring numbers along with a count. No number may be a majority.

Example: 1 1 2 3 4 1 6 1 7 1 1
Majority number is 1 since it occurs 6 times (> 11/2)

Solution:
maintain a counter and store the current number. If next number is same increment the counter, if different then decrement counter. If counter becomes zero, then store the next number as current number and set counter to 1, like a fresh start. After itertation is done, you will be left with a current number. Traverse the array once more to check if it is really majority or not. O(n) complexity.
(Moore voting algorithm).

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=5200260502650880
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

Check if the given binary tree is BST or not

Problem:
Check if the given binary tree is BST or not.

Solution:

public boolean isBSTMain(Node root) {
 return (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}

private boolean isBST(Node node, int min, int max) {
 if (node == null)  return true;
 
 if (node.data < min || node.data > max) return false;

 // left should be in range min...node.data
 boolean leftOk = isBST(node.left, min, node.data);
 if (!leftOk) return false;

 // right should be in range node.data..max
 return isBST(node.right, node.data, max);
}

Complexity:

time - O(n)
space - O(n) (the stack space for the recursion)

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

Find all pairs summing up to a given number

Problem:
Given an integer array, find pairs in an array which sum up to a given number.
For example: Array{4,5,1,3,2} and required sum=6 then output should be [1,5] and [2,4].

Solution:
1. O(n)/O(n):
Put all items to a hashtable, and then iterate over the array once more and check if the hashtable contains (sum-a[i]). Print the pair if so.

2. O(n log n)/O(1)
Sort the array and start pointers from both ends of the array checking if the given pair add up to the given value.
- If the current pair sum equals the value of the given number print the pair.
- If the current pair sum exceeds the given number decrement the right pointer by 1
- else increment the left pointer by 1

Complexity:

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

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

Determine the average salary w/o revealing individual salaries

Problem:
There are three people and they need to know the average of their salaries without knowing each other's salary. How will you do that?

Solution:

1. Here's a simple solution. We start out assuming everyone's salary is in a certain range, say 0 - 1 trillion. The first person picks a number uniformly at random in that range and informs only the second person about this random number. Since this number is just random, it conveys no information. The second person adds their salary to the number and informs the third person about this sum. The third person receives no info from this because of the random element added in. The third person adds their salary to this running total and informs the first person about the sum. The first person knows the random number and subtracts it out, leaving the first person with the sum of the second and third person's salary. The first person could have obtained this info from the average anyway, so no extra information has been conveyed. Finally the first person adds their salary and divides by 3.

2. More secure solution: Have them pick "two" random numbers and reveal the sum of two random numbers and their salary, then sum them all up. Each developer now exchanges one of their random numbers. Now, when they subtract random numbers from the total, none of them can guess each other's salary.
Once the random numbers are subtracted, divide it by 3, which is the average salary of three developer.

The added security is to avoid the third person disclosing the sum given by the second person in the first solution. Otherwise the first person could determine the salary of the second person.

Complexity:

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

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

Check if two huge files contain the same strings

Problem:

given two very big files , each having around 1 billion lines , u have to print all the lines that are common to both files . Please suggest a good optimal approach

Solution:
Use a Bloom filter. From Wikipedia:

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with a uniform random distribution.
To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1.
To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions are 0, the element is definitely not in the set – if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have by chance been set to 1 during the insertion of other elements, resulting in a false positive. In a simple bloom filter, there is no way to distinguish between the two cases, but more advanced techniques can address this problem.

Complexity:

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

Links and credits:

Algorithms and Data Structures Development

(a discussion posted in this members only group on LinkedIn)
http://en.wikipedia.org/wiki/Bloom_filter

Selecting randomly from an unknown sequence

Problem:
How to choose randomly from a sequence of unknown length. The typical use is to choose a random line from a file.

Detailed description:
You are given a file (and you do not know how big the file is, nor how big the lines in the file are). Write an algorithm that will generate a random number (which will be used to index into the file) such that the output of lines will be roughly proportional? That is if the file contained 4 lines, and if I ran the program 1 million times I should get each line printed approximately 250K times.

Solution:

import random

def random_element(seq):
    """Return an element chosen at random from `seq`."""
    it = None
    for n, elem in enumerate(seq):
        if random.randint(0, n) == 0:
            it = elem
    return it

To see why this function works, consider it inductively. For the initial case, we'll always pick the first element as "it", since a random int between 0 and 0 will be 0. So after one element, we've chosen uniformly from the one element we've seen.

For the inductive case, imagine we've read N-1 elements already, and "it" is a random element chosen uniformly from those N-1 elements. The chance that the Nth element should be chosen instead is 1/N, because at this point, the chance that any particular line should be "it" is 1/N. So we choose a random number, and if it's the 1/N outcome, we take the Nth line as "it." In the case that we don't take the new line, which is (N-1)/N, the old line is kept. It was chosen randomly from the N-1 lines that preceded this one, so each line has a final chance of ((N-1)/N)/(N-1), or 1/N, or being chosen. Therefore the new line and each of the old lines is equally likely, so the distribution is uniform.

Since the initial case meets our uniform-selection criterion, and we've shown that if N-1 satisfies it then N satisfies it, then by induction, our selection will be uniformly random for any N.

Complexity:

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

Links and credits:
http://nedbatchelder.com/blog/201208/selecting_randomly_from_an_unknown_sequence.html

Compute a partial sum of array using plus operator only

Problem:
There's an array of numbers A[1]...A[N]. Need to compute another array of numbers S[1]...S[N] such that each S[i] is a sum of all the elements A[1]...A[N] except the element A[i]. In other words:

S[i] = ƩA[j], 1 <= j <= N && j != i

Solution:
We need two passes over the array A[]. One to compute the sum in the forward direction (1..N) and assign the accumulated sum to each S[i] element. Another pass is performed in the backward direction (N..1) and adds the accumulated sum to the corresponding S[i] element. Each of the passes ensures that the sum accumulated in S[i] does not contain the value of A[i] itself:

1. take a variable say, Sum, initialize it as Sum = 0. 
2. For index i=1 to N do : 
      S[i] = Sum; 
      Sum+=A[i]; 
3. Sum = 0; 
4. For index i=N down to 1 do: 
      S[i]+=Sum; 
      Sum+=A[i]; 
5. Done.

Complexity:

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

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

Intersection of two linked lists

Problem:
There are two linked lists that intersect. Given two pointers to the heads of the lists, find the intersection point.

Solution:
Determine the length of each list - let it be L1 and L2. Traverse |L1 - L2| nodes in the longest list. Now both lists contain equal number of nodes before the intersection point. Simply traverse both lists with two pointers. Once the pointers point to the same node the intersection is found.

Complexity:

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

Links and credits:
http://www.kodelog.com/spot-the-intersection-of-linked-list/

Dutch national flag problem

Problem:
You are given an array of 1's 2's and 3's. Sort this list so the 1's are first, the 2's come second, and the 3's come third.

Ex: Input [1, 3, 3, 2, 1]
Output [1, 1, 2, 3, 3]

But there is a catch!! The algorithm must be one pass, which means no merge/quick sort. Also no extra list allocations are allowed, which means no bucket/radix/counting sorts.

You are only permitted to swap elements.

Solution:
One algorithm is to have the top group grow down from the top of the array, the bottom group grow up from the bottom, and keep the middle group just above the bottom. The algorithm stores the locations just below the top group, just above the bottom, and just above the middle in three indexes. At each step, examine the element just above the middle. If it belongs to the top group, swap it with the element just below the top. If it belongs in the bottom, swap it with the element just above the bottom. If it is in the middle, leave it. Update the appropriate index.

public class DutchNationalFlag {
 
    public static void dutchFlagSort(int[] arr, int p, int k) {
        int p_index = 0;
        int k_index = arr.length - 1;
        for (int i = 0; i <= k_index;) {
                if (arr[i] == p) {
                        swap(arr, i, p_index);
                        p_index++;
                        i++;
                }
                else if (arr[i] >= k) {
                        swap(arr, i, k_index);
                        k_index--;
                }
                else {
                        i++;
                }
        }
    }
 
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
 }

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=18824667
http://en.wikipedia.org/wiki/Dutch_national_flag_problem

Duplicate a fancy linked list

Problem:
Every node of the linked list has a random pointer (in addition to the next pointer) which could randomly point to another node or be null. How would you duplicate such a linkedlist?

Solution:
* Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node

* Now copy the arbitrary link in this fashion

original->next->arbitrary = original->arbitrary->next; /*TRAVERSE TWO NODES*/

This works because original->next is nothing but copy of original and
Original->arbitrary->next is nothing but copy of arbitrary.

* Now restore the original and copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;

* Make sure that last element of original->next is NULL.

Complexity:

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

Links and credits:
http://www.linkedin.com/groups/Every-node-linked-list-has-1920463.S.243967327?view=&gid=1920463&type=member&item=243967327&trk=eml-anet_dig-b_nd-pst_ttle-cn

Find two missing numbers

There's an array of 100 numbers. Another array contains only 98 numbers from the first one. Identify two missing numbers.

Constraints:

• Space complexity must be O(1).
  So you can't use any other data structure like a hash-map, etc.
• The arrays are immutable.
  So you can't e.g. sort them.

Math is your friend. For both arrays you need to count a sum of all numbers (sum and sum2), and a sum of squares of the numbers (sq_sum, sq_sum2). Then:

sum - sum2 = a + b
sq_sum - sq_sum2 = a^2 + b^2

(a + b)(a + b) = a^2 + b^2 + 2ab
(a + b)(a + b) - (a^2 + b^2) = 2ab
(sum*sum - sq_sum) = 2ab

(a - b)(a - b) = a^2 + b^2 - 2ab
               = sq_sum - (sum*sum - sq_sum) = 2sq_sum - sum*sum
sqrt(2sq_sum - sum*sum) = sqrt((a - b)(a - b)) = a - b
((a + b) - (a - b)) / 2 = b
(a + b) - b = a

Credit: see link below.

Complexity:

time O(N)

space O(1)

Links:
http://stackoverflow.com/questions/10218791/find-two-missing-numbers

Detect a loop in a linked list

Use two pointers: fast and slow. The slow one goes through all elements one by one. The fast one visits each 2nd element only (i.e. jumps to ->next->next).

If the fast pointer reaches the end of the list, then there's no loops. Otherwise both pointers will meet at some point in the loop, hence detecting the loop itself.

Implementation:

boolean isInInfiniteLoop(Node node) {
  if (node == null) {
    return false;
  }
  Node turtle = node; // slower moving node
  Node rabbit = node.next; // faster moving node
  while (rabbit != null) {
    if (rabbit.equals(turtle)) {
      // the faster moving node has caught up with the slower moving node
      return true;
    } else if (rabbit.next == null) {
      // reached the end of list
      return false;
    } else {
      turtle = turtle.next;
      rabbit = rabbit.next.next;
    }
  }
  // rabbit reached the end
  return false;
}

Source: http://eddii.wordpress.com/2006/11/15/detecting-infinite-loop/

To find the node at which the loop starts, one needs to run the above algorithm first and find the intersection point between the turtle and the rabbit. After that we simply do this:

while (rabbit != node) {
  rabbit = rabbit.next;
  node = node.next;
}

(remember that 'node' points to the head of the list.) I.e. the distance between the head of the list and the loop start is equal to the distance between the rabbit and the same loop start.

Complexity:

time O(n)

space O(1)

Links:

• http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm#Tortoise_and_hare