Directi Written Paper 2013

IIT D :

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 explore Paths in the code. explore Paths 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.


IIT R :

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 function that will return the largest num that can be obtained after O multiplication.

Eg: 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.

2. Given N set of points with X and Y coordinates.
1000<X[i]<1000
1000<Y[i]<1000
We have to calculate the length of the square that be constructed out of these points having
following features:
i. The points should lie on the square,
ii. The sides should be parallel to X or Y axis.
iii. The square should be constructed with minimum possible length.
Note: It is possible that all the corners not be the points.
For eg:N=5
X[]={0,2,3,5,7}
Y[]={3,0,0,0,3}
function should return 7
in case the square can't be formed or any other error return ­1

IIT G :

There were 11 test cases to pass for each question.

Q.1. Repeated from IIT Roorkee Q1.

Q.2. The question was very big with a story of IPL team selection. The summary of the story is:
Royal Challenger needs to form a team of X players. Each of the Y fans of Royal Challenger can
select X players of their preference. The team management have a criteria that, at least one player
have to be in the team from each of the fan’s preferences. So, find the minimum number of
players that can satisfy each of the fan’s preferences. For erroneous conditions return ­1.

Example:
numberOfPlayers  = 5
numberOfFans = 3
fanspreferences =
{
“10000”
“00100”
“00010”
}
output = 3
numberOfPlayers  = 4
numberOfFans = 3
fanspreferences =
{
“1000”
“0100”“0101”
}
output = 2
Given function signature:
int findminimum(int numberOfPlayers, int numberOfFans, char **fanspreferences)
{
}
http://www.careercup.com/question?id=5734638857224192


IIT KGP :

Q.1. Repeated from IIT Delhi Q1.

Q2 You are given a string that consists of digits. The string contains not only digits, but matched
round ­brackets as well.
Examples of such strings are
● "1234(56)"
● "03(5(68(42)7))"
Note that the round­brackets will always be matched, meaning
● The number of opening and closing brackets is exactly equal
● There will be no prefix that contains more closing bracke
"1234(56)"
"03(5(68(42)7))"
Note that the round­brackets will always be matched, meaning
The number of opening and closing brackets is exactly equal
There will be no prefix that contains more closing brackets than opening brackets
 In this string, the opening bracket is always preceded by a digit.
Now, you go through several iterations to get rid of the round brackets. The iteration
proceeds as
If the string contains round brackets, pick up any matched pair of round brackets that you
find
Repeat the entire expression within the round brackets, exa
ts than opening brackets In this string, the opening bracket is always preceded by a digit.
Now, you go through several iterations to get rid of the round brackets. The iteration proceeds
as
● If the string contains round brackets, pick up any matched pair of round brackets that you
find
● Repeat the entire expression within the round brackets, exactly as many times as, the digit
that immediately precedes the opening bracket in the matched pair
Note that the string after eliminating all the round brackets will always be the same no matter in
what order the round brackets are picked for expansion.
For example, consider the string "42(30(1)4(21()))8"
● We first pick up "(30(1)4(21()))" and repeat the expression inside the brackets 2 times.
● We do it 2 times, because the digit 2 immediately precedes this bracketed expression in
the string.
The string now becomes "430(1)4(21())30(1)4(21())8"
● We now pick "(1)" and repeat it 0 times, since 0 is the digit that immediately precedes it.
● Repeating 0 times effectively means that we ignore the expression.
● We can do this for both the "0(1)" substrings of the strings.
The string now becomes "434(21())34(21())8"
● Next, we look at "1()". Since the bracket contains nothing, we repeat the empty string
exactly 1 times.
● This also effectively means that we ignore the expression.
The string now becomes "434(2)34(2)8"
● We can now expand "4(2)" to "2222" in both the instances above to get the final string
"432222322228".
● This string has the length 12.
Implement the method stringLength in the given template. The parameters to  the method are
● S, the string that must be expanded.
Your method must return the length of the string after expanding the expression. Do not try to
actually find the expanded string since this string might be too big to fit into memory. Only
calculate the length and return it. You may assume that the answer is always less than 109. Note
that it is possible that the length of the expression in the end is 0.
You can assume that the input string always is always valid according to the  specification
above.Sample Test Case 1
"42(30(1)4(21()))8"
Answer as described above is 12
Sample Test Case 2
"1(1(1(30(9(12345678)))))"
Answer is 1. The expanded string is "3"
Constraints
● 1 ≤ Length of S ≤ 1000
● The result will be less than 109.
● Any algorithm of complexity O(N2) or better should pass.
Note: Be careful when returning a string in C. Declare "char str[]" globally and return "str". Local
char arrays are deallocated after a methodlevel2 call ends and will produce Segmentation Faults!


IIT K :

Q1. Given a binary tree where value of each internal node is 1 and leaf node is 0. Every internal
node has exactly two children. Now given level order traversal of this tree return postorder
traversal of the same tree.

Q2. same as IIT Kgp q2.(actually i think it is IIT R q2) but in place of rectangle they wanted a
square( just some additional test cases)

Q3. Given a matrix with 1 and 0 as entries. Find the perimeter of squares which enclose all the
1’s.All the 1s are contiguous i.e. there are no isolated 1s.For instance
01000
11100
10000
 here the answer will be 12.

Q4. given a string of the form AB2C3 and an int k.Expand the string as ABABC3 then ABABCABABCABABC.Then what is the kth element. You dont actually have to expand it as it will violated the memory constraints. You just have to find the kth element.

IIT B :

1. Question 1 from IITR

2. Given a 2D array containing dots(.) and hashes(#), find the perimeter of area covered by
hashes.
Ex. Perimeter of area covered by a single hash is 4. That of a couple of adjacent hashes(##) is 6.
For the following input, the answer should be 15.
. # # .
. # . .
### .