SDE-2 Interview Questions
- 0of 0 votes
AnswersHow will you implement a dictionary.
- Nascent August 08, 2016 in India| Report Duplicate | Flag | PURGE
Microsoft SDE-2 - 0of 0 votes
AnswerDesign a monitoring system for hotel booking site. Proper oops design.
- Nascent August 08, 2016 in India| Report Duplicate | Flag | PURGE
Microsoft SDE-2 - 1of 1 vote
AnswersGiven two strings, print all the inter-leavings of the Strings in which characters from two strings should be in same order as they were in original strings.
- mrityunjay21 July 26, 2016 in United States for Payments
e.g.
for "abc", "de", print all of these:
adebc, abdec, adbce, deabc, dabce, etc, etc| Report Duplicate | Flag | PURGE
Amazon SDE-2 Behavioral - 2of 2 votes
AnswersGiven a matrix of positive integers, you have to reach from the top left corner to the bottom right in minimum cost. You can only go one square right, down or diagonally right-down. Cost is the sum of squares you've covered. Return the minimum cost.
- mrityunjay21 July 26, 2016 in India for Payments
e.g.
4 5 6
1 2 3
0 1 2
Answer: 8 (4+1+0+1+2)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - 2of 2 votes
AnswersFind the length of maximum number of consecutive numbers jumbled up in an array.
- mrityunjay21 July 26, 2016 in India for Payments
e.g.: 1, 94, 93, 1000, 2, 92, 1001 should return 3 for 92, 93, 94| Report Duplicate | Flag | PURGE
Amazon SDE-2 Arrays - 3of 3 votes
AnswersA program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35
- gadha July 21, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures Java Object Oriented Design - -1of 1 vote
AnswersThis is a interview question which needs to be optimized for time.
- Abhi July 19, 2016 in India
Suppose you have a 2 dimensional Array and you have a String say "Amazon" inside the Array such that the individual characters can be present from Left to Right, Right to Left, Top to down and down to up.
I will explain with example :
char[][] a = {
{B,B,A,B,B,N},
{B,B,M,B,B,O},
{B,B,A,B,B,Z},
{N,O,Z,B,B,A},
{B,B,B,B,B,M},
{B,B,B,B,B,A}
};
The above Array has two Amazon Strings. You need to return the count of number of such strings present.| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersMilly and Pranjul are playing a game in which Pranjul will give an index of a chocolate.
- claud.qualityinfo July 14, 2016 in India
Then, Milly has to tell him the box number in which that chocolate is in. There are N
such boxes and Ci chocolates are there in ith the box. Description of index is given below
:
Suppose there are A1, A2 … AN chocolates in 1st, 2nd… Nth boxes respectively. So,
indexing of chocolates in 1st box will be from 1 to A1, similarly in 2nd box indexing will be
A1 + 1 to A2 … and indexing in Nth box will be from AN-1 + 1 to AN.
Milly is blind folded so she can’t see the boxes. You are required to help her.
Input
First line will contain N (No. of boxes). Next line will contain N space separated
integers denoting Ci, the number of chocolates in ith box.
Next line will contain Q (No. of times Pranjul will ask her). Then each next Q lines
will contain the asked index I.
Output
For every query, print in a new line : the box number in which that index of
chocolate is in.
Constraints
1 ≤ N, Q ≤ 105
1 ≤ Ci ≤ 10
1 ≤ Σ Ci ≤ 106
1 ≤ I ≤ Σ Ci| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersGiven input format, The first line has the number of employees of a company Z. The next two lines have employees to perform certain operations on. The first employee of the fourth line can be assumed to be the ceo of the company. Each line from then on has the format Employee X Employee Y where X manages Y. (and hence Y forms the child for X).
- thisandthat July 04, 2016 in India
input:
6
Rajesh
Ravi
//Tree Starts here
Ram Raj
Ram Goku
Raj Rajesh
Raj Richa
Richa Ravi
Its known that each person in the company can directly line manage a maximum of 2 other employees.
For the two employees in the first two lines, find the lowest common manager.
How to construct this tree in java to eventually do an lca?| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 1of 1 vote
AnswersYou are given an old touch smartphone numbers having dial pad and calculator app.
- tambimitesh22 July 01, 2016 in United States
The goal is to type a number on dialpad.
Calculator have 1-9 and +,-,*,/,= as operations. But as phone is old, some of the numbers and some operations can't be touched.
But you can always make a number using other numbers and operations. There could be multiple ways of making a number. You have to find minimum operation for making a number.
For ex: lets say 1,4,6,7,8,9 works and +,-,* works.
2,3,5 and / doesn't work.
If you have to type 18-> 2 operations. (Each touch is considered an operation)
If you have to type 5 -> '1+4=' that requires 4 operations. There could be other ways to make '5'.
The goal is to find minimum operations.| Report Duplicate | Flag | PURGE
Samsung SDE-2 Algorithm - 0of 0 votes
AnswersDesign for online card game say like poker or any other game. The classes etc..
- SS June 30, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 design - 0of 0 votes
AnswersDesign Food Panda or online food ordering system.
- SS June 30, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 design - 1of 1 vote
AnswersChess Knight Problem: - It deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location.
- SS June 30, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersGiven a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).
- ankit3600 June 14, 2016 in India
Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.
Note: all coordinates are real numbers
(a,b)
|----------------------------------------------|
|.......................................................|end
|.......................................................|
|start................................................|
|.......................................................|
|----------------------------------------------|(c,d)
Edit: You have to avoid sensors.
Also u can move in any direction any time.| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - -2of 2 votes
AnswersGiven a matrix which is spirally sorted. Remove an element and insert another element maintaining the sorted order.
- neer.1304 June 14, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven two sets of strings A and B. Find the
- neer.1304 June 14, 2016 in United States
(A-B) U (B-A) ( U = union ). The answer should be in lexicographical order and A’s elements should appear before B’s.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswerGiven a few points in first quadrant – (x1,y1) …..(xn,yn) and given another set of points (a1,b1…..an,bn), determine whether all the points (a1,b1…an,bn) have already occured in (x1,y1)…..xn,yn)
- neer.1304 June 14, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a graph where every two nodes are either friends or enemies with each other. Find a way to go from one node to the other.
- neer.1304 June 14, 2016 in United States
Restrictions:
1) You can also travel from one node to next if they are friends with each other
2) You have some “magic potions”. You can convert an enemy path to a friend path with a magic potion.
Find the path with min number of magic potions required.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersA planner wants to deign a city. A city having n points of interest and marked them from 0 - (n-1). Need to write two API:
- Harsh123 June 12, 2016 in India
public void buildRoad(int a, int b); // build road directly between a and b.
public boolean isRoadExist(int a, int b); // Check if there is any road connectivity exist between a & b (either directly or indirectly) then return TRUE else FALSE.
The solution should be in O(log n). You can first try in O(n).| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 0of 2 votes
AnswersWrite all jumbled number which is >0 && <N, where N is provided by the user.
- Harsh123 June 12, 2016 in India
A jumbled number is a number whose neighbour digit (either left or right) max differ by 1 value.
e.g.:
8987 is a jumbled number.
13 is not a jumbled number.
123456 is a jumbled number.
287 is not jumbled number.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 1of 1 vote
Answersprint all the characters present in the given string only once in a reverse order. Time & Space complexity should not be more than O(N).
- anonymous May 31, 2016 in United States
e.g.
1)Given a string aabdceaaabbbcd
the output should be - dcbae
2)Sample String - aaaabbcddddccbbdaaeee
Output - eadbc
3)I/P - aaafffcccddaabbeeddhhhaaabbccddaaaa
O/P - adcbhef
Answer :
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;
public class StringQAmazon {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
String inputStr = sc.nextLine();
System.out.println(stringManipulation(inputStr));
}
static String stringManipulation(String str) {
if(str.isEmpty())
return "";
else if(str.length()==1)
return str;
else {
str.toLowerCase();
StringBuilder strBuilder = new StringBuilder();
strBuilder.append(str);
strBuilder.reverse();
Set<Character> set = new LinkedHashSet<Character>();
for(int i =0; i<strBuilder.length(); i++){
set.add(strBuilder.charAt(i));
}
Iterator<Character> iter = set.iterator();
strBuilder=new StringBuilder();
while(iter.hasNext()){
strBuilder.append(iter.next());
}
return strBuilder.toString();
}
//return null;
}
}| Report Duplicate | Flag | PURGE
Amazon SDE-2 String Manipulation - 0of 0 votes
AnswersYou are given a structure msg
- neer.1304 May 24, 2016 in United States
struct msg
{
long timestamp;
double price;
string label;
};
The msg represents price of a stock on a given timestamp.
Create a class with two functions -
addStockPrice(msg m) -> Used to add Stock Price in Data structure
getAvgPriceForAStockLast10Minutes(String stockName) -> Get average price of a stock for last 10 minutes.
The program should be time and space optimized.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersFind number of islands of '1' in D dimensional array containing '0', '1'. where D > 2.
- prakhar.asthana04 May 24, 2016 in United States| Report Duplicate | Flag | PURGE
xyz SDE-2 Algorithm - 0of 0 votes
Answers...
- anonymous May 23, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 4 votes
AnswersTake an example of the traditional Iterator interface which has the following methods
- lks May 17, 2016 in United States
Interface Iterator<E>{
public boolean hasNext() {}
public E next() {}
public E remove() {}
}
You are given a list of iterators. You have to design a InterleaveIterator class which implements this
interface and implement the methods:
hasNext() and next()
such that these 2 methods returns interleaved values for the list of iterators:
Implement:
class InterleaveIterator<E> implements Iterator<E>{
@override
public boolean hasNext() {}
@override
public E next() {}
}
Example:
ArrayList<Integer> i1 = [1,2,3,4,5].iterator()
List<Node> i2 = [n1,n2].iterator()
Collection<E> i3 = [e1,e2,e3].iterator()
next() method of InterleaveIterator, should return in this sequence [1,n1,e1,2,n2,e3,3,e3,4,5]
Make this InterleaveIterator class generic and make sure that the class can accept a list of iterators
and interleave them| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 0of 0 votes
AnswersDesign and Implement: Producers and Consumer Problem. Producers produce different kind of messages and Consumers register themselves for different kind of messages. Need to design and implement Producer, Consumer and a Delegator which is responsible for storing and delivering the messages to appropriate listeners.
- neer.1304 May 12, 2016 in United States
Changed the question to handle millions of messages.
Changed the question to handle different priority messages.
Threading model for Producer, Listener and Delegator.
In the end he asked me to code 2 methods of Delegator.
1: which adds the message from Producer to its internal queue.
2: Delegate, which delivers the message to appropriate listener.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Software Design - 0of 0 votes
AnswersYou are given a graph and a node in the graph. Group the nodes connected to this node if they are also connected to each other. For example, the graph has nodes 1, 2, 3, 4, 5 where 1 is connected to 2, 3, 4; 2 and 3 are also connected to each other, 4 is just connected to 1 and 5 is a separate node. You are given node 1 as input. Output should be:
- doomguy April 05, 2016 in United States
2 3
4| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersGIven a string "str" and pair of "N" swapping indices, generate a lexicographically largest string. Swapping indices can be reused any number times.
- uvm March 15, 2016 in United States
Eg 1)
String = "abdc"
Indices:
(1,4)
(3,4)
Answer:
cdba, cbad, dbac,dbca
you should print only "dbca" which is lexicographically largest.| Report Duplicate | Flag | PURGE
Facebook SDE-2 Algorithm