## SDE-2 Interview Questions

- 0of 0 votes
Move all zeros to beginning input {1,2,3,0,0,0,4,5} output {0,0,0,1,2,3,4,5}

- 0of 0 votes
class Node{ int nodeId,int nodeParentId} is given.

Input : List<Node>

Output:Tree

- 0of 0 votes
Design TIC TAC TOE problem

- 4of 4 votes
Given a big rectangular plot of land that has rectangular or square sized buildings (all sides of every building are parallel to the big rectangular plot)... find the location and dimensions of the largest square that can be built in this rectangular plot

- 2of 2 votes
Find the number of bits set in a given character array.

After giving him a bit wise operation that was O(n) where n is the number of bits set, he wanted a more optimum solution

- 1of 1 vote
Given an array of integers and a number. WAP to find the pairs which sum of upto given number.

I solved it. Then he asked about writing test cases for this function.

I wrote below test cases

1.) All the elements should be number.

2.) Length of array should not be 0.

3.) Array itself should not be null.

4.) Given number, arrayLength can be represented by 32bits or 64 bits.

5.) number should not be negative.

6.) Input does not has pair, It should return false

7.) Input has pair, It should return true

8.) Input has all negative values and pair exists, then function should return true

9.) Input has all negative values and pair does not exists, function should return false

He told that he is looking for more test cases. Can you guys think of some more complex test cases.

- 1of 1 vote
You are given a catalog of books, which have following attributes :-

Name, Author, Publisher, Publish year, Category, Price, Count (sold)

Implement following APIs on top of this catalog -

1) addBookToCatalog(Book)

2) searchBook(by partial book name/author)

3) getMostSoldBooks(by author name/category, limit)

Expectations:

Maintain DB on memory

Code should be readable. Design, handle naming convention,handle exceptions & should be running

- 3of 3 votes
You have to compress a string in the following format.

eg 1- : input : aasasatb

output : 2a2sa1t1b

eg2 -: input: abcdbcdff

output :- 1a2bcd2f

- 0of 0 votes
design snakes and ladders game(multiplayer). extend it so that it can be hosted overs a server and played over a server

- 0of 0 votes
code library management system

a) add a book

b) issue a book

c) return a book

d) if a user has kept a book more than 10 days then there should be a fine of Rs. 1 per day post 10 days.

- 0of 0 votes
given daily stock rates of last year give the average stock rate price for a given day range

- 0of 0 votes
given n-ary tree. zigzag level order traversal.

- 0of 0 votes
given unsorted array and a number K. Find 2 numbers such that sum is K

- 0of 0 votes
there are M chocolate packets each packet can have variable number of chocolates in each packet.

There are N students (N<M).

Distribute chocolate packets to student such that

1) each student gets 1 packet

2) suppose m1,m2,...mn are the packets which are chosen to be distributed in sorted order of number of chocolates in them (nm-n1 must be minimum)

M = 1, 3, 4, 6 (4 packets with specified number of chocolates in them)

N = 2

Ans = 3,4

- 0of 0 votes
You have an organizational structure, which shows hierarchy of the organization. This hierarchy contains employees E or managers M who has some Employees or Managers reporting to M. Employee has ( id, name, JobDesc, salary etc). Design the data structure you would be using to store this hierarchy

1: Given an ID of an employee , print all the employee ID's who are directly reporting or indirectly reporting to the manager.

2. Given a bonus and performance rating of each employee divide it to the lowest level employees(in the hierarchy ) in the ratio of their rating. i.e 100 divided among 2:3 is 40 and 60. and print the bonus of each

3. Top 10 employees with ratio of bonus:salary

Note :-

1) Employee can have only 1 mgr, and a mgr has 1+ employees.

2) Input can be in any order for ex- employees might be input before his manager.

- 1of 1 vote
There are discounts on particular time period

suppost

Day1 - Day5 => 10%

Day2 - Day 8 => 5%

Day4 - Day6 => 20 %

find the period where maximum discounts is available.

For above example the period is Day4 - Day5 => 10+5+20

that means 35%

Provide the generalize solution. Period can be time also.

- 4of 4 votes
Sparse number is an integer if there are no adjacent 1 in it's binary representation.

Like: 5 -> 101 (no adjacent 1)

9 -> 1001 (no adjacent 1)

while 6-> 110 is not sparse number.

Now you are given an integer find the NEXT BIGGER sparse number.Please mind 'it is next bigger'.

- 0of 0 votes
You are to concatenate n strings (concatenate in any order) and a function:

