There are 5 thieves. They are all numbered one to five. They have 500 pieces of gold which need to be distributed among themselves. First the number 1 distributes it and after that a voting is done : if he gets majority votes his distribution is carried out else he is killed, if the votes are equal, then also distribution is done his way. If he is killed then next numbered person does the distribution and this goes on till number 5. Each thief values his life more than the gold. So how does the first thief distribute gold to get maximum and to not get killed also ? Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: First of all try to understand the problem. Hit again for hints. Hints: Think first for small numbers and then generalize the pattern. Solution: Observing the pattern: For 2 thieves, the proposal would be (500, 0) as even if second disagrees, it does not matter. For 3 thieves, the proposal would be (499, 0, 1). In this case, second will disagree but third will agree because if he disagrees, then 2nd will propose next as (500, 0) and he would get nothing. So on for 5 thieves, the proposal is (498, 0, 1, 0, 1)

Two friends decide to meet at a cafe between 11 am and 12 pm i.e. one hour. They also decide that the one who reaches before the other waits for 5 minutes and if the other does not arrive he leaves. What is the probability of their meeting ? Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Just imagine dude :P. Hit again for hints. Hints: Are you not able to solve this? or You want to check the solution. Hit again for Solution Solution: The probability is found using areas. The colored area represents the successful meeting since the difference between x and y co-ordinates of any point in the colored area is less than or equal to 5 on absolute value. Enlarge the image by clicking on it to see the answer

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. Count of 1 is not indicated. Write a program to find RLE of given string. Eg. input = "aabbbcddeef" RLE = "a2b3cd2e2f" input = "aaabbcddeeeef" RLE = "a3b2cd2e4f" Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remark dude :P. Hit again for hints. Hints: This is an intelligent problem, try to solve it without a hint. Hit again for Solution Solution: We simply use a switch while checking each character in input and count them if equal and print the count if count is greater than one. Complexity: 1. TIme : O(N) 2. Space : O(1) Code: void rle_encode(char[] input, int N, char[] output){ int index = 0, count = 1; char last = input[0]; for(int i=1; input[i]; i++){ if(last == input[i]){ count++; } else { output[index++] = last; if(count > 1){ output[index++] = count + '0'; count = 1; } last = input[i]; } } output[index++] = last; if(count > 1){ output[index++] = count + '0'; } }

You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest. You have a simple two-armed scale, and are permitted three weighing. Can you identify the odd ball, and determine whether it is heavier or lighter than the rest ? Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remark dude :P. Hit again for hints. Hints: Its a puzzle to puzzle you. No hints will be provided. Hit again for solution. Solution: Due to some problem while formatting the answer, I was unable to write here. So please find the image of the answer for this question.

Given an integer N. Devise an algorithm to find out the smallest integer greater than N having the same number of bits set as that of N. (When a bit is 1, we say it is set) Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Use concepts of bit manipulation. Hit again for hints. Hints: Try to find out general formula for number having same number of set bits. Hit again for solution Solution: Suppose N has last x bits 0 and then y bits 1, then in general the next number having same number of set bits is given by N + 2^(y-1) + 2^x - 1 -> Now 2^x is given by N&-N -> Suppose M = N + 2^x -> Similarly 2^(x+y) is given by M&-M -> So we get 2^(y-1) by (2^(x+y)/2^x >> 1) Complexity : Time : O(1) Space : O(1) Code : int next_equal_setbits(int N){ int K1 = N & -N; int M = N + K1; int K2 = M & -M; return K2 + ((K2/K1)>>1) - 1; }

Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N). Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Find all the combinations first [:)]. I hope this was obvious. [:P] Hit again for hints. Hints: list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed. Hit again for solution. Solution: We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed. Then for each combination we permute them using another recursive procedure Complexity : Time : O(N!) Space : O(N!) when storing results; O(1) if directly output the result Code : void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } void select(char *input, int start, int N, char *selection, int length, int K, stack<string> &combinations){ if(start <= N){ if(length == K){ selection[length] = '\0'; combinations.push(string(selection)); } else { select(input, start + 1, N, selection, length, K, combinations); selection[length] = input[start]; select(input, start + 1, N, selection, length + 1, K, combinations); } } } void permute(char *input, int index, int N, stack<string> &permutations) { if (index == N) permutations.push(string(input)); else { for (int i = index; i < N; i++) { swap(input + index, input + i); permute(input, index + 1, N, permutations); swap(input + index, input + i); } } } void all_permutations(char *input, int K, stack<string> &permutations){ int N = strlen(input); stack<string> combinations; char *selection = new char[K+1]; char *temp = new char[K+1]; select(input, 0, N, selection, 0, K, combinations); while(!combinations.empty()){ strcpy(temp, combinations.top().c_str()); permute(temp, 0, K, permutations); combinations.pop(); } }

