## SDE-2 Interview Questions

- 0of 4 votes
Take an example of the traditional Iterator interface which has the following methods

Interface Iterator<E>{

public boolean hasNext() {}

public E next() {}

public E remove() {}

}

You are given a list of iterators. You have to design a InterleaveIterator class which implements this

interface and implement the methods:

hasNext() and next()

such that these 2 methods returns interleaved values for the list of iterators:

Implement:

class InterleaveIterator<E> implements Iterator<E>{

@override

public boolean hasNext() {}

@override

public E next() {}

}

Example:

ArrayList<Integer> i1 = [1,2,3,4,5].iterator()

List<Node> i2 = [n1,n2].iterator()

Collection<E> i3 = [e1,e2,e3].iterator()

next() method of InterleaveIterator, should return in this sequence [1,n1,e1,2,n2,e3,3,e3,4,5]

Make this InterleaveIterator class generic and make sure that the class can accept a list of iterators

and interleave them

- 0of 0 votes
Design and Implement: Producers and Consumer Problem. Producers produce different kind of messages and Consumers register themselves for different kind of messages. Need to design and implement Producer, Consumer and a Delegator which is responsible for storing and delivering the messages to appropriate listeners.

Changed the question to handle millions of messages.

Changed the question to handle different priority messages.

Threading model for Producer, Listener and Delegator.

In the end he asked me to code 2 methods of Delegator.

1: which adds the message from Producer to its internal queue.

2: Delegate, which delivers the message to appropriate listener.

- 0of 0 votes
You are given a graph and a node in the graph. Group the nodes connected to this node if they are also connected to each other. For example, the graph has nodes 1, 2, 3, 4, 5 where 1 is connected to 2, 3, 4; 2 and 3 are also connected to each other, 4 is just connected to 1 and 5 is a separate node. You are given node 1 as input. Output should be:

2 3

4

- 1of 1 vote
GIven a string "str" and pair of "N" swapping indices, generate a lexicographically largest string. Swapping indices can be reused any number times.

Eg 1)

String = "abdc"

Indices:

(1,4)

(3,4)

Answer:

cdba, cbad, dbac,dbca

you should print only "dbca" which is lexicographically largest.

- 0of 0 votes
With input as a integer, write an algorithm to convert that to string without using any built in functions. It is a signed number.

Equivalent to String.valueOf(-123); //java

- 1of 1 vote
Given a number print the number of combinations you can derive from the number. 1=A, 2=B, 26=Z, 0=+.

For example: 1123 can be represented by 1,1,2,3 which would stand for AABC.

Another representation - 11,23 - JW

Another representation - 1,1,23 - AAW

Another representation - 11,2,3 - JBC

For number 1123, there will be 5 combinations.

- 0of 0 votes
In a binary tree, find and print the path with smallest weight.

Criteria: the tree contains integer values in the nodes. It may not be balanced tree. Weight is calculated by sum of values in the nodes in that path. Write code that returns the path as well as the minweight.

- -1of 1 vote
Given a circular array of images, in LandScape and Portrait mode. Bidirectional movement in array is allowed.

e.g.

LPPPLPPP

L-> Landscape

P-> Portrait

Cost of Viewing a Portrait image is Vp

Cost of Viewing a Landscape is (Rp(rotate) + Vp).

Cost of movement is -> m

once you visited the image viewing cost is zero if you revisit the image. Only movement cost is considered.

Jumps in array is not allowed.

Calculate the maximum number of images you can see with cost X.

- 3of 3 votes
Given a string e.g. ABCDAABCD. Shuffle he string so that no two smilar letters together.

E.g. AABC can be shuffled as ABAC.

- 0of 0 votes
Given a DNA sequence e.g. AAAGTAAGTAAGTGGG.....

Find all the duplicates with length 10.

- 0of 0 votes
Given a series of number form a binary tree find the minimum weight binary tree. The weight of the node is depth * value of the element + weight of the left tree + weight of the right tree.

