TopTalent : Could you briefly describe your student days at BITS Pilani ?

Romal : I always considered myself fortunate to be pursuing my degree at BITS Pilani. The curriculum here is quite flexible giving enough scope to nurture your interests apart from academics. I tried to make the most of it by being able to complete few higher degree courses in undergrad itself. The faculty here is pretty knowledgeable, I spent some great time working along with them in projects. Also the students here share great enthusiasm towards their career and play a big role in your development.

TopTalent : What makes Google special?

Romal : Google certainly ranks among the top companies to work at and the quality of the products and services they offer is well known. Also working in Google allows one to pursue his own interest along, since Google has such wide ranges of projects to offer. The work environment and the culture there adds every bit of fun to it.

TopTalent : How much preparation did you put in to bag this opportunity?

Romal : Unlike most others, I took my time off. My primary objective was to complete and furnish off some of my incomplete projects, so that I could be confident about them during placements. For programming, I used to practice codeforces problems. The contests it organizes contains a real good mix of mathematical, logical and algorithmic problems, and poses an environment much similar to coding rounds during placements. Besides, I had completed most of the algorithms from Cormen and then shifted to GeekForGeeks to refer to past years interview experiences.

TopTalent : Can you describe the complete hiring process of Google?

Romal : The whole hiring process was pretty smooth actually. It had one written round based on your overall knowledge of the field which basically had a few aptitude and coding questions. The shortlist was announced after two weeks and we were called for an on-site interview at its Bangalore office. Then followed four back-to-back interviews, mostly algorithmic. We were allowed to write the code through whichever medium we were comfortable with. I toggled through all – pen, board and online editor. There was very little delay and the accommodation and food were pretty good. Finally within a week, I got the CALL!

TopTalent : What topics do you think students should prepare for similar jobs like that of yours?

Romal : Firstly, they should have regular coding practice as most companies now prefer using coding rounds for shortlisting. The problems asked normally don’t require any deep knowledge of algorithms. They are to test your speed and logical thinking. Then comes personal interviews. Most of the companies prefer asking algorithmic problems. However, these questions could indirectly test your basics around other topics like operating systems and database management system as well. Mostly if your basics are clear, they look at the way you think and reach the solution.

TopTalent : From your experience, what are some of the important factors that the interviewers will be looking out for?

Romal : Many believe that interview questions keep on repeating every year so they could just mug up everything to clear such interviews. This brute force way doesn’t even work out for regular jobs let alone Dream Companies. In one of my interviews, the interviewer asked me a question which I had never seen before. When I finished reading the problem, he asked me to speak out everything that came to my mind and to not stop speaking till I reach some solution. Luckily for me, I did arrive at some solution. It was a mind boggling experience. These kind of interviews end up testing your thinking abilities more than anything. For Jobs like the one I am going to join, strong basics in algorithms and critical reasoning skills are essential. These are the two most important qualities that interviewers will be looking in you. The answer impresses nobody, the way you reach there is what matters.

TopTalent : What role does resume and CGPA play for applying to such jobs?

Romal : Resume serves two purposes. Firstly, getting you shortlisted for the interviews and secondly, to give a brief idea of the things you have been working around and and are comfortable with. This generally guides the interviewer to choose what to ask and what not to ask from. I personally referred to ‘Cracking the coding Interview’ for building my own resume. It contains a number of Do’s and Dont’s.

CGPA was never a thing to boast about in my resume. For most of the companies it just plays a role in the initial shortlisting. However for research based companies your CG does play a significant role. Though a high CG is a good thing to have, its just an indicative of how disciplined you are rather than a measure of your talent.

TopTalent : Would you like to share something exclusively for job seekers from elite colleges ?

Romal : Do not restrict yourself to some specific domain or subject, at least not at the undergrad level, but always have an overall sight of things and how they interrelate. Follow your interests and be good at it. Make most of the opportunities you get to learn as a part of your curriculum or through other online sources. And do possess a go-code mindset.

This article is powered by TopTalent.in – A high end Job portal for students and alumni of Premier Colleges in India.

MCQ Questions: 20 (+4, -1)

Subjective Question: 1

1) Given four matrices

P = 20×10

Q = 10×5

R = 5×10

S = 10×10

Find minimum no. of multiplication required for PxQxRxS?

a) 4000

b) 2500

c) 3000

d) None Of These

2) Two n-size arays are given . n1 in decreasing order and n2 in increasing order. If c1 is time complexity for n1 using quicksort and c2 is time complexity for n2 using quicksort. Then –

