SDE-2 Interview Questions
- 0of 0 votes
AnswersExpression tree evaluation and also write the class for the node and tree itself. (just basic structure like node and data)
- Desi May 13, 2019 in United States for Robotics| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersLRU cache. Basically started off with how would I store values and get them from memory for faster access. So I mentioned HashMap. and then interviewer added more info about deleting least recently used element.
- Desi May 13, 2019 in United States for Robotics| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven movement of Robot -
- neer.1304 April 22, 2019 in United States
G-GO one unit
L-Turn left
R-Turn right
Given an input of string have to find whether there exists a circle which the robot would traverse. Input of string is the set of G,L,R have to return yes or no.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 1of 1 vote
AnswersGiven a list of strings. Check whether any two strings, if concatenated will form palindrome or not.
- neer.1304 April 22, 2019 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswerThere is a hierarchical structure in an organization. A party is to be organized. No two immediate subordinates can come to the party. A profit is associated with every person. You have to maximize the total profit of all the persons who come to the party.
- neer.1304 April 22, 2019 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersDesign a vending machine with following functionalities
- neer.1304 April 21, 2019 in United States
Three types of Users : User, Operator, Admin
User can select and buy multiple items at a time. Money can be inputted multiple times (you will get the item if there is a time gap > 30 secs). He can also do window shopping (see only the prices of items and buy nothing)
Operator can load the items and mark the items as expired if needed, gets notified if a product goes out of stock.
Admin can own multiple vending machines, he should have a analytics report of the items purchased in a month. He can also change the prices directly and it should reflect in all the vending machines which he owns.
Exception handling in all the edge cases
Both HLD and LLD were expected.| Report Duplicate | Flag | PURGE
Amazon SDE-2 System Design - 0of 0 votes
AnswerYou have been given a set of inter-dependent tasks along with the time taken to execute them. We have more number of parallel processors available than the number of tasks given. There could be multiple starting tasks. There could also be cyclic dependencies. Calculate the minimum time required to complete all the task.
- neer.1304 April 21, 2019 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswerHow will you implement organizational chart? Implement two methods - isPeer - Should return true if two employees have same managers. isManager - should return true if manager is management chain of given employee.
- neer.1304 April 21, 2019 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersRelation between 2 animals is given. A is child of B C is child of B A is child of D
- neer.1304 April 21, 2019 in United States
An animal can be child of 0 to 2 parents. With this given data, find out if two animals are related to each other. Follow up question was - Maternal side animals, should not be related to patrernal side family.| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
AnswersYou have a 3x3 grid. In each cell you can have two colors, white or black. At the beginning, the matrix has some cells painted white and others black.
- neer.1304 April 21, 2019 in United States
If you change a color cell, that is, grid [i] [j] the cells grid [i-1] [j], grid [i + 1] [j], grid [i] [j-1] and grid [ i] [j + 1] also change (if these positions do not leave the 3x3 grid), that is, if they were white, they change to black.
Return, the minimum number of cells you have to flip for the 3x3 grid to be totally white. If you cannot do this, return -1!
Sample input/output - ibb.co/3Y0WVNR| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 1of 1 vote
AnswersGiven array of integer, count number of distinct sub array such that it has at most k odd elements and two sub array differ if only when they have at least one member differ.
Example:
{3, 2, 3, 4}, k = 1;
output; 7
[ [3], [2], [4], [3,2], [2,3], [2,3,4],[3,4] ]; Note we did not count [3,2,3] since it has more than k odd elements.
Example 2:
{6, 3, 5, 8}, k = 1;
[ [6], [3], [5], [8] , [6,3], [5,8] ] = 6
We did not count [3,5] as it has > k odd elements
Example 2:
{2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12}
There are these many arrays ;
[2], [2] , [5], [6], [9] , [2], [11], [9], [2], [11], [12]
[2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 9] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [5, 6, 9] , [6, 9, 2] , [9, 2, 11] , [2, 11, 9] , [11, 9, 2] , [2, 11, 12] , [2, 2, 5, 6] , [2, 5, 6, 9] , [5, 6, 9, 2] , [6, 9, 2, 11] , [9, 2, 11, 9] , [2, 11, 9, 2] , [11, 9, 2, 11] , [9, 2, 11, 12] , [2, 2, 5, 6, 9] , [2, 5, 6, 9, 2] , [5, 6, 9, 2, 11] , [6, 9, 2, 11, 9] , [9, 2, 11, 9, 2] , [2, 11, 9, 2, 11] , [11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2] , [2, 5, 6, 9, 2, 11] , [5, 6, 9, 2, 11, 9] , [6, 9, 2, 11, 9, 2] , [9, 2, 11, 9, 2, 11] , [2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9] , [5, 6, 9, 2, 11, 9, 2] , [6, 9, 2, 11, 9, 2, 11] , [9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9] , [2, 5, 6, 9, 2, 11, 9, 2] , [5, 6, 9, 2, 11, 9, 2, 11] , [6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2] , [2, 5, 6, 9, 2, 11, 9, 2, 11] , [5, 6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9, 2, 11, 12]
But only 18 get qualified as there are duplicates like [9, 2, 11] etc.
Qualified arrays are
[2] , [5], [6], [9] , [11], [12] , [2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [6, 9, 2] , [2, 11, 12] , [2, 2, 5, 6]
MY finding so far;
we can use sliding window technique, such that we start counting all sub array of len = 1 to n such that each sub array are different and have at most k odd elements
Here is the code, that i've written for this approach O(n^2)static int subArraysBrute(int arr[], int k) { int count = 0; Set<Integer> set = new HashSet<>(); //Count single length for (int i = 0; i < arr.length; i++) { count += set.contains(arr[i]) ? 0 : 1; set.add(arr[i]); } int len = 2; int odd; Set<List<Integer>> setArray = new HashSet<>(); while (len < arr.length) { setArray.clear(); for (int i = 0; i < arr.length - len + 1; i++) { int j = i + len - 1; odd = 0; List<Integer> ar = new ArrayList<>(); for (int x = i; x <= j; x++) { if (arr[x] % 2 != 0) odd++; ar.add(arr[x]); } if (!setArray.contains(ar)) { if (odd <= k) { count++; System.out.print(ar + " , "); } } setArray.add(ar); } len++; } return count; }
Other findings;
- nitinguptaiit April 20, 2019 in United States
1. We can't sort the array, as they will ruin the subarray property
2. We can't use simple sliding technique as they will mis so many sub arrays ( moving from left to right window) - I've tried this, this fails like any thing;
Probably, in second idea (sliding window), can be improve further such that once we counted sub arrays, we can run one more time and count those sub array which are left out.| Report Duplicate | Flag | PURGE
Uber SDE-2 Algorithm - 0of 0 votes
AnswersCount number of possible rhythm in a poem.
- nitinguptaiit April 18, 2019 in India
Explanation:
Twinkle, twinkle, little star, [ A ]
How I wonder what you are! [A]
Up above the world so high, [B]
Like a diamond in the sky. [B]
In the above poem, we see the first two line ( ending with "star" and "are" ) is in the rhythm that's why they are given as character "A" and similarly last two lines (ending with "high" and "sky" ] s in the rhythm that's why they are given as character "B".
Questions: Given "n" number of lines in a poem, Count number of possible rhythm in a poem.
P.S. output should be in lexicographical order only
Example:
n=1
only one possible "A"
Answer: A, count =1
n=2 [ possible chars are A,B]
AA
AB
BA <- This is not possible as it collide with AB. How? Look at the pattern
AB says first line has different rhythm and second line has different rhythm then first line.
Similarly BA is also shows the same ; first line has different rhythm and second line has different rhythm then first line.
Hence discard
n=2
AA
AB , count=2
n=3 [ possible chars are A,B, C]
AAA
AAB
ABA
ABB
ABC, count=5
Look we can't have AAC as it collide with AAB (first two are same and last is different in both)
Similarly other BCA/ BAC etc we'll discard them because of collide and lexicographical ordering.
n=4, there will be 15 [ we need to print all of them too ]
My Finding;
1. I found out that, this is just a bell number ( see the pattern 1,2,5,15.... )
2. I found, this is Dynamic programming question, we can generate the next n+1 from n; How
n=2 has
AA
AB
n=3
Take AA; there are three possiblilties to append a character is A,B,C
But since the last character is A; so lexicographically A and B can be appended at the most, since appending C could conflict with B.
AA(A)
AA(B)
Take AB; there are three possibilities to append a character is A,B,C
But since the last character is B; which is lexicographically smaller than A, so lexicographically A, B,C can be appended easily,
AB(A)
AB(B)
AB(C) <- this is possible since its not colliding with any thing
So ans; 5
AA(A)
AA(B)
AB(A)
AB(B)
AB(C)
Now lets try n=4 [ now its become complicated ;A,B,C,D]
Take AAA; possibilty A,B, not possible C/D conflict with B
AAA(A)
AAA(B)
Take AAB, Possibility is A, B C but what about D; is it possible ? Yes/No
AAB(A)
AAB(B)
AAB(C)
AAB(D) <- it collide with last C so discard ;
Hence with AAB
AAB(A)
AAB(B)
AAB(C)
Take ;
ABA(A)
ABA(B)
ABA(C)
ABA(D) Not possible ; collide with C
If you observe there is a pattern with last character to first character from right to left;
Solution: Brute force is obvious solution; and generating number is also fine since you can use Bell number [ i was not able to come up with this solution though, found later]
Any one can help me over here?| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 0 votes
AnswersDesign a data scrubber.
- kumar February 01, 2019 in India
Say a customer couldn't use Alexa with Philips light bulb. Now customer calls to Alexa/Amazon customer support they figure out the issue is not with Alexa it's with the Philips LED bulb.
Now amazon will redirect their customer call / chat to third party customer support (Philips in this case).
Now somehow we need prevent the possibility of third party customer support trying to exploit our customers. For ex: asking their bank accounts, credit card, Social Security number etc..
How will you do that for AMAZON level ?| Report Duplicate | Flag | PURGE
Amazon SDE-2 System Design - 1of 1 vote
AnswersPrroblem: write an algorithm to calculate the minimum cost to add new roads between the cities such that all the cities are accessible from each other
int numTotalAvailableCities = 6;
int numTotalAvailableRoads = 3;
int[,] roadsAvailable = { { 1, 4 }, { 4, 5 }, { 2, 3 } };
int[,] costNewRoadsToConstruct = { { 1, 2,5 }, { 1,3,10 }, {1,6,2} ,{ 5, 6, 5 } };
int numNewRoadsConstruct = 4;
- sunil.sebastian January 05, 2019 in United Statespublic class MinimumCostToConstructNewRoad { public static int getMinimumCostToConstruct(int numTotalAvailableCities, int numTotalAvailableRoads, int[,] roadsAvailable, int numNewRoadsConstruct, int[,] costNewRoadsConstruct) { int totalCost = 0; bool[] Visited = new bool[numTotalAvailableCities]; int[] Keys = new int[numTotalAvailableCities]; int[] Parent = new int[numTotalAvailableCities]; int[,] AdjMatrix = GetAdjecencyMatrix(roadsAvailable, costNewRoadsConstruct, numTotalAvailableCities); for (int i=0;i< numTotalAvailableCities;i++) { Keys[i] = Int32.MaxValue; } Keys[0] = 0; Parent[0] = -1; for(int i=0;i< numTotalAvailableCities-1;i++) { var u = FindMin(Visited, Keys); Visited[u] = true; for(int v=0;v< numTotalAvailableCities;v++) { if(Visited[v]==false && AdjMatrix[u, v]!=Int32.MaxValue && AdjMatrix[u,v]<Keys[v]) { Parent[v] = u; Keys[v] = AdjMatrix[u, v]; } } } for(int i=1;i< numTotalAvailableCities;i++) { totalCost = totalCost + AdjMatrix[Parent[i], i]; } return totalCost; } private static int FindMin(bool[] Visited, int[] Keys) { int min = Int32.MaxValue; int index = -1; for (int i = 0; i < Keys.Length; i++) { if (Visited[i] == false && Keys[i] < min) { min = Keys[i]; index = i; } } return index; } private static int[,] GetAdjecencyMatrix(int[,] roadsAvailable, int[,] costNewRoadsConstruct,int numTotalAvailableCities) { int[,] AdjMatrix = new int[numTotalAvailableCities, numTotalAvailableCities]; for (int i = 0; i < numTotalAvailableCities; i++) { for (int j = 0; j < numTotalAvailableCities; j++) { AdjMatrix[i, j] = Int32.MaxValue; } } int count = 0; for (int i = 0; i < roadsAvailable.GetLength(0); i++) { int start = roadsAvailable[i, count]-1; int end = roadsAvailable[i,count+1]-1; AdjMatrix[start, end] = 0; } for (int i = 0; i < costNewRoadsConstruct.GetLength(0); i++) { int start = costNewRoadsConstruct[i, count]-1; int end = costNewRoadsConstruct[i, count+1]-1; int cost= costNewRoadsConstruct[i, count + 2]; AdjMatrix[start, end] = cost; } return AdjMatrix; } }
| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - -1of 1 vote
AnswersImagine you have a computer keyboard that has all the letters mismatched
- klausv December 23, 2018 in United States
example:
typing q gives you a
typing w gives you b
all 26 letters in the alphabet are there, but typing one letter will give you another one
you are asked to write an algorithm to find whatever word you tried to type and count how many cycles you did to find the word
a restriction was set you need to type the whole word every time, not go character by character
note: a graph was suggested to represent the letter mappings| Report Duplicate | Flag | PURGE
Amazon SDE-2 Trees and Graphs - 1of 1 vote
AnswersYou have an array of numbers. You have to give the range in which each number is the maximum element. For Example, If array is [1, 5, 4, 3, 6] The output would be
- SRC December 12, 2018 in United States
1 [1, 1]
5 [1, 4]
4 [3, 4]
3 [4, 4]
6 [1, 5]| Report Duplicate | Flag | PURGE
Nutanix SDE-2 - 3of 3 votes
AnswersHow to find out distinct ngrams from a email_alias.
- ashwini.padhy89 December 05, 2018 in India
For instance xyz@gmail.com here the email_alias is xyz.for xyz if we want to find bigram then function should have input the email_id,and the number of grams lets say 2.
Than it has to return the distinct count of ngrams present in the email_alias.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Coding - 0of 0 votes
AnswersLet's assume we have a queue named 'Demo' which receives messages from various users.
- Sameer December 02, 2018 in United States
Create a Listener which will listen to the queue 'Demo' continuously and as soon as the message is send to the queue the Listener will print out the message.
The queue is running on port : 8161
Username : admin
Password : admin| Report Duplicate | Flag | PURGE
Microsoft SDE-2 - 1of 1 vote
AnswersGiven multiple tuples in the form of (A,B) where A is the parent and B is the child in a binary tree, find if the input is valid or not. 4 error conditions were provided:
- Ankita October 14, 2018 in United States
1. If a parent has more than 2 children,
2. If duplicate tuples entered,
3. If the tree has a cycle,
4. If more than one root possible.
For violation of multiple validity conditions, print the condition coming first in the above order.
If the input is valid, print the tree in a serial representation. For eg: If input is (A,B), (B,C), (A,D), (C,E) , output: (A(B(C(E)))(D))| Report Duplicate | Flag | PURGE
Starup SDE-2 Algorithm Problem Solving - 2of 2 votes
AnswersHow would you tell whether a graph has a node with n degree??
- shivamdurani220 October 11, 2018 in United States
tell your approach| Report Duplicate | Flag | PURGE
Google SDE-2 - 0of 0 votes
AnswersGiven max. travel distance and forward and backward route list, return pair of ids of forward and backward routes that optimally utilized the max travel distance.:
- rahul October 10, 2018 in United States
eg: max travel distance is : 11000
forward route list : [1,3000],[2,5000],[3,4000],[4,10000]
backward route list : [1,2000],[2,3000],[3,4000]
Result : [2,3] ...2 is from forward and 3 is from backward...total distance is 9000...no other combination is there which is >9000 and <=11,000.......0(n^2) solution is straight forward, thinking that sorting both might help.| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 1of 1 vote
AnswersThere is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.
- shivamdurani220 October 09, 2018 in United States
You can keep inputting the password, the password will automatically be matched against the last n digits entered.
For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.
Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.| Report Duplicate | Flag | PURGE
Google SDE-2 - 2of 4 votes
AnswersGiven a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.?
- shivamdurani220 September 15, 2018 in United States
please discuss approach first & then code it..| Report Duplicate | Flag | PURGE
Google SDE-2 - 0of 0 votes
AnswersDesign an email client where you can only send emails to people who are present in your contact list. Build for only the following functionaliy
- vardaansh1 August 26, 2018 in India
1) Send/Receive Emails
2) Add/Remove Contacts
3) See Inbox
4) See Sent Mail| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswersDesign a distributed LRU Cache.
- vardaansh1 August 26, 2018 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 0of 0 votes
AnswersWhat would be the sample class design of notification system?
- abc.xyz August 14, 2018 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersWhat would be the sample class design of tic tac toe game?
- abc.xyz August 14, 2018 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersWhat would be the sample class design of Outlook like meeting scheduler?
- abc.xyz August 14, 2018 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 1of 1 vote
AnswersThere are 3 threads. 1 is producer thread. 2 consumer threads. There is 1 buffer. Producer writes to the buffer. Consumers consume from buffer. How to synchronise between them so that consumers consume from buffer one after another, that is, the number of tokens that consumer thread1 consumes is same as number of tokens consumer thread2 consumes. Answer in c,linux
- mohapatrasandeep60 August 08, 2018 in India| Report Duplicate | Flag | PURGE
Hewlett Packard SDE-2 - 0of 2 votes
AnswersWhat is the best way to generate first N primes? (not primes up to N but first N primes)
- koustav.adorable July 22, 2018 in United States for Amazon Prime| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm