SDE-2 Interview Questions
- 1of 1 vote
AnswersGiven a n by m matrix of bits find the largest X that is formed in the matrix and return the size of the diagonal of that X. An X is defined as 2 equally sized diagonals that share a single 1.
- pretonesio September 02, 2013 in United States for Powerpoint
For instance, the matrix:
00100001
00010010
00001100
00001100
00010010
00100001
Will return a size of 1, because the given X is invalid as the middle part does not share a single 1. On the other hand, the following matrix
101
010
101
Will return a value of 3, as the diagonal is 3. Write such program,| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 1of 1 vote
AnswersFlipkart handles millions of users looking to buy or sell products. It also provides a search bar to the user as an interface to search for items. At times when typing users may enter a query string which may be single word by mistake but the intention of the user was to type them separately. For eg.,
- nilukush August 20, 2013 in India
User may have entered flipkartmobile when in real, his / her intention was to search for flip kart mobile.
Considering above scenario, implement an algorithm to split up query string provided by user given a list of dictionary words, i.e, you will be given a list of dictionary words and the user-input query string and you have to give the split up of query string which satisfies the following requirements / properties :
1. In case of multiple split-ups, conclude on the one that is lexicographically smaller, i.e, has spaces more towards the left. For eg.,
Assume you are given the list of words : flip, kart, flipkart, mobile and user-input query string is flipkartmobile. Hence, possible split-ups are flip kart mobile and flipkart mobile. The answer / output in this case should be flip kart mobile with more spaces towards the left.
2. Number of characters in query string shall be < 500 characters. Reason being hackers may try to provide a very long input and hence, this may consume processing and result in unresponsive website ultimately.
3. Repetition of dictionary words in query string is possible. For eg.,
Assume you are given the list of words : lg, mobile and user-input query string is mobilelglg. The answer / output in this case should be mobile lg lg.
Now, format of Input and Output :
Input
4 // number of dictionary words given
flip // list of dictionary words the number equaling to input above
kart
flipkartmobile
flipkartmobile // user-input query string
Output
flip kart mobile| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - -11of 11 votes
Answerswrite an algorithm for, the user request should be completed in logN time in a N story building with M elevators
- Vin August 17, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersGiven a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position.
- Vin August 17, 2013 in India
You can assume the die you throws results in always favor of you.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -5of 5 votes
AnswersGiven an array of positive integers, create another array of the same integer such that in the new array the integer at index i is the integer with highest frequency in the input integer.
- anonymous August 11, 2013 in United States
input array: {1,2,3,6,1,3,6,7,3,9,4,2}
output: {1,1,1,1,3,3,3,3,3,3,3}| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 2 votes
Answersfind the maximum no. of paths from (0,0) to (m,n) in a m*n matrix
- anonymous August 11, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 2 votes
AnswersCheck if a singly linkedlist of Integer is a palindron or not.
- anonymous August 11, 2013 in India
Extraspace: O(1)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 4of 4 votes
AnswersConsidering a stream of integers coming in. Design a datastructre to store only n of them. Insert if if does not exist in the datastructre. And if it reaches n, remove the first one inserted into the datastructure.
- anonymous August 11, 2013 in India
Datastructure should provide, addition, deletion and search all in O(1) time.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 2of 2 votes
AnswersGiven 3 Arrays of integer sorted in ascending order, get the sum of minimum difference using one element from each array.
- anonymous August 11, 2013 in India
where a, b, c are the elements from each array.
diff = |a-b| + |b-c|+|c-a|
complexitiy: worst case O(n)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersCreate an array from unbalanced binary tree, such that it should re create the same tree again.
- Jyothi August 11, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 3 votes
AnswersHow to find medium of 1 billion numbers across N distributed machines efficiently?
- seanren7 August 09, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 1of 3 votes
AnswersGiven 2 binary arrays A and B i.e. containing only 0s and 1s each of size N.
- tryingtosolvemystery August 07, 2013 in India
Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum possible value.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 3 votes
AnswersIn a Binary Tree, weight of each node is described by the value of the node multiplied by the level (i.e. for root node value is 1* value in root node), And the weight of tree is sum of all the node weights.
- prabal77 August 06, 2013 in India
Find the minimum tree weight out of all the binary trees possible from a given set of numbers.
P.S: No input and no sample data provided| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 0of 0 votes
AnswersThere is a stream of numbers coming in and you have to find K largest numbers out of the numbers received so far at any given time. Next problem is that a constraint is added. memory is limited to m. m < k. How would you achieve the goal still.
- tryingtosolvemystery August 06, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswersGiven a floor in a building, we need to place tiles on it.
- tryingtosolvemystery August 06, 2013 in United States
*You can use tiles of a given set of dimensions*. But each type of the tile has a given cost associated. (you cannot cut a tile). How would you tile the floor in minimum cost ? Also answer whether the floor can be tiled at all or not ?| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersFind all pairs of numbers in an array that sum to a given number, n, in linear time
- yashpal.jain August 04, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersDesign an LRU cache
- yashpal.jain August 04, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersDesign and describe the classes you would use when implementing the card game War.
- yashpal.jain August 04, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -2of 2 votes
AnswersGiven a n (large number) lists of customers who visited n webpages on n (large number) days, design a data structure to get customers who have visited the website on exactly "k" days and should have visited at least "m" distinct pages altogether.
- yashpal.jain August 04, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 3 votes
AnswersExcel columns are labelled alphabetically in length-lexicographic order, i.e., A, B, C, ..., Z, AA, AB, ....
- jatson August 02, 2013 in United States
Given the 1-based numeric index of a column, return the corresponding label.
Example 1:
1
Output 1:
A
Example 2:
54
Output 2:
BB| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersWhich one you prefer and why?
- yogi.rulzz July 23, 2013 in India
Vector of pointer,reference and object. which one you will prefer.| Report Duplicate | Flag | PURGE
Akamai SDE-2 C++ - 0of 0 votes
Answersyou have given a post-fix of a binary try in which either you have 0 child(leaf node) or 2 child(internal node).
- yogi.rulzz July 23, 2013 in India
one more condition that all internal node are denoted via "i" and leaf node via "l".
we have to create this binary tree with this posfix.| Report Duplicate | Flag | PURGE
Akamai SDE-2 Algorithm - 1of 1 vote
AnswersGiven two sorted arrays of equal length, how do you find a pair of numbers, one from each array, such that the absolute difference between the two numbers is minimum.
- Murali Mohan July 22, 2013 in India for Bangalore| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 10of 10 votes
AnswersA tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes that node with id k is the root. For ex:
3 3 3 -1 2 0 1 2 3 4
In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4.
- Murali Mohan July 22, 2013 in India for Bangalore
Given such an array, find the height of the tree.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersIn an N*M grid, in how many ways can you reach from top left (0,0) position to an arbitrary location (i,j) provided you can only move to the right or to the bottom in one step?
- Murali Mohan July 22, 2013 in India for Bangalore
How do you compute the number of ways from (0,0) to (i,j) if there are arbitrary number of blocks on the way?| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - -1of 1 vote
AnswersDesign a DVD renting library system
- pavi.8081 July 19, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Object Oriented Design - 0of 0 votes
AnswersYou are given a sorted array,increasing monotonically and decreasing in the same fashion.
- sayannayak July 18, 2013 in India for Bangalore
WAP to find the index of an element in this array without calculating the pivot.
Running time should be O(log n).You can assume there ia no duplicate element in this array.
e.g: the array is {1,7,10,12,25,30,27,20)
input: arr[],key=27. output=6
input :arr[],key=0. output=-1| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 3of 3 votes
AnswersDevelop an algorithm and write code to break a sentence without spaces into a sentence of valid words separated by spaces.
- Murali Mohan July 16, 2013 in India for Bangalore
For ex: thissentenceisseparated needs to be broken into: this sentence is separated
Assume that you have a dictionary to check for valid words. Your algorithm should return false if the sentence cannot be separated into valid words.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven n, how many structurally different binary trees can be formed?
- Murali Mohan July 16, 2013 in India for Bangalore
For ex: n = 1 => one tree
n = 2 => two trees
O O
/ \
O O
n = 3 => five trees
O O O O O
/ \ \ / / \
O O O O O O
/ \ / \
O O O O| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 0of 0 votes
AnswersGiven one integer n.
- sayannayak July 15, 2013 in India
You have to find out for any integer n,How many distinguished n*n boolean matrix you can form such that each row and each column contains exactly.ceil(n/2) zeroes.
Follow Up: Write your code if you want to print the matrices as well| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm