Nearest sibling of a node

Find the nearest sibling of a given node in a tree. Nodes on same level are siblings of each other.
_________A_________
_____B________C____
___D___E____H_____
__F_____G__I_______
Nearest sibling of G is I

Strategy:

Do breadth first traversal of a tree ..
For this, we need one FIFO queue . Starting from root of the tree, go on queuing nodes in a queue at each level, then dequeue the front node and enqueue it's children and so on ...
In above example,
1. Enqueue A - Queue = A
2. Dequeue A and Enqueue B and C - Queue = B C
3. Dequeue B and Enqueue D and E - Queue = C D E
4 .Dequeue C and Enqueue H - Queue = D E H
5. Dequeue D and Enqueue F - Queue = E H F
6. Dequeue E and Enqueue G - Queue = H F G
7. Dequeue H and Enqueue I - Queue = F G I
8. Dequeue F - Queue = G I
Hence, in the queue we can see that nearest sibling of G is I.

Searching a string in a set of strings

Given a string, search it in a set of strings (say among 1000s of string). What data structure would you use to store those 1000 strings and get the results fastest?

Variation:
Search a Word in a 2D Grid of characters
Given a 2D grid of characters and a word, find all occurrences of given word in grid. A word can be matched in all 8 directions at any point. Word is said be found in a direction if all characters match in this direction (not in zig-zag form).

The 8 directions are, Horizontally Left, Horizontally Right, Vertically Up and 4 Diagonal directions.
http://www.geeksforgeeks.org/search-a-word-in-a-2d-grid-of-characters/
http://www.geeksforgeeks.org/find-all-occurrences-of-the-word-in-a-matrix/

Strategy:
Solution 1 : Simple, but not best solution
Create a hashtable, and store all the strings in that hashtable. For the given string, search in that hashtable. In the worst case, if we get same hashcode for all the strings, then we have to compare with all the strings.

Solution 2 : Best solution
Create a Trie structure, and search for the string in that trie. Depending upon how we construct the trie, the complexity varies from O(n) to O(n*m) where n is the no.of characters in the given string, and m is the no.of different characters that we have in all the strings.

In the trie, for each node, if we create children for all the possible characters, then the complexity will be O(n), where n is the no.of characters in the given string. The memory requirement will be high in this case.

If we don't create children for all the possible characters, and create children only for the strings that exist in our set, then at each level, we have to search among the children to find the string. So, the complexity would be O(n*m) where n is the no.of characters in the given string, and m is the no.of different characters that we have in all the strings. In this case, we will not use extra memory. 

Find a string/pattern in a 2d character array

You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.

Example: Find “microsoft” in below matrix.

We can see the read color character, which form “Microsoft” in above 2D array.


Strategy:
Manually finding the solution of this problem is relatively intuitive, we just need to describe an algorithm for it. Ironically, describing the algorithm is not the easy part.

How do we do it manually? First we match the first element; if it matched we matched the 2nd element in the 8 neighbors of first match; do this process recursively; when last character of input pattern matches, return true.

During above process, you take care not to use any cell in 2D array twice. For this purpose, you mark every visited cell with some sign. If your pattern matching fails at some place, you start matching from the beginning (of pattern) in remaining cells. While returning, you unmark visited cells.

Lets convert above intuitive method in algorithm. Since we are doing similar checks every time for pattern matching, a recursive solution is what we need here.

In recursive solution, we need to check if the substring passed is matched in the given matrix or not. The condition is not to use the already used cell. For finding already used cell, we need to have another 2D array to the function (or we can use an unused bit in input array itself.) Also, we need the current position of input matrix, from where we need to start. Since we need to pass a lot more information than actually given, we should be having a wrapper function to initialize that extra information to be passed


Algorithm:

If you are past the last character in pattern
    Return true


If you got an used cell again
    Return falseIf you got past the 2D matrix  
    Return false


If searching for first element and cell doesn’t match
    findmatch with next cell in row-first order (or column first order)


otherwise if character matches
    mark this cell as used
    res = findmatch  with next position of pattern in 8 neighbors
    mark this cell as unused
    Return res


Otherwise
    Return false

Code:


#define MAX 100