Give a method to swap two numbers without using additional memory. Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remarks buddy, it's an easy one :P Hints: Do you really think this needs a hint? If you can't solve it, you can't. Solution: We may use addition/subtraction or XOR to achieve this. XOR does not cause overflows and hence is superior. Complexity: Time : O(1) Space : O(1) void swap_xor(int &num1, int &num2){ num1 ^= num2; num2 ^= num1; num1 ^= num2; } void swap(int &num1, int &num2){ num1 = num1 + num2; num2 = num1 - num2; num1 = num1 - num2; }

Give a fast method to multiply a number by 7. Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Remember when you were studying maths in junior high-school Hints: In how many ways can you multiply a number by 7? Solution: We multiply by 7 by first multiplying by 8 and subtracting the number from the result. Multiplication by 8 is equivalent to shifting left 3 bits. Complexity: Time : O(1) Space : O(1) Code: int multiply_7(int N){ return (N << 3) - N; }

Given 2D array with integers sorted both horizontally and vertically. Devise an efficient algorithm to search for key in the 2D array. What is the complexity ?  Eg.      1 4 7 13      2 5 9 15      3 6 10 16 Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Assume the row is sorted from left to right and column from top to bottom so that the least number is at top-left. Hints: While searching just look for the relevant data for existence of the required key. i.e. Think in which area there is a possibility of finding the key. Solution: Two solutions exists : First one is : Start from left-bottom While within boundary If key found print and exit If key is smaller move up else move right Second one : Let M < N (otherwise interchange the usage below) for each M 1D arrays do binary search in O(log N) Complexity: First : Time : O(M + N) Space : O(1) Second : Time : O(M log N) M < N Space : O(1) The advantage of second method is seen when M << N where second method degenerates to binary search whereas first method degenerates to sequential search. Code: /** * M rows * N columns * (row, col) position of searched key if successful **/ Method 1: bool search_2D(int *input, int M, int N, int key, int *row, int *col){ *row = M-1; *col = 0; while(*row > 0 && *col < N){ int current = *(input + N*(*row) + (*col)); if(key == current) return true; else if(key < current) (*row)--; else (*col)++; } return false; } Method 2: bool search_2D(int *input, int M, int N, int key, int *row, int *col){ int increment = 1, total_rows = M, total_cols = N; if(M > N){ increment = N; total_rows = N; total_cols = M; } for(*row =0; *row < total_rows; i++){ *col = 0; if(search_1D(input + *row, total_cols, key, col, increment)){ return true; } } return false; } bool search_1D(int *input, int N, int key, int *index, int increment){ int low = 0, high = N-1; while(low <= high){ *index = (low + high)/2; int value = *(input + (*index)*(increment)); if(value == key) return true; else if (value < key) low = *index + 1; else high = *index - 1; } return false; }

Assume you have infinite memory. Design an algorithm using stacks that can find the minimum and maximum at any point while reading an infinite sequence of numbers in least possible time. Eg. 5, 9, 2, 35, 23, 1, ... After 3rd element, the algorithm would tell min = 2, max = 9 After 6th element, algorithm would tell min = 1, max = 35 Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: There is an unlimited space. Hints: Use 3 stacks. Click again for solution. Solution: 1. 1st stack will be the main stack in which we are pushing all elements 2. 2nd stack will contain maximum elements up to that point 3. 3rd stack will contain minimum elements up to that point. So range can also be found in O(1) time, by popping from 2nd stack & 3rd stack and taking their difference. Complexities : Time : O(1) Space : Unlimited Code : template <class T> class range_stack<T> { private : stack<T> main, min, max; public : int push(T value){ main.push(value); if(main.empty()){ min.push(value); max.push(value); } else { if(min.top() > value) min.push(value); else min.push(min.top()); if(max.top() < value) max.push(value); else max.push(max.top()); } } T pop(){ T tmp = main.top(); main.pop(); min.pop(); max.pop(); return tmp; } T range(){ return max.top() - min.top(); } }

