## SDE-2 Interview Questions

- 0of 2 votes
Given a list of shops each of which have a list of toys with their prices and max number of children who can play with it at a time. Output the a list of best possible toy option from each shop given the number of children who are shopping.

ToyShopping

{

getListOfBestToysFromEachShop(List<Shop> shops);

}

Shop

{

int id,

List<Toy> listOfToys;

}

Toy

{

int toyId;

int shopId;

int price;

int maxChildren; //max number of children who can play with this toy

}

- 0of 0 votes
Design the classes for a Battleship Game. Write the attack function.

- 1of 1 vote
Write a program to check whether it is a valid binary tree or not. Check all test cases (e.g. No left Node case).

- 0of 0 votes
Given (a,b) can you reach to (c,d) if a and b can move either (a+b,b) or (a,a+b). Example a =1, b=4,c=5,d=9 then (1,4) -> (5,4) -> (5,9)

- 1of 1 vote
Design a logging system. The system contains multiple application servers which are logging the information to file system. In this scenario, we want to check and alarm in case an exception is thrown in any of the servers. We want a system that checks for appearance of specific words, "Error", "Exception", "Disk Full" etc. in the logs of any of the servers. How would you design this system?

What if we want to scale the system in future?

- 0of 0 votes
We need a functionality to block an user who makes more than 10 requests in last 5 minutes. You need to implement the following function.

{{

boolean block_user(int user_id)

{

//TODO: return true in case u want to block user

}

}}

- 0of 0 votes
object oriented design for robot vacuum cleaner.

write use cases, draw class diagram and interfaces

between them.

- 1of 1 vote
Design a deck of cards that can be used for different card game applications.

Please code out what you would need for the deck class and a card class.

Implement a deal method.

- 0of 0 votes
Design a system for searching strings in files present on a fileserver under a directory. there won't be any sub-directories. There could be more than thousand/lakhs files. And the file size could be in GBs. The matching line should be written to a single file. user will execute grep "string"

The sub-questions are

1) Design where the application executes on single machine.

2) Design where the application can execute on multiple machine.

3) Where could be the potential bottleneck.

4) What component would be bottleneck if 50 cores and slow disk.

5) What component would be the bottleneck if we 4 cores and fast disks.

- 2of 2 votes
You have two very large numbers that cannot be stored in any available datatypes. How would you multiply them?

How would you multiply more than two numbers?

- 0of 0 votes
How will you implement a dictionary.

- 0of 0 votes
Design a monitoring system for hotel booking site. Proper oops design.

- 1of 1 vote
Given two strings, print all the inter-leavings of the Strings in which characters from two strings should be in same order as they were in original strings.

e.g.

for "abc", "de", print all of these:

adebc, abdec, adbce, deabc, dabce, etc, etc

- 2of 2 votes
Given a matrix of positive integers, you have to reach from the top left corner to the bottom right in minimum cost. You can only go one square right, down or diagonally right-down. Cost is the sum of squares you've covered. Return the minimum cost.

e.g.

4 5 6

1 2 3

0 1 2

Answer: 8 (4+1+0+1+2)

- 2of 2 votes
Find the length of maximum number of consecutive numbers jumbled up in an array.

e.g.: 1, 94, 93, 1000, 2, 92, 1001 should return 3 for 92, 93, 94

- 2of 2 votes
A program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35

- -1of 1 vote
This is a interview question which needs to be optimized for time.

Suppose you have a 2 dimensional Array and you have a String say "Amazon" inside the Array such that the individual characters can be present from Left to Right, Right to Left, Top to down and down to up.

I will explain with example :

char[][] a = {

{B,B,A,B,B,N},

{B,B,M,B,B,O},

{B,B,A,B,B,Z},

{N,O,Z,B,B,A},

{B,B,B,B,B,M},

{B,B,B,B,B,A}

};

The above Array has two Amazon Strings. You need to return the count of number of such strings present.

- 1of 1 vote
Find the height difference between two nodes in a binary tree.

`1 2 3 4 5 6 7 8 9 10`

For example: For a given tree above, what would be the height difference between node 4 and node 10?

