## Recent Interview Questions

- 0of 0 votes
Given an N-ary tree with thousands of nodes, pair the leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have a common edge that was used in a previous pairing.

For example,

A

/ | \

B C D

/ / | \

E F G H

Leaf nodes: E, F, G, H & D

Possible Pairs in O/Ps:

a) (E-F), (G-H) or

b) (E-G), (F-H) or

c) (E-H), (F-G) or

d) (E-D), (F-G) or

e) (E-D), (G-H) or

f) (E-D), (F-H) or

g) (D-H), (F-G) or

h) (D-G), (F-H) or

i) (D-F), (G-H)

Note: If we pair(join) say, (E-F) then we can NOT pair any of the (D-G) or (D-H) as they SHARE the COMMON path from A to C.

i.e. E-B-A-C-F —> (E-F) pair

D-A-C-G —> (D-G) pair

D-A-C-H —> (D-H) pair

So the above case is NOT possible

- 0of 0 votes
On a screen, there are multiple rectangles drawn, when a user clicks on any point, find the smallest rectangle enclosing this point.

I could not come up with a solution. The end points of rectangles were given and also the the point where the mouse was kept was given.

- 0of 0 votes
Sort a matrix such that rows in ascending order and columns should be in descending order.

- 0of 0 votes
Input Parser and Processor

Problem

Implement a java program for querying data from a java object. Java object need to be constructed based on text data provided to program.

The parser should be generic to parse any input confirming to the hierarchical format similar to the one mentioned in sample

The Content of the file

[employee]

name=john

age=30

salary=100

[address]

houseno=221b

street=bakerstreet

[location]

place=xyz

state=abc

country=123

[/location]

[/address]

designation = srDeveloper

[/employee]

Sample Input and Output

employee.name Output John

employee.address.houseno Output 221b

employee.address.location.state Output abc

employee.manager Output NOT_FOUND

The program should work any object data specified as input file.

- 0of 0 votes
Tech Screening

Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry.

Interviewer was expecting O(N) solution for N asks.

Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks.

and integers are not given in a array, every time only one integer will be passed as input to your method.

- 0of 0 votes
Skynet

Skynet has grown to become the dominant force on earth and has almost completely wiped out the

human race. Skynet has been

building robots ever since it's inception and has been updating it's models every year while making

them better. Skynet wants to annihilate humanity completely. It plans to remove one last band of

humans lead by John Connor. Skynet thinks it can destroy these humans using only two of it's robots.

But Skynet doesn't want to send two robots with the same model number lest John Connor finds out a

weakness in that model and easily destroy both of them.

Skynet has at its disposal N robots and to save space Skynet has stored information about pairs of

robots belonging to the same model. If it doesn't have any info stored for a particular robot then it is

implied that the robot is the only one in that model.

Given these constraints, in how many ways can Skynet pick two robots to destroy John Connor and

his rag tag group of humans.

Inputs

N Total

number of robots. Each robot is assigned a number from 0 to N1

(2 <= N <= 100000)

P Number

of pairs for which Skynet has information (2 <= P <= 100000)

This is followed by P pairs. Each pair has two numbers P and P each where 0<=P <=N1

and

0<=P <=N1

and P != P

Output

Number of ways in which Skynet can select 2 robots such that both the robots are different models.

Example Input:

4 2

0 1

2 3

Example Output:

4

Explanation:

Here robots 0 and 1 are of one model, say model A. And 2 and 3 are of another model, say B.

Therefore the total number of

possibilities of picking 2 robots such that no two robots are of the same model are (

0, 2), (0, 3), (1, 2)

and (1, 4) = 4

- 0of 0 votes
Round 3

Question 1, you are given a puzzle, You can check the image here`https://drive.google.com/file/d/0B6-TjTC-KfTqQThBamxPa0NwNGM/view?usp=sharing`

You have to write a program to provide a solution for this.

- 0of 0 votes
Round 2

Question 1: Design a traffic signalling system for a city.

1.a : think as you were asked this question in a high level meeting with leadership teams, what would you do at that time ?

1.b : what are the check-list/to-do you will do before start of your project.

