DirectI Coding Test – IITB

The test was for 1 hour. It consisted of 2 coding questions

Question 1

Given N,O where N=No. of digits that can be displayed on calculator and O=No. of multiplication to be performed. The numbers used for the multiplication can be from {2,3,…8,9} 
2<=N<=8 
2<=O<=30 
Write a function that will return the largest number that can be obtained after O multiplication. 
Example
N=2, O=3 
The function should return 98, since the maximum no. generated after 3 multiplications 2*7*7. 

function should return -1 for error or invalid.

Question 2

Amazon Test – IITB

The test was for 90 minutes.
It consisted of 20 MCQs and 2 Coding Question

Coding Questions

Question 1
Minimum Coin Change Problem
Input
Vector of coin Denomination
Amount to be Obtained

Output
Minimum number of coins required. -1 if not possible

Question 2
Print all anagrams from the array of strings.
Input
5
aab baa aba cd dc

Output
aab baa aba
cd dc

Microsoft Test – IITB

There were 2 rounds.

1st round consisted of MCQs on programming, OS, DB, etc
2nd round consisted of 2 Coding Questions. There was some problem and hence the 2nd round was conducted again

Coding Questions

1. Reversing a linked list
2. Some manipulations on 2D array
3. Deleting every nth node in a linked list
4. Checking for palindrome.

DirectI Coding Test – IITD

The test was for 1 hour. It consisted of 2 coding questions

Question 1

You were given a Binary Tree (not necessarily a Binary Search Tree) to play with, say T. T had some special properties

Each internal node in T had exactly 2 children Each internal node in T was represented by an uppercase English alphabet (A-Z) Each leaf node in T was represented by a lowercase English alphabet (a-z) You were told remember T as long as you could. Hence, you memorised the string formed by traversing T in post-order. You used something similar to the pseudocode below

toPostOrderString (node)
if node is leaf
return node.value
else
T = “”
T = T + toPostOrderString(node.left)
T = T + toPostOrderString(node.right)
T = T + node.value
return T

Now, time has come to use that string again. The Eye has contacted you. Yes, the secret organisation mentioned in “Now you see me” ( don’t tell anyone they are real !! )

You remember the string you memorized back then. You must reconstruct the binary tree T. You are also given a string A. All the characters of A are uppercase English alphabets. Let us assume that T has L leaves. Then, there will be exactly L paths from the root to the leaves – 1 unique path to each leaf.

You have to tell The Eye the number of paths out of L, on which, A exists as a sub-sequence. Look at the explanation for the Sample Case 1 for clarity.

You have to implement the method explodePaths in the code. explodePaths is passed the following parameters, respectively
N, the number of nodes in T
S, the string representation of the post-order traversal of T.
Of course, the length of S will be equal to N.
K, the length of the string A
A, the string you must find in the paths from the root of T, to the leaves in T.

Note
It is not necessary that T is balanced. But, each internal node always has exactly 2 children. It is possible that both those children are internal nodes also. It is possible that only one of those children is an internal node. For the given string S, because of the constraint that each internal node has exactly 2 children, you will always be able to determine the tree T, uniquely. It is not necessary that all characters in T are unique. There may be several nodes with the same value. In this problem statement, by sub-sequence we mean not necessarily contiguous. This is different from a sub-string. Do not print the answer in explodePaths. Just return the value. The code-template interviewstreet provides does the input and output itself.

Consider the following tree
A
/  \
t    B
/  \
/      \
B      A
/  \     /  \
x   y  a    b

This tree is given in Sample Case 1 as
N = 9
S = “txyBabABA”
K = 2
A = “AA”
Now, there are 5 leaf nodes, and hence, 5 paths from the root to leaves : 1 for each leaf.

– A-t
– A-B-B-x
– A-B-B-y
– A-B-A-a
– A-B-A-b
Out of these 5 paths, you have to find the number of paths, on which “AA” exists as a sub-sequence. Of course, there are only 2 such paths

– A-B-A-a – A-B-A-b Hence the expected answer is 2.

In the same T above
The answer for A = “BB”, is 2
The answer for A = “BA”, is 2
The answer for A = “AB”, is 4
The answer for K = 1 and A = “A”, is 5
The answer for K = 1 and A = “B”, is 4

Constraints
N ≤ 10000 K ≤ 100.
The expected time complexity of the algorithm is O(N).

 

Question 2

