find whether a no is power of two

1. A simple method for this is to simply take the log of the number on base 2 and if you get an integer then number is power of 2.

2. Another solution is to keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.

#include<stdio.h> #define bool int /* Function to check if x is power of 2*/ bool isPowerOfTwo(int n) {   if(n == 0)     return 0;   while(n != 1)   {     n = n/2;     if(n%2 != 0 && n != 1)       return 0;   }   return 1; } /*Driver program to test above function*/ int main() {   int test_no = 31;   if(isPowerOfTwo(test_no))     printf("%d is a power of 2", test_no);   else     printf("%d is not a power of 2", test_no);   getchar(); }

3. All power of two numbers have only one bit set. So count the no. of set bits and if you get 1 then number is a power of 2. Please see http://geeksforgeeks.org/?p=1176 for counting set bits.

4. If we subtract a power of 2 numbers by 1 then all unset bits after the only set bit become set; and the set bit become unset.

For example for 4 ( 100) and 16(10000), we get following after subtracting 1
3 –> 011
15 –> 01111

So, if a number n is a power of 2 then bitwise & of n and n-1 will be zero. We can say n is a power of 2 or not based on value of n&(n-1). The expression n&(n-1) will not work when n is 0. To handle this case also, our expression will become n& (!n&(n-1))
Below is the implementation of this method.

#include<stdio.h> #define bool int /* Function to check if x is power of 2*/ bool isPowerOfTwo (int x) {   /* First x in the below expression is for the case when x is 0 */   return x && (!(x&(x-1))); } /*Driver program to test above function*/ int main() {     int test_no = 15;     if(isPowerOfTwo(test_no))        printf("%d is a power of 2", test_no);     else        printf("%d is not a power of 2", test_no);     getchar(); }

Level sum of the nodes in Binary Tree

vertical (column) sum of  a binary tree.

Example:

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

The tree has 5 vertical lines

Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7

We need to output: 4 2 12 3 7

Implementation:

void get_Vertical_Sum(Tree* T,int[] sum,int column)
{
   if(T==NULL)
      return;
   else
   {
     verticalSum[column]+=T->data;
     get_Vertical_Sum(T->left,column-1);
     get_Vertical_Sum(T->right,column+1);
   }
}

Horizontal (level) sum of a binary tree

Example:

    5
  /  \
 3    8
/ \  / \
1 4  6 10

for this tree a[0]=5, a[1]=11, a[2]=21…..

Implementation:

void get_Horizontal_Sum(Tree* T,int[] sum,int level)
{
   if(T==NULL)
      return;
   else
   {
     sum[level]+=T->data;
     get_Horizontal_Sum(T->left,level+1);
     get_Horizontal_Sum(T->right,level+1);
   }
}

Swap bits in a given number

Given a number x and two positions (from right side) in binary representation of x, write a function that swaps n bits at given two positions and returns the result. It is also given that the two sets of bits do not overlap.

---

Examples:
Let p1 and p2 be the two given positions.

Example 1 : –
Input:
x = 47 (00101111)
p1 = 1 (Start from second bit from right side)
p2 = 5 (Start from 6th bit from right side)
n = 3 (No of bits to be swapped)
Output:
227 (11100011)
The 3 bits starting from the second bit (from right side) are
swapped with 3 bits starting from 6th position (from right side)

Example 2 : –
Input:
x = 28 (11100)
p1 = 0 (Start from first bit from right side)
p2 = 3 (Start from 4th bit from right side)
n = 2 (No of bits to be swapped)
Output:
7 (00111)
The 2 bits starting from 0th postion (from right side) are
swapped with 2 bits starting from 4th position (from right side)

---

Solution
We need to swap two sets of bits. XOR can be used in a similar way as it is used to swap 2 numbers. Following is the algorithm.
1) Move all bits of first set to rightmost side
set1 = (x >> p1) & ((1U << n) – 1)
Here the expression (1U << n) – 1 gives a number that
contains last n bits set and other bits as 0. We do &
with this expression so that bits other than the last
n bits become 0.
2) Move all bits of second set to rightmost side
set2 = (x >> p2) & ((1U << n) – 1)
3) XOR the two sets of bits
xor = (set1 ^ set2)
4) Put the xor bits back to their original positions.
xor = (xor << p1) | (xor << p2)
5) Finally, XOR the xor with original number so
that the two sets are swapped.
result = x ^ xor

---

Implementation:

#include<stdio.h> int swapBits(unsigned int x, unsigned int p1, unsigned int p2, unsigned int n) {     /* Move all bits of first set to rightmost side */     unsigned int set1 =  (x >> p1) & ((1U << n) - 1);     /* Moce all bits of second set to rightmost side */     unsigned int set2 =  (x >> p2) & ((1U << n) - 1);     /* XOR the two sets */     unsigned int xor = (set1 ^ set2);     /* Put the xor bits back to their original positions */     xor = (xor << p1) | (xor << p2);     /* XOR the 'xor' with the original number so that the        two sets are swapped */     unsigned int result = x ^ xor;     return result; } /* Drier program to test above function*/ int main() {     int res =  swapBits(28, 0, 3, 2);     printf("\nResult = %d ", res);     return 0; }

Output:

 Result = 7

Following is a shorter implementation of the same logic

int swapBits(unsigned int x, unsigned int p1, unsigned int p2, unsigned int n) {     /* xor contains xor of two sets */     unsigned int xor = ((x >> p1) ^ (x >> p2)) & ((1U << n) - 1);     /* To swap two sets, we need to again XOR the xor with original sets */     return x ^ ((xor << p1) | (xor << p2)); }

---

Google Interview Puzzles

I gathered some of the important and top interview questions of Google from different people interviews. I hope This post helps those who are preparing for the Google Interview.

1.There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
Solve it without division operator and in O(n).

2.There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
Hint:
i)Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
ii)It should be done in O(n).

3.Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.

4.You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.
Note:Some position may be blank in the game। So your data structure should
consider this condition also.

5.You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.

6.How do you put a Binary Search Tree in an array in a efficient manner.
Hint:  If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.

7.How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Note:  You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.

8.Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 … in cn

9.Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.

10.Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?

11.How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?

12.Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi).How do you do the same ?

13.Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?

14.Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
Hint: Some kind of pointer handling with In Order Traversal – anybody in for writing some code

15.You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?

16.Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

17.Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?

18.Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

19.Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

20.Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

21.Given an array,
i) find the longest continuous increasing subsequence.
ii) find the longest increasing subsequence.

22.Write a function to find the middle node of a single link list.

23.Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

26.Implement put/get methods of a fixed size cache with LRU replacement algorithm.

27.You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

Distance is defined like this :

If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))”

Please give a solution in O(n) time complexity

28.Classic – Egg Problem
You are given 2 eggs.You have access to a 100-storey building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

You can discuss these puzzles in comments.if you have any more Google puzzles which are interesting and frequently asking in interviews comment it, i will add to the above 27 puzzles.