## SDE-2 Interview Questions

- 0of 0 votes
Fill the arrow with zeros in n*n matrix.{{0,0,0,0,0,0,0

0,0,1,1,1,0,0

0,0,1,0,1,0,0

0,0,1,0,1,0,0

0,1,0,0,0,1,0

0,0,1,0,1,0,0

0,0,0,1,0,0,0}}

- 0of 0 votes
Given a math expression in string format that contains only + & - and numbers. Return the sum in integer format. Eg: Input: "3+4-7+13" Output: 13.

"2+1-8+13" Output: 8

- 1of 1 vote
Print words in order which are occurring once in huge document. The RAM size 100MB and file size 10 GB.

Example: I am good. You are good.

Answer : I am You are

Note : It's not datastructure problem where we can simply make use of LinkedHashMap. The file size is going to be huge.

- 0of 0 votes
I participated interview event with Amazon and receive email from Amazon recruiter that the team was happy with my performance and would be giving me offer at Amazon Vancouver Office, Canada. However,17 days later i still not get an official offer. I did several follow up with the recruiter within the period, just to get some "they are finding team for me" response. What could go wrong? Why is it in my case that the offer is being process so slow?

- 0of 0 votes
given two array of elements representing the connection Nodes output the topology used?

Topology can be either Bus , circular or Star

input:

Number of nodes 3

Number of Connections : 2

{1,2}

{2,3}

Output Bus

Explanation

the topology formed would be 1->2->3 . hence Bus

input

number of nodes : 3

Number of connections : 3

{1,2,3}

{2,3,1}

Output: Circular

the topology formed is 1->2->3->1

hence circular

input:

number of nodes : 5

Number of connections : 5

2 3 4 5

1 1 1 1

Answer : StarTopology

Explanation : A star can be formed with this input

2 4

1

3 5

StarTopology

- 0of 0 votes
Design a system which helps to calculate average Skype call duration per day. In which events are tracked from mobile app. Need to take care of all edge cases like events can be logged to server in any sequence & there can be some events missing on server side also.

- 1of 3 votes
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

- 0of 0 votes
Design online multiplayer generic board game (like chess). How will you store sessions.(RDBMS or REDIS) How will the

competitor be chosen and notified(HTTP or what?).

What are the appropriate classes?

- 0of 0 votes
Design Recommendation system. How will you generate generate recommendations for millions of users. DB Schema, How will you improve latency? if the user is searching a item, when will you show next recommendations. How will you update, latency basically and consistency.

- 0of 0 votes
You are provided with 2D char array. You have to provide the 2D char array as response which contains the multiplication od the input array. For eg: input=> {{a,b},{c,d}}, output => {{a,c},{a,d},{b,c},{b,d}}

- 0of 0 votes
You are provided with different Excel files and the data format those files contain. You are also provided with low level parser. You have to design a system which takes the excel file and its data type as the input and returns the list of Data objects in the file.

- 1of 1 vote
Design JProfiler. How will you design datastructure and why, function stacktrace. HLD+LLD

- 0of 0 votes
Design a Fresh Grocery System. Means Daily usable Items, you cannot store them in inventory like bread, milk etc.

HLD+ DB Schema + Concurrency issues + Scalable architecture. How will you scale to multiple countries

- 1of 1 vote
How to develop a web based multiplayer chess game. There will be 2 player in each session. There will be multiple sessions.

My answer(I was not selected)

Each player will have a database with columns

user id(primary key), passwd,no of games played, won,drawn,last active time,sq1,sq2,...sq64,move made flag,pawn num, sqstart,sqend

where sq1-denotes square 1 and its value represents the pawn num in sq1

question- what all fields in database will be encrypted

answer-passwd

question- why not others

answer-may be system admin needs to access them

question – how will u start a session between players?

Answer-When a player logs in, his last active time is updated. Each player is shown a list of last active players to chose from.Or system can arbitrarily select one.When a player is selected, he gets a request. Each player receives a list of requests from other players. He choses from one. That player gets an acknowledgement others get negative acknowledgement. If acknowledgement does not come in time then that player is dropped and another player is selected.

Question- http connection, can not send request from server. How the 2 players will send request to each other and how session will be initiated?

Question-how the game will be stored?

The 64 squares sq1,sq2,..sq64 will each store the pawn number in them. From random number calculatio, it will be decided which one is white and which one is black 1st time. When a player makes move,has made move flag will be true. The last move is stored as sqstart,sqend,pawn number. Each time a move is made check for valid move.The other player continuously polls for has made move flag to know if it is his turn

