## SDE-2 Interview Questions

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

- 0of 0 votes
Knight movement on a chess board...

Given any source point and destination point. Need to find whether Knight can move to destination or not.

If yes, Then what would be the minimum movement.

Extended Question : Extend the solution when chess size is infinite.

PS : Had to solve without recursion

- 1of 1 vote
Write a recursive method to get the multiplication of two numbers such that there are minimum number of addition operations.

- 0of 0 votes
You are given two integer arrays A and B .

1<=i<=len(A) so i is iterator of array A

1<=j<=len(B) so j is iterator of array B

find all the pairs(i,j) such that : i < j and A[i]>B[j]

- 1of 1 vote
They conducted a hiring round and this was asked there ?

Hi friends This question was asked in recent hiring challenge at hackerearth , that is over now,Please discuss your strategies.I am not able to devise algorithm please provide some hints to solve it.

Pulkit is really good at maths. Recently, he came to know about a problem on matrices. Amazed by the problem he got, he asked Ashish the same problem. Ashish also being good at maths solved the problem within 5 minutes. Now, its your time to solve the problem.

You will be given n*m binary matrix. You need to tell if it is possible to delete a column such that after deleting that column, rows of the matrix will be unique. If yes than print "Yes" else print "No".

[Input]

First line contains an integer t denoting no.of test cases.

Next line contains 2 integers n and m denoting no.of rows and columns.

Next n line contains binary string of length m each.

[Output]

For each test case output "Yes" or "No".

[Constraints]

1<=t<=100

1<=n<=1000

2<=m<=1000

Sample Input (Plaintext Link)

2

3 3

101

000

100

2 2

11

11

Sample Output (Plaintext Link)

Yes

No

- 2of 2 votes
Design a Meeting Reminder Pop-up similar to one found on outlook.

Data Structure to be used and come up with classes.

- 0of 0 votes
How to find non- common elements between two string arrays. Eg: String a[]={"a","b","c","d"};

String b[]={"b","c"};

O/p should be a,d

- 0of 0 votes
Question was very similar to this one

http://www.hackerearth.com/thoughtworks-hiring-challenge/algorithm/swap-it-2/

Bob loves sorting very much. He is always thinking of new ways to sort an array.His friend Ram gives him a challenging task.He gives Bob an array and an integer K .The challenge is to produce the lexicographical minimal array after at most K-swaps.Only consecutive pairs of elements can be swapped.Help Bob in returning the lexicographical minimal array possible after at most K-swaps.

Input: The first line contains an integer T i.e. the number of Test cases. T test cases follow. Each test case has 2 lines. The first line contains N(number of elements in array) and K(number of swaps).The second line contains n integers of the array.

Output: Print the lexicographical minimal array.

Constraints:

1<=T<=10

1<=N,K<=1000

1<=A[i]<=1000000

Sample Input (Plaintext Link)

2

3 2

5 3 1

5 3

8 9 11 2 1

Sample Output (Plaintext Link)

1 5 3

2 8 9 11 1

Explanation

After swap 1:

5 1 3

After swap 2:

1 5 3

{1,5,3} is lexicographically minimal than {5,1,3}

Example 2:

Swap 1: 8 9 2 11 1

Swap 2: 8 2 9 11 1

Swap 3: 2 8 9 11 1