BLOG INDEX

  • Interview Details and Stage 1 (Coding)
  • Stage 2 (Home Interview)
  • Post Result Talk with Professor (about CDS/CSA, DREAM LAB, Research)

Date – 10-July-2020, Duration – approx. +45min (Between 10:45 am to 12 am)

Stages – Two (Online Test, Home-Interview),

There was Online Google Form asking for Preferences, SOP (why you have chosen preference), Projects List, Professional Website (LinkedIn etc.), Programming Skills profile link.

(You need a background, possible experience to select labs, because they have your profile at the time of interview and ask questions why this lab, why not this)

Labs allowing to CS/EE only – DREAM LAB, MARS LAB, VAL, CSL.

---------------------------------------------------------Stage 1

It consists of Basic Objective Question based on Engineering Mathematics and Discrete Mathematics.

Syllabus – (source CDS brochure) – Combinatorics, Linear Algebra, Probability, Statistics, Differential Equations, Plotting, Data Structures and Algorithms

Platform – HackerEarth

Pattern – 7 Questions (5 marks each), 5 Multiple choice questions, and 2 programming questions

Programming Languages allowed – C (gcc 5.4.0), C++, Java.

Time: Early Morning 7:30 to 8:30 am ( then non-stop 45 minute online test)

----------------------------------------------( round brackets are showing my thought process () )

Q1. A group of 12 people, consisting of 6 couples, have reserved a row of 12 seats at a movie theater. How many ways are there to seat these people if couples want to sit next to each other.

Options – 46080, 23040, 1200, 479001600

(My Reasoning: 6 group permutation then each couple permutation - 46080)

------------------------------------------------------------------------------------ 

Q2. The plot of $y=e^{-x}sin(2x)$

(well I used calculator to put x value and get y value)

( I can straightaway delete the option c, for other I went raw method)  (anyone knows better method can suggest)

Q3. Consider the system of equations

$x+3y-z=4$

$4x-y+2z=8$

$2x-7y+4z=0$

Options – No solution, unique solutions, infinitely many solutions, None of the above

(I got last two rows same on initial first row operation)


Q4. What is the sum of diagonal elements of the matrix  $\begin{pmatrix} 1 & -1 \\ -1& -1 \end{pmatrix}^{10}$

Options – 0, 32, 64, 128

(Eigen Value coming out to be = ±sqrt(2)) ( in hurry, and in morning sleep I have done raw matrix multiplication also)

-------------------------------------------------------------------------

Q5. You are randomly selecting one of two coins A and B and tossing it. Coin A is fair but Coin B has ¾ probability for tails. If after the coin toss you observe tails, what is the probability that you had selected coin B?

Options = 0.5, 0.6, 0.625, 0.4, None of the above

(applied Bayes theorem)

Q6. Graph Traversal BFS

Say you are given a graph with n vertices labeled with IDs 0 to (n-1). The graph data structure is provided as an adjacency matrix G of size n×n. The row i of the matrix corresponds to the neighbors of the vertex ID i  in the graph such that if there is a value 1 in the column of that row, there is an edge from vertex ID i to vertex ID j , and if there is a value 0 , there is no edge between vertex i and vertex j.

Given a source vertex ID s  preform a breadth first traversal (BFS) of the graph and print the IDs of the vertices visited. The traversal of unvisited children from any vertex should occur from the smallest to the largest child vertex ID.

Sample Input
4
0 1 1 0
0 0 1 1
0 1 0 1 
1 0 0 0
1
Sample Output
1
2
3
0

 

( code template was provided with necessary declaration, reading input in adjacency matrix, we have to write main code) ( i haven’t done this question)

---------------------------------------------------------------------------------

Q7. Frequencies of even and odd numbers in a matrix

Given a matrix A of order N × N, the task is to find the frequency of even and odd numbers in matrix.

You will read the input and write the output from/to standard IO (console). Sample template code to read and write from I/O is provided for C, C++, java. Choose one of the languages comfortable to you.

Input format:

The data type of elements of A is INT. You read the matrix A from the standard console input as explained below.

