Create a Binary Search Tree from Array

You are given an array representing the preorder traversal of a tree. From this array, construct the original BST.

for.eg. 

              { 60 40 30 28 35 42 70 65 62 68 72 }

 

Approach
Remember the property of a BST - parent is greater than its left and less than its right.
Now 60 is the root of the BST. Search for the possible right child. For this, scan the array from position 2 onwards till you encounter a bigger number than 60. So end up with 70. That is the right node. The left node is 40, the immediate number.
Next take 40 (the left child of root). Find its right child - the number greater than 40 and less than 70. It is 42. And the left child is 30.
Now take 72 (the right child of root). Fin its right child - the number greater than 70. We will find 72. Similarly, left child is 65.
For 30 the right child should be anywhere between numbers 28 and 35. So it is 35. Hence 28 is the left child.
For 42 there is no right child or left child as there are no numbers between 42 and 70.
And so on....

Solution

In place merge sort 2 sorted arrays

Given two sorted arrays A and B of size (m+n) and m respectively, design an algorithm to merge A and B in-place.

e.g.  A = {8, 12, 15, 20, 22, 0, 0, 0, 0}
        B = {6, 13, 18, 19}
 Result= {6, 8, 12, 13, 15, 18, 19, 20, 22}

Approach
Apply 2-way merge. Advantage of this method is - it can be extended for any number of arrays (k-way merge). Take the last elements of arrays (22 and 19), put the highest element to the end of Array A. Next take 20 and the previous smaller element (19). Compare and put 20 in the last but one position. so on..

Solution

Interview Street - pairs of numbers that have a difference of K

Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:3

Solution
This problem can be solved with hashing or by sorting.I have taken the sorting approach.
Sort the contents of the array in (n log n) time. Then for each number in the array, do a binary search to see if the num+k exists in the array.

In hashing approach, maintain a hashtable. As you iterate each number X, check if X+k exists in the hashtable with 1 value. If its there then you have a pair. Else put the key (X+k) and value '0'. 

Facebook Question - Find the longest increasing subsequence

Problem
You are given an unsorted array of integers. In that array, find the longest increasing subsequence.
For eg. {1, 5, 3, 4, 6, 1, 2, 4, 8, 5 }
In the above, there are multiple increasing sequences:
{1,5}
{3,4}
{3,4,6}
{1,2}
{1,2,4}
{1,2,4,8}
Of the above, last one is the longest sequence.
Write a program to solve the above. It should be linear O(N) time.

Approach
Initialize an array of same length as input. Call it current array. Read the first element and store it in this array. Keep navigating the input array and if the current element is greater than the last element in the current array, then put the value into the current array. If the value is less than the last current array element, then we need to start again. So we need to reset the current array. But hold on, the current array that we have might be the  longest subsequence. So before resetting the array check if the current length of current array is the biggest we found ever. If so copy the array elements into the result array.

current array: {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}
length: 1
maxlength:1

i=1, a[1] = 5 (increasing)
current array: {1, 5, 0, 0, 0, 0, 0, 0, 0, 0}
length: 2
maxlength: 2

i=2, a[2] = 3 (decreasing)
current array: {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}
result: {1, 5}
length: 1
maxlength: 2

i=3, a[3] = 4 (increasing)
current array: {3,4, 0, 0, 0, 0, 0, 0, 0, 0}
result:{1,5}
length: 2
maxlength:2

Solution

FaceBook Question - Find a missing number in 1 Billion numbers

Problem -
Facebook has over 1 Billion users and each user is assigned a unique FacebookID. Assume that each FacebookID is a valid int. These FacebookIDs are written in a text file sequentially. When an user de-activates his account on Facebook, the corresponding FacebookID is deleted from the file.
Write a program to find a user who has deactivated his account.

Approach -
Assuming int is 32 bits the total number of positive values supported are - 4,294,967,296. So it can support 4.2 billion numbers. 

1. Bit Map approach - We use a BitMap (or a boolean array in java) with values initialized to 0 (or false). The size of the bitMap is 2^32. Read each FacebookID and set the corresponding bitMap index to 1 (or true). Once all the 1 billion numbers are read and the bitMap updated - search for a bitMap value which is 0 and that is the missing number. 
So lets analyze the memory requirement for this approach. To store a bitMap of 2^32 size means 2^29 bytes (since 1 byte is 2^3 bits). This 2^29 bytes translates to 512 MB RAM. How did I arrive at this number?  2^29 = 536,870,912
or 536,870,912/1024 KB = 524,288 KB
or 524,288/1024 MB = 512 MB
So what if we didn't have this much RAM capability?

2. Bucket Partition Method - Take square-root of 2^32, which translates to 2^16 (=65,536). Create an int[] of size 65,536. Lets call these buckets. So there are 65,536 buckets. Each bucket is responsible for 65,536 values. So the bucket0 manages values (0,1,2... 65535). And bucket1 manages (65536, 65537 .... 131,071). and so on. This way the last bucket which is bucket65535 manages the last set of numbers.
Read each FacebookID and find the corresponding bucket. So for instance if the id is 9 it translates to bucket0. Do not store the value in the bucket, just increment the bucket value. So essentially each bucket just holds a count of numbers that it encountered in its limit. Once all the facebookIDs are read and the bucket counts set, identify a bucket which is not equal to 65,536. Lets say the bucket number is 1. Which means, the missing number is between 65536 to 131071. Lets call this TargetBucket.
Now reset the bucket values to 0. Next, read the faceBookIDs once again, but this time check if the value is between 65536 to 131071. If it is set the corresponding bucket to 1. This time our bucket0 manages 65536, bucket1 manages 65537, bucket2 manages 65538 and so on. Once all the values are read and the buckets populated, find a bucket which has 0. That is the missing number.
So what was the memory requirement for this one? 
2^16 bits or 2^13 bytes or 8,192 bytes or 8 KB. Woow, amazingly less!!

Solution
I have created a program which basically simulates the bucket partition method but limits itself to 16 Million numbers (16,777,216 or 2^24). It generates a text file of 16 million numbers with a few numbers skipped. So my bucket size is 4096 (or 2^12).

Microsoft: Find biggest number that can be formed from a list of unsorted numbers

  Microsoft Interview - Given an array of unsorted numbers (1 or 2 digits),
  Find the biggest number that can be created using these numbers
  For e.g. {6, 83, 12, 7, 16, 35}
  The biggest number that can be made is 83,7,6,35,16,12
 
Solution
  The idea is to create 2 maxheaps - one for one digit numbers
  The other for 2 digit numbers. Then compare and create final string.
 
  Extending this to any arbitary length is simple. Instead of using 2 maxheaps,
  use n maxheaps, where n is the length of the number with the maximum length.
  Compare and create can use N-way merge then, instead of simple if-else.

Sort array of 0,1,2

Given an array of 0s, 1s and 2s only in a mixed fashion. The task is to seperate out them such that 0s are on the left, 1s in the middle, and 2s on the right. The algorithm should run in linear time.

This problem is called "Dutch National Flag". There are lot of puzzles asked in the interview based on this.

Solution

Unimodal array has an increasing sequence followed by decreasing sequence, find the number at which the transition happens

  Unimodal array contains a list of 'N' integers. There exists M < N, such that
  a[0] to a[M] are in increasing series
  a[M+1] to a[N] are in decreasing series
  The problem is to find a[M] in O(Log N)
  E.g. {2, 4, 8, 10, 13, 18, 12, 7, 5, 4}. Here M is 18 as the switch happens after it

 Solution