Recent Interview Questions
- 3of 3 votes
AnswersA binary search tree is given. Find the ceiling value present in the BST of a given key.
eg-8 3 12 2 6 10 15 4
key - 13 => 15
- LAP June 24, 2013 in United States
key - 4 =>6
key - 8 =>10| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 2of 4 votes
AnswersGiven a binary tree return the level with maximum number of nodes
- ruddermechanic February 07, 2013 in United States1 / \ 2 3 /\ /\ 4 5 6 7 / \ 8 9
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven a BST, how would you return the nth smallest element. The code had to cover all the edge cases and was expected to write a logn solution
- pradeep1288 January 19, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C - 0of 0 votes
AnswersGiven a BST, with nodes having a parent pointer, a pointer to a node (any node), and a value. Find the path from the given node (pointer), to the node with the given value.
- underdog December 31, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Development Manager Algorithm - 0of 0 votes
AnswersFind the first missing number in an array of sorted numbers.
- coder December 09, 2012 in United States
Eg: Input : 4,5,6,7,9,11,14,18,19
Output : 8
Expected complexity : O(log n)
Approach is similar to binary search| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 12of 14 votes
Answerswe will name a number "aggregated number" if this number has the following attribute:
- holmespanda November 16, 2012 in United States
just like the Fibonacci numbers
1,1,2,3,5,8,13.....
the digits in the number can divided into several parts, and the later part is the sum of the former parts.
like 112358, because 1+1=2, 1+2=3, 2+3=5, 3+5=8
122436, because 12+24=36
1299111210, because 12+99=111, 99+111=210
112112224, because 112+112=224
so can you provide a function to check whether this number is aggregated number or not?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array of intergers. Write a program to print all the permutations of the numbers in the array. The output should be sorted in a non-increasing order. For example for the array { 12, 4, 66, 8, 9}, the output should be:
- Nidhi Jain September 02, 2012 in United States
9866412
9866124
9846612
....
....
1246689| Report Duplicate | Flag | PURGE
Google Arrays - 0of 0 votes
Answersfind the 2nd largest # in int array
- Itcecsa June 10, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Front-end Software Engineer Algorithm - 0of 0 votes
AnswersQ2. F2F Round-1, Amazon(Bangalore)
- Nitin Gupta May 12, 2012 in India
Given an array of integers having the property that first that array is strictly increasing then it is strictly decreasing, You have to search for a given number.
Constraint: Minimize the complexity| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java - 1of 1 vote
AnswersQ3. Written Exam Amazon(Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a singly linked list which may or may not contain loop and loop may or may not start from the head node. Count the number of elements in the linked list.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 2of 2 votes
AnswersConsider this string representation for binary trees. Each node is of the form (lr), where l represents the left child and r represents the right child. If l is the character 0, then there is no left child. Similarly, if r is the character 0, then there is no right child. Otherwise, the child can be a node of the form (lr), and the representation continues recursively.
- Itcecsa April 08, 2012 in United States
For example: (00) is a tree that consists of one node. ((00)0) is a two-node tree in which the root has a left child, and the left child is a leaf. And ((00)(00)) is a three-node tree, with a root, a left and a right child.
Write a function that takes as input such a string, and returns -1 if the string is malformed, and the depth of the tree if the string is well-formed.
For instance:
find_depth('(00)') -> 0
find_depth('((00)0)') -> 1
find_depth('((00)(00))') -> 1
find_depth('((00)(0(00)))') -> 2
find_depth('((00)(0(0(00))))') -> 3
find_depth('x') -> -1
find_depth('0') -> -1
find_depth('()') -> -1
find_depth('(0)') -> -1
find_depth('(00)x') -> -1
find_depth('(0p)') -> -1| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm - 0of 0 votes
Answerswrite a program in c# or java or c
- vamcrulz09 February 19, 2012 in United States
print the sequences from the input given by the user separated by semicolon
eg: 4678912356012356
output: 6789;123;56;0123;56;| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer C# - 0of 0 votes
AnswersGiven an array (length n), we need to find the subarray (length k) such that the sum of the first j elements of the subarray equals the sum of the remaining (k-j) elements of the subarray.
- PM January 09, 2012 in -
For e.g.
Array: 2,2,13,4,7,3,8,12,9,1,5
Output: 4,7,3,8,12,9,1 [4+7+3+8=12+9+1]
Could this be done with a complexity better than O(n^3)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
Answerstwo BST were given and find the largest common bst that exists between these two
- Anonymous June 22, 2011| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou have an integer array of length N, containing values in the range 1,2,3…N^2. Sort the array in O(N) time
- Anonymous November 19, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite a function to find the longest path of a tree
- mp March 22, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 2of 2 votes
Answershow would you merge two sorted arrays provided not to use a third array nor u can allocate extra space. try to optimize the problem to the best. time complexity should be less than O(n^2)
- not a looser January 19, 2009| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Software Engineer in Test Arrays - 6of 6 votes
AnswersYou are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.
Find number of 0-s in the given matrix.
Example:0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4
Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).
- emb June 26, 2016 in United States
Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N-1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).
Nice job, @gen-y-s :)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 5of 5 votes
AnswersSay you have a keypad that has keys for the numbers 0 through 9 and the correct code is some sequence of 5 digits. This keypad does *not* reset after entering an incorrect sequence of 5 digits. ie. If the correct sequence is 12345, entering 7512345 will succeed in opening it because it ends in the correct sequence. If the keypad actually resets after every 5 digits pressed, then it would not succeed b/c it would interpret the above sequence as "75123" then "45".
- Jason May 30, 2015 in United States
1. Write an algorithm that will try to find the correct code for this keypad. Assume you have an API similar to KeyPad.pressKey(int n) where you pass in a number (0...9) and it returns true if the keypad unlocks and false if it's still locked.
Note that you could easily enter all digits of all numbers 00000 through 99999 resulting in 5*100000 key presses, but remember that the panel does not reset after every sequence of 5 digits, so find a way to do this more efficiently. Notice for example that entering the stream 3791283780 will test the length 5 sequences 37912, 79128, 91283, 12837, 28378, 83780; not only the two disjoint sequences 37912 and 83780.
Think of this keypad as remembering the last 4 keys pressed (and the order pressed); when the next key is pressed, if the last 4 keys + the current key equal the correct code, the keypad will unlock. Assume the keypad does all this internally, so you can just keep feeding it keypresses and it will eventually unlock if the last 5 keypresses entered is the correct code.
2. Generalize your algorithm to work for a keypad where you don't know the length of the correct sequence in advance.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a String find the first non repeating char in a single pass of the string.
- um01 April 18, 2015 in United States
Assume a big character set like utf-8 (eleminate use of char[256])
Avoid any subloop to have a very optimal solution| Report Duplicate | Flag | PURGE
Yahoo SDE1 Algorithm - 0of 0 votes
AnswersTake a string as input and add the digits present in that
- Poornima March 31, 2015 in United States
string.
Ex:I/P="asdf12bgt3bh5j"
O/P=20
I/P="iuy2hjg4jhg8"
O/P=14
I/P="7 13"
O/P=20| Report Duplicate | Flag | PURGE
Java - 2of 2 votes
AnswersFind the longest sequence of prefix shared by all the words in a string.
- employee11 July 15, 2014 in Israel
"abcdef abcdxxx abcdabcdef abcyy" => "abc"| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a function to remove the duplicated characters from a string, and maintain the order of the characters.
- 4661 July 11, 2014 in United States
ex. “abracadabra” ? “abrcd”| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven a random generator rand(5) which generates numbers between 0 to 4. How do u generate numbers between 0 to 6, I.e. Implement rand(7).
- hulk April 16, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Brain Teasers - 4of 4 votes
AnswersGiven a current absolute path, e.g., "/usr/bin/mail", and a relative one, e.g, "../../../etc/xyz/../abc" return the absolute path created from the combination of the first two paths. In the example strings, the answer should be "/etc/abc".
- meh March 24, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou have two numbers decomposed in binary representation, write a function that sums them and returns the result.
- getmax0 December 16, 2013 in United States
Input: 100011, 100100
Output: 1000111| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Bit Manipulation - 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 - 0of 2 votes
AnswersGiven an array of ints, find the most frequent non-empty subarray in it. If there are more than one such sub-arrays return the longest one/s.
Note: Two subarrays are equal if they contain identical elements and elements are in the same order.
- Epic_coder June 29, 2013 in United StatesFor example: if input = {4,5,6,8,3,1,4,5,6,3,1} Result: {4,5,6}
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm