SDE-2 Interview Questions
- 1of 1 vote
AnswersHow 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.
- anurag6989 August 21, 2014 in India
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.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - -1of 1 vote
Answersan 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.
- Rahul Sharma August 20, 2014 in India| Report Duplicate | Flag | PURGE
Directi SDE-2 Algorithm - 0of 0 votes
AnswersStore 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
- geekrocker August 18, 2014 in India| Report Duplicate | Flag | PURGE
Sonoa Systems SDE-2 Problem Solving - 0of 0 votes
AnswersHi, I was asked a this one at the interview. Below is the problem statement:
- vaibhavrastogi4 August 13, 2014 in United States
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.| Report Duplicate | Flag | PURGE
Cisco Systems SDE-2 Algorithm - 3of 3 votes
AnswersGiven a 2 dimensional matrix where some of the elements are filled with 1 and rest of the elements
- mknarayan1711 August 02, 2014 in India for Media Experience Team
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| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven an array of heights of poles. Find the no of poles which are visible if you are standing at the ith pole
- Rahul Sharma July 26, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersTraverse a given 2D matrix from given source to destination in such way that every cell should be visited exactly one time (we have to cover all cells of matrix exactly once and have to reach at destination).
- Rahul Sharma July 12, 2014 in India| Report Duplicate | Flag | PURGE
Oracle SDE-2 Algorithm - 2of 2 votes
AnswersGiven N sets of integers, remove some sets so that the remaining all sets are disjoint with one another. Find the optimal solution so that the number of sets remaining at the end is maximum
- Rahul Sharma July 12, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersDifference between struct and class.
- JSDUDE June 25, 2014 in United States for LSB
When would you use one over the other
What is padding? Do both struct and class have padding| Report Duplicate | Flag | PURGE
Expedia SDE-2 Object Oriented Design - 0of 0 votes
AnswersExplain the underlying working of how inherited function gets invoked. So if Dog and Cat, inherited from Animal, inherit Eats. How does the right Eats get called for Dog/Cat
- JSDUDE June 25, 2014 in United States for LSB
private inheritance vs composition
When would you use private inheritance| Report Duplicate | Flag | PURGE
Expedia SDE-2 Object Oriented Design - 0of 0 votes
AnswersWhat is a static function? Explain in detail
- JSDUDE June 25, 2014 in United States for LSB| Report Duplicate | Flag | PURGE
Expedia SDE-2 Object Oriented Design - 0of 0 votes
AnswersImplement an atoi function in C++
- JSDUDE June 25, 2014 in United States for LSB| Report Duplicate | Flag | PURGE
Expedia SDE-2 Algorithm - 0of 0 votes
AnswersDifference between threads and process.
- JSDUDE June 25, 2014 in United States for LSB
When would you use one vs the other
Where on the stack are values stored for their local variables?
If there are two threads each with two local variables, where will these variables be stored| Report Duplicate | Flag | PURGE
Expedia SDE-2 Threads - 0of 0 votes
AnswersYou have a rabbit who wants to cross a river by jumping over the various rocks in it. All the rocks are in a straight line and the distance between them is also given. Your rabbit can only perform jumps of specific lengths. You have to output the minimum number of jumps required to cross the river (if possible). Rabbits can jump both in forward and backward direction.
- k.87.sharma June 25, 2014 in India
The number of rocks is M and the number of possible jump lengths is N.
For e.g. M=4 , N=2,
distance between m1-m2= 1
m2-m3= 2
m3-m4 =1
rabbit can perfrom jump of length 3 and 1.
output= 2 (minimum jump to cross the river)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a List of Students that are already sorted based on names, write a function to return list of students that is sorted based on grade (four possible grades are a,b,c and d). If two students has same grade, they should be sorted internally based on name.
I have written a code based on bucket sort. Something like this. Not sure whether this is optimal.
- dumUser June 06, 2014 in United Statespublic List<Student> sortByGrade(List<Student> students) { List<Student> aGradeStudents = new LinkedList<Student>(); List<Student> bGradeStudents = new LinkedList<Student>(); List<Student> cGradeStudents = new LinkedList<Student>(); List<Student> dGradeStudents = new LinkedList<Student>(); for(Student st : students) { switch(st.getGrade()) { case 'a' : aGradeStudents.add(st); break; case 'b' : bGradeStudents.add(st); break; case 'c' : cGradeStudents.add(st); break; case 'd' : dGradeStudents.add(st); break; }; } List<Student> sortedStudents = new LinkedList<Student>(); sortedStudents.addAll(aGradeSudents); sortedStudents.addAll(bGradeSudents); sortedStudents.addAll(cGradeSudents); sortedStudents.addAll(dGradeSudents); }
| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven an array of sorted numbers, find the index of first occurrence of the given number.
- dumUser June 06, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersWrite a function, for a given number, print out all possible way to make up that number eg: 2 - 1 1,2
- sLion May 25, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersA furniture can be made of material like metal, wood, .... Also there are different furniture types chair, table, sofa. A wood furniture should be tested against choaking. metal furniture is tested against fire, etc. Design these in OOAD.
- geekyjaks May 24, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 0of 0 votes
AnswersThere are N nodes. Each node has a non negative integer value. Define a optimistic algorithm which ensures that all node has all other node's value.
- geekyjaks May 24, 2014 in India
Constraint: While a node is sending data to another data, it can't receive data, vice versa.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 16of 18 votes
AnswersMachine Coding:
- ponmurugesh2012 May 20, 2014 in India
Design and code application similar to IPL website.
1. There are players who belong different teams [CSK, RCB,etc].
2. User can create their own team from the player set
3. When a match happens, there are possible outcome in each ball [one run, six, wicket, run-out, etc]
4. on each outcome, players involved will get points [eg: six = batsman 5 points, wicket = batsman minus 5 and bowler +5, etc]
5. Based on outcome, the user created team also should be able to calculate his points.
6. Solution should be working code, extensible and performance.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Coding - 0of 0 votes
AnswersYou 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.
- poorna.chandra.akp May 19, 2014 in India
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| Report Duplicate | Flag | PURGE
InMobi SDE-2 - 1of 1 vote
AnswersHuman gene consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T.
- poorna.chandra.akp May 19, 2014 in India
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| Report Duplicate | Flag | PURGE
InMobi SDE-2 - 0of 0 votes
AnswerYou 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.
- poorna.chandra.akp May 19, 2014 in India
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| Report Duplicate | Flag | PURGE
InMobi SDE-2 - 0of 0 votes
AnswersYou 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).
- iwanna May 05, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersImplement multiple producer and multiple consumer problem in java.
- hulk May 03, 2014 in India| Report Duplicate | Flag | PURGE
Infibeam SDE-2 Java - 1of 1 vote
AnswersFor a given binary search tree, replace each node with sum of all node which are greater then of equal to current node.
- Razz May 02, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 0of 0 votes
AnswersGiven two tables
- hulk April 29, 2014 in India
1. Candidate having: Id , Name
2. Vote: Id, CandidateId
Give query to give the name of the winning candidate| Report Duplicate | Flag | PURGE
Infibeam SDE-2 SQL