SDE-2 Interview Questions
- 1of 1 vote
AnswersCoding Round Assignment
- hulk April 29, 2014 in India
------------------------------------
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| Report Duplicate | Flag | PURGE
Infibeam SDE-2 Algorithm - 0of 0 votes
AnswersDesign 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.
- hulk April 29, 2014 in India
The interviewer is mainly interested on how to store the interesting locations in a DB.| Report Duplicate | Flag | PURGE
Infibeam SDE-2 System Design - 5of 5 votes
Answerswrite a program to give an array such that:
- doctorking5891 April 29, 2014 in United States
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| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersAn extension of Dijkstra's algorithm:
- poorna.chandra.akp April 28, 2014 in United States
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.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 - 2of 2 votes
AnswersInterview gave towers of Honai with 4 pegs namely: source, helper1, helper2, destination.
- poorna.chandra.akp April 28, 2014 in India
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.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 2 votes
AnswersGiven 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.
- Nitin April 28, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven 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.
- hulk April 26, 2014 in India
You have to print the sub-sequence also.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 1of 1 vote
AnswersGenerate all Kaprekar Number (refer Wiki for Kaprekar number's definition) from 1 to 999999.
- hulk April 26, 2014 in India
I gave a brute force approach of generating all number in the range and checking if it is Kaprekar or not.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm Brain Teasers - 1of 1 vote
AnswersFor 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.
- Razz April 26, 2014 in India
Eg: P = {4,6,-3,1,5,9,-2} then S ={4,6,-3,1,5,9} //Correct output.| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersAs you are on Seattle, tell me how many rain drops pour on earth every year
- Mukesh Dua April 24, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 - 0of 0 votes
AnswersWe 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.
- Mukesh Dua April 24, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 - 0of 0 votes
AnswersGiven 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
- valheru April 23, 2014 in United States| Report Duplicate | Flag | PURGE
Big Fish iOS Developer Sorting Amazon SDE-2 Algorithm - 1of 1 vote
AnswersDesign a web-site like Paypal.
- hulk April 21, 2014 in India
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.| Report Duplicate | Flag | PURGE
Amazon SDE-2 System Design - 0of 0 votes
AnswersGiven 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.
- Nitin April 13, 2014 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 5of 5 votes
AnswersGiven 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
- Rahul Sharma April 04, 2014 in India
E.g i/p = {2,4,6,9,5,1}
o/p= { -1,1,2,3,2,-1}| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven 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
- Rahul Sharma April 04, 2014 in India
o f a s
l l q w
z o w k
and the string is follow, then the function should return true.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven 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
- Rahul Sharma April 03, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Coding - 0of 0 votes
AnswersA 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
- nikhils.codecracker March 25, 2014 in India for Retail
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.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Math & Computation - -2of 4 votes
AnswersAsked to explain how to check Binary tree is BST?
- Mohit March 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -3of 3 votes
AnswersFind Nodes which are at "K" distance from given node.
- Mohit March 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -3of 3 votes
AnswersFind In order predecessor in BST.
- Mohit March 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -4of 4 votes
Answersasked me about assembly line problem.
- Mohit March 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - -4of 4 votes
Answersasked me to solve Knapsack Problem
- Mohit March 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - -3of 3 votes
AnswersAsked to explain how to check Binary tree is BST?
- Mohit March 23, 2014 in India
then asked me to write whole code of it.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 3 votes
AnswersFind Nodes which are at "K" distance from given node.
- Mohit March 23, 2014 in India
explain logic and write full code with all boundary conditions.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -3of 3 votes
AnswersFind In order predecessor in BST.
- Mohit March 23, 2014 in India
explain logic and write full code with all boundary conditions.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 2 votes
AnswersIn a Binary tree, every element(node's value) must contain the sum of its left and right sub-trees.
- pavi.8081 March 08, 2014 in India
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.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersIn Amazon web site, the product items has to show with different attributes combination for clothers.
Example:
color - red blue green
size - XL X M S
pattern - checks lines
so output should be in below format in different combinations:
red - xL - checks
red - xL - lines
red - X - checks
red - x - lines
red - M - checks
:
:
green - S - checks
green - S - lines
Note:- In above example, no. of attributes is 3. but attributes can be N.
Below is the code, I have written. Hope it will be useful for anyone.
This is an non-recursive logic which will work for large value of N. time Complexity is O(n2).------------------------------------------------------------------------------------- package com.test; import java.util.Scanner; public class Solution { public static void main(String args[] ) throws Exception { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ Scanner in = new Scanner(System.in); int n = in.nextInt(); in.nextLine(); //to read new line String[][] attributes = new String[n][]; int i=0; while(i < n) { String temp = in.nextLine(); String[] values = temp.split(" "); attributes[i] = values; i++; } printAttributesCombination(attributes); } static void printAttributesCombination(String[][] attributes) { int count[] = new int[attributes.length]; int totalcount[] = new int[attributes.length]; //initialize the totalcount and temp index count initialize(count, totalcount, attributes); while(isDone(count,totalcount)) { printArray(attributes,count); } } static void initialize(int count[], int totalcount[], String[][] attributes) { for(int i = 0; i < count.length; i++) { count[i] = 0; totalcount[i] = attributes[i].length - 1; } count[count.length-1] = -1; } static boolean isDone(int count[], int totalCount[]) { boolean prevIndexSet = true; boolean canTerminateLoop = false; int i = 0; for(i = count.length - 1; i >= 0 ; i--) { if(count[i] == totalCount[i]) { count[i] = 0; prevIndexSet = true; canTerminateLoop = true; } else { count[i] = count[i] + 1; prevIndexSet = false; canTerminateLoop = false; } if(!prevIndexSet) break; } if(canTerminateLoop && i == -1 ) return false; return true; } static void printArray(String[][] arr, int count[]) { System.out.println(); for(int i = 0; i < arr.length; i++) { System.out.print(" " + arr[i][count[i]]); } } } -------------------------------------------------------------------------------------
Output:
- Thirumaleshwar Kunamalla March 07, 2014 in United States
==============
Sample1:-
============
3
a b c
d e f
g h i
a d g
a d h
a d i
a e g
a e h
a e i
a f g
a f h
a f i
b d g
b d h
b d i
b e g
b e h
b e i
b f g
b f h
b f i
c d g
c d h
c d i
c e g
c e h
c e i
c f g
c f h
c f i
Sample2:-
============
4
a b
a b c
d e
f i
a a d f
a a d i
a a e f
a a e i
a b d f
a b d i
a b e f
a b e i
a c d f
a c d i
a c e f
a c e i
b a d f
b a d i
b a e f
b a e i
b b d f
b b d i
b b e f
b b e i
b c d f
b c d i
b c e f
b c e i| Report Duplicate | Flag | PURGE
Amazon SDE-2