int strCat(str1, str2); // returns the concatenated str length

Concatenate all strings in any order so that total cost is minimum.

Example: Strings A="abc", B="wxyz", C="a"

Cost of strCat(A,B) = (3+4) = 7

Cost of strCat(AB,C) = 7+1 = 8

Total cost = 7+8 =15

Other way:

Cost of strCat (A,C) = 3+1 = 4,

Cost of strCat (AC,B) = 4+4 = 8

Total Cost = 4+8 = 12

In this case, min(12,15) = 12 so Ans=12.

- 0of 0 votes
Assume a Game where a player can jump from one step to other to reach the final step.

From any given step Player can go to another step in any direction North, South, East or West. (i.e ) from Any given step user has a choice of multiple steps to choose from to proceed towards final step.

Some steps may not lead you in right direction to final step, in that case he need to retrace back.

To jump from one step to another Player uses a ladder. Distance between adjacent steps is not constant, they differ for each pair.

What is longest length of a ladder needed for the player to reach the final step from the starting step.

- 0of 0 votes
Implement a MessageBroker which accept messages from Publisher and deliver to Subscriber.

To begin with start with single Publisher and Subscriber. But design it in such a way to scale up to many publisher and subscriber associated with a Single Broker.

Take Performance and parallel processing into consideration.

- 0of 0 votes
A mechanical engineer is writing a design specification for two gears to transmit motion between two parts, A and B, in a machine she is designing.

the distance between A and B is equal to D.

There are n types of gears, Agear type of i has a radius Rj and cost Cj.

The two gears specified, i and j , must have Ri+Rj >= D, inorder for there to be a way of placing them so that they touch and work togeather. The objective is

to find the pair which costs the least.

You need to produce a design table that gives the most suitable match for every gear type in the list. For every gear type 'i', you need to consider its description (Ri,Ci)

and list the gear type 'j' to pair with 'i' in table position T[i]. The best map might be the same type(Ti=i). if there are multiple solutions with the same cost,

choose the gear with the largest radius.If both the cost and radius you need are found in more than one gear type, choose the type with the smallest index j.

If no radius can be found that allow the distance D to be covered, table should contain 0.

Input

n D

R1 R2 ... Rn

C1 C2 ... Cn

Output

T1 T2 ... Tn

- 0of 0 votes
You are given heights of n candles .

First day you lit one candle

second day you need to lit two candles

Third day you need to lit three candles

..........

........

till possible.

After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.

So you need to tell the maximum number number of days , you can carry on lighting the candles.

Example : there are three candles of heights {2 , 2 ,2 }

Answer : 3

1.You light first candle on day one. heights -> {1,2,2}

2.You light second and third and extinguish first one . heights ->{1, 1,1}

3.You light all the candles. heights -{0,0,0}

- 0of 0 votes
Given a 2 D array with m Entry points (which are on the edges) and n exit points which are on the edges give the total number of paths that are possible.

- 0of 2 votes
Given an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1< j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].

**Example:**

For n=6

6 7 8 1 2 3

Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays

we can get 1 2 3 6 7 8 , that is sorted.

How can we figure out minimum number of swaps in most effective way ?

- 0of 0 votes
Scenario : Multi Seller E-commerce Website

Given a list of products in a customer basket find the minimum number of seller required to deliver his order,so as to optimise shipping part.

Assuming you have already have below data

Customer orders products : P1,P2,P3,P4,P5,P6

Products and seller mapping

P1 = [1,2,3,4]

P2=[2,4,5,6]

where 1,2,3 etc denotes seller_ids.

p1

- 0of 0 votes
For a given matrix, find the maximum product of k elements. The elements can be formed from continuous 4 elements horizontally, vertically or diagonally. Eg: For k= 4, the maximum product is (6*4*7*9) from the last column,

1 2 0 -1 4

3 1 2 4 6

0 2 3 1 4

1 3 2 0 7

2 1 3 2 9

- 0of 0 votes
Given a function rev(int i) which reverses the segment of array ar[] from 0-i, Implement a function sort() using rev().

- 0of 0 votes
Design your own String Pooling system. It should return a String with request of more length. String pool should have strings of different sizes available. When requested, it should just be returned to client and when client is done using string, it should be added back to string pool for other client to use.

- 1of 1 vote
You have a file with 100 billion URLS, find first unique URL.

- 1of 1 vote
Design a data structure for following operations in O(1) time.:

insert

remove (FIFO)

find MODE