## SDE-2 Interview Questions

- 0of 0 votes
You have a rectangular chocolate bar that consists of width x height square tiles. You can split it into two rectangular pieces by creating a single vertical or horizontal break along tile edges. For example, a 2x2 chocolate bar can be divided into two 2x1 pieces, but it cannot be divided into two pieces, where one of them is 1x1. You can repeat the split operation as many times as you want, each time splitting a single rectangular piece into two rectangular pieces.

Your goal is to create at least one piece which consists of exactly nTiles tiles. Return the minimal number of split operations necessary to reach this goal. If it is impossible, return -1.

Complete the function getMinSplit, which takes in 3 integers as parameters. The first parameter is width of the chocolate, the second is height of the chocolate and third is nTiles, the number of tiles required.

Constraints

- width will be between 1 and 109, inclusive.

- hight will be between 1 and 109, inclusive.

- nTiles will be between 1 and 109, inclusive.

Example 0

5

4

12

Returns: 1

You can split the chocolate bar into two rectangular pieces 3 x 4 and 2 x 4 by creating a single vertical break. Only one break is necessary.

Example 1

12

10

120

Returns: 0

The chocolate bar consists of exactly 120 tiles.

Example 2

2

2

1

Returns: 2

Example 3

17

19

111

Returns: -1

Example 4

226800000

10000000

938071715

Returns: 2

- 1of 1 vote
Human gene consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T.

Your job is to make a program that compares two genes and determines their similarity as explained below.

Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of the genes to make them equally long and score the resulting genes according to a scoring matrix.

For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in -GT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal length. These two strings are aligned:

AGTGAT-G

-GT--TAG

In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.

* denotes that a space-space match is not allowed.

The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.

Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):

AGTGATG

-GTTA-G

This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the similarity of the two genes is 14.

You are expected to complete the function getDNAAlignment, which takes in two strings as argument.

Constraints

Length of both strings will not exceed 1000.

Both string will be non-empty strings.

strings will only consists of character from set {'A', 'C', 'G', 'T'}

Sample Input 00

AGTGATG

GTTAG

Returns: 14

Sample Input 01

AGCTATT

AGCTTTAAA

Returns: 21

- 0of 0 votes
You are a coin collector in a country, where the silver coin denominations runs from 1 to 1000000. You have N coins with you with various denominations.

Apart from the silver coins, the country also issues gold coins which can be used as any value. With the given silver and gold coins, find out the maximum continous denomination streak you can achieve.

For example, if you have 4 silver coins of value 2, 3, 5 and 9 and 1 gold coin. You can have a maximum streak of 4 coins by using the gold coin as value 4.

Input format.

The first line contains 2 integers, S and G. S is the number of silver coins you have and G is the number of gold coins you have. S lines follow, each line is the value of the corresponding silver coin

Output format:

One integer, representing the maximum streak you can have using the coint.

Sample Input 1

4 1

2

3

5

7

Sample Output 1

4

- 0of 0 votes
You have a set of pairs of characters that gives a partial ordering between the characters. Each pair (a, b) means that a should be before b. Write a program that displays a sequence of characters that keeps the partial ordering (topological sorting).

- 0of 0 votes
Implement multiple producer and multiple consumer problem in java.

- 1of 1 vote
For a given binary search tree, replace each node with sum of all node which are greater then of equal to current node.

- 0of 0 votes
Id Key Value

-- --- -----

1 name hulk

2 age 22

3 name ironman

4 age 35

Write an efficient SQL Query to fetch the id of all users whose name starts with h and having age between 22 and 35.

- 0of 0 votes
Given two tables

1. Candidate having: Id , Name

2. Vote: Id, CandidateId

Give query to give the name of the winning candidate

- 1of 1 vote
Coding Round Assignment

------------------------------------

MERCHANT'S GUIDE TO THE GALAXY

You decided to give up on earth after the latest financial collapse left 99.99% of the earth's population with 0.01% of the wealth. Luckily, with the scant sum of money that is left in your account, you are able to afford to rent a spaceship, leave earth, and fly all over the galaxy to sell common metals and dirt (which apparently is worth a lot).Buying and selling over the galaxy requires you to convert numbers and units, and you decided to write a program to help you.The numbers used for intergalactic transactions follows similar convention to the roman numerals and you have painstakingly collected the appropriate translation between them.Roman numerals are based on seven symbols:

Symbol Value

I 1

V 5

X 10

L 50

C 100

D 500

M 1,000

Numbers are formed by combining symbols together and adding the values. For example, MMVI is 1000 + 1000 + 5 + 1 = 2006. Generally, symbols are placed in order of value, starting with the largest values. When smaller values precede larger values, the smaller values are subtracted from the larger values, and the result is added to the total. For example MCMXLIV = 1000 + (1000 − 100) + (50 − 10) + (5 − 1) = 1944.

The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear four times if the third and fourth are separated by a smaller value, such as XXXIX.) "D", "L", and "V" can never be repeated.

"I" can be subtracted from "V" and "X" only. "X" can be subtracted from "L" and "C" only. "C" can be subtracted from "D" and "M" only. "V", "L", and "D" can never be subtracted.

Only one small-value symbol may be subtracted from any large-value symbol.

A number written in Arabic numerals can be broken into digits. For example, 1903 is composed of 1, 9, 0, and 3. To write the Roman numeral, each of the non-zero digits should be treated separately. In the above example, 1,000 = M, 900 = CM, and 3 = III. Therefore, 1903 = MCMIII.

