SDE1 Interview Questions
- 0of 0 votes
AnswersNuclear Rods
- rayasamharish October 04, 2015 in India
A core meltdown has occurred at the Fubaru nuclear plant. There are
n nuclear fuel rods that are damaged and need to be removed using
specialized radiation-hardened robotic equipment
with solid-lead isolation chambers. Remote imaging has already
uniquely identified every damaged fuel rod and assigned it a number
between 1 and n. The imaging data also records which fuel rods were
fused to each other during the meltdown. Every recovery sortie by the
robot can pick up one set of nuclear fuel rods that are directly or
indirectly fused to each other.
The recovery costs per sortie are proportional to the square root of the
number of fused rods recovered. So the cost is K to recover K rods.
Isolation chambers are available for all positive integer costs (1, 2, 3, …).
An isolation chamber can be used multiple times, and each use will
incur the same cost. The robot can also recover a lower number of rods
than a chamber's capacity on a sortie.
Find the minimal cost to recover all the radioactive rods by completing
the given function.
Input
The first parameter integer n specifies the number of rods. The second
parameter pairs is an array of pairs of rods that are fused together. Each
item in the array contains exactly two integers, P and Q separated by a
space (" "), which means that the rod numbered P is fused to the rod
numbered Q. *Note - Each item in the array is a string which needs to be
parsed to P and Q
Output
2
Constraints
2 ≤ N ≤ 100,000
1 ≤ P, Q ≤ N
P ≠ Q
Sample Input
4
2
1 2
1 4
Sample Output
3
Explanation
Rods #1, #2, #4 are connected to each other (2-1-4) so they are in a
single group of 3. The sortie to recover them will cost 2 (with isolation
chamber capacity 2 = 4). Rod #3 is not fused to any other, so it can be
recovered at a cost of 1 (with isolation chamber capacity 1 = 1).| Report Duplicate | Flag | PURGE
Practo SDE1 - 0of 0 votes
AnswersStringChain
- rayasamharish October 04, 2015 in India
You are given a library with n words (w[0], w[1], ..., w[n - 1]). You
choose a word from it, and in each step, remove one letter from this
word only if doing so yields a another word in the library. What is the
longest possible chain of these removal steps?
Constraints:
1 ≤ n ≤ 50000
1 ≤ the length of each string in w ≤ 50
Each string composed of lowercase ascii letters only.
Input Format:
Complete the function "longest_chain" which contains an array of
strings "w" as its argument.
Output Format:
Return a single integer that represents the length of the longest chain of
character removals possible.
Sample Input #00:
6
a
b
ba
bca
bda
bdca
Sample Output #00:
4| Report Duplicate | Flag | PURGE
Practo SDE1 - 0of 0 votes
Answers(x-1)! % x = -1 in efficient way.
- Ray September 19, 2015 in United States| Report Duplicate | Flag | PURGE
SDE1 Math & Computation - 4of 4 votes
AnswersGiven three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|+|b-c| +|c-a| is minimum.
- Rahul Sharma September 16, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersGiven two strings, return true if they are one edit away from each other, else return false. An edit is insert/replace/delete a character.
- codewarrior September 07, 2015 in United States
Ex. {"abc","ab"}->true, {"abc","adc"}->true, {"abc","cab"}->false| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersGiven a linked list and a positive integer n, reverse the order of nodes in between n and last but n nodes.
- codewarrior September 05, 2015 in United States
example: 1->2->3->4->5, n=2. Output is 1->4->3->2->5| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersGiven a postfix expression as a string, evaluate it and return the result. example : "423+*" ->20. The Postfix expression is well formed(need not check for bad expression)
- codewarrior September 05, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersFind the total number of connected components in a graph (there can be forests)
- codewarrior September 05, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 - 4of 4 votes
AnswersThis is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution.
- satish1987 August 12, 2015 in United States
Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property.
For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further.
Input:
A Single number N for which we want to produce the sequence.
Output:
A space separated list of sequence or NA if there is no possible sequence.
Example Input:
3
Example Output:
2 3 1 2 1 3
Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswerThis is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution.
- satish1987 August 12, 2015 in United States
Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property.
For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further.
Input:
A Single number N for which we want to produce the sequence.
Output:
A space separated list of sequence or NA if there is no possible sequence.
Example Input:
3
Example Output:
2 3 1 2 1 3
Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).| Report Duplicate | Flag | PURGE
Mathworks SDE1 Algorithm - 1of 1 vote
AnswersDesign a data structure in which we can do all CRUD operations in O(1) ?
- Aman Mittal August 07, 2015 in India
CRUD- Create, Retrieve, Update, Delete| Report Duplicate | Flag | PURGE
Flipkart SDE1 Data Structures - 0of 0 votes
AnswersYou have an app that uses a 3rd party video player. The VP has the functionalities - play, pause, seek and close. On close, the VP makes a callback to your app. To the callback it sends the below parameters
- coolcoder3 August 04, 2015 in India
* videoLengthInSecs
* VideoPart[]. VideoPart {startTime, endTime}. Denotes a continuous part of the video that was watched without any disturbance caused by pause, seek.
Your app should be able to determine whether the user has watched the entire video or not.
60, [{0, 30}, {30, 60}]
return boolean| Report Duplicate | Flag | PURGE
StartUp SDE1 Algorithm - 0of 0 votes
AnswersThere are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get atleast one dish of his chioce. What is the minimum number of different type of dishes we can order?
- prashant2006ster July 28, 2015 in India
Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row.
n = 6 k = 7
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 1 0 0
0 0 1 0 0 1 0
0 0 0 1 0 0 1
Output
3
Explanation
Take dish number 5,6,7.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -1of 1 vote
AnswersAn input device can read input of 8 bytes over 2 seconds. It needs control over an input buffer during this operation. A disk writer can write data of 16 bytes over 4 seconds to the disk. It too needs control over the data buffer for the duration of its operation.
- FoogleDrive July 12, 2015 in United States
Design a system that can capture input from input device and write it onto the disk. The interviewer explicitly asked for detailed code for the implementation.
---EDIT---
The input device thread cannot be blocked, if made to wait, data gets overwritten and we have to capture all data available to the input device
P.S.: I don't think we can use synchronized block from java since their locks cannot be interrupted, I have read up on trylock() mechanism but not entirely sure how the exact code would look like.| Report Duplicate | Flag | PURGE
Microsoft SDE1 - 1of 1 vote
AnswersImplement a simple, persistent, thread-safe, cache, which should ideally be able to store up to 1 million product names.
- sunilkanaujia.manit July 06, 2015 in India| Report Duplicate | Flag | PURGE
Palantir Technology SDE1 - 0of 0 votes
AnswersOn a screen, there are multiple rectangles drawn, when a user clicks on any point, find the smallest rectangle enclosing this point.
- ritwik_pandey July 05, 2015 in India
I could not come up with a solution. The end points of rectangles were given and also the the point where the mouse was kept was given.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswerSkynet
- glory for dreams July 02, 2015 in United States
Skynet has grown to become the dominant force on earth and has almost completely wiped out the
human race. Skynet has been
building robots ever since it's inception and has been updating it's models every year while making
them better. Skynet wants to annihilate humanity completely. It plans to remove one last band of
humans lead by John Connor. Skynet thinks it can destroy these humans using only two of it's robots.
But Skynet doesn't want to send two robots with the same model number lest John Connor finds out a
weakness in that model and easily destroy both of them.
Skynet has at its disposal N robots and to save space Skynet has stored information about pairs of
robots belonging to the same model. If it doesn't have any info stored for a particular robot then it is
implied that the robot is the only one in that model.
Given these constraints, in how many ways can Skynet pick two robots to destroy John Connor and
his rag tag group of humans.
Inputs
N Total
number of robots. Each robot is assigned a number from 0 to N1
(2 <= N <= 100000)
P Number
of pairs for which Skynet has information (2 <= P <= 100000)
This is followed by P pairs. Each pair has two numbers P and P each where 0<=P <=N1
and
0<=P <=N1
and P != P
Output
Number of ways in which Skynet can select 2 robots such that both the robots are different models.
Example Input:
4 2
0 1
2 3
Example Output:
4
Explanation:
Here robots 0 and 1 are of one model, say model A. And 2 and 3 are of another model, say B.
Therefore the total number of
possibilities of picking 2 robots such that no two robots are of the same model are (
0, 2), (0, 3), (1, 2)
and (1, 4) = 4| Report Duplicate | Flag | PURGE
National Instruments SDE1 C++ - 0of 0 votes
AnswersCan we find majority element optimally than O(n) ?
- rahulkumar5july June 19, 2015 in India
Following with what if array is sorted ?| Report Duplicate | Flag | PURGE
Adobe SDE1 - 0of 0 votes
AnswerCan we tell in almost constant time that a perticuler array dont have majority element ?
- rahulkumar5july June 19, 2015 in United States| Report Duplicate | Flag | PURGE
Adobe SDE1 - 0of 0 votes
Answersfind sum of longest increasing subsequence ?
- rahulkumar5july June 18, 2015 in India
Not the maximum sum,sum of longest subsequence.
Eg. 1, 8,2, 3
ans-> 6| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersGiven a N-ary Tree. Return true if it follows Sum Property otherwise false.
- chaturvediprerna03 June 17, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswerGiven a mxn grid, each of it’s element be either ‘.’, ‘R’, ‘G’ or ‘B’,
- ritwik_pandey June 17, 2015 in India
where ‘.’ -> empty, ‘R’ -> Red, ‘G’ -> Green, ‘B’ -> Blue
A Blue strip has width 1 and length greater or equal to one.
A Red strip has length 1 and width greater or equal to one.
If a Red strip and a Blue strip overlaps, the overlapped portion will become ‘G’.
Find the minimum number of strips required to cover the whole grid.
1<= m,n <=100
Input
5 5
..B..
..GRR
..B..
R....
R....
Output
4| Report Duplicate | Flag | PURGE
Flipkart SDE1 General Questions and Comments - 2of 2 votes
AnswersGiven a sorted array with only 0's and 1's.Count the number of 0's.
- steelrahul June 16, 2015 in India for Hyderabad
e.g: 0 0 0 0 1 1
Ans: 4.| Report Duplicate | Flag | PURGE
Amazon SDE1 - 2of 2 votes
AnswersGiven n (of size m) Linked lists
- steelrahul June 16, 2015 in India for Hyderabad
Print all set(head of linked list) of link list that intersect with each other.
e.g.
1-->2-->3-->4-->5
6-->7-->8-->4-->5
8->9->10->11->12
13->14->15->12
16->17->18
1 6
8 13
16| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersA non-empty zero-indexed array A consisting of N numbers is given. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.
- Gear June 15, 2015 in United States
For example, consider array A such that
A[0] = -5 A[1] = -3 A[2] = -1
A[3] = 0 A[4] = 3 A[5] = 6
The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.
Write a function
int absDistinct(int A[], int n);
that, given a non-empty zero-indexed array A consisting of N numbers, returns absolute distinct count of array A.
Assume that:
array A is sorted;
N is within the range [1..100,000];
each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].
For example, given array A such that
A[0] = -5 A[1] = -3 A[2] = -1
A[3] = 0 A[4] = 3 A[5] = 6
the function should return 5, as explained above.
?| Report Duplicate | Flag | PURGE
SDE1 - 0of 0 votes
AnswersA magnitude pole of an array A consisting of N integers is an index K such that all elements with smaller indexes have values lower or equal to A[K] and all elements with greater indexes have values greater or equal to A[K], i.e.
- Gear June 13, 2015 in United States
when and
when K < L < N.
For example, 5 is a magnitude pole of array A such that
A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9.
This array doesn't have any more magnitude poles.
Write a function
int magnitudePole(int A[], int n);
that given an array A consisting of N integers returns any of its magnitude poles. The function should return -1 if array A doesn't have any magnitude poles. Assume that . Assume that each element of the array is a non-negative integer not exceeding 1,000,000.
For example, given array A such that A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9
the function should return 5, as explained above.
?| Report Duplicate | Flag | PURGE
SDE1 - 0of 0 votes
AnswersDesign and code the sudoku solver.
- kri1311 May 27, 2015 in India| Report Duplicate | Flag | PURGE
Flipkart SDE1 - 0of 0 votes
AnswersThere is a zoo and there are several groups(number of groups:K) of people for tour. Each group is having different size (g1,g2,g3…gK). There is one bus with capacity C. Journey starts from a point and bus will come back to the same point. A group can only be included in the bus if all the members of the groups can be accumulated in bus. After coming back from the tour, each group in the bus will again wait in the queue at the bus-stand. Bus-driver earns a rupee for each person travelled. You have to find the earning of the bus driver after R rounds.
- kri1311 May 27, 2015 in India
For example :
Number of groups G = 4
Group size for each group : 2 4 3 5
Bus capacity : 7
Number of rounds R : 4
queue : (from front side) 2 4 3 5
First round : 2 4 (we can’t take 3rd group as 3 members can’t be accumulated after 2 and 4.)
queue : 3 5 2 4 (1st and 2nd group are enqueued. i.e. 2 and 4)
Second round : 3
queue : 5 2 4 3
Third Round : 5 2
queue : 4 3 5 2
Fourth Round : 4 3
After 4 rounds, total earning is 6+3+7+7 = 23.| Report Duplicate | Flag | PURGE
Flipkart SDE1 Algorithm - 0of 0 votes
AnswersDesign a Traffic signal . List all entities and classes involved. How will you handle pedestrian crossings etc.
- kri1311 May 27, 2015 in India| Report Duplicate | Flag | PURGE
Flipkart SDE1 Algorithm