bool findmatch_wrapper(char mat[MAX][MAX], char *pat, int nrow, int ncol)
{
    if (strlen(pat) > nrow*ncol)
        return false;
    
    int used[MAX][MAX] = {{0,},};


    return findmatch(mat, pat, used, 0, 0, nrow, ncol, 0);
}


//level: index till which pattern is matched
//x, y: current position in 2D array


bool findmatch(char mat[MAX][MAX], char *pat, int used[MAX][MAX], int x, int y, int nrow, int ncol, int level)
{
    if (level == strlen(pat)) //pattern matched
        return true;
        
    if (nrow == x || ncol == y)
        return false;
        
    if (used[x][y])
        return false;    
    
    if (mat[x][y] != pat[level] && level == 0)
    {
        if (x < (nrow - 1))
            return findmatch(mat, pat, used, x+1, y, nrow, ncol, level); //next element in same row
        else if (y < (ncol - 1))
            return findmatch(mat, pat, used, 0, y+1, nrow, ncol, level); //first element from same column
        else 
            return false;
    }    
    else if (mat[x][y] == pat[level])
    {
        bool res;
        //marking this cell as used
        used[x][y] = 1;       
             
        //finding subpattern in 8 neighbours     
        res = (x > 0                                    ? findmatch(mat, pat, used, x-1, y, nrow, ncol, level+1) :   false) ||
              (res = x < (nrow - 1)                     ? findmatch(mat, pat, used, x+1, y, nrow, ncol, level+1) :   false) ||
              (res = y > 0                              ? findmatch(mat, pat, used, x, y-1, nrow, ncol, level+1) :   false) ||
              (res = y < (ncol - 1)                     ? findmatch(mat, pat, used, x, y+1, nrow, ncol, level+1) :   false) ||
              (res = x < (nrow - 1) && (y < ncol -1)    ? findmatch(mat, pat, used, x+1, y+1, nrow, ncol, level+1) : false) ||
              (res = x < (nrow - 1) && y > 0            ? findmatch(mat, pat, used, x+1, y-1, nrow, ncol, level+1) : false) ||
              (res = x > 0 && y < (ncol - 1)            ? findmatch(mat, pat, used, x-1, y+1, nrow, ncol, level+1) : false) ||
              (res = x > 0 && y > 0                     ? findmatch(mat, pat, used, x-1, y-1, nrow, ncol, level+1) : false);


        //marking this cell as unused
        used[x][y] = 0;
        return res;
    }
    else
        return false;
}

Company Specific Preparation

Microsoft Preparation:
Labels-------
Linked List
http://sudhansu-codezone.blogspot.in/search/label/Linked%20List
http://geeksforgeeks.org/forum/tags/linked-lists
+

Tree
http://sudhansu-codezone.blogspot.in/search/label/Tree

+
Puzzles
http://sudhansu-codezone.blogspot.in/search/label/Puzzle
Intrvw Links--------
http://geeksforgeeks.org/forum/view/company-interview?company=43
http://mycareerstack.com/questions/?company=Microsoft
http://placementsindia.blogspot.in/search/label/Microsoft

Amazon Preparation:
http://tech-queries.blogspot.in/search/label/Amazon%20Interview
http://letschat.info/list-of-amazon-questions/ 

Knapsack Problem

Given a set of items, each with a weight (w_i) and a value (v_i), determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Alternatively,
US Pizza gives you a bowl that can hold 100 gms of salad. You have different salad items each having its own Nutritional Value (NV) and availability. You are supposed to find the way one should fill his bowl so that he gets maximum nutrition. They need not take all of the available quantity. Taking a fraction of the salad item is allowed.
Items          Nutrition Value per Gram         Available
Noodle      10                                                           100 gm
Soyabean  30                                                             15 gm
Macroni     5                                                            100 gm
Fruits         40                                                             10 gm


Strategy:
It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

Define m[i,w] to be the maximum value that can be attained with weight less than or equal to w using items up to i.

We can define m[i,w] recursively as follows:

• m[0,w] = 0
• m[i,0]=0
• m[i,w] = m[i-1,w] if w_i > w (the new item is more than the current weight limit so this element cannot be accepted because it’s weight is larger than w )
• m[i,w] = max(m[i-1,w] ,m[i-1,w-w_i ] + vi) if w_i < = w.