A high school has a strange principal. On the first day, he has his students perform an odd opening day ceremony:There are one thousand lockers and one thousand students in the school. The principal asks the first student to go to every locker and open it. Then he has the second student go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth student does this to every fourth locker, and so on. After the process is completed with the thousandth student, how many lockers are open ?

You are given a weighing machine. Find the minimum number of denominations of weights you need to measure any N kgs given that you may use the denominations on any side of the weighing machine.

Devise an algorithm to find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive). Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remarks for this one. Hints: No hints will be provided for this problem. Think more buddy, Yes! you can. Solution: The solution is using bitmaps (arrays of bits) 1. Initialization will take O(N) but checking for existence will be done in O(1) 2. Bitmap array will be char[M/8] since a char is 8 bits long Complexities : Time : O(N) in initialization, O(1) in access Space : O(M) Code : // init() is called once for all numbers in list one by one to initialize the bitmap void init(int[] bitmap, int M, int num){ int base = num/8; int offset = 1 << (n%8); bitmap[base] |= offset; } bool exists(int[] bitmap, int M, int num){ int base = num/8; int offset = 1 << (n%8); return (bitmap[base] & offset); }

Devise an algorithm to find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive). Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj, Gurpreet & Ankit Remarks: Use concepts of bit manipulation. Check for right-most bit. Hints: The rightmost bit may be set to zero by (N & N-1), so we do it twice and if the number becomes zero, it means it had 2 bits as 1 before thus having the required form 2^x + 2^y. Also consider the case where x = y separately. Solution: The rightmost bit may be set to zero by (N & N-1), so we do it twice and if the number becomes zero, it means it had 2 bits as 1 before thus having the required form 2^x + 2^y. When x = y: The number of bits set to 1 in binary representation of N is one. Applying N=(N & N-1), once will make N=0. Now, one cannot apply N= (N & N-1) again, as this will change the value of N ( ! = 0 ). Hence, one must check if after using the formula N=(N & N-1) ,N has become 0 or not. Another test case is when N=1 , 0 . In that case N&(N-1) = 0 and it doesnt mean x=y. So in our algorithm the first step must be modified as : if(N>1), use the formula N=(N& (N-1) ) and check if N=0. Hence, We consider the case when x=y, so only one bit is set. Also we check if number is not 0 or 1 initially for which answer is false. bool check_form(int N){ if(N < 2) return false; N = N & (N-1); if(!N) return true; return !(N & (N-1)); }

Fint out the matching socks: Michael have ten pairs of black socks, eight pairs of white socks and seven pairs of green socks. Everything is mixed in a draw. As there is no light he were not able to identify the color of the socks. How many of the socks did he want to take to match one pair ? p.s. - For Remarks please hit the question name once, given in the question itself. For Hint, hit it twice and for the solution, hit it thrice. Remarks: There is no difference between left and right socks. Hints: The principle used is the Pigeon Hole Principle. Try to learn more about it from Wikipedia, since many clever solutions result from clever application of the principle. Solution: The answer is 4 since in worst case all 3 socks taken first will be different color then the 4th one would be repetition. However if we consider a left sock to be different from right one, then at least 10 + 8 + 7 + 1 = 26 socks are needed.

A blind search (also called an uninformed search) is a search that has no information about its domain. The only thing that a blind search can do is distinguish a non-goal state from a goal state.

For more read here about Blind Search

Code:
 

#include<iostream>
#include<cstdlib>
#include<map>
#define MAX 50
using namespace std;

map <int,int> mp;

void printpath(int start)
{
 if (mp[start]==-1)
 {
  cout<<start<<endl;
  return;
 }
 else
 {
  cout<<start<<"  ";
  printpath(mp[start]);
 } 
}
int main()
{ 
 int n,adj[MAX][MAX],v[MAX];
 int rnd,start,end,temp;
 bool solve=false;
 cout<<"enter the no of nodes : ";
 cin>>n;
 cout<<"enter the adjacency matrix : ";
 for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
   cin>>adj[i][j];
 for(int i=0;i<n;i++)
  v[i]=0;
 cout<<"enter the start and end node: ";
 cin>>start>>end;
 temp=start;
 v[start]=1;
 mp[end]=-1;
 while(!solve)
 {
  rnd=random()%n;
  //cout<<"reached here";
  //cout<<"  "<<rnd<<endl; 
  if(rnd==end && adj[start][rnd]==1)
  {
   mp[start]=rnd;
   solve=true;
  }
  else
  {
   if(adj[start][rnd]==1 && v[rnd]==0)
   {
    mp[start]=rnd;
    //cout<<mp[start]<<endl;
    v[rnd]=1;
    start=rnd;
   }
   else
    continue;
  }
 } 
 printpath(temp);
 return 0;
}

In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution. If the change produces a better solution, an incremental change is made to the new solution, repeating until no further improvements can be found.

For example, hill climbing can be applied to the Traveling Salesman Problem. It is easy to find an initial solution that visits all the cities but will be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much shorter route is likely to be obtained.

Read more about Hill Climbing Problem

Code:

#include<iostream>
#include<cstdio>
using namespace std;
int calcCost(int arr[],int N){
 int c=0;
 for(int i=0;i<N;i++){
  for(int j=i+1;j<N;j++) if(arr[j]<arr[i]) c++;
 }
 return c;
}

void swap(int arr[],int i,int j){
 int tmp=arr[i];
 arr[i]=arr[j];
 arr[j]=tmp;
}

int main(){
 int N;
 scanf("%d",&N);
 int arr[N];
 for(int i=0;i<N;i++) scanf("%d",&arr[i]);
 int bestCost=calcCost(arr,N),newCost,swaps=0;;
 while(bestCost>0){
  for(int i=0;i<N-1;i++){
   swap(arr,i,i+1);
   newCost=calcCost(arr,N);
   if(bestCost>newCost){
    printf("After swap %d: \n",++swaps);
    for(int i=0;i<N;i++) printf("%d ",arr[i]);
    printf("\n");
    bestCost=newCost;
   }
   else swap(arr,i,i+1);
  }
 }
 printf("Final Ans\n");
 for(int i=0;i<N;i++) printf("%d ",arr[i]);
 printf("\n");
 return 0;
}

Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.

For more please refer Minimax

Code:

#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;

vector <int> vec;

int large(int a,int b)
{
 if(a>b)
  return a;
 else
  return b;
}

int small(int a,int b)
{
 if(a>b)
  return b;
 else 
  return a;
}

void max_min(int p,int q,int *max,int *min)
{
 if(p==q)
 {
  *max=vec[p];
  *min=vec[q];
 }
 
 else if(p==(q-1))
 {
  if(vec[p]>vec[q])
  {
   *max=vec[p];
   *min=vec[q];
  }
  else
  {
   *max=vec[q];
   *min=vec[p];
  }
 }
 
 else
 {
  int m=(p+q)/2;
  int max1,max2,min1,min2;
  
  max_min(p,m,&max1,&min1);
  max_min(m+1,q,&max2,&min2);
  *max=large(max1,max2);
  *min=small(min1,min2);
 }
}

int main()
{
 int a,n=0;
 int min=0,max=0;
 
 cout<<"enter the elements (enter -1 to quit) :  ";
 while(1)
 {
  cin>>a;
  if(a==-1)
   break;
  else
  {
   vec.push_back(a);
   n++;
  }
 }
 max_min(0,n-1,&max,&min);
 
 cout<<"MAX = "<<max<<"\t"<<"MIN = "<<min<<endl;
 
 return 0;
}

