## SDE-2 Interview Questions

- 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).

- 0of 2 votes
Write all jumbled number which is >0 && <N, where N is provided by the user.

A jumbled number is a number whose neighbour digit (either left or right) max differ by 1 value.

e.g.:

8987 is a jumbled number.

13 is not a jumbled number.

123456 is a jumbled number.

287 is not jumbled number.

- 1of 1 vote
print all the characters present in the given string only once in a reverse order. Time & Space complexity should not be more than O(N).

e.g.

1)Given a string aabdceaaabbbcd

the output should be - dcbae

2)Sample String - aaaabbcddddccbbdaaeee

Output - eadbc

3)I/P - aaafffcccddaabbeeddhhhaaabbccddaaaa

O/P - adcbhef

Answer :

import java.util.Iterator;

import java.util.LinkedHashSet;

import java.util.Scanner;

import java.util.Set;

public class StringQAmazon {

public static void main(String args[]) {

Scanner sc = new Scanner(System.in);

String inputStr = sc.nextLine();

System.out.println(stringManipulation(inputStr));

}

static String stringManipulation(String str) {

if(str.isEmpty())

return "";

else if(str.length()==1)

return str;

else {

str.toLowerCase();

StringBuilder strBuilder = new StringBuilder();

strBuilder.append(str);

strBuilder.reverse();

Set<Character> set = new LinkedHashSet<Character>();

for(int i =0; i<strBuilder.length(); i++){

set.add(strBuilder.charAt(i));

}

Iterator<Character> iter = set.iterator();

strBuilder=new StringBuilder();

while(iter.hasNext()){

strBuilder.append(iter.next());

}

return strBuilder.toString();

}

//return null;

}

}

- 0of 0 votes
You are given a structure msg

struct msg

{

long timestamp;

double price;

string label;

};

The msg represents price of a stock on a given timestamp.

Create a class with two functions -

addStockPrice(msg m) -> Used to add Stock Price in Data structure

getAvgPriceForAStockLast10Minutes(String stockName) -> Get average price of a stock for last 10 minutes.

The program should be time and space optimized.

- 0of 0 votes
Find number of islands of '1' in D dimensional array containing '0', '1'. where D > 2.

- 0of 0 votes
Given a road divided in blocks

_ * * _ _ * _ _ _

1 2 3 4 5 6 7 8 9

where ‘*’ represent damaged block. There is a rollar that is used to repair the road.

Rollar is of fixed length K. Given the damaged locations (N) and the size of rollar K.

Have to find the minimum number of blocks that rollar would cover so that it repairs all damaged blocks.

For Example for above case if K=3, N=3(2,3,6) Ans would be 5(2,3,4,5,6)

_ * * _ _ * _ _ _

1 2 3 4 5 6 7 8 9

1: -(234)

2 : -(456)

Another example : N=4(4,6,8,10) and K=2

- - - * - * - * - * - -

1 2 3 4 5 6 7 8 9 10 11 12

Ans =6 (4 5 6 8 9 10)

Rolar may not repair continuously. There can be gaps.

- 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.