a) c1 > c2

b) c1 < c2 c) c1 = c2 d) None of these 3) If there is a N sorted array then what is time complexity of finding 2 no.s having sum less than 1000.

a) O(1)

b) O(n^2)

c) O(n)

d) O(logn)

4) There are some process . In which of the scheduling algo CPU utilization is minimum. If I/O burst time is 90ms and CPU burst time is 10ms.(question is very long to remember)

5)

int func(int x, int *y, int **z)

{

int p, q;

x += 2;

p = *y++;

q = **z++;

q = **z++; //Not a repeated line.

}

void main()

{

int a = 5, *b, **c;

b = &a;

c = &b;

printf(“%d”,a);

}

6) Find the least significant digit of 2^3*google where google=10^100.

a) 2

b) 4

c) 6

d) 8

7) Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

a) A(n) = Omega(W(n))

b) A(n) = Theta(W(n))

c) A(n) = O(W(n))

d) A(n) = o(W(n))

8) Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

0 1 8 1 4

1 0 12 4 9

W = 8 12 0 7 3

1 4 7 0 2

4 9 3 2 0

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

a) 7

b) 8

c) 9

d) 10

9) In the graph given in question 8, what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

a) 7

b) 8

c) 9

d) 10

10) A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

|0| |

|1| |

|2| 42|

|3| 23|

|4| 34|

|5| 52|

|6| 46|

|7| 33|

|8| |

|9| |

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

a) 46, 42, 34, 52, 23, 33

b) 34, 42, 23, 52, 33, 46

c) 46, 34, 42, 23, 52, 33

d) 42, 46, 33, 23, 34, 52

11) How many different insertion sequences of the key values using the same hash function of question 10 and linear probing will result in the hash table shown above?

a) 10

b) 20

c) 30

d) 40

12) The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is

a) T(n) = 2T(n – 2) + 2

b) T(n) = 2T(n – 1) + n

c) T(n) = 2T(n/2) + 1

d) T(n) = 2T(n – 1) + 1

13) Given three semaphores, S0, S1 and S2 initialized as S0=1, S1=0, S2=0 and processes P0, P1 and P2.

P0 : while(true)

P0, P1 and P2.

P0 : while(true)

{

wait(S0);

printf(“ 0 “);

Release(S1);

Release(S2);

}

P1: while(true)

{

Wait(S1);

Release(S2);

}

P2: while(true)

{

Wait(S2);

Release(S0);

}

Find out how many times the process P0 executes printf statement.

a) At least twice

b) Exactly once

c) Exactly twice

d) Exactly thrice

14) Given the following program construct

{

if ( a == b ) { S1; exit(); }

else if ( c==d ) { S2; }

else { S3; exit(); }

S4;

}

Given 4 test cases, find out which one among the following covers all the 4 statements

T1: a, b, c and d are same.

T2: a, b, c and d are all distinct.

T3: a == b and c != d.

T4: a != b and c==d.

a) T1, T2 & T3;

b) T1, T4.

c) T2, T4.

d) T1, T2 & T4.

15) 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 FCFS in terms of response time

a) I only

b) I and III only

c) II and III only

d) I, II and III

16) Sequences of logical pages access :

1 2 3 2 4 1 3 2 4 1

Implemented Optimal,LRU,FIFO Page replacement techniques.

Then no. of page faults in :

a) Optimal < LRU < FIFO b) Optimal < FIFO < LRU c) Optimal = FIFO d) None 17) Find the no. of page faults for Optimal Page replacement technique in the given sequence of question no. 16.

a) 5

b) 6

c) 7

d) 8

18) Given a simple graph of 6 nodes (note- it’s a simple graph) then tell which of the following is a set of valid graph degrees.

a) 4,4,1,1,1,1

b) 4,4,2,1,1,1

c) 4,4,2,2,1,1

d) None

19)

gcd(n,m)

{

if (n%m == 0)

return n;

n = n%m;

return gcd ( m, n);

}

What is the complexity of calculating gcd(n, m) in worst case?

a) O(lgn)

b) O(lgm)

c) O(lg(lgn))

d) O(lg(lgm))

20)

void f(char * x)

{

x++;

*x = 'a';

}

int main()

{

char * str = "hello";

f(str);

cout << str;

system("pause");

return 0;

}

a) hello

b) hallo

c) allo

d) empty string

SECTION B – Subjective Question

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. Find all the distinct tours of a knight placed on (x,y) of a NxN chessboard.

X,Y Knight can go to 8 positions.(default rule). Write a running code.