The solution can then be found by calculating m[n,W]. To do this efficiently we can use a table to store previous computations. This solution will therefore run in O(nW) time and O(nW)space. 

Solution to alternate problem:
     All we need to do here is start with the item that provides the highest nutrition/gram and take the maximum available quantity unless the bowl is full. If after this, the bowl still has space, you take the item with the second highest nutrition/gram value. And so on.

I am sure you get the idea. For the given example, you would take 10 gm of Fruits (Full = 10, Remaining = 90), 15 gm of Soyabean (Full = 25, Remaining = 75), and to fill up the rest, with 75 gm of Noodles (Full = 100, Remaining = 0). In this way of selection, you get the maximum nutritional value, 1600 (10*40 + 15*30 + 75*10).

Flip Game

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.
http://www.programcreek.com/2014/04/leetcode-flip-game-java/

Stream is divisible by 3 or not

Suppose you are getting an infinite binary stream of characters then after any point of time you need to print whether the no is divisible by 3 or not, how will you do that?


Method:

A binary number is divisible my 3 if the number of ‘1s’ at even position – number of ‘1s’ at odd positions in the binary digit is divisible by 3

498 in binary is 111110010 no of even ‘1’ bits =3 and no of odd ‘1’ bits =3 so 3-3 =0 Hence 498 is divisible by 3.

So in the infinite stream of binary characters maintain two counters odd and even and update them whenever you get a ‘1’ at the position. Whenever you need to check the divisibility by 3 subtract odd from even and check the divisibility of the remainder from 3.

This question can be generalized for checking divisibility by other numbers as well. It is easy in the case of even numbers such as

If the rightmost bit is 0, then it is divisible by 2,
If rightmost two bits are zeros then the number is divisible by 4,
If rightmost three bits are zeros the number is divisible by 8 and so on.

However it is tricky in case of odd numbers. We just saw for 3, let us check for 5 as well

For 5, note that 2^j == 1, 2, -1, -2 mod 5 for j == 0, 1, 2, 3 mod 4 respectively.

So let A, B, C, D be the number of bits which are 1 with n congruent to 0, 1, 2, 3 mod 4,
and take A + 2 B - C - 2 D. Then x is divisible by 5 iff the result is divisible by 5.

E.g. for 11110101 we have A = 2, B = 1, C = 2, D = 1, result = 0 so it's divisible by 5.
You may find it easier to start at the right end and go digit-by-digit, adding or subtracting 1 or 2 for each 1 as appropri

Search a Word

Given a large file, how will you store the words in the file so that searching of a word can be done in constant time? Also how will you find the 10 most frequently occurring words in the file?

Approach:

Searching for words in a file is a very common interview problem and is asked a lot. There are 2 approaches to deal with this.

On would be to make use of Hash Table and store the count of the word as the value and the word as the key. Once the Hash Table has been made we can use a min-heap to find out the 10 most frequently occurring words. A new word is compared with the root and if its count is more than the root element then the root is replaced by that word and heapify is called again on the heap.

The other approach would be to use trie. In trie each node represents a character of a word and has pointer to a character which comes after it in a valid word. This structure supports insertion and search operation in O(k) where k is the length of the word so it can be treated as constant time. You can read more about trie here.

An even more space efficient variation of trie would be a radix tree in which if a node has only one child then the node of the tree is merged with it. Read here

Once the trie has been constructed we can traverse through it in O(n) time (through each of the leaf node --> time spent in reaching a leaf node is considered to be constant time) and again use a min-heap to find the 10 most frequently occurring words. Both the approaches have the space complexity of O(n) and time complexity of O(nlog10).

As ever, Hash tables have the problem of collisions, hence some would argue that tries are better. But the point is the argument that all the words in trie can be found using O(n) times, is fallacious because we will be actually visiting each node and that will be equal to the total number of nodes in the trie.

However, we must realize that trie or suffix tree, is useful data structure, and has a number of practical applications as can be read in this discussion thread . You can find some extensions and implementations here. 

 

Food for thought:
The interviewer can make the problem more complex by saying that we may choose to get any number of the most frequently occurring words.

The solution to this problem would be to construct the hash table with the word count, sort the hash table once it has been created (of course it will destroy the structure) and then get any number of most frequently occurring words. We should pay attention in this case tries cannot be used. until we are ready to build a different min-heap for each request.

