Question

link

In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.

Write a program with:

1. parent pointer provided
2. parent pointer not provided

Solution

If have parent pointer, it’s easy. Read solution here or [CC150v4] 4.5 Find Next Node in BST.

If no parent pointer, then we make use of the property of BST, can get an O(h) solution. h is the height.

A very good solution from this blog.

1. Start with root.
2. If the node is given has less than root, then search on left side and update successor.
3. If the node is greater than root, then search in right part, don’t update successor.
4. If we find the node
   1. if the node has right sub tree, then the minimum node on the right sub tree of node is the in-order successor.
   2. otherwise, just return successor

The most important point is: we only update successor during left turn, and don’t update during right turn.

Code

written by me

public TreeNode inorderSuccessor(TreeNode root, TreeNode target) {
    if (target.right != null) {
        return this.findLeftMost(target.right);
    } else {
        return this.traverse(root, new TreeNode(-1), target);
    }
}

private TreeNode traverse(TreeNode cur, TreeNode pre, TreeNode target) {
    if (cur.val == target.val) {
        return pre;
    } else if (cur.val < target.val) {
        cur = cur.right;
        return traverse(cur, pre, target);
    } else {
        pre = cur;
        cur = cur.left;
        return traverse(cur, pre, target);
    }
}

private TreeNode findLeftMost(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

Question

link

Write a program to find the anti-clock-wise peripheral (boundary) of a complete tree.

For a complete tree peripheral (boundary) is defined as

1. First the root
1. Then nodes on left edge
1. Then leaf nodes
1. Then nodes on right edge

For the above tree, peripheral will be: 0 1 3 7 8 9 10 11 12 13 14 6 2

Solution

It’s a very tricky solution. Very clever I would say.

1. print root node
2. print left nodes and leafs of left subtree in same order
3. print leafs and right nodes of right subtree in same order

Do practise this question again in the future!

Code

written by me

I used an Enum in the code.

public enum PeriType {
    LEFT, RIGHT, LEAF
}

private void peripheral(TreeNode root) {
    printNode(root);
    helper(root.left, PeriType.LEFT);
    helper(root.right, PeriType.RIGHT);
    System.out.println();
}

private void helper(TreeNode node, PeriType type) {
    if (node == null) {
        return;
    }
    switch (type) {
    case LEFT:
        printNode(node);
        helper(node.left, PeriType.LEFT);
        helper(node.right, PeriType.LEAF);
        break;
    case RIGHT:
        helper(node.left, PeriType.LEAF);
        helper(node.right, PeriType.RIGHT);
        printNode(node);
        break;
    case LEAF:
        if (node.left == null && node.right == null) {
            printNode(node);
        } else {
            helper(node.left, PeriType.LEAF);
            helper(node.right, PeriType.LEAF);
        }
        break;
    }
}

private void printNode(TreeNode root) {
    System.out.print(root.val + " ");
}

Question

link

Find Nth fibonacci number in O(logN) time complexity.

Solution

It’s a recursive sequence, where we can get the following equation:

A* [ F(1) F(0) ] = [ F(2) F(1) ]
A* [ F(2) F(1) ] = [ F(3) F(2) ] = A^2 * [ F(1) F(0) ]
A* [ F(3) F(2) ] = [ F(4) F(3) ] = A^3 * [ F(1) F(0) ]
..
..
..
..
A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ] = A^n * [ F(1) F(0) ]

Which means:

So all that is left is finding the nth power of the matrix A. Well, this can be computed in O(log n) time, by recursive doubling. For more, see question post or here.

Code

not written

Question

link

A very basic programming puzzle is being asked in programming interviews since last few years. Which of the below two loops will run faster?

/* First */  
for(i=0;i<100;i++)  
 for(j=0;j<10;j++)  
     //do somthing

/* Second */  
for(i=0;i<10;i++)  
 for(j=0;j<100;j++)  
     //do somthing  

Solution

