SDE1 Interview Questions
- -6of 6 votes
AnswersTraveling Salesman Problem
- blessedmanisha86 August 31, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersThere is a compressed string eg. ”ab2c3”, the string has lowercase characters and numbers. We can uncompress the given string as follows: whenever we get a number “n” in the string, the portion of the string before the number will repeat “n” times. So in the above example, we get a 2, so string will become “ababc3”, now we get a 3, so final string will be “ababcababcababc”.
- Rahul Sharma August 28, 2014 in India
Given a compressed string and a number k, you have to output the k’th character in the uncompressed string.
1 <= length of string <= 1500
1 <= n <= 1000
1 <= k < 2^31
example:
input: ab2c3 10
output: c| Report Duplicate | Flag | PURGE
Directi SDE1 Algorithm - 0of 0 votes
AnswersOn a very large rotated sorted array with one or more duplicates, find the index of a particular number: 20,30,30,45,60,60,5,17,17,19
- Digi Digi August 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersHow would you architect a client based recommendation feature(based on customer history) on product detail page?
- Digi Digi August 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersDesign Customers who viewed this also viewed that for an online shopping portal
- Digi Digi August 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersConsider a regular polygon with N vertices labelled 1..N. In how many ways can you draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line segment joining two non adjacent vertices of the polygon.
- Rahul Sharma August 24, 2014 in India
Input:
The first line contains the number of test cases T. Each of the next T lines contain two integers N and K.
Output:
Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000003.
Constraints:
1 <= T <= 10000
4 <= N <= 10^9
1 <= K <= N
Sample Input:
3
4 1
5 2
5 3
Sample Output:
2
5
0
Explanation:
For the first case, there are clearly 2 ways to draw 1 diagonal - 1 to 3, or 2 to 4. (Assuming the vertices are labelled 1..N in cyclic order).
For the third case, at most 2 non-intersecting diagonals can be drawn in a 5-gon, and so the answer is 0.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersThere are 8 statues 0,1,2,3,4,5,6,7 . Each statue is pointing in one of the following four direction North, South, East or West.
- viksolanram4 August 18, 2014 in United States
John would like to arrange the statues so that they all point in same direction. However John is restricted to the following 8 moves which correspond to rotation each statue listed 90 degrees clockwise. (N to E, E to S, S to W, W to N)
Move A: 0,1
B: 0,1,2
C: 1,4,5,6
D: 2,5
E: 3,5
F: 3,7
G: 5,7
H: 6,7
Help John figure out fewest number of moves to help point all statues in one direction.
Input : A string initialpos consisting of 8 chars. Each char is either 'N,'S,'E,'W'
Output: An integer which represents fewest no. of moves needed to arrange statues in same direction. If no sequence possible then return -1.
Sample test cases:
input: SSSSSSSS
Output: 0
Explanation: All statues point in same direction. So it takes 0 moves
Test case 1:
Input : WWNNNNNN
Output: 1
Exp: John can use Move A which will make all statues point to North
Test Case 3:
input: NNSEWSWN
Output: 6
Exp: John uses Move A twice, B once, F twice, G once. This will result in all statues facing W.
Note: Read input from stdin and output from stdout| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven a set of restaurants (the number being quite large) and its geographical location(x,y) , you are allowed to do an significant amount of pre-processing on it. Now suppose there are x customers located at position (s,t), design an efficient algorithm to find the k nearest restaurants to these customers.
- Rahul Sharma August 16, 2014 in India| Report Duplicate | Flag | PURGE
Directi SDE1 - 2of 2 votes
Answershow to do this round1 question 1:
- dsAlgo August 15, 2014 in India
http://www.geeksforgeeks.org/directi-interview-set-5-campus/
A string can contain only a, b or c. There cannot be 2 consecutive same character. First and last character cannot be same. Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’. We need to find the string replacing ‘?’ that satisfy the above conditions. For multiple answer display lexicographically smallest string. For no answer possible display “Not Possible”.| Report Duplicate | Flag | PURGE
Directi SDE1 - 0of 0 votes
AnswersHow to remove file named "~" ?
- Pinky August 09, 2014 in India for ECOX| Report Duplicate | Flag | PURGE
Amazon SDE1 Unix - 2of 2 votes
AnswersGiven a file containing a list of ip addresses that have lost their dots(.'s), write a program to find the ip addresses, assume ipv4. input: 11111 output. 1.1.1.11, 11.1.1.1, etc
- rk August 09, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 - 2of 2 votes
AnswersYou are given an array of both negative and positive integers. You need to rearrange the array such that positive and negative numbers alternate. Also, the order should be same as previous array and only O(1) auxiliary space can be used and time complexity boundation O(n).
- peechus July 29, 2014 in United States
eg. -2 3 4 5 -1 -6 7 9 1
result – 3 -2 4 -1 5 -6 7 9 1.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
Answerswe have website having several web-pages. And also there are lot many user who are accessing the web-site.
- Rahul Sharma July 28, 2014 in India
say user 1 has access pattern : x->y->z->a->b->c->d->e->f
user 2 has access pattern : z->a->b->c->d
user 3 has access pattern : y->z->a->b->c->d
user 4 has access pattern : a->b->c->d
and list goes on for lot many users which are finite and numbered.
Now the question is we have to determine the top 3 most occurring k-Page-sequence.
for the above example result will be : (k=3) a->b->c , b->c->d , z->a->b.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 5of 5 votes
AnswersWrite a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1
- 3139a1m July 02, 2014 in India
e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28
ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1
I gave the obvious o(n^2) solution. He asked to optimize it.| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm - 0of 0 votes
AnswersWrite a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1
- 3139a1m July 02, 2014 in India
e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28
ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm - 4of 4 votes
AnswersTwo finite, strictly increasing, integer sequences are given. Any common integer between the two sequences constitute an intersection point. Take for example the following two sequences where intersection points are
- blackfever June 29, 2014 in India
printed in bold:
First= 3 5 7 9 20 25 30 40 55 56 57 60 62
Second= 1 4 7 11 14 25 44 47 55 57 100
You can ‘walk” over these two sequences in the following way:
1. You may start at the beginning of any of the two sequences. Now start moving forward.
2. At each intersection point, you have the choice of either continuing with the same sequence you’re currently on, or switching to the other sequence.
The objective is finding a path that produces the maximum sum of data you walked over. In the above example, the largest possible sum is 450 which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62
this is the same problem which I saw in SPOJ Problem Set| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWrite a java program to evaluate given arithmetic expression to get maximum possible answer. ( Expression will contain only 3 type of operations +,-,* ). it will not contain any brackets. so the order of operator precedence will not be there. any part of the expression can be executed in any order to get the maximum possible ans.
- sedhuait June 27, 2014 in India| Report Duplicate | Flag | PURGE
Broadsoft SDE1 - 0of 0 votes
AnswersReverse the alternate level nodes of the binary tree.
- singhvivekpes June 25, 2014 in United States
a
/ \
b c
/ \ / \
d e f g
/ \ / \ / \ / \
h i j k l m n o
Modified tree:
a
/ \
c b
/ \ / \
d e f g
/ \ / \ / \ / \
o n m l k j i h| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 4 votes
AnswersGiven a complete binary tree, Find a Max element
- sLion June 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Data Structures - 0of 0 votes
AnswersBase class is given you need to stop exposing the base class methods without touching the base class at all.
- hareendrareddy June 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Java - 0of 0 votes
AnswersWhat happens when you enter URL in browser.
- suresh June 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWrite a program to convert a decimal number into binary your code should work on both big endian and small endian machine. U have given a variable which tell u whether machine is big endian or small endian
- suresh June 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven a graph, if we were to print all nodes within k hops of a given node, which algorithm would we use, the answer to this was obviously a Breadth first search. He followed it up asking, if one were to use Depth first search instead to code this problem instead, one would encounter bloated running times for Graphs with certain attributes (Perhaps Dense graphs or some such). Describe what types of graphs would a DFS algorithm falter with and why.
- suresh June 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven a floor of dimensions 2 x W and tiles of dimensions 2 x 1, write code to find the number of ways the floor can be tiled.
- suresh June 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersYou are given a sequence of black and white horses, and a set of k stables numbered 1 to k. You have to accommodate the horses into the stables in such a way that the following conditions are satisfied:
- suresh June 07, 2014 in India
a. You fill the horses into the stables preserving the order of horses. For instance, you cannot put for horse 1 into stable 2 and horse 2 into stable 1. You have to preserve the ordering of horses.
b. No stable should be empty and No horse should be left unaccommodated.
c. Take the product (number of white horses * number of black horses) for each stable and take the sum of all these products. This value should be the minimum among all possible accommodation arrangements.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm