## SDE-2 Interview Questions

- 3of 3 votes
given a pre and post order kindof a traversal (2 arrays) create an n-ary treee out of it with struct of the form :

struct node {

int data;

struct node *child[MAX];

int child_num;

}

- 0of 0 votes
Implement the divide of two integers without using the divide operator.

After implementing the O(n) algorithm to subtract the divisor from the divider, he asked me to implement a better algorithm.

I started working towards bit manipulation, but ran out of time.

He also hinted that I could have used binary search. Not sure how though.

- 0of 0 votes
Given a stack of magazines create an anonymous love note (pick words or alphabets from the magazine and create the note)...

He gave me the choice of handling words or alphabets

Assume you have a scanned copy of the magazine as a string.

Once I implemented both words and alphabets, he asked me to scale it to mass production and maximize the throughput of a fulfillment center handling this

- 2of 2 votes
Design a robot that will take your order and make sandwiches for you.

Once I was done with this, I was supposed to extend it to have multiple robots doing this job like an assembly line handling multiple sandwiches and other edible items

Once I handled that, he asked me to create a web service for this that will handle online ordering. He also wanted me to implement fulfillment centers

- 1of 1 vote
Write code/ logic to count number of words in a string delimited by " ". Anything apart form " " are ignore for the counting. String could be very big as big as 5 GB of data. So add logic to handle such large strings..

ex: aaa b c ddd e = Count (5)

aaaaaaaaaaa = Count(1)

a

b

c

d

Count(1) as there are no spaces rather carriage returns are found.

PS: In case above question is not clear do let me know.

- 1of 3 votes
Given two input string check if anyone is substring of other.

example aaaaaabbb, aaaabbb

return true

PS: Don't use any internal string library :)

- 0of 0 votes
Given a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.

- 0of 0 votes
`6 / \ 3 5 / \ \ 2 5 4 / \ 7 4`

There are 4 leaves, hence 4 root to leaf paths:

Path Sum

6->3->2 632

6->3->5->7 6357

6->3->5->4 6354

6->5>4 654

Answer: 632+6357+6354+654=13997

- 0of 0 votes
6

/ \

3 5

/ \ \

2 5 4

/ \

7 4

There are 4 leaves, hence 4 root to leaf paths:

Path Sum

6->3->2 632

6->3->5->7 6357

6->3->5->4 6354

6->5>4 654

Answer = 632 + 6357 + 6354 + 654 = 13997

- 0of 0 votes
Write a program to make the following possible with any given tree.

6

/ \

3 5

/ \ \

2 5 4

/ \

7 4

There are 4 leaves, hence 4 root to leaf paths:

Path Sum

6->3->2 632

6->3->5->7 6357

6->3->5->4 6354

6->5>4 654

Answer = 632 + 6357 + 6354 + 654 = 13997

- 0of 0 votes
Suggest a Data Structure to do the following opperations with time complexity O(1).

insert(int element); //insertes an element in O(1);

delete(int element); //deletes an element in O(1);

lookup(); // returns any element in random from the list at O(1);

- 0of 0 votes
O/p the expected value of the number of people to deliver the information

I/P dependency graph

1234

1-0111

2-1000

3-1001

4-1010

o/p

2.66

- 0of 0 votes
How would test this method ?

public static bool DateBetweenDates(DateTime startDate, DateTime endDate, DateTime dateToTest)

{

if (startDate.Year > dateToTest.Year)

return false;

if (endDate.Year < dateToTest.Year)

return false;

if (startDate.Month > dateToTest.Month)

return false;

if (endDate.Month < dateToTest.Month)

return false;

if (startDate.Day > dateToTest.Day)

return false;

if (endDate.Day < dateToTest.Day)

return false;

else

return true;

}

- 0of 0 votes
Given graph below, and the Y-axis co-ordinates in and array, find the lowest point of every dip in the graph.

(I know graph looks horrible but i tried my best)`70 / 60 /\/ 50 / 40 /\ / 30 / \ / 20 /\/ \/ 10 /`

Array is : 0 10 20 10 30 40 50 40 30 20 10 20 30 40 50 60 50 60 70

Result List : 0 10 10 50

- 0of 2 votes
Given a +ve integer, find the next highest number in the numerical order using the same numbers present in the given integer.

Example : 218765

O/P : 251678

- 1of 1 vote
given expression with operands and operators (OR , AND , X-OR) , in how many ways can u evaluate the expression to true, by grouping in different ways? Operands are only true and false.

for example true & false | true ^ false can be grouped to true & ((false | true) ^ false) and so on..

the following wiki of the above question

http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

- 2of 2 votes
You are given a string S. Each character of S is either ‘a’, or ‘b’. You wish to reverse exactly one sub-string of S such that the new string is lexicographically smaller than all the other strings that you can get by reversing exactly one sub-string.

For example, given ‘abab’, you may choose to reverse the substring ‘ab’ that starts from index 2 (0-based). This gives you the string ‘abba’. But, if you choose the reverse the substring ‘ba’ starting from index 1, you will get ‘aabb’. There is no way of getting a smaller string, hence reversing the substring in the range [1, 2] is optimal.