Random Selection from a Linked List 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.  Conditions :  Use random number function rand() that returns a number between 0 and 1. It must be done in O(N) time p.s. - For Remarks please hit the question name once, given in the question itself. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. For hints, please hit the question name again. Hints: No hints. For the solution, please hit the question name again. Solution: 1. Take 2 arrays R[K] and Num[K] 2. For each element in sorted array read one by one and do :      1. Generate a random number r.      2. If R is not full, insert r into R and element into Num array else replace r with highest random number in R and insert current element into corresponding index in Num array (Note that we want to keep the least K random numbers and corresponding elements in list) 3. Print Num[] Complexities : Time : O(N) Space : O(K) Code : void random_selection(int[] input, int N, int K){ int number[K]; double random[K]; int count = 0; for(int i=0; i<N; i++){ double r = rand(); if(r < number[count-1]){ index = insert(random, K, &count, r); number[index] = input[index]; } } for(int i=0; i<K; i++){ printf("%d ", number[i]); } } int insert(double *list, int K, int *count, double entry){ if(*count == K-1){ (*count)--; } int i = *count; while(*(list+i) > entry){ *(list + i + 1) = *(list + 1); i--; } *(list + i + 1) = entry; (*count)++; return i+1; }

Can you calculate properly?: Three people check into a hotel. They pay $30 to the manager, and go to their room. The manager finds out that the room rate is $25 and gives $5 to the bellboy to return. On the way to the room the bellboy reasons that $5 would be difficult to share among three people so he pockets $2 and gives $1 to each person. Now each person paid $10 and got back $1. So they paid $9 each, totaling $27. The bellboy has $2, totaling $29. Where is the remaining dollar ?  p.s. - For Remarks please hit the question name once, given in the question itself. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. For hints, please hit the puzzle name again. Hints: No hints. For the solution, please hit the puzzle name again. Solution: True its just a slip of tongue. 3 rooms money paid = $27 = Manager $25 + bellboy $2. Plus $1 to each of them.

Following are the questions asked to one of the successful candidates in Amazon Interview :-

Round 1: 
 

     1. A Twin Prime number is a prime number which differs from other prime number by two. eg    (5,7), (11,13), (17,19), (29,31), (41,43), (59,61)........ Prove that number between twin primes is divisible by 6. 

     2. You have a binary tree with non-negative numeric values stored in its nodes, you need to find out the maximum possible sum of all the nodes. Selection of nodes for the sum follows following constraint: 

If you have selected any node for the sum, you can not select its immediate parent and its children for sum.

Hint : Answer does not include level order traversal for obvious reasons.
 

     3. Find all permutations of a string.


 

Round 2:

     1. For a given company, you need to maintain the stock prices (closing price of a day) for last "m" years. [By "m" years he meant, if the year say increases by 1 then database has data of "(m+1)" years, not that the data for "m"th year gets deleted]

Now suggest a data-structure for holding the stock prices of all the companies such that 

(a). The stock price (closing price of the day) of a given company on a given date can be searched easily.   

(b). The stock prices for all the companies can be printed for a given date. 

