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.
 

Given an array of integers and a number N. [Consider array to be sorted]
Find out all pairs of numbers of the array whose sum is N.
Simply find out all integers a, b of array such that a + b = N


Solution:

Algorithm:

1. Take two variables that holds the value of First and Last index of array.
2. Loop while First < Last:

Now sum value stored in First and Last index of the array.

If sum is greater than N

decrease Last by 1.

If sum is less than N, 

increase First by 1.

If sum is equal to N, 

print values stored at First and Last index. 
Decrease Last by 1 and Increase First by 1.

This is quite intuitive after reading and this solution is taking advantage of Sorted Array.
 

Majority Element is an element of an array that occurs more than half the number of times in the array.Easy Problem: 
Assume that an integer array A[1..n] has a majority element and elements other than majority element are distinct. How to find majority element. What's the space and time complexity of the algorithm ?Hard Problem: 
Assume that an integer array A[1..n] has a majority element and elements other than majority element need NOT be distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Both easy and hard may be solved using the following solution in ~(n-1) comparisons.

Solution (HARD) :

This algorithm uses an observation that if we consider our array to be list of voters and array value is the candidate to whom they are voting, then majority element is the winning candidate.

Additionally, if all other candidates are merged to form one candidate then still it will fail to defeat the majority element candidate (hence the name majority element).

So we can think of it this way. Assuming a negative vote decrease the count of majority element then still the count of majority element would be atleast 1.

int majority_hard(int[] input, int n){

int element = input[0];
int votes = 1;

for(int i=1; i<n; i++){

if(input[i] == element)

votes++;

else if(votes > 0)

votes--;

else {

element = input[i];
votes = 1;

}

}
return element;

}

However, the easy problem may be solved using ~n/2 comparisons using the pigeon hole principle :

Solution (EASY) :

If the total size N is even then, the majority element must duplicate in consecutive positions in some pairs of positions. If N is odd, then it must either duplicate in consecutive positions or must be the last element.

int majority_easy(int[] input, int n){

for(int i=0; i<N; i+=2){

if(input[i] == input[i+1])

return input[i];

}

return input[N];

}

Try to study the solutions and practice writing compact and elegant code. You'll automatically get efficiency with elegance.


Courtesy: Vibhaj

Find second smallest element in an array A[1..N] of size N. (We would like to do in much less than 2N comparisons if possible).


Solution:

I suppose the method to solve is mentioned in Cormen and it takes n + log(n) - 2 comparisons. (Tournament style with saving elements that lost to minima; then searching for second minima in them)

Similar method is using Heap data structure to do it in n + log(n) comparisons. (Build heap in n and Min heapify in log(n))

The question does not end here as the above solutions use comparisons to get 2nd and in general kth minima. We can use other methods without comparisons (at the cost of space) to get kth minima.

I thought of using Trie data structure to get it done easily. We simply assume the maximum digits in the elements in the array and padd them with 0's at the beginning to make them D digits large. We insert each into D level trie and the pre-order traversal gives all elements in correct sorted order.

Bucket sort, Radix sort are other possibilities. Try to learn about these methods.


Courtsey: Vibhaj
 

This is today's problem :

Given an array of N integers (both positive and negative), find the sub-sequence with largest sum.

For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest sum is 10 (start index = 3, end index = 6)
{4 5 -1 2}


Solution :

A simple linear algorithm will work by keep track of the current subsequence sum. If that
sum ever drops below zero, that subsequence will not contribute to the subsequent maximal subsequence since it would reduce it by adding the negative sum.

#include<iostream>
using namespace std;
int main()
{
int input[10], i, sum = 0, start = -1, end = -1, current = -1, max = -1;//testing for an array of 10 elements
for(i =0;i<10;i++)
      cin>>input[i];
for(i=0; i<10; i++)
{
 sum += input[i];
 if(sum < 0)
 {
        sum = 0;
        current = i+1;
 }
 if(sum > max)
 {
        max = sum;
        start = current;
        end = i;
 }
}
cout << "Start : " << start << " End : " << end << endl<<"Elements are : ";
for(i = start;i <= end;i++)
cout<<input[i]<<" ";
return 0;
}

You are given a number N which will be large (within limits of machine representation of long integer)
You need to find the total trailing zeros in N! (factorial)
Give attention to time complexity. Reduce it as far as possible.

Eg, 
N = 6 
N! = 720
Count = 1 (trailing means to the end)



Solution:

Keep on dividing N by 5 repeatedly and add the quotient each time until number becomes 0. The sum of all the quotients will be the number of trailing zeros.
Code:

#include<iostream>
using namespace std;
int main()
{
int N;
cin>>N;
int count = 0;
while(N > 0)
{
    count += N/5;
    N = N/5;
}
cout<<count; 
return 0;
}

For beginners :

Implement Stack and Queue by yourself. Many of you have not done it yet. Implement all the primitive operations on Stack and Queue. Try to implement it without using an Array.

For others:

1. Implement a Stack using 2 Queues.
2. Implement a Queue using 2 Stacks. [Implementing any structure means all the primitive operations have to be performed].

Code it.


P.S. - Its not bad to be a beginner :)



Solution :


Basically in this problem, You need not to be efficient in terms of time and space complexity. You just need to think how this goal will be achieved. 
For Stack using 2 Queues basic idea is, 
For PUSH operation:
ENQUEUE all the elements in only one of the Queue [after first PUSH, insert into non-empty Queue] (using flag is an option or you may check this as a condition of emptiness).
For POP operation:
DEQUEUE all the elements except one from the non-empty Queue and ENQUEUE all of these De-queued elements of first Queue into the second one making first Queue empty.

Similarly for Queue using 2 Stacks. 

You have 25 horses and 5 tracks and you need to find out top 3 horses. What is the minimum number of races required to do this ?







p.s. - Answer will be posted after 2 days from respective questions. Although we're always open for discussion in comments :)






Solution:


For 1st question:
Group 25 horses in 5 groups:

A : A1, A2, A3, A4, A5 [Decreasing order of speeds]

B : B1, B2, B3, B4, B5

C : C1, C2, C3, C4, C5

D : D1, D2, D3, D4, D5

E : E1, E2, E3, E4, E5

Five races will have to take place for ranking in groups themselves.

One race for A1, B1, C1, D1, E1 for ranking of the groups.

Now A1>B1>C1>D1>E1

So A1 is the topper. We now need to find 2 more horses for 2nd and 3rd position.

Here is the key observation.

Selection by Elimination  [We need to find 2 more horses, if any horse is slower than 2 horses except A1 then it can not be included in the solution]

1. D1 and E1 can not be included in the solution as both of them are slower than B1 and C1

and hence their whole group is eliminated as they were best from their groups.

2. A4, A5 can not be included in the solution as they are slower than A2 and A3.
3. B3, B4, B5 can not be included in the solution as they are slower than B1 and B2.

4. C2, C3, C4, C5 can not be included in the solution as they are slower than C1 which is slower than B1 itself.

So we are now having only 5 possible horses for 2 positions which can be found out in just one race. [A2, A3, B1, B2, C1] Top 2 of this group will be ranked 2nd and 3rd after A1.