Romal : I always considered myself fortunate to be pursuing my degree at BITS Pilani. The curriculum here is quite flexible giving enough scope to nurture your interests apart from academics. I tried to make the most of it by being able to complete few higher degree courses in undergrad itself. The faculty here is pretty knowledgeable, I spent some great time working along with them in projects. Also the students here share great enthusiasm towards their career and play a big role in your development.

TopTalent : What makes Google special?

Romal : Google certainly ranks among the top companies to work at and the quality of the products and services they offer is well known. Also working in Google allows one to pursue his own interest along, since Google has such wide ranges of projects to offer. The work environment and the culture there adds every bit of fun to it.

TopTalent : How much preparation did you put in to bag this opportunity?

Romal : Unlike most others, I took my time off. My primary objective was to complete and furnish off some of my incomplete projects, so that I could be confident about them during placements. For programming, I used to practice codeforces problems. The contests it organizes contains a real good mix of mathematical, logical and algorithmic problems, and poses an environment much similar to coding rounds during placements. Besides, I had completed most of the algorithms from Cormen and then shifted to GeekForGeeks to refer to past years interview experiences.

TopTalent : Can you describe the complete hiring process of Google?

Romal : The whole hiring process was pretty smooth actually. It had one written round based on your overall knowledge of the field which basically had a few aptitude and coding questions. The shortlist was announced after two weeks and we were called for an on-site interview at its Bangalore office. Then followed four back-to-back interviews, mostly algorithmic. We were allowed to write the code through whichever medium we were comfortable with. I toggled through all – pen, board and online editor. There was very little delay and the accommodation and food were pretty good. Finally within a week, I got the CALL!

TopTalent : What topics do you think students should prepare for similar jobs like that of yours?

Romal : Firstly, they should have regular coding practice as most companies now prefer using coding rounds for shortlisting. The problems asked normally don’t require any deep knowledge of algorithms. They are to test your speed and logical thinking. Then comes personal interviews. Most of the companies prefer asking algorithmic problems. However, these questions could indirectly test your basics around other topics like operating systems and database management system as well. Mostly if your basics are clear, they look at the way you think and reach the solution.

TopTalent : From your experience, what are some of the important factors that the interviewers will be looking out for?

Romal : Many believe that interview questions keep on repeating every year so they could just mug up everything to clear such interviews. This brute force way doesn’t even work out for regular jobs let alone Dream Companies. In one of my interviews, the interviewer asked me a question which I had never seen before. When I finished reading the problem, he asked me to speak out everything that came to my mind and to not stop speaking till I reach some solution. Luckily for me, I did arrive at some solution. It was a mind boggling experience. These kind of interviews end up testing your thinking abilities more than anything. For Jobs like the one I am going to join, strong basics in algorithms and critical reasoning skills are essential. These are the two most important qualities that interviewers will be looking in you. The answer impresses nobody, the way you reach there is what matters.

TopTalent : What role does resume and CGPA play for applying to such jobs?

Romal : Resume serves two purposes. Firstly, getting you shortlisted for the interviews and secondly, to give a brief idea of the things you have been working around and and are comfortable with. This generally guides the interviewer to choose what to ask and what not to ask from. I personally referred to ‘Cracking the coding Interview’ for building my own resume. It contains a number of Do’s and Dont’s.

CGPA was never a thing to boast about in my resume. For most of the companies it just plays a role in the initial shortlisting. However for research based companies your CG does play a significant role. Though a high CG is a good thing to have, its just an indicative of how disciplined you are rather than a measure of your talent.

TopTalent : Would you like to share something exclusively for job seekers from elite colleges ?

Romal : Do not restrict yourself to some specific domain or subject, at least not at the undergrad level, but always have an overall sight of things and how they interrelate. Follow your interests and be good at it. Make most of the opportunities you get to learn as a part of your curriculum or through other online sources. And do possess a go-code mindset.

This article is powered by TopTalent.in – A high end Job portal for students and alumni of Premier Colleges in India.

MCQ Questions: 20 (+4, -1)

Subjective Question: 1

1) Given four matrices

P = 20×10

Q = 10×5

R = 5×10

S = 10×10

Find minimum no. of multiplication required for PxQxRxS?

a) 4000

b) 2500

c) 3000

d) None Of These

2) Two n-size arays are given . n1 in decreasing order and n2 in increasing order. If c1 is time complexity for n1 using quicksort and c2 is time complexity for n2 using quicksort. Then –

a) c1 > c2