If we want to avoid sorting, there has to be some constraint on the number of most frequently occurring words that we can ask for. If there is an upper bound 'k', we can again resort to the use of min-heap and give the desired most frequently occurring words.

Find defective ball

You have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weighings how do you find the defective one?

Level of water

If you are on a boat and you throw out a suitcase, will the level of water increase or decrease?

Measure weights in balance

Puzzle 1:

The puzzle is if the shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1, 3 and 4 only. Now the question is how many minimum weights and names the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also. Answer for this puzzle is given below.

Solution :

This is simply the numbers 2^0,2^1,2^2 ... that is 1,2,4,8,16... So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, and 512. Comments your suggestions or other answers.

Puzzle 2:

This is same as the above puzzle with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg. Answer for this puzzle is given below.

Solution:

For this answer is 3^0, 3^1, 3^2... That is 1,3,9,27,81,243 and 729.

Round MAnhole Covers

Why are manhole covers round? Do manhole covers really need to be circular?

River, Soldiers & Boat

Consider there are 10 soldiers on the one side of the river. They need to go to the over side of the rever. There is no bridge in the rever and no one can swin in the rever. One of the soldiers spots the boat with two boys inside. The boat is very small and the boys in the boats also very small. The boat can either hold two boys or one soldier. Now tell me how can all soldiers go to the other side of the river using this boat ?

Globe Walker

How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started?

Aeroplanes round the world

The puzzle question is : On Bagshot Island, there is an airport. The airport is the homebase of an unlimited number of identical airplanes. Each airplane has a fuel capacity to allow it to fly exactly 1/2 way around the world, along a great circle. The planes have the ability to refuel in flight without loss of speed or spillage of fuel. Though the fuel is unlimited, the island is the only source of fuel.

What is the fewest number of aircraft necessary to get one plane all the way around the world assuming that all of the aircraft must return safely to the airport? How did you get to your answer?

Notes:

(a) Each airplane must depart and return to the same airport, and that is the only airport they can land and refuel on ground.

(b) Each airplane must have enough fuel to return to airport.

(c) The time and fuel consumption of refueling can be ignored. (so we can also assume that one airplane can refuel more than one airplanes in air at the same time.)

(d) The amount of fuel airplanes carrying can be zero as long as the other airplane is refueling these airplanes. What is the fewest number of airplanes and number of tanks of fuel needed to accomplish this work? (we only need airplane to go around the world)

Solution:

The fewest number of airplane is 3!

Imagine 3 airplane: A (black), B (red) and C (green). A is going to fly round the world. All three aircraft start at the same time in the same direction.

Check out the pics (where blue arrow shows fuel transfer):

After 1/6 of the earth's circumference, C passes 1/3 of its fuel to B and returns home, where it is refueled and starts immediately again to tail A and B. So, at 1/6 circumference:
A = 2/3 fuel left
B = 2/3 (fuel left) + 1/3 (refueled by C) = Full tank
C = 2/3 (fuel left) - 1/3 (refueling B) = 1/3 fuel left
Then C backs to the airport with 1/3 fuel left.


Now A and B go to the 1/4 earth's circumference, meaning that they're gonna spend another 1/6 fuel in their tanks to reach that point. At this point, B transfer fuel to A until A's tank is full.
So, at 1/4 circumference:
A = 1/2 (fuel left) + 1/2 (refueled by B) = Full tank
B = 5/6 (fuel left) - 1/2 (refueling A) = 1/3 fuel left.
After that B returns to 1/6 circumference, which consumes B fuel until only 1/6 tank left and doesn't enough to bring it back to the airport.
Luckily, C already departed at the point with fuel of 2/3 tank and now awaits to refuel B.
B and C then return to the airport with 1/3 fuel each.


A (now with full tank) can go 1/2 world's length, meaning it will reach 3/4 earth's distance.

With the same scheme as above, B now goes to the opposite direction from the airport and awaits A at point 3/4 circumference with 5/6 tank of fuel. A who runs out of fuel is saved by B and received 1/2 tank of fuel.
So, at 3/4 circumference:
A = 0 (fuel left) + 1/2 (refueled by B) = 1/2 fuel left.
B = 5/6 (fuel left) - 1/2 (refueling A) = 1/3 fuel left.
A now has the enough fuel to go straight home to the airport.

