SDE1 Interview Questions
- 6of 6 votes
AnswersIn a certain language which has same alphabets as in english language (ie. a-z), but the order of the alphabets is different (for eg 's' is the first character, 'g' is second, and likewise). Given a dictionary of this new language (which has words arranged according to new alphabetical order), FInd out the order of alphabets in this language.
- sgarg June 09, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Google SDE1 Software Engineer / Developer SDE-2 Algorithm - 2of 2 votes
AnswersGiven a 2D rectangular matrix of boolean values, write a function which returns whether or not the matrix is the same when rotated 180 degrees.
- nr June 06, 2013 in United States for maps| Report Duplicate | Flag | PURGE
Google SDE1 - 0of 4 votes
AnswersGiven a matrix consisting of nos you can print the max length of sequence possible where in a sequence each consecutive nos have a diff of +1 or -1.
- bharat June 06, 2013 in United States
Ex :
3 5 7 3
4 5 8 1
6 4 5 2
here sequence is
3
4 5
4 5| Report Duplicate | Flag | PURGE
Amazon SDE1 - 2of 2 votes
AnswersGiven a 'friendship' graph, how would you generate friend suggestions for people, and how would you distribute the data across machines?
- nr June 04, 2013 in United States for google map| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersHow to find in a binary tree, whether all leaves are at same level or not, and return a boolean value after identifying this.
- seth June 04, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 1of 3 votes
AnswersGiven a binary tree, a complete path is defined as a path from root to a leaf. The sum of all nodes on that path is defined as the sum of that path. Given a number K, you have to remove (prune the tree) nodes from the tree which lie on a path having sum less than K.
- seth June 04, 2013 in India
Note: A node can be part of multiple paths. So we have to delete it only in case when all paths from it have sum less than K.| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersWrite code to Print the power set of given string
- sachin323 June 03, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersBar raiser round
- sachin323 June 03, 2013 in United States
Write code to return Kth smallest node from BST| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersFind a pair of numbers from Array that will sum up to K
- sachin323 June 03, 2013 in United States
me : I know this , told him both approaches using sorting as well as HashTable| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWrite a Program for Dictionary which has functionality of lookup and insert . This program should be able to add words on the fly
- sachin323 June 03, 2013 in United States
I wrote simple code using HashTable
follow up
1) Now we are getting too many words what happens
me: Hashtable will dynamically resize resulting into performance hit . Also they might get hashed to same location as well as we might run out of main memory
2) Okay you are out of main memory , How will you scale this program
me: I will create buckets of HashTable lets say 26 buckets for one for each alphabet and would put them on different machines
3) Lets say you are out of memory on those machines too
me: Okay I need to put them on secondary storage . Here we can have fileSystem or Database . I chose database . I will create simple DB schema of BucketNumber and word .
I will use buckets on main memory as cache , if we are not able to find a word in the bucket then query databse with bucket number and words then remove the least number times looked up word (every time we lookup a word we increament the count i.e value in key,value pair on hashtable) from that bucket and add this word .
I mentioned that bottleneck in this case will be every time a word is not present we need to query DB which usually has high latency which will result into performance hit
4) Lets say we are okay with latency but what if we are getting inserting words between that are only between only in two buckets ex. words starting from a and b only| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersA stirng is represented using a linked list how will you find if it the string is palindrom.
- rawat011 May 31, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test SDE1 Algorithm - 3of 3 votes
AnswersThere are N floors and N persons each one is tagged with some random unique number between 1 to N(represents floor number).
- bharat May 31, 2013 in India
We have a lift which can accommodate one person at a time. Every person is in some random floor.
Initially lift is at floor 1 and all floors have single person. Problem here is.. we have to move the persons to their corresponding floor with minimum travelled distance of lift.
Restriction : Lift can have at most one person at a time.
One more thing we have to think of is .. At a time, we can keep more than one person in a floor.. means, we don't necessarily need to take the person out from the floor if we keep another person on the same floor.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersHow the java calculate the size for Hashset and what would b the output. Jsutify your answer with Java point of view..
- techieDeep May 29, 2013 in United States
import java.util.HashSet;
public class HashTest {
private String str;
public HashTest(String str) {
this.str = str;
}
@Override
public String toString() {
return str;
}
@Override
public int hashCode() {
return this.str.hashCode();
}
public static void main(String args[]) {
HashTest h1 = new HashTest("1");
HashTest h2 = new HashTest("1");
String s1 = new String("2");
String s2 = new String("2");
HashSet<Object> hs = new HashSet<Object>();
hs.add(h1);
hs.add(h2);
hs.add(s1);
hs.add(s2);
System.out.print(hs.size());
}
}| Report Duplicate | Flag | PURGE
Adobe SDE1 - 1of 1 vote
AnswersDesign a counter across all Google's servers.
- nr May 29, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 0of 0 votes
AnswersFor a given BST, connect each of its right child to its inorder successor.
- Razz May 27, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersGive me real time application of BST.....
- nr May 23, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersGiven a list of n points in 2D space. Lets call them (X1,Y1), (X2,Y2) .... (Xn,Yn). Find the optimal way to retrieve the result of following query.
- Amm Sokun May 22, 2013 in India
SELECT min(X) FROM (2D Points) WHERE Y between Ymin and Ymax.| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm - -3of 3 votes
AnswersYou have an array of binary numbers as "00001101000001010100000..."... We need to find the First occurrence of 1 in this series.. using binary search.
- imvrajendra May 21, 2013 in India
we need to design an algorithm of complexity less than O(n).. and we need to use binary search strictly..| Report Duplicate | Flag | PURGE
Amazon SDE1 Arrays - 0of 0 votes
AnswersGiven a Binary Search tree along with the parent pointer, find the next largest node for the given node. Give the time and space complexity. The node Structure is
- chetan12189 May 14, 2013 in India
class Node {
Int data;
Node left;
Node right;
Node parent;
}| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWrite a Javascript program for the following problem -
- EK MACHCHAR May 13, 2013 in United States
(Actually, any language is fine with me but it was a JS interview)
Given a large number of strings occurring on a web page, find the largest group of strings that are likely to be swapped with each other.
e.g mat, rat, groom, broom, cat
answer => mat, rat, cat and not groom, broom
I coded edit distance, got hopelessly lost beyond that.
As for hints, he said that it being a web page don't count on traversing a given string more than once.| Report Duplicate | Flag | PURGE
TP SDE1 Algorithm JavaScript - 2of 2 votes
AnswersSort an array which only has 0's and 1's. Do not use count sort.
- CodeNameEagle May 10, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm Arrays - 0of 0 votes
AnswersGiven a sorted array find whether odd number of numbers exist s.t. sum is K. 0 is a permitted value in array. Negatives may not be permitted. But he was not conclusive there. He was expecting Javascript code and O(n) complexity.
- EK MACHCHAR May 10, 2013 in United States
e.g. [12, 2, 1, 4] , searching 1 => yes, 5 => no because 4+1 make the number of numbers even!| Report Duplicate | Flag | PURGE
TP SDE1 JavaScript - 0of 0 votes
AnswersData-structure and algorithm used in Load Balancer??
- nr May 06, 2013 in United States
Explaining algorithm write code for it| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 0of 0 votes
Answers1. N-Petrol bunk problem: There are n petrol bunks located in a circle. We have a truck which runs 1 km per 1 liter (mileage 1kmpl). Two arrays are given. The distances between petrol bunks are given in one array. Other array contains the no of liters available at each petrol bunk. We have to find the starting point such that if we start at that point , you we would able to visit entire circle without running out of fuel. Initially truck has no fuel
- blackfever May 05, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersQ1. What is inheritance
- JSDUDE May 04, 2013 in United States
2. Polymorphism
3. Diff between Pure Virtual class and Virtual Class
4. Adv and dis-adv of C# and C++ over each other
5. Sequence in which constructors are called when a child class object is created and why is the order so.| Report Duplicate | Flag | PURGE
Microsoft SDE1 Object Oriented Design - 1of 1 vote
AnswersGiven a rotated sorted array, find the MIN of the array.
- JSDUDE May 04, 2013 in United States
He pointed out a mistake in my
int middle = (begin+end)/2 which could overflow if the array size was INT_MAX.
Answer was:
middle = (end-begin)/2 + begin| Report Duplicate | Flag | PURGE
Microsoft SDE1 Arrays - 2of 2 votes
AnswersGiven a binary tree, print its perimeter:
- JSDUDE May 04, 2013 in United States
node, left->most nodes from top to bottom, leaf nodes from left-> right, right->most nodes from bottom to top
----------------------------1
-----------------------2--------3
------------------4-----5-----6--------7
-------------8------9-----10------11-----12
should print:
1-2-4-8-9-5-10-11-12-7-3
5 because it doesn't have any children. 10 and 11 are children of 6 and 8 & 9 are children of 4.
Apologies for the messy diagram.| Report Duplicate | Flag | PURGE
Microsoft SDE1 Trees and Graphs - 0of 0 votes
AnswersGiven a Binary tree and a node, return it's post-order predecessor
- JSDUDE May 04, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE1 Trees and Graphs