1. The First executes assignment operations 101 times, while Second executes only 11 times.
2. The First does 101 + 1100 = 1201 comparisons, while the Second does 11 + 1010 = 1021 comparisons.
3. The First executes 1100 increments, while the Second executes 1010 increments.

Code

The following code proves why First is faster.

public static void solution() {
    int i, j, k, l;
    k = 0;
    l = 0;
    /* FIRST */
    for (i = 0, l++; i < 10; i++, k++)
        for (j = 0, l++; j < 100; j++, k++)
            ;
    // printf("First Loop: %d\t%d\n", k, l);
    System.out.println(k);
    System.out.println(l);

    k = 0;
    l = 0;
    /* SECOND */
    for (i = 0, l++; i < 100; i++, k++)
        for (j = 0, l++; j < 10; j++, k++)
            ;
    // printf("Second Loop: %d\t%d\n", k, l);
    System.out.println(k);
    System.out.println(l);
}

output is : 1010, 11, 1100, 101

Question

link

Given a string, recursively remove adjacent duplicate characters from string. The output string should not have any adjacent duplicates.

Input: azxxzy

Output: ay

First “azxxzy” is reduced to “azzy”. The string “azzy” contains duplicates, so it is further reduced to “ay”.

Analysis

We could do it recursively until all pairs are removed, but it’s not good.

There’s an O(n) solution.

Solution

Most obvious solution is to use a stack. In the end, the stack stores all unmatched chars.

But we can also do it without using space (assuming the input is char array). Just use the original char array to store result, with the helper of 2 pointers. The code is very much concise.

Code

Refactored code by me

public static String remove_pair(char[] input) {
    int len = input.length;
    int right = 1, left = 0;

    while (right < len) {
        // Cancel pairs
        while (right < len && left >= 0 && input[right] == input[left]) {
            right++;
            left--;
        }
        if (right == len) {
            break;
        }
        input[++left] = input[right++];
    }
    return String.valueOf(input).substring(0, left + 1);
}

Question

link

Given an array of integers find the maximum and minimum elements by using minimum comparisons.

Solution

Compare in Pairs.

1. If n is odd then initialize min and max as first element.
2. If n is even then initialize min and max as minimum and maximum of the first two elements respectively.
3. For rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.

Number of comparison is 1.5*n.

There’s also a Tournament Method from G4G, but the implementation is a bit difficult.

Code

not written by me

public static void minmax2(int[] a) {
    if (a == null || a.length < 1)
        return;

    int min, max;

    // if only one element
    if (a.length == 1) {
        max = a[0];
        min = a[0];
        System.out.println("min: " + min + "\nmax: " + max);
        return;
    }

    if (a[0] > a[1]) {
        max = a[0];
        min = a[1];
    } else {
        max = a[1];
        min = a[0];
    }

    for (int i = 2; i <= a.length - 2;) {
        if (a[i] > a[i + 1]) {
            min = Math.min(min, a[i + 1]);
            max = Math.max(max, a[i]);
        } else {
            min = Math.min(min, a[i]);
            max = Math.max(max, a[i + 1]);
        }

        i = i + 2;
    }

    if (a.length % 2 == 1) {
        min = Math.min(min, a[a.length - 1]);
        max = Math.max(max, a[a.length - 1]);
    }

    System.out.println("min: " + min + "\nmax: " + max);
}

Question

link

Given preorder, construct the BST.

Solution

We can get Inorder traversal by sorting the given Preorder traversal. So we have the required two traversals to construct the Binary Search Tree.

A very similar approach would be always spliting the array by the head value. Time complexity is O(nlgn) for a balanced BST, or O(n²) for a screwed tree.

Howver, there’s O(n) solutions.

The trick is to set a range {min .. max} for every node. Initialize the range as {INT_MIN .. INT_MAX}. The first node will definitely be in range, so create root node. To construct the left subtree, set the range as {INT_MIN …root->data}. If a values is in the range {INT_MIN .. root->data}, the values is part part of left subtree. To construct the right subtree, set the range as {root->data..max .. INT_MAX}.