It is the IPL auction time.
Royal Challengers team management had prepared a set of X top quality players among the marquee list of the auction. Given the monetary constraints they would not be able to bid for all of them. Though the natural way of handling this was based on cricketing abilities of the players the management was put in a fix because of a promotional campaign run by Royal Challenege Mineral Water – the main sponsors of the team jersey.

As per the campaign the top Y consumers of Royal Challenge Mineral Water were selected as an esteemed set of fans for their team and each one of them got a chance to give their preferred set of players among the X chosen by the team management. What has put the team management in a fix is that they need to bid for at least one player in each of the fans preference list. Though the bidding strategy changes a lot at real time, the team management wants to find minimum number of players among X that they should bid, such that each fan is satisfied (i.e., at least one player from their preference list is picked).

Help the team management with this and get a chance to interview with them for a role of computer based sports analyst. To stop you from using your bias, the names of players are replaced by identifiers.

You have to finish the implementation of the function minimumStars. The input to minimumStars comprises of
numberOfPlayers – the number of players that the team management short listed
numberOfFans – the number of fans whose preference must be met
fansPreferences – an array of numberOfFans strings with numberOfPlayers characters in each string.
The jth character in the ith string is 1 if the jth player is in the ith player’s preference list, or 0 otherwise.

The function must return minimum number of players that must be selected such that for each fan, at least one of his preferred player is selected. It is possible that some fan has sneaked in a preference where he has not preferred any player. It is not possible to satisfy this fan. If it is not possible to satisfy any one of the fans, the function should return -1.

Constraints
numberOfPlayers <= 10
numberOfFans <= 100

Your code is considered correct only if you pass all Test Cases

Sample Case 1
Input
numberOfPlayers = 3
numberOfFans = 3
fansPreferences = { “110”, “001”, “011” }

Output
2
Assuming everything is 1-indexed, selecting player 1 and player 2 would appease fan 1 and fan 3, but none of the favourites of fan 2 would have been present.

Sample Case 2
Input
numberOfPlayers = 5
numberOfFans = 3
fansPreferences = { “10000”, “00011”, “01100” }

Output
3

The expected complexity for the solution is O( (numberOfFans) * 2^(numberOfPlayers) ).

LinkedIn Coding Test – IITD

The test was for 2 hours. It consisted of 3 coding questions

Question 1
There are N steps and given another input X i.e. you can climb 1,2,3….X steps at a time. How many number of ways can you reach the top stair.
For example, given n = 3, x = 4
you can go 1,1,1 or 1,2 or 2,1 or 0,3 etc. So, it’s should be 4.
Input
N and X
Output
Number of ways can you reach the top stair

Question 2
Given a graph G, find the diameter of the graph.

Question 3
Was related to intervals. Will update it soon

LinkedIn Coding Test – IITB

The test was for 2 hours. It consisted of 3 coding questions

Question 1
Given N rectangles, find the area of their union.
Input
N rectangles whose sides are parallel to x-y axis
Top-right and bottom-left coordinates of the rectangle are given
Output
Area of the union of these rectangles
Constraints
1 < N < 50000

Question 2
Given 2 cups of volume m and n, get a volume of l using these operations:
1.  Emptying any of the cups
2. Refilling any of the cups
3. Transferring the contents of 1 cup to other
Input
m, n and l
Output
Minimum number of operations required to do this. -1 if not possible
Constraints
1 < m,n,l < 2000

Question 3
Find the number of triplets (a, b, c) such that 1 <= a <= b <= c <= N and a^2 + b^2 + c^2 = N.
Input
N
Output
Number of Triplets
Constraints
1 < N < 10^8

Google Test Questions

Google’s test was a pen and paper test. It comprised of 20 MCQs and 1 coding question

Section A

1. Quick-sort is run on two inputs shown below to sort in ascending order
   (i) 1,2,3, ….,n
   (ii) n, n – 1, n – 2, …., 2, 1
   Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
   a) C1 < C2
   b) C1 > C2
   c) C1 = C2
   d) We cannot say anything for arbitrary n
2. We are given a set X = {x1, x2, …, xn} where xi = 2^i. A sample S (which is a subset of X) is drawn by selecting each xi independently with probability pi = 1/2. The expected value of the smallest number in sample S is:
   a) 1 / n
   b) 2
   c) sqrt(n)
   d) n
3. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
   a) R is NP-complete
   b) R is NP-hard
   c) Q is NP-complete
   d) Q is NP-hard
4. For any string s ∈ (0 + 1)*, let d(s) denote the decimal value of s (eg: d(101) = 5, d(011) = 3). Let L = {s ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 = 4}. Which of the following statements is true?
   a) L is recursively enumerable, but not recursive
   b) L is is recursive, but not context-free
   c) L is context-free, but not regular
   d) L is regular