Weight of the root node is the weight of the tree . Find the minimum weight binary tree out of all possible binary trees that are possible.

- 0of 0 votes
This was the 2nd round. Face to face. DS and Algo

Q1) Given an array 'A' of size 'n' and a number 'm' such that 'm <= n'. For all subsets of 'A' of size 'm', return the difference between the number of non-increasing and non-decreasing sub-sequences.

He asked me to write the program on paper in any language.

This is how i approached it.

1) First i gave the brute force solution and explained it to him. He liked it.

2) Then he asked for the complexity of the solution. I gave right ans.

3) Then i told him that it can be optimized by 'xyz' approach.

4) Then he asked me if i can write the solution. I said i will first explain him how it can be solved. Then if he wants me to write the code, he will have to leave me alone for some time. He agreed. I explained.

5) There was a bug in my solution. He gave a test case that exposed it. Then i rectified the bug. He accepted.

6) He said that it. He does not need the full code.

- 0of 0 votes
This was the first round. A written test. I was asked to write a complete program that can execute with proper syntax. Also comment on the complexity and add comments to code where necessary. And i had to write it on Paper. Three questions were given and was asked to answer any two. I was given 1hr time for this.

This was one of the questions

Q) You are given a BST and a number k. Find the node in the tree which has the value closest to k.

- 0of 0 votes
This was the first round. A written test. I was asked to write a complete program that can execute with proper syntax. Also comment on the complexity and add comments to code where necessary. And i had to write it on Paper. Three questions were given and was asked to answer any two. I was given 1hr time for this.

This was one of the questions.

Q) You are given a linked list and two integer nums 'm' and 'n'. Retain 'm' elements and delete 'n' elements. Do this repeatedly till the end of the linked list.

- 0of 0 votes
What data str should we use to store restaurants(having location info), So that we can easily find the list of restaurants near my current location ?

- 0of 0 votes
Given login/logout time of all users for a particular website in below form.

userId, login time, logout time.

Now store this data in some data structure, so that we can efficiently query total number of users who logedin and logedout in given time range.

- 1of 1 vote
Given an array of 0s and 1s, and k, Find the longest continuous streak of 1s after flipping k 0s to 1s.

E.x array is {1,1,0,0,1,1,1,0,1,1}

k = 1 (which means we can flip ‘k’ one 0 to 1)

Answer: 6 (if we flip 0 at index 7, we get the longest continuous streak of 1s having length 6)

- 0of 0 votes
Design a chat application. How will u handle huge data?

- 0of 0 votes
Design an online pizza delivery system. Complete OO Design needed.

- 0of 0 votes
Organization has online services running across world. To use online services, User create account by entering personal details like - First Name, Last Name, Phone number, Address and etc...

Russia has passed new law that any Russian citizen who is creating account to use online services, his account information needs to store in Russia first and then read-only copies allowed to replicate across the world.

Please suggest cost effective solution/design for this scenario otherwise online services will be blocked to use in Russia. How do we handle if any other country Germany is also come up with this law?

Issues:

1. Do not have mechanism to identify citizenship of user.

2. If Russia user creates an account, he/she should not wait to use online services.

What is cost effective solution?

- 0of 0 votes
Implement a finite state machine.

– The machine should have one start state and can have multiple end states

– It should be extensible (I should be able to add any number of states or transitions at any time)

– I should be able to set notifications on or off for any state or for the whole state machine

- 0of 0 votes
You are given some equations which may contain > or = on different-different operand. For example there are valid input and invalid (a=5, b<a=50)

String e1 = "a>b=1";

String e2 = "a>b=2";

String e3 = "a>c>e=3";

String e4 = "a>c>f=4";

String e5 = "b>a=5";

String e6 = "a>b>c=5";

String e7 = "b=7";

String e8 = "a>b>c>d=99";

String e9 = "a>b=99";