-- Source: Wikipedia (http://en.wikipedia.org/wiki/Roman_numerals)Input to your program consists of lines of text detailing your notes on the conversion between intergalactic units and roman numerals. You are expected to handle invalid queries appropriately.

Test input:

-------------

glob is I

prok is V

pish is X

tegj is L

glob glob Silver is 34 Credits

glob prok Gold is 57800 Credits

pish pish Iron is 3910 Credits

how much is pish tegj glob glob ?

how many Credits is glob prok Silver ?

how many Credits is glob prok Gold ?

how many Credits is glob prok Iron ?

how much wood could a woodchuck chuck if a woodchuck could chuck wood ?

Test Output:

---------------

pish tegj glob glob is 42

glob prok Silver is 68 Credits

glob prok Gold is 57800 Credits

glob prok Iron is 782 Credits

I have no idea what you are talking about

- 0of 0 votes
Design a mobile app which based on the current location suggests Interesting places to the user. We already have a set of interesting places stored. The focus is on getting the nearby places say in radius of 100 Miles from current location quickly.

The interviewer is mainly interested on how to store the interesting locations in a DB.

- 5of 5 votes
write a program to give an array such that:

1. the data value is from 1 to n

2. the length of it is 2*n

3. the two elements with same value keep the same number distance.

for example, when n = 3, the length of array is 6, the array should be like: 2, 3, 1, 2, 1, 3. there are two elements between "2" pair, and three elements between "3" pair and one element between "1" pair

- 1of 1 vote
An extension of Dijkstra's algorithm:

In a graph each vertex represents a city.

And each edge defines the connectivity between two vertices.

Each edge has two more information

1) the distance between the two vertices

2) A Boolean flag indicating if the destination is uphill or downhill to the source.

One constraint: you can change the path from uphill to downhill or downhill to uphill only once.

E.g: initially if you are going up the hill and at some point choosed to go down the hill, you can not change to take a path which is uphill again..

Similarly you are going down the hill and at some point choosed to go up the hill, you can not change to take a path which is down hill again..

O/P: find the shortest path between source to destination.

- 2of 2 votes
Interview gave towers of Honai with 4 pegs namely: source, helper1, helper2, destination.

What are the minimum number of steps to move N number of discs from source to destination.

he was looking for a recursive function which defines the number of moves required for N and the minimum value for that function.

- 0of 2 votes
Given a circular linked list with each node either r,g,y or b. number of nodes of each color are same. Arrange the nodes in a specified order. Eg. if list is like "rrrgggyyybbb" and order is "rgyb" then after rearrangement it should be "rgybrgybrgybrgyb". Just a bit more explanation...the question was given in form of students stading in a circular fashion and color denotes the club they are in. Hence adding new node or list is not possible.

- 0of 0 votes
Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

You have to print the sub-sequence also.

- 1of 1 vote
Generate all Kaprekar Number (refer Wiki for Kaprekar number's definition) from 1 to 999999.

I gave a brute force approach of generating all number in the range and checking if it is Kaprekar or not.

- 1of 1 vote
For a given array with positive and negative element, find sub array with maximum sum. Sub array must have same sequence of element as that of parental array.

Eg: P = {4,6,-3,1,5,9,-2} then S ={4,6,-3,1,5,9} //Correct output.

- 1of 1 vote
Construct an array of size 10 such that if a[x] =y then x should be repeated y times in that array. Eg: If a[1] = 2 then 1 should be present in that array 2 times.

- 0of 0 votes
As you are on Seattle, tell me how many rain drops pour on earth every year

- 0of 0 votes
We have a bag containing numbers 1, 2, 3, …, 100. Each number appears exactly once, so there are 100 numbers. Now one number is randomly picked out of the bag. Find the missing number.

- 0of 0 votes
Given 2 sorted lists that are of even and equal size, output the median. If there is no middle number, return the average of the 2 middle numbers

- 0of 0 votes
Design a web-site like Paypal.

The interviewer was interested in the

i) Major components & the way they will interact.

ii) Various way of scaling the web-site to support many users

iii) Handling the failure cases like when the DB goes down, etc.

- 1of 1 vote
Given a binary matrix of 0 and 1. Find the longest sequence of 1's either row wise or column wise.

For example

0 0 0 0 0 0

0 1 1 1 0 0

0 0 0 1 0 0

It should return 1 1 1

- 0of 0 votes
Given a list of interval , find the maximum overlapping interval. For ex if input is (0,5) (2,9) (8,10) (6,9) then ans is 2,9 as its overlap are 3.

- 4of 4 votes
Given stock price of Amazon for some consecutive days. Need to find the maximum span of each day’s stock price. Span is the amount of days before the given day where the stock price is less than that of given day

E.g i/p = {2,4,6,9,5,1}

o/p= { -1,1,2,3,2,-1}

- 1of 1 vote
Given a matrix of characters and a string, find whether the string can be obtained from the matrix. From each character in the matrix, we can move up/down/right/left. for example, if the matrix[3][4] is

o f a s

l l q w

z o w k

and the string is follow, then the function should return true.

- 0of 0 votes
Given 2 strings str1 and str2. What is the efficient way to navigate from str1 to str2? The constraints are i) a string can be changed to another string by changing only one character. ii) all the intermediate strings must be present in dictionary. If not possible, return “not possible to navigate from str1 to str2″. (pre-processing is allowed and enough memory is available). for example: str1 = feel and str2 = pelt, then the navigation is feel -> fell -> felt -> pelt

- 0of 0 votes
A number series have numbers in the increasing order where numbers are of the form 2^m*3^n*5^p. where m,n,p are an non negative integers. The initial few number of the series are

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18......

Write a function to get the nth term of such a sequence.

- -2of 4 votes
Asked to explain how to check Binary tree is BST?

- -3of 3 votes
Find Nodes which are at "K" distance from given node.