The key is the we need a public variable as a pointer (to traverse thru the array).

There’s another O(n) solution using stack. I wont' cover for now.

Code

written by me

It’s not an easy question, to be frank.

int p;

public TreeNode solution(int[] preorder) {
    p = 0;
    return helper(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private TreeNode helper(int[] A, int min, int max) {
    int len = A.length;
    if (p >= len) {
        return null;
    } else if (A[p] < min || A[p] > max) {
        return null;
    }
    TreeNode root = new TreeNode(A[p]);
    p++;
    root.left = helper(A, min, root.val);
    root.right = helper(A, root.val, max);
    return root;
}

Question

link

You are given a collection of nuts of different size and corresponding bolts. You can choose any nut & any bolt together, from which you can determine whether the nut is larger than bolt, smaller than bolt or matches the bolt exactly. However there is no way to compare two nuts together or two bolts together. Suggest an algorithm to match each bolt to its matching nut.

Analysis

Use the idea of quicksort. Find pivot and divide.

Solution

1. Take a nut from the nuts pile
2. Divide bolts around it in 2 parts, which are smaller and larger than this.
3. Find a matching bolt to this nut.
4. Divide nuts in 2 parts, which are smaller and larger than matching bolt.

Now we have 2 subsets of Nuts and Bolts.

At every step, we will be able to divide these piles in 2 halves and reduce complexity by a factor of 2.

Average case time complexity will be O(nlogn), but O(n²) when pivot is selection poor.

Question

link

There is long list of natural numbers. Remove every 2nd no from list in 1st pass. Remove every 3rd no from list in 2nd pass. Find whether Nth natural no will exist after P passes. N and P are inputs.

Example: N is 15 and p is 3.
Initial: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
After 1st pass: 1 3 5 7 9 11 13 15 17 19
After 2nd pass: 1 3 7 9 13 15 19
After 3rd pass: 1 3 7 13 15 19
After 4th pass: 1 3 7 13 19

So we see that 15 exists after 3 passes but vanishes after 4th pass.

Analysis

We see that in any of the pass new position will be decreased by no of elements deleted between 1 and current position.

Example: originally number is 15. After 1st pass, it becomes 8th element. After 2nd pass, it becomes 8 - (8 / 3) = 6th element.

We stop when either P(i-1)/(i+1) is an integer, or when number is smaller than pass.

Code

not written by me

bool check_posiiton(int n, int p)  
{  
 int cur = n;  
 int i = 0;  
 while (i <= p)  
 {  
     i++;  
     if (cur%(i+1) == 0)  
     {  
         //Vanishes in this pass  
         return false;  
     }  
     else if (cur < (i+1))  
     {  
         //Number exist denominator is greater than numerator  
         return true;  
     }  
     cur = cur - cur/(i+1);  
 }  
 return true;  
}  

Game #1

link

Two players take turns breaking a chacolate bar (rectangle-shaped consist of squares). The last to break a piece wins the game.

Design the strategy.

Solution

Each time the bar is broken, total number of pieces increase by 1. Suppose there’re even number of squares, 1st player wins regardless of breaking strategy. And vice versa.

Problem #2

link

75 teams took part in a competition where teams met 1-on-1. Each time the defeated team drops out.

How many meets are needed to before one team is declared a winner?

Solution

Each game will eliminate 1 game, so it needs 74 games.

Splitting Piles

link

Given a random number of items in a pile. Ask an audience to split a pile into two piles, multiply the numbers of items in the two new piles and keep adding the results. The process stops when there is no pile with more than 1 chip.

For example, let start with 9 chips:

Before the audience told the final number, you immediately guess it’s 36. How did you do it?

Solution

The result does not depend on how the piles are split; but only on the initial size of the very first pile. Answer is always N(N - 1)/2.

This can be proved by mathematical induction.