remarks- ur design is not scalable.

- 0of 0 votes
You are given a Log that contains UserId, ProcessId, Start Time, End Time and Resource Consumption during that time, you need to find out the user who has utilized the most resources.

Example:`UID PID StartTime EndTime Consumption`

`1 1 200 300 100`

`2 2 230 340 80`

`1 3 245 315 50`

`1 4 305 330 20`

Time 200 signifies: 02:00.

Output: UID# 1

UserID 1 because he has consumed the most number of resources between 200 to 315 (Resource Consumption: 150).

- 1of 3 votes
Design an order tracking system using the below constraints.

Once an order is received, it will be assigned to a delivery boy and sends notification at every stage of the order such as order received with expected time of delivery, delivery boy assigned, order picked up, order delivered.

State how your design will help scale and what will be the performance SLAs that will you will set for your design. The system should be able to horizontally scalable from hundreds of orders to million orders and should perform at almost the same level irrespective of the number of orders received.

- 2of 2 votes
Singleton Design pattern. How you make it double ton(in even call of getInstance() first object should be return and odd call of getInstance() second instance should be return). Make it triple ton.

- 1of 1 vote
Print series 010203040506. Using multi-threading 1st thread will print only 0 2nd thread will print only even numbers and 3rd thread print only odd numbers.

- 0of 0 votes
Add a digit to a number that is represented by a linked list, where each node is a digit of the number. The linked list couldn’t be modified, except the digits to be modified in answer and the number could be infinitely long. Need to do it in O(1) space.

- 1of 1 vote
Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

- 0of 0 votes
Maximum difference between node and its ancestor in Binary Tree in O(n) time.

- 0of 0 votes
Given a very large binary number which cannot be stored in a variable, determine the remainder of the decimal equivalent of the binary number when divided by 3. Then generalize to remainder of any number 'k'

- 2of 2 votes
Given a pre-order traversal, construct a binary search tree in O(n) time.

- 0of 0 votes
Given a large text file, find an efficient algorithm to find the least distance(measured in number of words) between any two given words.

- 0of 0 votes
Given a set of start date and end date design a data structure to return a given date falls in.

Example

1Sep 2016 - 10 Sep 2016

1 Jan 2009 - 31 Aug 2015

given 12 Jan 2014 should return 1 Jan 2009 - 31 Aug 2015

- 1of 1 vote
You are given a text file. You have to return the list of starting index of the given word in text file. Design an efficient DS for that.

Example :-

Text file content : “geeks for geeks”

word : “geeks”

List : {0,10}

- 0of 0 votes
In a file, there are two columns, first column has some word (String) and 2nd column has some value (Double).

Example :-

ABC 23.4

ERF 34.89

WERT 122.9

Now user wants some arithmetic operations like

1) ABC + ERF = 23.4 + 34.89 = 58.29

2) ABC – WERT = 23.4 – 122.9 = -99.5

Design an efficient DS for these kind of operations.

- 0of 0 votes
There are n Thread , n/2 thread are producer and n/2 are consumer, number produced by producer-1 thread must be consumed by consumer-1 thread. Thread must also run in order, producer 1, then consumer 1, again producer 2 and then consumer 2…so on…..

- 0of 0 votes
Implement function which add n days to given date without using inbuilt library.

- 0of 0 votes
You are given a set of N horizontal lines which are connected by equal number of vertical lines to form squares of size 1x1. Now some segments are removed. You need to count the number of squares of all sizes (1x1, 2x2, ..., NxN) with all sides present.

Image : https://he-s3.s3.amazonaws.com/media/uploads/1ce3516.png

In the above example you see four horizontal and vertical lines and few missing segments. Now you need to count the number of squares of all sizes with all sides.

Input :

First line is a positive integer N, number of horizontal and vertical lines.

Second line is positive integer M, number of segments removed.

Then there are m lines, each containing V,i,j or H,i,j where i and j are positive integers. H,i,j indicates a horizontal missing segment in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in ith vertical line between the jth and (j+1)th point on the line.

Output :

Is the total number of squares in the figure with all sides along the remaining lines in the figure.

Sample Input :

4

4

H,2,1

H,3,1

V,2,2

V,2,3

Output :

5

Explanation : Here in this figure we have 4 squares of size 1x1 and 1 square of size 3x3, hence total is 5.