Recent Interview Questions
- 4of 6 votes
AnswersGive you two sequences of length N, how to find the max window of matching
- Code2Win June 08, 2013 in India
patterns. The patterns can be mutated.
For example, seq1 = “ABCDEFG”, seq2 = “DBCAPFG”, then the max window is 4. (
ABCD from seq1 and DBCA from seq2).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer String Manipulation - 7of 7 votes
AnswersWrite a function that gets a billion integers. How can you find the midian in most efficient way (time)?
- adam2008 February 16, 2013 in United States
same question, but the input is an endless stream of integers, and we want to find the current median.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersImagine you have a sequence of the form 0123456789101112131415... where each digit is in a position, for example the digit in the position 5 is 5, in the position 13 is 1, in the position 19 is 4, etc.
- 352905 February 04, 2013 in United States
Write a function that given a position returns the digit in that position.
(You could think that this sequence is an array where each cell only holds one digit so given an index return what digit is in that index, however you cannot really create an array since the sequence is infinite, you need a way to based on the index calculate the digit that goes there).
The function has to return a single digit.
Other examples:
index = 100, result = 5
index = 30, result = 2
index = 31, result = 0
index = 1000, result = 3| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGenerate a number is range (1,n) but not in a list (i,j)
- superffeng September 27, 2012 in United States for Site reliabilty
for example range is (1,1000), list is [2,3,5,9,199,200,344]| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Algorithm - 0of 0 votes
AnswersA list contains repeated numbers , all the numbers are repeated odd number of times except one which is repeated even number of time. WAP to find out that number ( which is repeated even number of times).
- maverick July 17, 2012 in India
( I gave the solution using extra space . He then asked me to give solution without extra space )| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow to check a whether a very big number n^n = k
- banerjees36 June 22, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Systems Design Engineer Algorithm Data Structures - 0of 2 votes
AnswersPrint All common ancestor of Given Binary tree in O(n)
- NaiveCoder April 30, 2012 in India
without using Extra space.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersGiven an array find 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time.
- ninja April 03, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.
- NaiveCoder March 21, 2012 in India
eg :
Matrix
{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}
And pattern is microsoft.
It's funny when google looks for pattern of microsoft ;)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 1of 1 vote
AnswersThere is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum. As for how to compute the cost of moving one group to another point, please see the following example.
- xiaoc10 March 11, 2012 in United States
Group1: (0, 1), 4
Group2: (1, 3), 3
Group3: (2, 0), 5
. 4 . .
. . . 3
5 . . .
If all of these three groups moving to (1, 1), the cost is: 4*((1-0)+(1-1)) + 5*((2-1)+(1-0))+3*((1-1)+(3-1))
My idea is :
Firstly, this two dimensional problem can be reduced to two one dimensional problem. In the one dimensional problem, I can prove that the best spot must be one of these groups. In this way, I can give a O(G^2) algorithm.(G is the number of group).
Use iterator's example for illustration:
{(-100,0,100),(100,0,100),(0,1,1)},(x,y,population)
for x, {(-100,100),(100,100),(0,1)}, 0 is the best.
for y, {(0,100),(0,100),(1,1)}, 0 is the best.
So it's (0, 0)
Is there any better solution for this problem.
Thanks,| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersGiven a set of unique numbers from 1 to 1000, propose a data structure that allows you to perform the following operations in constant time.
- Fab February 10, 2012 in United States for Instant Video
1- Insertion,
2- Deletion,
3- Searching,
4- Get any random number.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHow to find a first non repeating character in a String ?
- Nikhil July 21, 2011| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Java - 0of 0 votes
AnswersGiven two arrays A & B of length l, containing non negative integers, such that the sum of integers in A is the same as sum of integers in B.( The numbers need not be the same in both the arrays.)
- Jan November 26, 2010
Now if you start with an index 'k' in each array and do the following summation, SUMMATION (Ak-Bk), where Ak is the value at index k of array A, and Bk is the value at index k of array B, where 'k' increments and wraps back all the way to k-1, the final sum value will be zero.
Question: Find a suitable 'k' such that during any point in the summation, SUMMATION(Ak-Bk) is always non negative. Find such a 'k' in O(n) time.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a document and a query of K words, how do u find the smallest window that covers all the words at least once in that document? (given you know the inverted lists of all K words, that is, for each word, you have a list of all its occurrrences). This one is really hard. Could someone propose an algorithm in O(n)?
- Anonymous November 11, 2009| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answersyou can go to a fast food restaurant to buy chicken nuggets in 6-pack, 9-pack or 20-packs. is there such a number N, such that for all numbers bigger than or equal to N, you can buy that number of chicken nuggets?
- cunomad September 19, 2009| Report Duplicate | Flag | PURGE
Epic Systems Brain Teasers - 0of 0 votes
AnswersIt will gain you more knowledge, intensify your soft skills, strong work ethics and grow your network. What is it?
- lucykabazzi January 31, 2019 in United States| Report Duplicate | Flag | PURGE
Business Question - 1of 1 vote
AnswersYou are given an array of integers(with all valid input) You have to write a function which will produce another array, where the value in each index of the array will be the product of all values in the given array accept that index.
- Azarbaizan January 10, 2017 in United States for Market Place
Example
Array 1: 1 2 3 4 5
Array 2: 120 60 40 30 24.
Come up with a solution of O(n^2) can you improve it?| Report Duplicate | Flag | PURGE
Amazon Software Engineer Arrays - 1of 1 vote
AnswersGiven integer k and a subset S of set {0, 1, 2, ..., 2^k - 1}
- emb December 13, 2015 in United States
Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a)
& here is bit-wise and.
Do it faster than O((2^k)^2), assume k <= 16
Example:
0b111
0b101
0b010
Answer: 2
0b110
0b011
0b101
Answer: 0| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersWrite program for the following scenario
- APV July 25, 2015 in India for Amazon Wireless
Input Array :- {1,2,3,4,5,5,5,6,7,7}
Output:- 5 is repeated 3 times
7 is repeated 2 times| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Arrays - 10of 12 votes
AnswersGiven a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.
- lilzh4ng June 10, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersPrint the following pattern using C/C++
- deepanshuchg March 14, 2015 in India
(For n=4)
1
2*3
4*5*6
7*8*9*10
7*8*9*10
4*5*6
2*3
1
PS: Printing above triangle is easy and I easily did it, but couldn't print the lower triangle.| Report Duplicate | Flag | PURGE
Josh Software Developer C++ - 1of 1 vote
AnswersGiven a Tree:
A /\ B C /\ /\ D E F G
Write a function that prints:
- santidltp January 05, 2015 in United States
A
BC
DEFG| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow can we get square of a number without using * or carrot sign.
- newbee August 30, 2014 in United States| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer Algorithm - 21of 23 votes
AnswersGiven a undirected graph with corresponding edges. Find the number of possible triangles?
- redsanket March 25, 2014 in United States
Example:
0 1
2 1
0 2
4 1
Answer:
1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 6of 6 votes
AnswersTwo container of 5 L and 3 L are given. Then are is 9.5L water given you need to make 4L water with minimum attempts and water wastage.
- Sachdefine January 11, 2014 in India for Kindle| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Brain Teasers - 4of 6 votes
AnswersArrange the numbers in an array in alternating order.
- codefreak November 16, 2013 in United States
For example if the array is [a1, a2, a3, a4.. ]arrange the array such that b1<=b2>=b3<=b4 and so on.
Sampe Input: 3 5 7 8 4 9
Sample Output: 3 < 5 > 4 < 8 >7 < 9| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Arrays - 7of 7 votes
AnswersPattern Matching
- mamidi.laxman.lnu June 11, 2013 in United States
----------------
Characters: a to z
Operators: * +
* -> matches zero or more (of the character that occurs previous to this operator)
+ -> matches one or more (of the character that occurs previous to this operator)
Output if a given pattern matches a string.
Example:
pattern:a*b
string:aaab b, ab, aab, aaab, ab
output:1
pattern:a+aabc
string:ab aabc, aaabc, aaaabc ..
output:0
pattern:aa*b*ab+
string:aab aab, aabab, aaaabbab
output:1
pattern: a+a*b*
string: a ab, aab, aaabb
output: 1
Valid Assumptions: Please assume that both the pattern and string input are valid| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 0of 0 votes
AnswersDesign a DS for storing browsing history.
- Nascent April 20, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Adobe Software Engineer / Developer