## SDE1 Interview Questions

- 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 - 1of 1 vote

AnswersPrint permutations of a string.

- Sugarcane_farmer June 01, 2014 in India

I started with the recursive answer. He asked me the complexity. (Had no idea). But is was large

Then he asked me, if i could optimise it. I said i could sense this can be done using DP. Could not get how to do it though.

I had quick perm code, but dint understand it(saw it night prev to interview) so dint answer that.| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

Answersimplement bool isFactorialDivisible( int x, int y)

- suresh June 01, 2014 in India

Return true if x! is divisible by y

else return false| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersGiven a continuous stream of strings, maintain strings such that duplicate are eliminated on the fly. The interviewer wanted working code. So coded the solution during the interview and emailed it to him 10 mins after.

- suresh June 01, 2014 in India

So if you get “Ted”, “John”, “Mark”, “Ted”, “David”, at the moment in

time, the list should contain John, Mark, David| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersFoo was not amongst the most brilliant students of his class. So, he has some pending exams to clear. As the exams are approaching, this time he vowed to pass in all of them. This will only happen if he is not under stress. Foo's stress can be calculated using a simple function called Foo_function which depends upon the time for which Foo studies continuously .

- avinash.it09 June 01, 2014 in India

Foo_funtion is defined as follows:

F(t)=A(t^3)+B(t^2)+C*(t)+D, F(t)<=10^18

where A,B,C,D belong to the set of prime numbers. t is the time in minutes for which foo studies continuously.

As foo is not very good at solving cubic equations, he seeks your help to find out the maximum number of minutes for which he can study continuously without taking stress. Help him find t such that F(t+1) > K, and F(t) <= K, where K is the maximum stress Foo can bear.

Input:

The first line of the input contains a single integer T denoting the number of test cases. each test case consists of a single line containing 5 space seperated positive numbers a, b, c, d, K.

Output:

for each test case, output a single integer t denoting the maximum time for which foo can study continuously without taking stress.

Constraints:

1 <= T <= 10^4

A, B, C, D belong to a set of prime numbers such that F(t) would never exceed 10^18

t >= 0

1 <= K <= 10^18

Sample Input (Plaintext Link)

2

2 2 2 2 10

2 3 5 7 1000

Sample Output (Plaintext Link)

1

7

Explanation

In the 1st test case for t = 2 foo will be under stress because F(2)=30 > K, therefore he can study for a maximum time of 1 minute without having stress.

In the 2nd test case for t = 8 foo will be under stess because F(8)=1263 > K, therefore he can study for a maximum time of 7 minutes continuously without having stress.

Time Limit 5 sec(s) (Time limit is for each input file.)

Memory Limit256 MB

Source Limit1024 KB| Report Duplicate | Flag | PURGE

InMobi SDE1 Algorithm - -1of 1 vote

AnswersGiven a integer N, print the decimal form of 1/2n.

- avinash.it09 May 31, 2014 in India

Example:

N=1, print 0.5

N=2, print 0.25

Adding leading/unsignificant zeroes will lead to wrong answer. Example, printing 0.50 instead of 0.5 in above case will lead to wrong answer.

Input and Output:

First line contains T, the number of testcases. Each testcase consists of N in one line.

Print required answer in one line for each testcase.

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 200

Sample Input (Plaintext Link)

2

2

1

Sample Output (Plaintext Link)

0.25

0.5

Explanation

You need to print output in decimal form only. There is no limit on number of decimal digits in output.

So correct output of 100 will be "0.0000000000000000000000000000007888609052210118054117285652827862296732064351090230047702789306640625"

Time Limit1 sec(s) (Time limit is for each input file.)

Memory Limit256 MB

Source Limit1024 KB| Report Duplicate | Flag | PURGE

InMobi SDE1 - 0of 2 votes

AnswersUse smart ways to find prime factors and then arrive at the result for large A & B in input. Bruteforce won't work.

- avinash.it09 May 31, 2014 in United States

Given A,B print the number of pairs (a,b) such that GCD(a,b)=1 and 1<=a<=A and 1<=b<=B.

Input:

First line contains an integer T, the number of testcases. Each of next T lines contains two space separated integers denoting Aand B.

Output:

Output T lines, each containing single integer, the required output for each test-case.

Constraints:

1 <= T <= 10

1 <= A <= 10^5

1 <= B <= 10^5

Sample Input (Plaintext Link)

1

3 2

Sample Output (Plaintext Link)

5

Explanation

1,1

1,2

2,1

3,1

3,2

Time Limit5 sec(s) (Time limit is for each input file.)

Memory Limit256 MB

Source Limit1024 KB| Report Duplicate | Flag | PURGE

Amazon SDE1 - 1of 1 vote

AnswersGiven a BST, find out the minimum length form root to leaf with sum S. Note that:

- Nascent May 29, 2014 in India

a) Path from root to leaf node.

b) Sum of node of the path is S.

c) if multiple such path exist, print minimum length path.

d) What is advantage of BST rather than BT used for this algorithm, how it improve the performance. in BST, is it required to explore both side ?| Report Duplicate | Flag | PURGE

Microsoft SDE1 - 1of 1 vote