The first row has the value of N, which gives the size of A. the following N rows are rows of A, with each row having N integers separated by a space. There is a trailing space at the end of a line.

Output Format:

You should output integers which are number of odd (OO) and Even Numbers (EE) in the given matrix to standard console output

OO

EE

Sample Input
4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
Sample Output
8
8

(Similar template code is given)

(it was simple, just have to check odd and even number then have to count)

-------------------------------

Takeaway:

  1. Do programming after Gate if you are in safe side. Else do both programming and interview preparation.
  2. Keep practicing mathematics. As an engineer always practice math. It will never leave as long as you are in engineering. In fact, entire computer is built on mathematics model (Turing machine).

Please utilize your B. Tech Time properly, Do Labs properly, read subject (at least try) from Std. Books and guide your juniors. If you have done B. Tech then please utilize your MTech time properly.

-------------------------------------STAGE 2 - Home Interview

There was waiting room and other main interview panel.

Platform – Microsoft Team

My preferences was:

  1. Distributed Research on Emerging Applications & Machines (DREAM LAB)
  2. Cloud Systems Lab (CSL)
  3. Video Analytics Lab (VAL)

( Reason was background subject related to DREAM then IOT which I have little bit experience)

There were 4 professor, 3 male, 1 female. Out of which 3 have asked me questions. (Rest 1 was of V.A.Lab I think)

As far as I remembered (No visuals from there side, and short name were there) – There was Prof. Yogesh Simmhan, Female faculty Prof. J. Lakshmi. Rest I don’t remember name.

They started with reading my application, then my lab preference (why this or that), projects, gate score and reason for Gap in year. ( they asked me reason for VAL, I said I have read Image processing subject in my B.Tech and done some projects related to video manipulation)

(after Interview I have seen notification that someone viewed my LinkedIn profile at the starting of interview, as provided in form)

So, then They started: (I will try to format questions as they have said as best as I can)

-------------------------------------------------------

P1 (first professor): So, we will start with Data Structures and Algorithm. It is fundamental subject and should be known by all.

(Q1) Suppose, we have an array of ‘n’ numbers, I have to take min 10 elements, what should be the algorithm and time complexity.

(well I was not prepared for DSA, but every system subject but still I have given Gate, I know things right.)

[ I started with explanation of First sorting the array and then indexing array for first 10 elements]

P1: What is the time complexity of your process.

[told about using sorting algo – quick sort O(n.logn) and then indexing O(1)]

P1: Can you reduce the time complexity; can you think of it in other way.