1.c : how will you go over each and every check-list/to-do

1.d : Once you have done all this, what are the design principle you will follow.

1.e : what kind of system you would choose(I gave distributed/centralized)

1.f : Tell me the pros and cons of these type which you have listed

1.g : how do you go over your goal.

1.h : how will you make the cons go away from one system which out changing it to another type(like possible modification).

1.i : How will to achieve your goal which was given to you by LT team.

1.f : Now lets write the code for a road intersection, make it generic enough both in terms of colors, and ordering, so what it can be used anywhere.

Note that : a road intersection may have many traffic lights one for each side of the roads

- 0of 0 votes
Round 1

Question 1.a

You are given a stock market feed of a single stock.

It contains the change over the previous value. you have to find out the max gain one can get out of it.

Example : -1, 2, 6, -5, -3 7, -3

Days 0 1 2 3 4 5 6

Answer is buy before day 1 and sell it after day two.

WAP for this.

Question 1.b : How do you make the changes in previous code to return the maximum loss. Please note that the changes should be minimum only.

Question 1.c: Lets undo the Question 1.b's additional changes, and now lets you are given a limit on how many days one can hold the money, lets say "k", which means, the investor will give you the money for k days only. you have to again make the additional change to figure out the optimal start date and end date.

Few Example

input : -1 -6 10 2 -5 20 5 -10 6

days 0 1 2 3 4 5 6 7 8

Max Gain : End of first day to end of 6th day, amount is 32.

Max Loss : End of 6th day to end of 7th day, amount is -10.

if K is 3 then the max gain is 25, which is end of 4th day to end of 6th day.

Edits : Interviewer was expecting O(N) solution here.

- 2of 2 votes
You are given four integers 'a', 'b', 'y' and 'x', where 'x' can only be either zero or one. Your task is as follows:

If 'x' is zero assign value 'a' to the variable 'y', if 'x' is one assign value 'b' to the variable 'y'.

You are not allowed to use any conditional operator (including ternary operator).

Follow up: Solve the problem without utilizing arithmetic operators '+ - * /'.

- 0of 0 votes
Not sure what topic this falls under.

"Improve metrics on the system."

Intentionally vague requirement to see how I ask questions. In my case, it ended up being a discussion about making database queries faster.

- 0of 0 votes
Given a string such as "123", convert it to an integer. Basically, write Integer.parseInt(string).

- 0of 0 votes
Given a CSV of names and ages, perhaps:

Alice, 30

Bob, 17

Clyde, 49

Sort the names by age.

- -1of 1 vote
Given a List of Strings, return the number of sets of anagrams.

For instance, given:

<abc,cab,dac,beed,deb,few,acd>

return 5

- 0of 0 votes
A paper consists of a series of consecutive numbers from 1 up to 2^n values. For example,

For case 2^1, content of the paper is,

1 2

For case 2^2, content of the paper is,

1 2 3 4

For case 2^3, content of the paper is,

1 2 3 4 5 6 7 8

There will be n number of commands for 2^n case. Below are the commands,

L – Fold the paper from Left edge to Right edge

R – Fold the paper from Right edge to Left edge

After performing the n number of commands, there will be a single number in all layer of paper, you need to write down the numbers in all layers when you see the paper from upside of it.

Please provide an efficient algorithm.

Example:

Content of the paper (2^3):

1 2 3 4 5 6 7 8

Commands: LRL

Output:

5 4 1 8 7 2 3 6

- 0of 0 votes
Q: Print out the number that is a duplicate in this unsorted array.

My follow up clarification questions:

Are the pairs always guaranteed to be sequential? Yes

Do we always know the size of the array? Yes

Will there always be just one number that does not have a pair? Yes

Original problem:`int main() { int pairs[] = {1,1,7,7,3,3,19,19,4,10,10,11,11,15,15,2,2}; }`

My solution:

