## SDE-2 Interview Questions

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

- -3of 3 votes
Find In order predecessor in BST.

- -4of 4 votes
asked me about assembly line problem.

- -4of 4 votes
asked me to solve Knapsack Problem

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

then asked me to write whole code of it.

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

explain logic and write full code with all boundary conditions.

- -3of 3 votes
Find In order predecessor in BST.

explain logic and write full code with all boundary conditions.

- 0of 2 votes
In a Binary tree, every element(node's value) must contain the sum of its left and right sub-trees.

Follow up question: how would you solve this if you can ONLY increment the value of a node

Eg. If a node’s value is 20 and its sub-tree sum is 10, the node’s value can’t be set to 10 because you can only increment.

How would you solve this if you can ONLY increment the value of a node

Further clarifications.

1. You can make assumption that leaf nodes retain their original value and does not change.

2. "Sum of its left and right subtrees" means sum of all nodes' values in its left subtree + sum of all nodes' values in its right subtree.

PS: I am asking this question coz I am not sure of its solution myself. Hence seeking experts' advice.