SDE-3 Interview Questions
- 0of 0 votes
AnswersGiven a 3x3 tic-tac-toe board with players 1 and 2. Find all the possible ways player 1 can lose given a particular configuration of the board.
- seafan0034 February 26, 2018 in United States
For example (0 denotes empty spot):
input:
0, 1, 0
2, 2, 1
1, 1, 2
Output: 1 (because the only move for player 2 to win would be to play board[0,0])
The input board can have any configuration (player 1 and 2 can be in all possible spots with any number).| Report Duplicate | Flag | PURGE
Microsoft SDE-3 Math & Computation - 1of 1 vote
Answersgiven a set of digit from 1 to 9 {1,2,3,4,5,6,7,8,9}, write code to find k elements whose sum is equal to n.
- CoolGuy December 10, 2017 in India
e.g.
k=3, n= 9
{1, 2, 6}, {1, 3, 5}, {2, 3, 4}
vector<vector<int>> findKElementsSum(int k, int n)
{
}| Report Duplicate | Flag | PURGE
Amazon SDE-3 - 1of 1 vote
AnswersHow would you like to efficently find the total number of possible ways with which given string may be converted to whole dictionary words.
- CoolGuy December 08, 2017 in India
Example :
String = “Dogeatscare”
possible combinations – “Dog, eat, scare ” and “Dog, eats, care”
output is 2.| Report Duplicate | Flag | PURGE
Amazon SDE-3 - 0of 0 votes
AnswersAn art museum has the shape of a square and it contains N*N rooms. Some of the rooms are open and they contain art, other rooms are locked. There are guards in some of the open rooms. The museum's administration is afraid of a break in and they would like to evaluate how well the guards are positioned in the open rooms inside the museum. Precisely, they wish to know for each open room what is the distance to the colest guard. This distance is the min number of rooms a guard needs to pass through to reach that room. The guards can only move through the open rooms North, South, East and West and they can't leave the museum.
- ajay.raj December 05, 2017 in United States
'.' is for open room 'G' is for open room where a guard is '#' is for a locked room Noboday can enter or pass through thesse rooms.| Report Duplicate | Flag | PURGE
Google SDE-3 - 0of 0 votes
Answersclass QueryVector
- CoolGuy December 01, 2017 in India
{
QueryVector(vector values)
{
// Implement
}
vector GetIndices(list filters)
{
// Implement
}
}
Say for example vector is like
{“an”, “apple”, “day”, “keeps”, “doctor”, “away”, “apple”, “iphones”, “cool”, “doctor”, “recommends”}.
GetIndices(“apple”) should return (1, 6)
GetIndices(“doctor”,”cool”) should return (4,8,9)
GetIndices(“random”) should return empty vector ()
GetIndices(“random”,”keeps”,”day”,”doctor”) should return empty vector (2,3,4,9)
Important:
1. There can be millions of values in the input vector of string
2. GetIndices can be called repeatedly and it should be optimized
3. How storage optimization is considered and bitmaps etc are used.| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - -1of 1 vote
AnswersHow to design a Debugger both HLD and LLD?
- koustav.adorable September 19, 2017 in India| Report Duplicate | Flag | PURGE
Amazon SDE-3 System Design - 0of 0 votes
AnswersGiven MxN binary matrix, find the largest sub-square matrix with all 1’s.
- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersDesign a geographically partitioned multi-player card game, that supports multiple players, multiple games at a time.
- neer.1304 August 31, 2017 in United States
Each game will have one contractor like ones we have in a bar, He can play a game or just watch it. Integrate payment systems.
First HLD was required, use cases, flow diagram. then a low level design was required all necessary classes where will you use polymorphism, where inheritance, multithreading, synchronised approach if needed, socket connections| Report Duplicate | Flag | PURGE
Amazon SDE-3 design - 2of 2 votes
AnswersDesign a Netflix type system. Start from HLD to LLD.
- neer.1304 August 31, 2017 in United States
Consider requirements like search, video serving, authentication, security, serving multi quality video.| Report Duplicate | Flag | PURGE
Amazon SDE-3 design - 0of 0 votes
AnswersGiven an array of integers. We need to answer two types of queries point update and range sum in minimum time.
- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersPut the given random pointers in linkedlist to point to next greater node such that if you transverse the list using random pointers, list become sorted. duplicates are allowed.
- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 1of 1 vote
AnswersFind third highest value in a binary tree
- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersYour input is a double array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.
- talal.nabulsi5 August 27, 2017 in United States
Ex:
input is {3,4,5,1} --> output: 72
input is {1,1,1,5} --> output: 15
Follow up, if there are numbers <0| Report Duplicate | Flag | PURGE
Google SDE-3 Algorithm - 0of 0 votes
AnswersToday Google phone interview I was asked to code multithreading solution to return union of two sorted arrays in java for given number of processors. Does anybody can provide a short neat code sample om that?
- marcin.jolkowsky August 26, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE-3 - 0of 0 votes
Answers// Create a numeric binary tree structure/classes that have left and right children and an integer numeric value.
- deepmh August 14, 2017 in United States for Amazon Fresh
// Write a function 'isBalanced' for a node that returns true if the sum of all the children on the left is equal
// to the sum of all the children on the right.
//Example:
// [12] [12].isBalanced() -> True. [3, 3]
// / \
// [3] [1] [1].isBalanced() -> True. [2, 2]
// / \
// [2] [0]
// / \
// [2] [0]
// - Part I: setup and isBalanced() function
// - Part II: implement “allBalancedNodes()” <— given a node, finds all balanced children
// allBalancedNodes(12) -> returns a list of balanced nodes: { [1], ... }| Report Duplicate | Flag | PURGE
Amazon SDE-3 Data Structures - 0of 0 votes
AnswersGiven a list of employees and their bosses as a CSV file , write a function that will print out a hierarchy tree of the employees.
- Trutgeek August 01, 2017 in United States for Phone Interview| Report Duplicate | Flag | PURGE
Amazon SDE-3 Data Structures - 0of 0 votes
AnswersFirst asked how you can write a tree in a file?
- Ghosh June 17, 2017 in India
Next question was lets say value of one node is changed, how can you update that in that file without writing the whole tree in file again?d| Report Duplicate | Flag | PURGE
SDE-3 Algorithm Data Structures - 0of 0 votes
AnswersFind the first non repeating character in a string. For example if the input string "abcdeabc", non repeating character is "e"
- kag May 24, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - -1of 1 vote
AnswersFind if a mathematical string is balanced in terms of parenthesis. For example "(1+2)" is balanced and "(1+2" is not balanced.
- kag May 24, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswerDesign and implement an algorithm to assign an unlimited M number of messages evenly among N number of servers (N will not change).
- aifra2000 May 20, 2017 in United States
Input to the algorithm
A message contains a message identifier and a text string. The algorithm will be fed one message at a time.
There are N numbers of servers (N will not change), each can be identified by a unique id.
Output of the algorithm
When the algorithm is called to process a message, it should output the id of the server that the message is assigned to.| Report Duplicate | Flag | PURGE
Facebook SDE-3 - 2of 2 votes
AnswersApple On-site at Cupertino
- aonecoding May 10, 2017 in United States
Team Data Warehousing
Questions on Hadoop, Hive and Spark
I. Given a table with 1B of user ID and product IDs that the users bought, and another table with product ID mapped with product name. We are trying to find the paired products that are often purchased together by the same user, such as wine and bottle opener, chips and beer … How to find the top 100 of these co-existed pairs of products. If going with hadoop, where is the bottleneck and how to optimize?
II. Someone put distribute Random()*ID in a Hive script to prevent data skew. What would be the problem here?| Report Duplicate | Flag | PURGE
Apple SDE-3 design - 1of 1 vote
AnswersApple On-site at Cupertino
- aonecoding May 10, 2017 in United States
Team Data Warehousing
III. Given three letters ABC, where AB->C, AC->B, BC->A (sequence doesn’t matter). Get the length of the path to convert from a given string to a single character.
For example, “ABACB” goes to “ACCB” (based on AB ->C, convert s[1] and s[2] to C)
“ACCB” goes to “BCB” (based on AC->B)
“BCB” goes to “AB”
“AB” goes to “C”
So it takes 4 steps to change the given string into a single character.
If a given string cannot be resized to 1 character, such as “AAA” or "ABACABB", return -1.| Report Duplicate | Flag | PURGE
Apple SDE-3 Algorithm - 1of 1 vote
AnswersApple On-site at Cupertino
- aonecoding May 10, 2017 in United States
Team Data Warehousing
There were 6.5 rounds in total, that 0.5 on package negotiation with the HR and the remaining rounds with 2 managers and 4 engineers.
Only three pure coding questions were asked.
I. Use a stack to sort given data.
II. Given an array with positive integers only, find the MIN integer that is missing from the array.| Report Duplicate | Flag | PURGE
Apple SDE-3 Algorithm - 0of 0 votes
AnswersYou have given a tree, where each node can have multiple children. You have to find if the tree has a cycle or not.
ExA / \ / \ B C / | \ | \ D E F E H | B
This tree has a cycle from B -> E -> B.
- sonesh April 28, 2017 in United States
Please note that you only know the nodes that you have traveled in the tree, so at the beginning, you will only know that there is a root node and nothing else about any other node.
The followup question was to print the cycle in the tree if found.| Report Duplicate | Flag | PURGE
Electronic Arts SDE-3 Algorithm - 0of 0 votes
AnswersDesign a system having multiple jobs, interacting with each other such that :
- neer.1304 March 10, 2017 in United States
1) A job can run for very long periods (1-2 days)
2) A node can fail/crash on which certain job is running
system should be scalable
3) Amount of data getting transferred is huge
4) Data in the system is very sensitive and needs security
job/s can fail| Report Duplicate | Flag | PURGE
Amazon SDE-3 Software Design - 0of 0 votes
AnswersTop View of a Binary Tree in constant space
- neer.1304 March 10, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersGiven a pattern containing only Is and Ds. I for increasing and D for decreasing. Devise an algorithm to print the MINIMUM number following that pattern. Digits from 1-9 and digits can’t repeat.
- neer.1304 March 10, 2017 in United States
Example:
1. Input: D Output: 21
2. Input: I Output: 12
3. Input: DD Output: 321
4. Input: II Output: 123
5. Input: DIDI Output: 21435
6. Input: IIDDD Output: 126543
7. Input: DDIDDIID Output: 321654798| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersImplement ConcurrentHashMap class in Java
- neer.1304 March 10, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersImplement LinkedHashMap class in Java
- neer.1304 March 10, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm - 0of 0 votes
AnswersYou have been given a grid with some doors, walls and some empty spaces.
- neer.1304 March 10, 2017 in United States
1st part : You have to tell the least no of moves to go from random position in the grid to the nearest door. You can move in four directions only, i.e, left, right, above, below.
2nd part : Least distance of every empty cell to the nearest door. Lots of discussion was done on both the parts of the problem.| Report Duplicate | Flag | PURGE
Amazon SDE-3 Algorithm