B (with only 1/3 fuel left on the tank) then refueled by C at 5/6 circumference, and both plane now have enough fuel to go back to the airport.

Probability of Parking Slot

The probability of finding the parking slot occupied is 1/3. You find it empty for 9 consecutive days. Find the probability that it will be empty on the 10th day.

Concept:
The answer to this question is 2/3, why ? Read the question carefully, it says what is the probability of finding it empty on the 10th day. Now in probability if an event has already happened it cannot have an effect on the probability of an event to occur in future. The parking slot has been empty for 9 days but that does not effect the 10th day.

Had the question been what is the probability of finding a parking slot empty for 10 consecutive days then the answer would have been (2/3)^10. 

Minimum Sips

Given 1000 bottles of juice, one of them contains poison and tastes bitter. Spot the spoiled bottle in minimum sips.

We can do it in log(n) and that would be 10 sips. Of course it can be done in 1000 sips by checking each bottle but to do it in 10 sips you can take one drop from 500 bottles and mix them, if it is sour than the bottle is in those 500 or it is in different 500.Then out of those 500 you take 250 and do the same and rest is the binary search  .

Generate TRUE

Given a number x, less than 100. How will you generate true with probability x/100. So if x = 65, how will you generate true with probability 65/100. You can represent true by 1 and false by 0.

Strategy:

We can make use of rand() function to generate a number less than 100 by taking rand()%100. If the number is less than x, you can output true, otherwise you output false.

If you are asked to generate true x times, then you use the same logic to generate true or false with probability x/100 and 1 - x/100 and keep recording the number of true and false. Eventually either all true or all false, will have come up and then you can simply output the remaining true or false.

Coloring Houses

There are N houses in a row. Each house can be painted in either Red, Green or Blue color. The cost of coloring each house in each of the colors is different.

Find the color of each house such that no two adjacent house have the same color and the total cost of coloring all the houses is minimum.

Hint:The question intends to state that cost of painting any house in any color is different, so if cost of painting House 1 in Red is say, X then the cost of painting House 2 in red will some other value Y. It can be considered each house has different dimensions and hence cost of painting in each color is different, and the cost of paint for each house also varies 

Strategy:

This problem can be modeled as a Dynamic Programming problem. The DP equation can be given as

C[i][c] = H[c] + min(C[i-1][x]) 
                          x ∈ {Red, Blue, Green}
                          x ≠ c

Here C[i][c] is the cost of painting the row of houses ending at the i^th house such that the i^th house is painted in color 'c' and c is chosen such that the previous house is not in the same color. 

Food for Thought: An easier variant of the same problem, that can be solved using Greedy Approach will be when the cost of painting any house in any color is the same. In this case how will you paint the houses?

Two Rectangles overlap or not

Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.

Two overlapping rectangles. A rectangle can be defined by its upper left and lower right corner.

 Assume that the two rectangles are given as point (P1, P2) and (P3, P4) respectively. One direct way to attempt. How about asking yourself how the two rectangles cannot overlap each other? Two rectangles do not overlap when one is above/below, or to the left/right of the other rectangle.

The condition’s expression is:
! ( P2.y < P3.y || P1.y > P4.y || P2.x < P3.x || P1.x > P4.x )

Using De Morgan’s law, we can further simplify the above expression to:

( P2.y = P3.y && P1.y = P4.y && P2.x = P3.x && P1.x = P4.x )

Code:

/*

(P1,P2)=rect1,(P3,P4)=rect2 

 P1,P3-->topleft points

P2,p4-->bottomright points 

*/ 

#include<iostream>
using namespace std;

struct Point
{
  float x;
  float y;
};

struct Rect
{
  Point topLeft;
  Point bottomRight;
};

bool isIntersect(Rect rect1, Rect rect2)
{
  if (rect1.topLeft.x >= rect2.bottomRight.x 
      || rect1.bottomRight.x <= rect2.topLeft.x 
      || rect1.topLeft.y <= rect2.bottomRight.y 
      || rect1.bottomRight.y >= rect2.topLeft.y)
    return false;
    
  return true;
}