**oding Round 1 (90 min) :**

Q1(Simple brute force solves 12 testcases….O(n) using dequeue solves all 13 testcases) - Max Subarray problem

Q2(Simplest Greedy)

Activity Subselection Problem

Q3(Dynamic Programming)

**Coding Round 2 ((25 min + 15 min extended)):**

1 Question

There is a tree..we are given n denoting the number of nodes….and we are given (n-1) nodes pair between which edges exist….Now, a edge is like a light chain which can be turned on by switching on(i.e. selecting) any one of the nodes it belongs to(an edge will have 2 nodes :p).The edge will be on even if only one of the nodes is selected and even if both are selected but it will be off if neither of the 2 nodes are selected. Now, we need to find the minimum number of nodes that we need to select(i.e. turn on) so that all the edges are turned on…..

Sample input(n and then (n-1) pairs)

5

1 2

1 3

2 4

3 5

3 6

Output(single integer)

2

Explanation:

Turning on the node number 3 and 2 will turn on the entire range of edges.

There is a tree..we are given n denoting the number of nodes….and we are given (n-1) nodes pair between which edges exist….Now, a edge is like a light chain which can be turned on by switching on(i.e. selecting) any one of the nodes it belongs to(an edge will have 2 nodes :p).The edge will be on even if only one of the nodes is selected and even if both are selected but it will be off if neither of the 2 nodes are selected. Now, we need to find the minimum number of nodes that we need to select(i.e. turn on) so that all the edges are turned on…..

Sample input(n and then (n-1) pairs)

5

1 2

1 3

2 4

3 5

3 6

Output(single integer)

2

Explanation:

Turning on the node number 3 and 2 will turn on the entire range of edges.

Interview Round 1(Time – 1:15-1:30)

Interview Round 1(Time – 1:15-1:30)

Q1

Maximize XOR of 2 numbers….(best solution is using trie)

Q3

A dictionary with many given words…given a string with random missing spaces, find all the valid possible correct outcomes of the string.

Solved using recursion…didn’t complicate too much..

next he added that the dictionary also contains the count of the number of times it has previously occurred. I was asked based on that what parameter will i use to determine which of those possible outcomes of string is most likely?

Eg >

d[]={ a=2 ; ab=4 ; c=3 ; bc=5} solve for string “abc”

Here 2 possibilities are

1. a…bc ::we have count for each “a” and “bc” as x=2 and y=5

OR

2. ab…c :: we have count for each “ab” and “c” as x=4 and y=3

Took a page out of my project, in FCM, we use distt formula between a point and cluster centers to decide the membership function of the point being a part of the cluster..In this case i used distance formula from center(sqrt(x^2 +y^2)) as the value to decide the better possibility of the string..The farther from the center, the more likely it is….

A dictionary with many given words…given a string with random missing spaces, find all the valid possible correct outcomes of the string.

Solved using recursion…didn’t complicate too much..

next he added that the dictionary also contains the count of the number of times it has previously occurred. I was asked based on that what parameter will i use to determine which of those possible outcomes of string is most likely?

Eg >

d[]={ a=2 ; ab=4 ; c=3 ; bc=5} solve for string “abc”

Here 2 possibilities are

1. a…bc ::we have count for each “a” and “bc” as x=2 and y=5

OR

2. ab…c :: we have count for each “ab” and “c” as x=4 and y=3

Took a page out of my project, in FCM, we use distt formula between a point and cluster centers to decide the membership function of the point being a part of the cluster..In this case i used distance formula from center(sqrt(x^2 +y^2)) as the value to decide the better possibility of the string..The farther from the center, the more likely it is….

Interview Round 2(Time – 30-45 min)

Interview Round 2(Time – 30-45 min)

Q1

Just like in Q2 of Interview Round 1, there r n houses wid given heights in an array…We have a paint brush that paints any length and width in one stroke given that it is continuous and has no blank spaces in between…U r allowed only horizontal/vertical paint strokes…Find minimum number of strokes needed to paint all the buildings without causing any spill…

It was simple enough… create a func(f) find the minimum val of the array and then call func(min->right) and func(min->left) and add them and add 1 extra.. I gave this soln in less time and optimized O(n) soln and he seemed happy wid it…

Q2

I first gave a simple soln using a map pair but he asked me how would i store the map so that i wouldn’t have to check which came first…So, i used a doubly linked list similar to the solution in the given link…

I first gave a simple soln using a map pair but he asked me how would i store the map so that i wouldn’t have to check which came first…So, i used a doubly linked list similar to the solution in the given link…

I did well in both these round and was called for the HR round eventually.

HR Round

HR Round

It was one of the best interview i have ever had. Discussed about my projects, college life, internship , interests, strength, weakness and about what i consider a good life, a good job and how susceptible will i be to change in role within the company etc..

## No comments:

## Post a Comment