SDE-2 Interview Questions
- 3of 3 votes
AnswersGiven a singly connected linked list, find the largest palindrome in the list in O(1) space.
- neer.1304 November 29, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 3of 3 votes
AnswersGiven a linked list consisting of String in each Node . Given just a pointer to the head Node find whether the resultant String formed by combining all the Nodes of the linked list is a palindrome or not in O(1) space and O(n) time.
- neer.1304 November 29, 2015 in United States
eg – Consider this linked List structure
“aba” -> “cd” -> “efe” -> “d” -> “caba”
Hence this structure is palindrome .| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersFace to Face
- siva.sai.2020 November 29, 2015 in United States
Q4) two arrays given to you. First array contains number s. Second array contains key values.
We need to find smallest window in first array which covers all second array elements.
e.g:
Input= {6,7,1,3,2,4,5,2,3,1,2,5}
Keys = {2,5,1}
answer: from 9th index to 11th index is the smallest window.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersFace to face
- siva.sai.2020 November 29, 2015 in India
Q3) stream of numbers coming, get 'n' min elements at any point of time| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersWritten test:
- siva.sai.2020 November 29, 2015 in India
Q2) in single linked list reverse alternative k nodes.
e.g. k=3 , 1->2->3->4->5->6->7->8->9->10
3->2->1->4->5->6->9->8->7->10
void reverseAlternativeKNodes(node *&head, int k);| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersWritten Test question:
- siva.sai.2020 November 29, 2015 in India
Q1) Given binary tree find largestPath size from one leaf to another leaf.
int getLargestPathSize(node *root);| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswerGiven an N-ary tree with thousands of nodes in it. Pair (Join) the Leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have Intersecting path.
- neer.1304 November 28, 2015 in United States
For example,
A
/ | \
B C D
/ / | \
E F G H
Leaf nodes: E, F, G, H & D
Possible Pairs in O/Ps:
a) (E-F), (G-H) or
b) (E-G), (F-H) or
c) (E-H), (F-G) or
d) (E-D), (F-G) or
e) (E-D), (G-H) or
f) (E-D), (F-H) or
g) (D-H), (F-G) or
h) (D-G), (F-H) or
i) (D-F), (G-H)
Note: If we pair(join) say, (E-F) then we can NOT pair any of the (D-G) or (D-H) as they SHARE the COMMON path from A to C.
i.e. E-B-A-C-F —> (E-F) pair
D-A-C-G —> (D-G) pair
D-A-C-H —> (D-H) pair| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a tree, and a pointer to some node in the tree, print the left most element in the same level as that node
- neer.1304 November 28, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven an input of the calendar objects of 10,000 employees, input is a time interval T and an employee[] array, find the first interval where all the employees in the employee[] array are free for a minimum time interval T (i.e schedule the meeting)
- neer.1304 November 28, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 2 votes
AnswersGiven a binary tree, connect all node in the same level in toggle manner.
- neer.1304 November 27, 2015 in United States
Toggle the linking every K level. For first K level, you should link to next right node. Next K you should link to next left and so on.
Node structure is :
struct node
{
int data;
struct node *left, *right, *next;
};
Each level next should point to the next right or left node in the level. For last node in each level, next should be NULL
For ex - if K=2 then for first 2 level of tree connect next pointer from left to right and for next 2 levels connect next pointer from right to left and so on.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 1of 1 vote
AnswersDesign a restaurant reservation system - You need to design everything from scratch - Identify actors in the system, identify what all data should be stored in persistence storage (and why). How would you make your design scalable?
- Abhigyan Mehra November 25, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Software Design - 1of 1 vote
AnswersDesign a data structure which could perform the following operations in O(1):
- Abhigyan Mehra November 25, 2015 in India
- Insert(), Delete(), Search(), getRandom()
getRandom() should pick a "random" element from your data structure, and should not be predictable (for instance always picking the "first" element from your DS)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 0of 0 votes
AnswersGiven a very large array of sorted integers, find the number of times a particular integer has been repeated in the array. Required complexity : O(logN)
- Abhigyan Mehra November 25, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a string regex and another string pat find whether the pattern is acceptable against given regex string.
- neer.1304 November 23, 2015 in United States
Regex string contains following characters and special characters:
1. Normal alphabets – a to z and A to Z
2. ‘$’ – all string should end with all characters preceding $
Example:
Regex :abc$ ,
Pattern: abcd(Not acceptable) , abc(acceptable), ab(Not acceptable), dhfusdhabc(acceptable) etc..
3. ‘^’ – all string should start with all characters exceeding ^
Example: Regex : ^abc
Pattern: abcd(acceptable) , abc(acceptable), ab(Not acceptable), dhfusdhabc(NOT acceptable) etc..
Regex: ^ then only pattern acceptable is null.
4. ‘.’ – any character can be mapped to dot except null
Example 1: Regex : .abc
Pattern: Zabc(acceptable) , abc(NOT acceptable), ab(Not acceptable), habc(acceptable) etc..
Example 2: Regex :a.bc
Pattern: abc(NOT acceptable) , aXbc(acceptable), ab(Not acceptable), habc(NOT acceptable) etc..
5. ‘*’-the character just preceding * can be repeated n time where (n>=0)
Example 1: Regex :abc*de
Pattern: abccccccccccde (acceptable), abcde(acceptable), abcccd(not acceptable)| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswerGiven a list a1,a2,a3….an. Comparison between elements is given like a1>a2, a3>a5, a4>a2…..etc. Find whether there are any situations that we can sort the list in to the ascending order on the basis of comparison. Yes or No , explain the conditions
- neer.1304 November 23, 2015 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersGiven 2D Array of only 0s and 1s, Find the row which gives max decimal value.
- Rajarathinam Antony November 22, 2015 in India
Input: int array[3][3] = {{0,1,0,}{1,1,0},{1,0,1}};
Output : 2(second row)...decimal value is 6| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersFind the largest substring in s1, such that all characters in the substring are present somewhere in s2
- johnsvakel November 20, 2015 in India| Report Duplicate | Flag | PURGE
unknown SDE-2 Algorithm - -1of 1 vote
AnswersDesign and implement a scalable multi-player N*N TicTacToe game.
- neer.1304 November 19, 2015 in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 3of 3 votes
AnswersI had two interviews with Google
- sameer November 17, 2015 in India
first) one with US person...he asked decent question with lot of hints...experience : positive
and
then second) interview with person from India...I prepared for one month but he asked me very tough one graph/tree question...never gave single hint and based on that one question he judged my seven years of experience in Software Development (I never experienced what they say...Google looks for approach and not final answer)
Q.1 : Arrange array in wave form A1 > a2 < a3 > a4 ...
O(n.log-n) (Note: its not A1 >= A2)
Q.2 : Given Graph with Tree characteristics, find one node as root so that height of tree will be minimum| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 3of 3 votes
AnswersImagine a man reading a book.
- zr.roman November 16, 2015 in Russia
He can perform only 2 possible actions of reading:
1) read a page in a minute (careful reading),
2) read two pages in a minute (look through).
Nothing else is permitted.
Calculate the number of all possible combinations of book reading ways with given number of pages.
Example: given 3 pages.
Answer is 3 combinations, as follows:
1st: Careful reading (1) - careful reading (1) - careful reading (1),
2nd: Careful reading (1) - look through (2),
3rd: Look through (2) - careful reading (1).| Report Duplicate | Flag | PURGE
SDE-2 Algorithm - 2of 2 votes
AnswerHow do we achieve (google news) personalization.
- sati November 05, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -2of 2 votes
AnswersCadbury bar size of 5*3 can be distributed to 4 children.
- Deep November 04, 2015 in India
5*4 can be distributed to 5 children.
6*3 can be distributed to 2 children.
6*4 can be distributed to 3 children. so the whole carton can be distributed among 14 children
Program output shall be 14.
Input/Output Specification: M,N,P,Q are the integer type (M,N values are the ranges for the length of cadburybar P,Q values are the ranges for breadth of Cadbury bar)
Output: Number of children who will receive cadbury bar from the carton.| Report Duplicate | Flag | PURGE
Cisco Systems SDE-2 Algorithm - 0of 0 votes
Answers2. VeryLongInt
- siva.sai.2020 October 18, 2015 in India
Design a class which can add and subtract integers up to 1000 digits. You can make the following assumptions
No need to handle overflow or underflow (extra credit if you do)
Copy constructor is available
“+” and “-” are binary operators| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
Answers1. Balanced Parentheses
- siva.sai.2020 October 18, 2015 in India
Given a string s of parentheses (ex: “(()”), return the minimum number of parentheses that need to be inserted to make it into a well formed string
A well formed (balanced) string of parentheses is defined by the following rules: ● The empty string is well formed. ● If s is a well formed string, (s) is a well formed string. ● If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string.
Implement
int MinNumInsersertionsForBalancing(const string& s)| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 1of 1 vote
AnswersSort an array of 0s, 1s and 2s
- NoMind October 18, 2015 in India
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
The problem is similar to http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
But they have added 1 trick into the question, You cannot use high = n;
It means don't calculate the length of array.
Can anyone help me in writing the code for this problem ?| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a list of sorted arrays, like List<int[]>. Prepare and return a single sorted list.
- teli.vaibhav October 11, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
- teli.vaibhav October 02, 2015 in United States
ex-
Tree1:
5
1 6
5 4 3 6
Tree2:
1
3 4
6 5
have identical integers.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven a string which may contain parenthesis. We must verify the validity of the string.
- teli.vaibhav October 02, 2015 in United States
ex-
1) "<ad675+-fkmfd>" is a valid string
2) "<[((kskfhdbh7)" is invalid
3) "[<<((shfs8))>>]" is valid
Extension to the question -
Suppose you had a hash table that told you how a parenthesis starts and how it ends as a key value pair, how would you then validate the string.
ex - <key,value> = < '(' , ')' > indicates '(' is a start parenthesis and ')' should be the end of that paranthesis.
<'A','&'> indicates that 'A' is a start parenthesis and '&' is the end parenthesis.
Note: Validity means a parenthesis that starts, must end.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven a grid of m*n size. Each block in grid has some amount of gold.
- neer.1304 September 22, 2015 in United States
We start from first column of the grid(any row) and we can move in 3 direction - right, right-up and right-down.
What is the maximum amount of gold we can collect from the grid.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm