My GATE 2017 rank is 101 and I was targeting IIT Kanpur and IIT Delhi for admission. So in this blog I am writing about my tests experience at IIT Kanpur.

This year they called around 400 people for the test. They conducted 3 tests(Objective, Programming and Subjective). They conducted Objective and Programming test on 13^{th} May. On the basis of these 2 tests, they shortlisted around 180 people for Subjective test which was conducted on 14^{th} May. Among all these 3 tests, Objective test was the easiest one.

**Objective Test**

Objective test consist of 3 sections(Theory, Systems and Statistics & Data science). Each section was of 50 marks and we have to attempt any 2 sections in 3 hours. There were some fill in the blanks and one line answer questions too and for the questions with options, more than one option can be correct. There was no negative marking. Some of the questions asked in this test are :

**1) Theory**

i) 8a + 19b = 1. So find out the possible values of a and b.

ii) one dfa was given and we have to choose the correct regular expression for it from the options given

iii) DFA was given and the probability of each link in DFA was also given. So we have to find the probability to reach a particular state using the given 2 strings.

**2) Systems**

i) A question on semaphore to find initial value of semaphore variable

ii) To find number of hosts in a network given the subnet mask

iii) Difference between clustered and non-clustered indexes

iv) Number of clustered and non-clustered indexes

v) A query is given with EXIST clause and we have to rewrite it without using EXIST

vi) A question on finding accuracy of Branch prediction. A DFA was given for it and program sequence was also given telling whether it will take the branch or not

**Programming Test**

I am not able to recall questions from Statistics & Data science because I attempted only theory and Systems section. Next was the programming test. There were 4 programs to solve in 3 hours. Marks of each program were 30, 40, 60 and 75. The questions asked where :

1) Question to check anagram ( 40 marks )

2) Starting index of leaves and value of leaves of complete binary tree where given, with the property that parent will have min(left child, right child). We have to return the the contents of indices asked for the tree. ( 30 marks )

for example,

starting index = 3 and

leaves values are 1, 9, 5 and 2

above 2 information will be given, So the tree will be like

min(1,2)=1

/ \ 1

min(1,9) min(5,2) => / \

= 1 = 2 1 2

/ \ / \ / \ / \

1 9 5 2 1 9 5 2

3) There are p prisoners and c ( > p) cell blocks. c and p will be given as input. Also a sorted list of c integers will be given. You are required to choose p integers from c integers such that the minimum distance between adjacent prisoners is maximized. You have to output this minimum distance. ( 60 marks )

4) We have to find addition factors of a number in lexicographic order for n<15. ( 75 marks )

for example if n=4 then output will be

1 1 1 1

1 1 2

1 3

2 2

**Subjective Test**

Finally there was a subjective test similar to objective one. We have to attempt questions from any 2 sections in 3 hours. There were 3 questions from theory and 3 questions from Systems. Questions asked where :

**1) Theory**

i)

a) if degree of vertices < 3, then prove that the graph will be union of vertex disjoint path and cycle.

b) Graph Matching was explained. Let S and R be the matching graph, then a new graph G=(S-R) ∪ (R-S), will be union of vertex disjoint path and cycle. Also prove that the cycle obtained will be of even length.

ii) Consider a grammar G with productions P. Let INIT(G) be the grammar with production P' such that

P' = P ∪ ( A->B | such that A->BC belongs to P ) ∪ ( A->epsilon | such that A->b belongs to P )

prove that:

a) Prefix(G) is subset of INIT(G)

b) INIT(G) is subset of Prefix(G)

iii) Algorithm to find strongly connected components in the graph

**2) Systems**

i) Question on semaphore. A program was given which was incrementing variable y. 8 processes where allowed to execute the program. Initial value of y was given. We have to find possible values of y after all 8 processes complete their execution.

ii) Information about main memory and cache was given. We have to find number of bits for tag and index for direct mapped, set associative and fully associative cache. We also have to find cache capacity including tag overhead for each cache. Also explain the working of each cache mechanism.

iii) I didn't understood this question.

I have written as many questions that I recall. If you guys remember any more questions especially for objective one, write in the comment, I will add it.

Verdict :- Selected :)

The fact is to improve the maximum distance using binary search.

similar problem: http://www.spoj.com/problems/AGGRCOW/

Topcoder has a nice tutorial for modified binary search.