[I started with some non-sense (I think greedy type, he pointed out my mistake) then in last I changed to naming unsorted array and using linear search for first element and then using it for 10 times, which will give time complexity as 10 times of O(n)

P1: Can you reduce it further.

(okay reducing more, think Vijay think)

[ I said we have to search an entire array at least one time to look for min element so it will minimum take O(n) time]

( they have given me time to think and come to solution)

P1: Topic changed

(Q2) do you know about sparse matrix.

(well I was thinking I have heard that name before and then)

[ it consist of minimum element like that]

P1: He immediately pointed out my mistake, and then said about sparse graph, using zeros and one in matrix.

( I got the link to area in my brain for that topic)

[ then I told about general adjacency matrix, zeroes for no edge, 1 for graph edge between vertex]

P1: okay great. Can you draw adjacency matrix.

[ drew graph then matrix and showed]

P1: now as we see for sparse matrix, it is taking more space can you provide alternate data structure.

[yes, I described adjacency list][ they asked me to draw and show]

P1: In sparse matrix, we have just 1 but it can be any non-zero value, right. So whatever data structure you have given can it provide such value.

[I said yes, and said it is linked list node, along with node and address we can have another parameter in that node.] [ they asked me to draw and show]

(now level increases.)

P1: Okay, great. Now I have vector of ‘n’ number and I need to multiply that vector with data structure you have provided. Like we do in adjacency matrix and matrix multiplication. Can your data structure do that.

[ Initially I asked him to explain one more time. Then I formulated first matrix multiplication. M as adj matrix and B as vector ( I asked vector to be column vector to support multiplication) then showed A(n*n) * B(n*1)

Then I took adj list data structure and …………]

( I know I have struck there but whatever my thinking process and direction I keep on explaining)

( there was google doc where I have to show him doing that)

[ I said we will traverse node by node, look for node number and then multiply it with that index in vector only)

( okay great, bolne ko to kuch bhi bol skte he, esa kr lo wesa kr lo, par ab bol diya ab kya)

P1: great. Can you construct the program for that in the google docs.

(I was like, seriously?? Right now?? I don’t know where all my programming skills have gone to may be still sleeping for morning routine) ( ham bhi kha haar maan le wale the)

[ I tried, started, got confused, got lots of question what should be struct data name, what is node name, what is node header. Then he said just right main programming construct, you know C. well okay. I again started righting adj matrix code but then changed to traversing the linked list code. Wrote few lines of loop. He said okay we can stop now.]

P1: asked another faculty member whether he wanted to asked me about video lab or not. He said not needed.

P1: then he asked female faculty to ask me about OS question.

( I was like, okay I know OS, I can do that good)

------------------------------------------------------------------ 

P2 (female faculty) : Vijay, do you know OS, how much have you read.

[ I said I have read basic concepts of OS and covered GATE syllabus topics]

P2: what is time sharing scheduling algorithm in OS.

[ I confirmed whether they are asking for Round Robin or not.]

P2: she said to explain it

[Explained arrival of process, ready queue, time quantum, preemption and execution till completion]

P2: Can you determine parameter by looking at that we can say the time quantum gives fair chance for every process or not.

(from now onwards, deep thinking process arrived)

[ I tried to explain her, having n number of process they will execute one by one ……]

She interrupted and explained what she is asking for.

[ I said we can calculate time quantum if we have given n number of process, context switching time, to allow fair share for all process]

She again explained that What is the parameter or ratio by which looking at that we can say that time quantum is fair for all process or not.

[ I told her about using turn around time, average turn around time to check if all process is executing efficiently.]

She asked what is turnaround time.

[ I told her basic definition]

Then she explained the effect if some processes are having large burst time or some having less. ( as far as I understood it was like convoy effect in fcfs type). She said how in that you can say turn around time will be that parameter.

[ now I have accepted my invalid point. I asked whether we can use some combination of waiting time or turn around time]

She again explained that she is looking for parameter by seeing it like if I say it is greater than 1 then we can say it fair or less than 1 not fair like that.

( now I was asking God for some help, to show some mercy and path to think, but God was busy fighting Corona)

[ Now I got stuck, completely blank, I asked for some hint]

How can you determine which process should execute or are waiting long enough to affect their performance?

[ meanwhile I said to her about using aging to determine priority whether they are waiting long enough or not required attention]

( I think aging is bit out of context for current question)

She said expected value or probability you can find for that.

[ I told about using burst time for calculation, then finding expected burst time and using that value as time quantum]

( yes I know, I was shooting arrows in dark, but I have to think right, If I stop then my brain will stop thinking at all)

She asked again how will you determine the burst time of process. Do you think process already have burst time before execution.

( I was like, well in gate question I have seen burst time before execution)

[ I was again started saying by seeing instruction whether they require cpu time or io time and calculating that, we can look for that instruction]

( I have seen expected burst time in SJF but at that as we are talking for round robin it doesn’t struck my mind)

She was like, how will you do that, suppose we have data instruction or require processing of the data in that case.

( I again chanted similar thing, looking for instruction and all)

She said suppose we are doing 3 by 3 matrix multiplication having large value of data it will take time. But again thing like we are having large matrix multiplication then in that how you will determine.

( I was like ohhh, ye kya ho gya, hamre jaal me hum hi faste jaa rhe he)

[ I said time complexity initially, but interrupted and then I explained my mistake and accepted it]

(She was nice, explained me properly, gave time to think, corrected my wrong thinking, In the end she was like smiling at my acceptance of mistake. And I was still thinking for some point to come back)

She said we should stop now, no problem and passed me to next interview.

---------------------------------------------------------------------- 

P3: do you know distributed system

[ I said I have read in B. Tech and explained working of Distributed system in short and RPC message passing]

P3: sounds great, so do you know basic synchronization concepts

[ I said yes for OS, but I don’t remember for Distributed system]

P3: yeah no problem. Concepts are same. It works like OS. So can you explain reader-writers problem

[explained about readers process and writer process]

He interrupted me asked me about synchronization problem involved.

[ I said 4 condition related to it]

He said okay. He asked do you think it gives equal chance to both reader and writer.

[ I said if we give priority to reader then writer may starve, or to writer then reader may starve]

Okay. Can you write the sudo code for reader writer synchronization solution in google doc.

[ okay, started writing meanwhile keeping on explaining whatever I was writing and why I was writing]

He interrupted me find mistake in my code where I have written mutex(x)….code…..mutex(x)

He said do you know semaphore and its function wait (), signal ().

[I immediately got my mistake and said sorry and corrected it down(x)….code…..up(x).]

[ meanwhile I was initializing binary semaphore x, but confused in spelling of semaphore or semafore.]

He said no problem in spelling just write rest of code.

( I was like why, here and now, what happen, even silly spelling mistake)

[I wrote all the code]

He asked suppose writer is in database and readers got suspended. Larger num of readers. So how they will resume their execution and in what order.

[ I explained about suspending list in semaphore and fifo way to wake up the process]

He further asked about priority in which reader and writer will be allowed.

[ I said if one reader is already entered into database then slowly all readers will execute first then writer may get chance]

P3: So do you know graph coloring problem. And its use?

[ I explained it in short manner of using it to color the node. And said I have seen its use in register allocation in compiler]

P3: can you explain graph coloring algorithm.

[ I said I don’t remember the algorithm, as I have solved question in rough manner and explained that manner of identifying large clique, using color and reusing them unless necessary.]

In the last he asked me whether I know programming or not.

[ I said I have done competitive programming 2 year before and from past 2 years I was focusing on Gate but I know basic programming.]

( and it ended, they disconnected me)

--------------------------------------------------------------------- 

Takeaway:

  1. As I have felt, they were looking for how far I can think, because that OS question seem like research itself. How I formulate my answer and explain clearly. They were cooperative, giving time, explaining, correcting mistakes.
  2. Basic Gate preparation will not help much, you have to pick up book and start reading out after Gate (if you haven’t). I have read OS for basic topics but still you have to try.
  3. I was calm and trying to think hard for solution but still at that moment it was just not coming up. So, it is very much necessary to answer properly. Practicing how you will give the answer, starting from basic point to slowly increasing level with clarity.
  4. At least revise all your short notes once after Result and practice math.

If nothing happens, you don’t get selected no problem, you got chance and experience. You can improve further building on it;.

Result: declared in the evening, got mail in morning. Selected.

GATE Score – 807, EWS

---------------------------------------Post Result Talk

Next day Prof. Yogesh Simmhan (Dream Lab) called me for this good news, my performance and discussed about its lab, department preference I can change if I want, what they will do in lab etc.

  • He asked me whether I have visited the lab page or profile page and I am interested in it or not. (dream lab was my first preference and interview was little bit about that)
  • About Lab – He said Lab overall works on Distributed System. Every few years idea of distributed system keeps changing, new technology emerges, and last few year IOT has been on emerging areas that is expanding. So we have multiple projects going on IOT, some of the newer ones have to do with how can you, for example, make use of Raspberry Pi class device, can be deployed as a part of smart cities, even for example Drones, we have projects coming around drones. IISc has new center on Autonomous computing that’s coming up, so for that we are trying to examine how drones, these flying platforms can we seen on as computing platform. We think of drone as flying platform, but to me a drone is nothing but a mobile phone (with flying capacity). So, we have mobility aspect of it and we also have sensors sort of video camera and so on that are modeled on the top of phone and flyer on.
  • Some of Problems we are looking at how can you actually do some of the computing at the top of say video streaming, maybe even doing some deep learning …. So on, on top of the drone platform itself. And then there is some system aspect of it so how do you tradeoff between parallel computing on top of the drone itself as energy efficiency, right because drone has only captive amount of energy which you can use for flying and computing. And if you do too much computing, you might actually reduce flight time and so on. And how can these drones actually do task co-operatively, not just observational task even computing task co-operatively. So, can you actually move data from one node to another and then sort of distributed computing, you can think of flying Hadoop cluster right, as what drone could be considered as. Lot of interesting problem around IOT and drone computing like we are starting to look into. Some of these also have lit bit flavor of Machine Learning and Application domain for us because of anywhere and everywhere. (So, it is kind of thing you will be interested in?)
  • Interest - One thing I can set of tell you is that one way to think about since you applied for Research program, it is not course program, right which means that the lab that you join is way more important than the department you join. Research student take typically one semester of course, and three semester or almost one and half year is spent in research lab doing research. Courses can be taken in any department, IISc doesn’t restrict you saying if you join a department A then you can only take course from A. In fact, many of my students take courses like operating system in CSA department. It is very flexible. What really matter is the research lab you join and the kind of research you do. That is why maybe doing little bit of homework on that and understanding what your interest are would be helpful
  • Department – One thing I can tell you is system department in computer science typically looks at more classic computer system perspective like architecture and operating system. They are parallelly good at it. (some professor name). what the CDS work on the newer system like cloud computing, big data platforms, IOT, and so on. So that is the set of difference. If you like classic operating system and you like to work on Linux kernel and so on something like CSA might be good. If you want to set of do the next higher level, if you want to see like how tens of hundreds of distributed systems could be working co-operatively together to solve emerging problems. Things like edge computing drone computing didn’t exist five years back and cloud computing didn’t sort of prevalent ten years back. But we use fundamentals idea about operating system because at the end of the day your synchronization primitives are going to be similar whether it is one-two thread on single processor or across hundred machines across a wide area network, in terms of memory you will be going to network for coordination and so on. That I would say is set of key difference between some of the CSA based systems lab and the CDS system lab. (that is why think about it)
  • Department Preference – what IISc will do is IISc will give only single offer based on department priority that you have chosen. They will not give choice to you, let say both CSA and CDS are willing to take you. If one department is higher choice you only get a single offer from that department, and if you decline it, it is declining entire IISc offer. Now you have chance to speak with faculty at both CDS and CSA, so do a little bit of homework and if you strongly feel that something at dream lab will be right lab for you. You have time till Monday to change department preference. But do look through the lab because that’s going to be like I said critical part, what does the actual area you want to work on and based on that You should chose your department where that lab is present.
  • Advisor/LAB – I would be one of your primary choices and even within the department since you have given the priority order, we would sort of respect that, but we also encourage to talk to couple of other labs, so that you enough information and choice is up to you. If you are interested in dream lab at CDS, I will be happy to take you (based on performance in interview and resume). I think you have one month after you join to finalize your lab after you join the department. It is two-way street, both the lab must be interested in you and you must be interested in lab, if both of these happen, then you will be able to.
  • Students/Research – way we do interview we want to understand the overall skills of the student because research itself is such a fast-moving area, we don’t want to hire someone who has narrow set of skills. At the end of the day we do not expect student to be set like sort of extremely talented when they come but must have sound fundamentals and they should be really passionate about what they wanted to do. Because it was like what Edison said Innovation is set of 99 percent perspiration and 1 percent inspiration. As long as student willing to work really hard, they enjoy what they are doing and they are interested in system research. IISc or Lab or Department will provide the right environment for you to thrive. Sometimes student design their own projects and they come in and say this looks nice but I wanted to do something related to this. That way you can carve a whole new topic for yourself, that is the kind of flexibility we offer. Research is not like a production line; it is not a kind of algorithm that you follow. Research is all about creativity, trying to find about very interesting problems and trying to solve that to the best of your abilities. All the students and faculty are hardworking and they expect a lot. The reason we are able to compete with some of the top 100 university in world is not just because we have right students but we have hard working students.

Thank You for Reading. Hope It helps. Constructive Views are welcomed.

posted Jul 18, 2020 edited Jul 25, 2020 by
19
Like
2
Love
0
Haha
0
Wow
0
Angry
0
Sad

1 Comment