## SDE-2 Interview Questions

- 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

- 0of 0 votes
A file of encoded message contains only numbers. Original message contains only lowercase letters and spaces. So character ‘a’ is mapped to 1 ‘b’ to 2 and so on till ‘z’ is mapped to 26. Given an input of numbers find out the number of ways you can decode it in original message. Eg. 123 can be decoded in 3 ways as 'abc', 'lc' or 'aw'

- 1of 1 vote
How will you design, and what data structure will you use for a contact list in a cell Phone. It should support insert/modify/delete/search functionality like that provided in a cell phone.

Suppose some of the entries are

Aman

Amazon

Neha Aman

and we type 'ama'

then the result should show all the above three enteries.

Also it should be possible to search using phone numbers.

- -1of 1 vote
an array is given.for each number at index i,find a number at index j such that aj 3.N number of books is given.each books is having some pages pi.How books should be alloted to m students so that maximum number of pages alloted to a student is minimum.Each student will read atleast one book.and one book can be read by only one person.find minimum value.

- 0of 0 votes
Store a Tree of URI and give a java implementation for it to return handler for the URI , eg : url mapping like in spring-config.xml

- 2of 2 votes
There is a binary tree. We are given 3 nodes a, b and c. We need to find a node in the tree such that we remove all edge from that node we get a, b and c in three different trees

- 0of 0 votes
Hi, I was asked a this one at the interview. Below is the problem statement:

1) I have a array of n bitstring elements of width m bits, for example:

{1001, 0101, 1100, 0011, 1111, 0000, 0001}

2) We have to apply a filter such that out of these n elements, only k elements pass through the filter while the rest gets blocked, for example

{1001, 0101, 1100, 0011, 1111, 0000, 0001} -- filter -- > {1001, 1100, 1111}

3) Filter has been designed based on a concept of mask and ID.

mask: It tells which bits to consider out of the m bit bitstring elements. Only those bits which are set to '1' would be used for checking while the rest be ignored. for example, a mask of {1000} would mean only 4th bit would be considered for checking while the filter won't care about the other bits of an element.

ID: It is the allowed value for the designed mask. for example, an ID of 1xxx (where x is don't care) with a mask of 1000 means that any element which has 4th bit as '1' would be allowed while if the 4th bit is '0', that element would be blocked. Since the mask doesn't check the 1st, 2nd and 3rd bit, any value, '1' or '0' would be allowed to be passed through the filter

For the above example, a single mask of 1000 and ID of 1xxx solves the problem. We need to find a generic solution for any set of n elements and k allowed elements. All of the k element might not get covered by a single mask and ID. We need to find the optimum solution using minimum number of mask,ID sets with their values.

- 2of 2 votes
Given a 2 dimensional matrix where some of the elements are filled with 1 and rest of the elements

are filled. Here X means you cannot traverse to that particular points. From a cell you can either traverse to left, right, up or down

Given two points in the matrix find the shortest path

between these points

For example if the matrix is

1 1 1 1 1

S 1 X 1 1

1 1 1 1 1

X 1 1 E 1

1 1 1 1 X

Here S is the starting point and E is the Ending point

- 0of 0 votes
Given an array of heights of poles. Find the no of poles which are visible if you are standing at the ith pole