AnswersYou have given M array each of size n all array are sorted separately write a program to make a big sorted array of size m*n . during discussion he told me to prove many lemma like height of tree is log(n)( for n elements) sum of n natural number is (n*n+1)/2 and many more. He modified problem many times don’t use extra space do it in space etc.

- suresh May 22, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 1of 1 vote

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 May 22, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersU have given 10 files and you have given a string suggest data structure which ll facilitate efficient search of string in the file if string appears more than ones in that case u have to print line number and file in which they appear.

- suresh May 22, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 4of 6 votes

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:

- nishu May 21, 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 - 0of 0 votes

AnswersLet's say a website attracts a lot of traffic . How would you find at what instant of time (milliseconds or seconds , assume as you want) the traffic was super high ? What data structure would you go for and why ?

- AlgoBaba May 20, 2014 in India| Report Duplicate | Flag | PURGE

Flipkart SDE1 Algorithm - -3of 3 votes

AnswersDraw a graph as a graph. Assume there is graphics library to draw lines and all. Just tell how will you order the vertices such that the edges don't intersect and they seem ordered.

- kenadams.awesome May 18, 2014 in India| Report Duplicate | Flag | PURGE

Google SDE1 Data Structures - 0of 2 votes

AnswersNeed to implement something like pastebin wherein you paste some text, you are given an url. The url can be used anywhere to access the text.

- kenadams.awesome May 18, 2014 in India

Various problems, features and design of this architecture were discussed.| Report Duplicate | Flag | PURGE

Google SDE1 System Design - 0of 0 votes

AnswersThere are N lanes, and the speed of each lane is given. There are many cars in all the lanes and the start position and the length of each car and its corresponding lane is given. There is a frog which an do 2 functions: wait() or jump().

- kenadams.awesome May 18, 2014 in India

Find if there is a path for the frog to go from lane 1 to lane N without getting hit by any of the moving cars.| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 0of 0 votes

AnswersYou are given very huge file , with each line containing a single word. We have to give the count and word which is repeated most. I answer of using TRIE data structure to hold the word. I am reading a word at a time and incrementing the counter if i am getting the same word. I am keeping a global max count to keep the max count and the word. Complexity will be O(total letters in the file);

- ur.devesh May 16, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersGiven a binary search tree (BST) with each node having some value. You have to compute for each node the summation of all nodes whose value is greater than the current node.I have used the DFS kind of algorithm.

- ur.devesh May 16, 2014 in United States`Dictionary<node,bool> visited = new Dictionary<node,bool>(); int Traverse(node n ) { if(node.Right == null) if(node.Left != null && !visited(node.Left)) Traverse(node.Left); return node.value; node.Summation = Traverse(node.Right); if(node.Left != null && !visited(node.Left)) Traverse(node.Left); return node.Value + node.Summation; }`

| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersGiven a table of the form:

- 14mit1010 May 11, 2014 in United States

1 A,B,C,A,B

2 A,B,A,A,A

3 C,D,C

Give the number of duplicate characters, eg: for 1 there are 2 A's and 2 B's, so the result is 2

For 2 A is repeated 4 times so the result is 3

For 3, C is repeated twice so the result is 1

My suggestion was to use a CLRSQL function to calculate it| Report Duplicate | Flag | PURGE

Microsoft SDE1 SQL - 0of 0 votes

AnswersProvided a number dictionary and a number, x , which is formed from the number dictionary. Find the rank of the number x? Rank is defined as the position of the number x when all the number formed from the dictionary are sorted.

- ASimpleCoder May 10, 2014 in India

Example

Input :{4,1,5}

X : 451

Output : 4

(145,154,415,451,514,541). 451 comes at 4th position| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersWrite a binary search function in C that will work for any datatype. You cannot accept the datatype in the function arguments.

- Sanyam Jain May 03, 2014 in India| Report Duplicate | Flag | PURGE

Adobe SDE1 - 0of 0 votes

Answerswrite a program to generate random numbers without using the in-built functions?

- vrajendra.singh.mandloi May 02, 2014 in india| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersMachine Coding 1 hour

- hulk April 26, 2014 in India

------------------------------

U have an organizational structure, which shows hierarchy of the organization. This hierarchy contains employees E or managers M who has some Employees or Managers reporting to M.

Employee has ( id, name, JobDesc, salary etc).

Design the data structure you would be using to store this hierarchy

problem 1: Given an ID of an employee , print all the employee ID's who are directly reporting or indirectly reporting to the manager.

problem 2: prefix search of employees by String. If employees have nishant and nikhil. If searched by "ni" we need to print all details of both nishant and nikhil.

problem 3(bonus): search should print all emloyee's and their details if a given string is subString of the name of an employee.(Like a phonebook contacts search)

P.S- This was asked to one of my friend in Flipkart.| Report Duplicate | Flag | PURGE

Flipkart SDE1 Data Structures - 4of 4 votes

AnswersGiven a random generator rand(5) which generates numbers between 0 to 4. How do u generate numbers between 0 to 6, I.e. Implement rand(7).

- hulk April 16, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm Brain Teasers - 4of 4 votes

AnswersCar parking problem. An array given represents actual order of cars need to be parked. Like for example order is 4,6,5,1,7,3,2,empty. If cars are parked in some order like empty,1,2,3,7,6,4,2. Some person needs to get them into correct order, list out all instructions to the person to get in correct order with least number of swaps.

- hulk April 16, 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