You need to create JSON string from it.

{

‘a’: {

‘b’: [1,2,99],

‘c’: {

‘e’:3,

‘f’:4

}

},

‘b’: {

‘a’ : 5

}

}

Input: You are given those string in string array

Output:

Construct JSON

Print it

- 0of 0 votes
There is down-turn in the ship-building industry. Ace Shipping Corp (ASC) wants to be prepared by having a system that will help evaluate the total cost saving they will achieve if they were to ‘let go’ some employees.

Following are the rules for drawing up this Firing List:

Each manager at every level in the organization will have to contribute ‘heads’ from his team to the firing list

The input to the system would be a small integer k (=1,2, etc) which would be the number of employees chosen per manager. The output would be the total cost saved for this k. Different values of k would give an idea of the total cost saving achieved.

The primary selection criteria is Performance Rating. k employees with the minimum rating under a given manager are to be selected.

If two employees have the same rating, the one with the higher salary gets selected (to maximize cost saved)

The activity might be requested for the sub-org under any manager. The default is to consider the entire org.

Although total number of reportees for a manager is usually of the order of 10, it could possibly be a much larger number in some org too. An optimal way of choosing the k reportees would be preferred.

The following information needs to get stored per Employee:

Employee ID (unique)

Name

Performance Rating (1-5, 1 is lowest, 5 is highest)

Salary (Rs)

- 0of 0 votes
Description:

A company, create classes for each type of employee and calculate working hours and wages/salaries that will be received.

Example General Manager, IT Manager, Accounting, Marketing, Finance, Procurement Managers

Manager and Higher level employees wont have overtime wage. Overtime wage is 1.5 times higher than the usual wage. Working hours are limited as 8 hours. More than this limit will be considered as overtime.

Inputs:

Employee Name, Surname

Title/Role

Salary

Daily Working hour

Outputs:

Date

Employee Name, Surname

Daily Wage.

- 0of 0 votes
There is a car company and customers ask the car company for 'n' cars for start - end time intervals.

A company can get multiples request for the cars, find the minimum numbers of cars that the car company should have, to satisfy all the requirement for the given list of time intervals:

Eg :

for interval 1-3 cars needed are 2

for interval 2 -3 cars needed are 3

for intervals 3-4 cars needed are 4

for intervals 5-6 cars needed are 2

Answer is 5 for above, as we there is overlap between interval 1-3 & 2-3

- 0of 0 votes
I have a photo storage service. The actual photos are present in some storage and the index of these photos is present at some other place. The index is huge, say trillions of photos. Design the class for index node of each photo (with attributes like name*, date*, size*, accesscontrol, camera details, shot details, etc) such that 1. It is serializable. 2. For faster processing, I am interested in first 3 attributes. When deserializing the bytes of object, parse these 3 attributes i.e. instead of deserializing whole class, deserialize only part of the class (members marked by*), other members of class should be deserialized on demand with another call.

How will you test the performance of your serialization/ deserialization?

- 0of 0 votes
there is a chess board of dimension n X n. You are given with 2 squares on that board S(x1,y1) ;M(x2,y2). S is a fixed point. M can move diagonally. it can move any number of steps or jumps in 1 move . Find the minimum number of moves M needs to reach S

- 1of 1 vote
there is a news publishing/subscribing product of Amazon where electronic contents are collected from owners like newspaper, magazines. Customer is using kindle. Design how customer will get the content when his system kindle connects to net. how to send the contents to device?

- 0of 0 votes
This was a design question, discuss data structures/ complexities, etc.

There is a huge HashMap (Key-Value store). This is present in storage, dont worry about the Storage.

1. Build its index. Distributed system for indexing. Different cases: Key is a String/ Double/ complex structure, etc. How will you replicate this index structure - whole index is replicated/ parts of index are replicated.

2. How will you synchronize access (read/ write) if there are multiple replicas of the index partition. What if the actual Storage partition also has replicas.

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