`void PrintDuplicate() { int pairs[] = { 1, 1, 7, 7, 3, 3, 19, 19, 4, 10, 10, 11, 11, 15, 15, 2, 2}; int size = 17; bool numberFound = false; for (int i = 0; i < size; i += 2) { if (i + 1 > size || pairs[i] != pairs[i + 1]) { std::cout << pairs[i] << std::endl; numberFound = true; break; } } if (!numberFound) { std::cout << "All pairs matched" << std::endl; } }`

I believe this should give an O(n log n) solution with no extra space necessary.

After this solution they gave me a hint about using a binary search or a BST.

I do not see how that would have made this solution better than mine. Taking the array then moving the data to a BST would just be duplicating the process.

You could use a hashtable and every time you encounter a number see if it matches one you have already found, but that is only useful if this was an unsorted array.

What are the thoughts on my solution and why they would have gave me a hint at using a BST or a binary search on the array?

- 0of 0 votes
You have a function f1() that generates 0 or 1 with the equal probability. Write a function f29() that generates a number between 0 and 29 with equal probability.

- 0of 0 votes
Given two numbers a=12, b =36 write a method that return an integer value c=3612, with out using arithmetic and string operations.

- 0of 0 votes
Given a pond where all the stones are lined at a distance of one unit (C in each row and there are R such rows).

Each stone has a special value which denotes the length of the jump the frog can make i.e if frog is on stone (x,y) and value is k then frog can jump to (x+dx,y+dy) where dx+dy=k and frog doesn’t leave the bounds.

Find the min number of jumps to reach the stone at (R,C). Also print the path taken by frog to reach the stone.

- 0of 0 votes
Given 1000 elephant ,none of whom exact heights are known, there are statements given which will be of two forms

i- E_i is taller than E_j

OR

ii- E_i is smaller than E_j

Calculate the ascending order of the elephants(in terms of height).

For ex-

1) E1 is taller than E3

2) E3 is smaller than E2

3) E2 is taller than E1

Then order would be E3, E1, E2

- 0of 0 votes
Design a cache module for an image server. The server accepts image requests from users and sends them back the images. The cache should always hold in-memory the 10 most recently requested images. The cache should also support multiple requests simultaneously

- 0of 0 votes
Find the most frequent element in an array in logn time.

- 0of 0 votes
Given a 5 x 5 Grid comprising of tiles numbered from 1 to 25 and a set of 5 start-end point pairs.

For each pair,find a path from the start point to the end point.

The paths should meet the below conditions:

a) Only Horizontal and Vertical moves allowed.

b) No two paths should overlap.

c) Paths should cover the entire grid

Input:

Input consist of 5 lines.

Each line contains two space-separated integers,Starting and Ending point.

Output:

Print 5 lines. Each line consisting of space-separated integers,the path for the corresponding start-end pair.

Assume that such a path Always exists.

In case of Multiple Solution,print any one of them.

Sample Input(Plaintext Link)

1 22

4 17

5 18

9 13

20 23

Sample Output(Plaintext Link)

1 6 11 16 21 22

4 3 2 7 12 17

5 10 15 14 19 18

9 8 13

20 25 24 23

- 0of 0 votes
Let's say I am setting up my company and it has three buildings(B1,B2,B3). The company has both permanent employees and contractors. Permanent employees can access all the buildings and contractors will have access only to building B3. How do you get started with the design?

- 0of 0 votes
Implement an iterator in java. It should be thread-safe

- 0of 0 votes
Write a function to print Tree which can have any number of nodes, in level order each level in new line.

1

2 3

4 5 6

if above is tree then answer should be,

1

2,3

4,5,6

- 0of 0 votes
Write a function to print Tree which can have any number of nodes, in level order each level in new line.

1

2 3

4 5 6

if above is tree then answer should be,

1

2,3

4,5,6

- 0of 0 votes
Convert a string to it's permutated string using only adjacent Swapping. e.g. CAT, TAC

Output: CAT, CTA, TCA, TAC

- 0of 0 votes
Tech Screening round

Q.1 : a non decreasing sorted array is rotated by some random amount, write a routine to figure out this random amount.you can consider the clockwise rotation.

Write the test cases for it.

Interviewer wanted to see prod ready code.

- 1of 1 vote
Serialize & Deserialize a binary tree