SDE-2 Interview Questions
- 1of 1 vote
AnswersThere are discounts on particular time period
- Dinesh Pant April 26, 2015 in India
suppost
Day1 - Day5 => 10%
Day2 - Day 8 => 5%
Day4 - Day6 => 20 %
find the period where maximum discounts is available.
For above example the period is Day4 - Day5 => 10+5+20
that means 35%
Provide the generalize solution. Period can be time also.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 4of 4 votes
AnswersSparse number is an integer if there are no adjacent 1 in it's binary representation.
- Rahul Sharma March 30, 2015 in United States
Like: 5 -> 101 (no adjacent 1)
9 -> 1001 (no adjacent 1)
while 6-> 110 is not sparse number.
Now you are given an integer find the NEXT BIGGER sparse number.Please mind 'it is next bigger'.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Coding - 0of 0 votes
AnswersYou are to concatenate n strings (concatenate in any order) and a function:
- alanturing06022014 March 22, 2015 in United States
int strCat(str1, str2); // returns the concatenated str length
Concatenate all strings in any order so that total cost is minimum.
Example: Strings A="abc", B="wxyz", C="a"
Cost of strCat(A,B) = (3+4) = 7
Cost of strCat(AB,C) = 7+1 = 8
Total cost = 7+8 =15
Other way:
Cost of strCat (A,C) = 3+1 = 4,
Cost of strCat (AC,B) = 4+4 = 8
Total Cost = 4+8 = 12
In this case, min(12,15) = 12 so Ans=12.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswerAssume a Game where a player can jump from one step to other to reach the final step.
- vinodjayachandran March 21, 2015 in India
From any given step Player can go to another step in any direction North, South, East or West. (i.e ) from Any given step user has a choice of multiple steps to choose from to proceed towards final step.
Some steps may not lead you in right direction to final step, in that case he need to retrace back.
To jump from one step to another Player uses a ladder. Distance between adjacent steps is not constant, they differ for each pair.
What is longest length of a ladder needed for the player to reach the final step from the starting step.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 1of 1 vote
AnswersImplement a MessageBroker which accept messages from Publisher and deliver to Subscriber.
- vinodjayachandran March 15, 2015 in India
To begin with start with single Publisher and Subscriber. But design it in such a way to scale up to many publisher and subscriber associated with a Single Broker.
Take Performance and parallel processing into consideration.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Problem Solving technical - 1of 1 vote
AnswersA mechanical engineer is writing a design specification for two gears to transmit motion between two parts, A and B, in a machine she is designing.
- nik.cse2005 March 13, 2015 in United States
the distance between A and B is equal to D.
There are n types of gears, Agear type of i has a radius Rj and cost Cj.
The two gears specified, i and j , must have Ri+Rj >= D, inorder for there to be a way of placing them so that they touch and work togeather. The objective is
to find the pair which costs the least.
You need to produce a design table that gives the most suitable match for every gear type in the list. For every gear type 'i', you need to consider its description (Ri,Ci)
and list the gear type 'j' to pair with 'i' in table position T[i]. The best map might be the same type(Ti=i). if there are multiple solutions with the same cost,
choose the gear with the largest radius.If both the cost and radius you need are found in more than one gear type, choose the type with the smallest index j.
If no radius can be found that allow the distance D to be covered, table should contain 0.
Input
n D
R1 R2 ... Rn
C1 C2 ... Cn
Output
T1 T2 ... Tn| Report Duplicate | Flag | PURGE
Myntra SDE-2 Arrays - 0of 0 votes
AnswersYou are given heights of n candles .
- Rahul Sharma March 11, 2015 in India
First day you lit one candle
second day you need to lit two candles
Third day you need to lit three candles
..........
........
till possible.
After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.
So you need to tell the maximum number number of days , you can carry on lighting the candles.
Example : there are three candles of heights {2 , 2 ,2 }
Answer : 3
1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 0of 2 votes
AnswersGiven an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1< j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].
- Rahul Sharma February 26, 2015 in India
**Example:**
For n=6
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.
How can we figure out minimum number of swaps in most effective way ?| Report Duplicate | Flag | PURGE
Google SDE-2 - 0of 0 votes
AnswersScenario : Multi Seller E-commerce Website
- Algorithmist February 26, 2015 in India
Given a list of products in a customer basket find the minimum number of seller required to deliver his order,so as to optimise shipping part.
Assuming you have already have below data
Customer orders products : P1,P2,P3,P4,P5,P6
Products and seller mapping
P1 = [1,2,3,4]
P2=[2,4,5,6]
where 1,2,3 etc denotes seller_ids.
p1| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersFor a given matrix, find the maximum product of k elements. The elements can be formed from continuous 4 elements horizontally, vertically or diagonally. Eg: For k= 4, the maximum product is (6*4*7*9) from the last column,
- mailtosano February 13, 2015 in United States
1 2 0 -1 4
3 1 2 4 6
0 2 3 1 4
1 3 2 0 7
2 1 3 2 9| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a function rev(int i) which reverses the segment of array ar[] from 0-i, Implement a function sort() using rev().
- Rahul Sharma February 07, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Coding - 0of 0 votes
AnswersDesign your own String Pooling system. It should return a String with request of more length. String pool should have strings of different sizes available. When requested, it should just be returned to client and when client is done using string, it should be added back to string pool for other client to use.
- msgsmg January 23, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 - 1of 1 vote
AnswersYou have a file with 100 billion URLS, find first unique URL.
- aks January 19, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 1of 1 vote
AnswersDesign a data structure for following operations in O(1) time.:
- aks January 19, 2015 in India
insert
remove (FIFO)
find MODE| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersDesign an LRU cache, where you remove an element not only by time lapsed since last used but also by a cost associated with each element. F(t, c) is a method to find weight for each element. Where c is cost and t is time since last used.
- aks January 19, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersDesign a TinyURL like Service.
- R@M3$H.N January 16, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Data Structures Problem Solving System Design - 0of 0 votes
Answersyou have experience with a 3x3 Sudoku.Think about 2*2 sudoku:
- Rahul Sharma January 13, 2015 in India
The array has 4 rows and 4 columns.
The numbers 1, 2, 3 and 4, each appears exactly once in each row.
The numbers 1, 2, 3 and 4, each appears exactly once in each column.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 1, 2 and columns 1, 2.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 1, 2 and columns 3, 4.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 3, 4 and columns 1, 2.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 3, 4 and columns 3, 4.
Your task is:
1. Count all possible different solutions of the 2*2 sudoku.
2.Print all solutions.
3.Store all solutions.| Report Duplicate | Flag | PURGE
Google SDE-2 - -1of 1 vote
AnswersDesign a site similar to junglee.com. Assume you are given a crawler, design a distributed system , what ds will you use , some basic api’s etc.
- sh January 12, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 System Design - 0of 0 votes
AnswersWrite a code to find if a link list is palindrome . Linklist consists variable string at each node. for eg
- abhi January 12, 2015 in India
a->bcd->ef->g->f->ed->c->ba
The above given linklist is palindrome and func shd return - True| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersDesign and Implement a Telephone database structure in which a Customer Entry has PhoneNum,Name,Address.
- R@M3$H.N December 31, 2014 in United States
a) Given any PhoneNum return all the Customer details
b) Given any Name list all the Entries (As Name can be duplicate, only PhoneNum is unique)
c) Also Name searching should support Prefix Based.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 2of 2 votes
AnswersConstructing Bridges:
- R@M3$H.N December 25, 2014 in India
A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river.
Construct as many Non-Crossing Bridges as possible.
Input:
Above Bank >> 7 4 3 6 2 1 5
Below Bank >> 5 3 2 4 6 1 7
are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)
Output:
(1,1) (3,2) (4,3) (6,4) (7,5)| Report Duplicate | Flag | PURGE
StartUp SDE-2 Algorithm Data Structures - 0of 0 votes
AnswersImplement the divide of two integers without using the divide operator.
- JSDUDE December 12, 2014 in United States for AWS Infrastructure Planning, Analysis and Optimization
After implementing the O(n) algorithm to subtract the divisor from the divider, he asked me to implement a better algorithm.
I started working towards bit manipulation, but ran out of time.
He also hinted that I could have used binary search. Not sure how though.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Math & Computation - 0of 0 votes
AnswerGiven a stack of magazines create an anonymous love note (pick words or alphabets from the magazine and create the note)...
- JSDUDE December 12, 2014 in United States for AWS Infrastructure Planning, Analysis and Optimization
He gave me the choice of handling words or alphabets
Assume you have a scanned copy of the magazine as a string.
Once I implemented both words and alphabets, he asked me to scale it to mass production and maximize the throughput of a fulfillment center handling this| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersDesign a robot that will take your order and make sandwiches for you.
- JSDUDE December 12, 2014 in United States for AWS Infrastructure Planning, Analysis and Optimization
Once I was done with this, I was supposed to extend it to have multiple robots doing this job like an assembly line handling multiple sandwiches and other edible items
Once I handled that, he asked me to create a web service for this that will handle online ordering. He also wanted me to implement fulfillment centers| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 4of 4 votes
AnswersWrite code/ logic to count number of words in a string delimited by " ". Anything apart form " " are ignore for the counting. String could be very big as big as 5 GB of data. So add logic to handle such large strings..
- Jai December 12, 2014 in United States
ex: aaa b c ddd e = Count (5)
aaaaaaaaaaa = Count(1)
a
b
c
d
Count(1) as there are no spaces rather carriage returns are found.
PS: In case above question is not clear do let me know.| Report Duplicate | Flag | PURGE
SDE-2 Arrays - 1of 3 votes
AnswersGiven two input string check if anyone is substring of other.
- Jai December 10, 2014 in United States
example aaaaaabbb, aaaabbb
return true
PS: Don't use any internal string library :)| Report Duplicate | Flag | PURGE
SDE-2 Algorithm - 0of 0 votes
AnswersGiven a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.
- hacker123 December 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Arrays - 0of 0 votes
Answers6 / \ 3 5 / \ \ 2 5 4 / \ 7 4
There are 4 leaves, hence 4 root to leaf paths:
- jeevanus November 17, 2014 in India for Hydrabad
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| Report Duplicate | Flag | PURGE
Amazon SDE-2