- 0of 0 votes
Milly and Pranjul are playing a game in which Pranjul will give an index of a chocolate.

Then, Milly has to tell him the box number in which that chocolate is in. There are N

such boxes and Ci chocolates are there in ith the box. Description of index is given below

:

Suppose there are A1, A2 … AN chocolates in 1st, 2nd… Nth boxes respectively. So,

indexing of chocolates in 1st box will be from 1 to A1, similarly in 2nd box indexing will be

A1 + 1 to A2 … and indexing in Nth box will be from AN-1 + 1 to AN.

Milly is blind folded so she can’t see the boxes. You are required to help her.

Input

First line will contain N (No. of boxes). Next line will contain N space separated

integers denoting Ci, the number of chocolates in ith box.

Next line will contain Q (No. of times Pranjul will ask her). Then each next Q lines

will contain the asked index I.

Output

For every query, print in a new line : the box number in which that index of

chocolate is in.

Constraints

1 ≤ N, Q ≤ 105

1 ≤ Ci ≤ 10

1 ≤ Σ Ci ≤ 106

1 ≤ I ≤ Σ Ci

- 0of 0 votes
Given input format, The first line has the number of employees of a company Z. The next two lines have employees to perform certain operations on. The first employee of the fourth line can be assumed to be the ceo of the company. Each line from then on has the format Employee X Employee Y where X manages Y. (and hence Y forms the child for X).

input:

6

Rajesh

Ravi

//Tree Starts here

Ram Raj

Ram Goku

Raj Rajesh

Raj Richa

Richa Ravi

Its known that each person in the company can directly line manage a maximum of 2 other employees.

For the two employees in the first two lines, find the lowest common manager.

How to construct this tree in java to eventually do an lca?

- 1of 1 vote
You are given an old touch smartphone numbers having dial pad and calculator app.

The goal is to type a number on dialpad.

Calculator have 1-9 and +,-,*,/,= as operations. But as phone is old, some of the numbers and some operations can't be touched.

But you can always make a number using other numbers and operations. There could be multiple ways of making a number. You have to find minimum operation for making a number.

For ex: lets say 1,4,6,7,8,9 works and +,-,* works.

2,3,5 and / doesn't work.

If you have to type 18-> 2 operations. (Each touch is considered an operation)

If you have to type 5 -> '1+4=' that requires 4 operations. There could be other ways to make '5'.

The goal is to find minimum operations.

- 0of 0 votes
Design for online card game say like poker or any other game. The classes etc..

- 0of 0 votes
Design Food Panda or online food ordering system.

- 1of 1 vote
Chess Knight Problem: - It deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location.

- 2of 2 votes
Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).

Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.

Note: all coordinates are real numbers

(a,b)

|----------------------------------------------|

|.......................................................|end

|.......................................................|

|start................................................|

|.......................................................|

|----------------------------------------------|(c,d)

Edit: You have to avoid sensors.

Also u can move in any direction any time.

- -1of 1 vote
Given a matrix which is spirally sorted. Remove an element and insert another element maintaining the sorted order.

- 0of 0 votes
Given two sets of strings A and B. Find the

(A-B) U (B-A) ( U = union ). The answer should be in lexicographical order and A’s elements should appear before B’s.

- 0of 0 votes
Given a few points in first quadrant – (x1,y1) …..(xn,yn) and given another set of points (a1,b1…..an,bn), determine whether all the points (a1,b1…an,bn) have already occured in (x1,y1)…..xn,yn)

- 0of 0 votes
Given a graph where every two nodes are either friends or enemies with each other. Find a way to go from one node to the other.

Restrictions:

1) You can also travel from one node to next if they are friends with each other

2) You have some “magic potions”. You can convert an enemy path to a friend path with a magic potion.

Find the path with min number of magic potions required.

- 0of 0 votes
A planner wants to deign a city. A city having n points of interest and marked them from 0 - (n-1). Need to write two API:

public void buildRoad(int a, int b); // build road directly between a and b.

public boolean isRoadExist(int a, int b); // Check if there is any road connectivity exist between a & b (either directly or indirectly) then return TRUE else FALSE.

The solution should be in O(log n). You can first try in O(n).