Input:

First line contains a number T, the number of test cases.

Each test case contains a single string S. The characters of the string will be from the set { a, b }.

Output:

For each test case, print two numbers separated by comma; for example “x,y” (without the quotes and without any additional whitespace). “x,y” describe the starting index (0-based) and ending index respectively of the substring that must be reversed in order to acheive the smallest lexicographical string. If there are multiple possible answers, print the one with the smallest ‘x’. If there are still multiple answers possible, print the one with the smallest ‘y’.

Constraints:

1 ? T ? 100

1 ? length of S ? 1000

Sample Input:

5

abab

abba

bbaa

aaaa

babaabba

Sample Output:

1,2

1,3

0,3

0,0

0,4

- 1of 1 vote
Given a sorted array, construct Balanced BST

- 0of 0 votes
Find all the Leaders in an Array.

An Array element is Leader if all the elements following that array element is lesser than or equal to it.

Ex: Arr = {13, 17, 5, 4, 6, 2}

O/p: 17, 6, 2

- 6of 6 votes
Given a number M (N-digit integer) and K-swap operations(a swap

operation can swap 2 digits), devise an algorithm to get the maximum possible integer?

Examples:

M = 132 K = 1 output = 312

M = 132 K = 2 output = 321

M = 7899 k = 2 output = 9987

M = 8799 and K = 2 output = 9987

- 2of 2 votes
n mice are playing in the desert, when one of them notices some hawks flying in the sky. It alerts the other mice who now realize that the hawks are going to attack them very soon. They are scared and want to get inside holes to ensure their safety.

Mice and holes are placed on a straight line. There are m holes on this line. Each hole can accommodate only 1 mouse. A mouse can either stay at its position, or move one step right from x to x+1, or move one step left from x to x-1. Any of these movements takes 1 minute.

Assign mice to holes so that the time required for all the mice to move inside the holes is minimized.

Input Format

The first line contains an integer T, the number of test cases. This is followed by T blocks of input:

First line contains 2 positive integers n and m separated by a single space.

Next line contains n space separated integers, denoting the positions of the mice.

Next line contains m space separated integers, denoting the positions of the holes.

Note: No two holes have the same position.

Output Format

For each testcase, print the minimum time taken by all the mice to reach inside the holes.

Constraints

1 ≤ T ≤ 17

1 ≤ n ≤ 131072

1 ≤ m ≤ 131072

n ≤ m

-108 ≤ mouse[i] ≤ 108

-108 ≤ hole[j] ≤ 108

Sample Input

1

3 4

2 0 -4

3 1 2 -1

Sample Output

3

Explanation

One possible solution is :

Assign mouse at position x=-4 to hole at position x=-1 -> 3 minutes

Assign mouse at postion x=2 to hole at position x=2 -> 0 minutes

Assign mouse at postion x=0 to hole at postion x=3 -> 3 minutes

So the answer is 3, after 3 minutes all of the mice are in the holes.

- 0of 0 votes
Write a function to determine if a binary tree is a true binary search tree and give the average performance of the function.

- 0of 0 votes
Design an elevator system for a high rise building.

- 0of 0 votes
Design an alarm clock.

- -1of 1 vote
A Load Balancer has the following functions:

`getHost() addHost(String) removeHost(String)`

Implement these functions using any data structure you wish. Also indicate the average performance for each function and what you expect to be its call count in a typical system with respect to each other of the three functions. In other words, how often do you expect getHost() to be called compared to addHost(...)?

Constraints:

Hosts are unique.

getHost() returns a random host from the host group

- 0of 0 votes
write a function for a BST to implement best case search.If exact search key not available in BST then return best suited key.Ex- if a tree has keys 21 15 26 30 55 7 and if my search key is 25 then this function should return 26.

- 1of 1 vote
How to impliment Google map

Data Structure and algorithm.

1. Zoom in/out

2. horizontal/ vertical.

Assumtion - all the image of earth with pixel\Any other assumption is allowed

- 1of 1 vote
Given an unsorted array of ints,sort the shortest sub-array which results in sorting of the whole array.

Ex:

i/p: [-1,0,4,3,2,1,7,8,9]

By sorting sub array [4,3,2,1] the whole Array is sorted.

i/p: [10, 15, 20, 30, 25, 40, 35, 45, 50, 60]

By sorting sub array [30, 25, 40, 35] the whole Array is sorted.

i/p: [-1,0,4,3,2,1,7,8,9,-2]

Shortest sub-arry to be sorted is [-1,0,4,3,2,1,7,8,9,-2]

- 0of 0 votes
How to implement Dictionary, I gave solution using Tries then they asked how to implement using HashMap.

> What is the advantage of HashMap over Tries.

> What is the advantage of Tries over HashMap.

> How to implement dictionary using HashMap so that when i press a character it will list all the words starting with that character.

- 0of 0 votes
Given two Binary Tree, need to check both are same or not(Without using recursion). Extend the solution for Tree.