5. Common data for questions 5 and 6
   The 2n vertices of a graph G corresponds to all subsets of a set of size n. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly 2 elementThe number of vertices of degree zero in G is:
   a) 1
   b) n
   c) 2n – 1
   d) None
6.  The number of connected components in G is:
   a) 2n
   b) n + 2
   c) n C 2
   d) None
7. There are 5 nested loops written as follows,
   int counter = 0;
   for (int loop_1=0; loop_1 < 10; loop_1++) {
        for (int loop_2=loop_1 + 1; loop_2 < 10; loop_2++) {
             for (int loop_3=loop_2 + 1; loop_3 < 10; loop_3++) {
                  for (int loop_4=loop_3 + 1; loop_4 < 10; loop_4++) {
                       for (int loop_5=loop_4 + 1; loop_5 < 10; loop_5++) {
                                counter++;
                       }
                  }
              }
         }
   }
   What will be the value of counter in the end (after all the loops finished running)?
   a) 15C5
   b) 14C5
   c) 10C5
   d) 10 * 9 * 8 * 7 * 6 * 5
8. The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:
   void enter_CS(X) {
   while(test-and-set(X));
   }
   void leave_CS(X) {
   x=0;
   }
   In the above solution , X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:
   1. The above solution to CS problem is deadlock free
   2. The solution is not starvation free
   3. The processes enter CS in FIFO order
   4. More than one process can enter CS at the same timeWhich of the above statements is TRUE
   a) 1
   b) 1 and 2
   c) 1 and 3
   d) 2 and 4
9. The following ‘C’ code prints:
   void f(char *x) {
   x++;
   *x = ‘a’;
   }int main() {
   char *str = “hello”;
   f(str);
   printf(“%s”, str);
   }

   a) hello
   b) allo
   c) hallo
   d) empty string

10. An insurance company issues a policy on a small boat under the following conditions:
    The replacement cost of $5000 will be paid for a total loss. If it is not a total loss, but the damage is more than $2000, then $1500 will be paid. Nothing will be paid for damage costing $2000 or less and of course nothing is paid out if there is no damage. The company estimates the probability of the first three events as .02, .10, and .30 respectively. The amount the company should charge for the policy if it wishes to make a profit of $50 per policy on average is:
    a) $250
    b) $201
    c) $300
    d) $1200
11. We are given an array A with 8 distinct elements. Arrays B and C have 5 and 3 elements respectively and they are populated with elements from A. (The union of elements in B and C give the elements in A).In how many ways can the arrays B & C be populated such that both B and C have elements in sorted (ascending) order.
    a) 56
    b) 128
    c) 256
    d) None
12. Increasing the RAM of a computer typically improves performance because:
    a) Virtual memory increases
    b) Larger RAMs are faster
    c) Fewer segmentation faults occur
    d) Fewer page faults occur
13. Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.
    Process P:
    while (1) {
    W:
    print ‘0’;
    print ‘0’;
    X:
    }Process Q:
    while (1) {
    Y:
    print ‘1’
    print ‘1’
    Z:
    }
    Synchronization statements can be inserted only at points W, X, Y and Z. V() increments the semaphore, whereas P() decrements it. Which of the following will always lead to an output staring with ‘001100110011’ ?
    a) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
    b) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0
    c) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
    d) P(S) at W, V(S) at X, p(T) at Y, V(T) at Z, S initially 1, and T initially 0
14. Which of the following statements are true?I Shortest remaining time first scheduling may cause starvation
    II Preemptive scheduling may cause starvation
    III Round robin is better than first come first serve in terms of response time

    a) I only
    b) I and III only
    c) II and III only
    d) I, II and III

15.  A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds) respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will approximately be:
    a) 120 us (micro seconds)
    b) 165 us
    c) 180 us
    d) 175 us
16. Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequences 4, 34, 10, 7, 19, 73, 2, 15, 6, 20. Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests it it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?
    a) 95ms
    b) 119ms
    c) 233ms
    d) 276ms

Section B

In a language, there are only 4 characters ‘h’, ‘i’, ’r’, ‘e’. and we have to write a function which takes a string as input and returns whether the given input string is a “valid word” or not.
Definition of valid word :

1. A given word is a valid word if it is of the form h^n i^n r^n e^n where n >=1. (eg: hhiirree)
2. Valid words has concatenation property i.e. if w1 and w2 are valid words w1w2 is also a valid word.