## SDE1 Interview Questions

- 0of 0 votes

AnswersMice and holes are placed in a straight line. There are n holes on this line. Each hole can accomodate only 1 mouse. A mouse can stay at his position, move one step right from x to x+1, or move one step left from x to x−1. Any of these moves consumes 1 minute.

- Selfies September 13, 2014 in -

Assign mice to holes so that the time when the last mouse gets inside a hole is minimized.

for example if there are 3 mice positions of mice are:

4 -4 2

positions of holes are:

4 0 5

the answer should be 4

because:

Assign mouse at position x=4 to hole at position x=4 : Time taken is 0 minutes

Assign mouse at postion x=-4 to hole at position x=0 : Time taken is 4 minutes

Assign mouse at postion x=2 to hole at postion x=5 : Time taken is 3 minutes

After 4 minutes all of the mice are in the holes.| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 6 votes

AnswersThere are a large number of leaves eaten by caterpillars. There are 'K"' caterpillars which jump onto the leaves in a pre-determined sequence. All caterpillars start at position 0 and jump onto the leaves at positions 1,2,3...,N. Note that there is no leaf at position 0.

Each caterpillar has an associated 'jump-number'. Let the jump-number of the i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves in the order 1,241,3*1,... till it reaches the end of the leaves - i.e, it eats the leaves at the positions which are multiples of /'.

Given a set 'A' of 'IC elements. 'e<=15.,. 'N'<=109, we need to determine the number of uneaten leaves.

Input Format:

N -number of leaves

A - Given array of integers

Output Format:

An integer denoting the number of uneaten leaves.

Sample Input:

N = 10

A = [2,4,5]

Sample Output:

4

Explanation

1,3,7,9 are the leaves which are never eaten. All leaves which are multiples of 2, 4, and 5 have been eaten.

Java Code:

- balakrishna.pininti September 09, 2014 in United States`public class Solution { //need to complete the function below static int countUneatenLeave(int N, int[] A { } public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); final String fileName = System.getenv("OUTPUT_PATH"); BufferedWriter bw = new BufferedWriter(new FileWriter(fileName)); int res; int _N; _N = Integer.parseInt(in.nextLine()); int _A_size = Integer.parseInt(in.nextLine()); int[] _A = new int(_A_size]; int _A_item; for(int _A_i = 0; _A_i < _A_size; _A_i++) { _A_item = Integer.parseInt(in.nextLine()); _A[_A_i] = _A_item; } res = countUneatenLeaves(_N,_A); bw.write(String.valueOf(res)); bw.newLine(); bw.close(); } }`

| Report Duplicate | Flag | PURGE

Google SDE1 Developer Program Engineer Algorithm - 5of 5 votes

AnswersGiven a Sorted integer array which is rotated N number of times. You have no idea what that N is. An element in the array can occur more for any number of time. Write a method to search the position of a given element. If there are more than one of the same element, return the position of the first element.

- jeevanus September 04, 2014 in India for Microsoft CRM| Report Duplicate | Flag | PURGE

Microsoft SDE1 Algorithm Data Structures Sorting - 0of 0 votes

AnswersRecursively implement a function that returns boolean value by checking if a binary tree is binary search tree or not.

- mohanraj1311 September 03, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - -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 ﬁnite, 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 ﬁnding 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

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window