(By all companies he meant if a company say starts today, its data will also get added to the database and if a company gets closed today its data won't be deleted). 

     2. For compiling a java program you need a list of JARs as libraries but the given JARs have internal dependencies between them: 

eg. JAR1 can only be loaded after loading JAR2 and JAR3. JAR2 is also dependent on JAR3 and JAR4. 

Now write a program to load all the JAR files following their dependency rules.


 

 
Round 3:

     1. You are given an array, infinity on both the sides along with the current position of the pointer [Think of magnetic tape and the head of the reading machine].
Now the data stored in the array can be of length either of 1 byte or 2 bytes.
If the data is of 1 byte, then 1st bit will be 0.
If the data is of 2 bytes, 1st bit of 1st byte the data will be 1 and 1st bit of 2nd byte will be having a Don't Care condition. 
You are given the current position of pointer as the start of a new data. Find the starting position of data, previous to the current data. In other words, find the previous data.

Round 4:

     1. Database Question: 
The main aim was to ask how is a database implemented internally. [Answer : using B and B+ trees]


     2. Synchronization of threads:
You have an account and deposit & withdraw operations should be mutually exclusive, but the ReadAccountValue should not be blocked even if a thread is using deposit or withdraw method.
Account {
       Deposit();
       Withdraw();
        ReadAccountValue(); 
} 
For ReadAccountValue method, do not return an illegal value. (say a thread uses ReadAccountValue while other thread uses Withdraw(), do not return the illegal previous value)

p.s. - For any kind of confusion, don't hesitate in asking.

Devise an algorithm :
There is an array A[N] of N numbers. Find a Product Array P[N] of an array A[N] which is defined such that for all i<N, P[i] = (product of all elements of A except A[i]).
For example, P[0] will be multiplication of A[1] to A[N-1] and P[1] will be multiplication of A[0] and from A[2] to A[N-1].
Solve this without using division operator and in O(N) time.


Solution :

1. Calculate backward product in product array P[i] = Product(A[i+1]*...*A[N])
2. Take a variable p=1
3. For each element of input, multiply it by p and multiply P[i] by p

Complexities :

• Time : O(N)
• Space : O(1)

Code : 

void product_array(int[] input, int[] product, int N){
product[N-1] = 1;

for(int i=N-1; i>-1; i--){
product[i] = product[i+1]*input[i+1];
}

int p = 1;
for(int i=0; i<N; i++){
if(i > 0){
p *= input[i-1];
}

product[i] *= p;
}
}

Courtesy : Vibhaj

100 passengers are boarding an airplane with 100 seats.
Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order.
However, the first passenger lost his ticket so he just took a random seat.
For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat.
What's the probability that the last passenger would sit on his own seat ?


Solution:

Let us say that everyone is sitting except for the 100th passenger. Consider where can he sit - he can sit in either seat numbered 100 or 1. There cannot be any other seat vacant for him.

We can prove this using contradiction. Lets say that a seat numbered n=55 is vacant for 100th passenger. Since passenger 55 came earlier he should be sitting in his seat if its vacant. So seat 55 cant be vacant. This logic can be applied to all seats except for seat 1 and 100.

So all permutations of the seating arrangement would result in last person sitting in either seat 1 or seat 100. Both the options are equally likely.

So answer = 1/2. 


Courtesy : Vibhaj  

Given the heads of two linked lists, find whether they have any common node. If yes, find the common node.
Try to solve it as elegantly as possible.


Solution:

1. Subtract the length of smaller list from the larger one.
2. Move a pointer ahead on larger list by the difference of lengths.
3. Now put a pointer on head of smaller list.
4. More two pointers together.
5. The point at which they meet is the point where they short.

Code:
 

Node *getShortedNode(Node *list1, Node *list2){

int d = length(list1) - length(list2);

if(d < 0){
   d = d * (-1);
   Node *tmp = list1;
   list1 = list2;
   list2 = tmp;
}

Node *ptr1 = list1;
for(int i=0; i<d; i++)
{
   ptr1=ptr->next;
}

Node *ptr2 = list2;
while(ptr1 != NULL){
 if(ptr1 == ptr2)
   break;
 ptr1 = ptr1->next;
 ptr2 = ptr2->next;
}
return ptr1;
}

int length(Node *list){
int count = 0;
while(list != NULL){
 list = list->next;
 count++;
}
return count;
}

Following are the interview questions asked by Facebook to one of the successful candidates Mr. Saket Jalan, CSE, IT-BHU as told by him :

Complete process was of 5 technical rounds and then 1 HR round:

Online Round Question

Given a dictionary consisting of n 3 letter words, with n<100. We need to compute all possible 3*3 grids such that 3 letter words lying on each row, each column and each diagonal is in dictionary. 

Interview Round 1:

write a code that prints the tree level wise. Then he asked to reduce space in cost of time.

Interview Round 2:

Given n distinct numbers from 1 to n. Write a code that prints all the k-element subsets. for eg: for n=4, k=2: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4). Then I was asked to write the equation of its complexity. 

Interview Round 3:

It was elimination round, everyone was given below Q and had to write code within 45 minutes along with test cases.
Given a structure, with data members as string and number. A list consists of structure data, sorted in dictionary order by strings. Now, write a function, that takes a prefix, and returns all the numbers corresponding to the string that have this prefix in dictionary. Also write the test cases.
They judged it based upon coding style, time and space complexity.

Interview Round 4:

Last round. In a game a player can score either 2,3 or 7 runs. A player has just entered the ground and he sees "score" on the board. Write a program that returns number of ways in which this score can be obtained. eg: 10 can be obtained by (3+7), (7+3), (2+2+2+2+2), (2+2+3+3), (2+3+2+3), (2+3+3+2), (3+2+2+3), (3+2+3+2), (3+3+2+2)
Then he asked to reduce space complexity. 

HR:Usual Questions like why Facebook? why not other companies? and many things from CV.

Almost every interviewer asked about some of my projects from the CV. and yes STL was allowed except in round 3.