The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
1,752 views

                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 13th May. On the basis of these 2 tests, they shortlisted around 180 people for Subjective test which was conducted on 14th 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 :)

posted May 22, 2017 in Interview Experience by Loyal (9,065 points)
edited May 24, 2017 by | 1,752 views
0
Like
0
Love
0
Haha
0
Wow
0
Angry
0
Sad

21 Comments

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.

 

In this problem we need to choose p integers from c integers such that the minimum distance between adjacent prisoners is maximized

Does this mean that these p integers has to be in adjacent indexes?

Say 1,2,3,4 is a valid index to choose 4 integer but 1,4,7,9 is nto valid since these are not adjacent.Can you help me in understanding this question?

Let's say  |c| = 5 and |p| = 3 

c sequence -> 1, 3, 7, 8, 9 (As far as i think the c sequence can be considered as point distances in a straight line)

Now, where can we place 3 prisoners such that the distance between them is maximum.

Let's say we put them as 1, 3, 7, 8, 9 , here min distance between any two adjacent prisoners is 1 (9-8 = 1).

Let's try another possibility 1, 3, 5, 7, 8, here the min distance between any two adjacent prisoners is (8-5 = 3).

We wan't such placements such that minimum distance between any two prisoner is maximized.

did anyone solve 4th programming question ?? is it related to partitions.

4th programming question:-https://www.geeksforgeeks.org/generate-unique-partitions-of-an-integer/

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,861 questions
47,532 answers
145,982 comments
62,293 users