b) c1 < c2 c) c1 = c2 d) None of these 3) If there is a N sorted array then what is time complexity of finding 2 no.s having sum less than 1000.

a) O(1)

b) O(n^2)

c) O(n)

d) O(logn)

4) There are some process . In which of the scheduling algo CPU utilization is minimum. If I/O burst time is 90ms and CPU burst time is 10ms.(question is very long to remember)

5)

int func(int x, int *y, int **z)

{

int p, q;

x += 2;

p = *y++;

q = **z++;

q = **z++; //Not a repeated line.

}

void main()

{

int a = 5, *b, **c;

b = &a;

c = &b;

printf(“%d”,a);

}

6) Find the least significant digit of 2^3*google where google=10^100.

a) 2

b) 4

c) 6

d) 8

7) Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

a) A(n) = Omega(W(n))

b) A(n) = Theta(W(n))

c) A(n) = O(W(n))

d) A(n) = o(W(n))

8) Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

0 1 8 1 4

1 0 12 4 9

W = 8 12 0 7 3

1 4 7 0 2

4 9 3 2 0

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

a) 7

b) 8

c) 9

d) 10

9) In the graph given in question 8, what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

a) 7

b) 8

c) 9

d) 10

10) A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

|0| |

|1| |

|2| 42|

|3| 23|

|4| 34|

|5| 52|

|6| 46|

|7| 33|

|8| |

|9| |

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

a) 46, 42, 34, 52, 23, 33

b) 34, 42, 23, 52, 33, 46

c) 46, 34, 42, 23, 52, 33

d) 42, 46, 33, 23, 34, 52

11) How many different insertion sequences of the key values using the same hash function of question 10 and linear probing will result in the hash table shown above?

a) 10

b) 20

c) 30

d) 40

12) The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is

a) T(n) = 2T(n – 2) + 2

b) T(n) = 2T(n – 1) + n

c) T(n) = 2T(n/2) + 1

d) T(n) = 2T(n – 1) + 1

13) Given three semaphores, S0, S1 and S2 initialized as S0=1, S1=0, S2=0 and processes P0, P1 and P2.

P0 : while(true)

P0, P1 and P2.

P0 : while(true)

{

wait(S0);

printf(“ 0 “);

Release(S1);

Release(S2);

}

P1: while(true)

{

Wait(S1);

Release(S2);

}

P2: while(true)

{

Wait(S2);

Release(S0);

}

Find out how many times the process P0 executes printf statement.

a) At least twice

b) Exactly once

c) Exactly twice

d) Exactly thrice

14) Given the following program construct

{

if ( a == b ) { S1; exit(); }

else if ( c==d ) { S2; }

else { S3; exit(); }

S4;

}

Given 4 test cases, find out which one among the following covers all the 4 statements

T1: a, b, c and d are same.

T2: a, b, c and d are all distinct.

T3: a == b and c != d.

T4: a != b and c==d.

a) T1, T2 & T3;

b) T1, T4.

c) T2, T4.

d) T1, T2 & T4.

15) 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 FCFS in terms of response time

a) I only

b) I and III only

c) II and III only

d) I, II and III

16) Sequences of logical pages access :

1 2 3 2 4 1 3 2 4 1

Implemented Optimal,LRU,FIFO Page replacement techniques.

Then no. of page faults in :

a) Optimal < LRU < FIFO b) Optimal < FIFO < LRU c) Optimal = FIFO d) None 17) Find the no. of page faults for Optimal Page replacement technique in the given sequence of question no. 16.

a) 5

b) 6

c) 7

d) 8

18) Given a simple graph of 6 nodes (note- it’s a simple graph) then tell which of the following is a set of valid graph degrees.

a) 4,4,1,1,1,1

b) 4,4,2,1,1,1

c) 4,4,2,2,1,1

d) None

19)

gcd(n,m)

{

if (n%m == 0)

return n;

n = n%m;

return gcd ( m, n);

}

What is the complexity of calculating gcd(n, m) in worst case?

a) O(lgn)

b) O(lgm)

c) O(lg(lgn))

d) O(lg(lgm))

20)

void f(char * x)

{

x++;

*x = 'a';

}

int main()

{

char * str = "hello";

f(str);

cout << str;

system("pause");

return 0;

}

a) hello

b) hallo

c) allo

d) empty string

SECTION B – Subjective Question

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. Find all the distinct tours of a knight placed on (x,y) of a NxN chessboard.

X,Y Knight can go to 8 positions.(default rule). Write a running code.

## No comments:

## Post a Comment