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

Two non-repeating numbers in an unsorted array

Design an algorithm to find two non-repeating numbers in an array where other numbers are repeated.
for eg.
input array: {2, 8, 6, 8, 3, 9, 2, 9}
result: 3,6

Approach:-

XOR all the numbers. This gives a value x. 

2^2, 8^8, and 9^9 all become 0. So the remaining is 6^3.

0110

0011

------

0101

------

So x in this case is 5. Take the last set bit, in this case is 1 (that is the unit place). So in the result, one number has 1 in position 1 and the other number has 0 in position 1. That is the reason we have 1 in the result.

Next scan the input array again, but as the numbers are inspected check if the number has 0 or 1 in the position 1. Make 2 XOR groups - one group of numbers with 1 in position 1 and the other group having 0.

The result is the 2 numbers.

Solution

First occurrence of a number in a sorted array

Given a sorted array of numbers where each number is repeated multiple times,  design an algorithm to find the first occurrence of a given number.
for e.g.
input array: {2,2,2,3,4,5,5,5,6,6,6,7,7,7,7,12,12,15,19}
number: 6
Here number 6 is found in position 8,9 and 10 (0-indexed). However, 8 is the first index.

Approach:- Using binary search locate the block of numbers containing the list of target number.
Once the list is found, apply binary search on the block again.

Solution

Single non-repeating number

Given an array of numbers where every number except one is repeated, efficiently find the number.
for e.g. {9, 1, 8, 7, 8, 1, 9}
Answer: 7

Approach
Sorting and finding each number with the next number - this is not an ideal approach as it takes O(N^2).
Instead use bit manipulation. XOR all numbers and the left out number is the result

Solution

Sum of Digits until it becomes a single digit

You are given a huge number and the task is to add the number till it becomes a single digit.
E.g.
Number = 9580658690133945975556610984511994659
 9+5+8+0+6+5+8+6+9+0+1+3+3+9+4+5+9+7+5+5+5+6+6+1+0+9+8+4+5+1+1+9+9+4+6+5+9     =195
  1+9+5 =  15
  1+5 = 6
  Result = 6
 
  Wait!! Can I do it in one pass?? Yes O(N) solution
  Add the values. If sum is divisible by 9, result is 9.
  Else result is (sum mod 9). In the above case, after the first pass the result is 195. Hence 195%9 = 6, the   desired answer.

Solution

Count number of 1's in a Number

Count the number of 1's in a number's representation.
E.g. Number 23 is 0001 0111
So there are 4 One's

Approach
Left Shift a number (equivalent to dividing by 2). Then if divided number is a double of original number, ignore. Else increment count (the original number is odd).
23 >> 1   gives 11
11 >> 1   gives 5
5  >> 1    gives 2
2 >> 1     gives 1

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