Recent Interview Questions
- 6of 6 votes
AnswersGiven an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array.
- PradeepN October 27, 2015 in United States
Brute force is obvious, but must be done faster than O(n^2)
Ex. [3,4,5,9,2,1, 3]
Return [3, 2, 1, 0, 1, 1, 0]
First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersYou are given large numbers of logs, each one of which contains a start time (long), end time (long) and memory usage (int). The time is recorded as MMDDHH (100317 means October 3rd 5PM) Write an algorithm that returns a specific time (hour) when the memory usage is the highest. If there are multiple answers, return the first hour.
- aijackmoore September 21, 2015 in United States
e.g. 100207 100208 2
100305 100307 5
100207 100209 4
111515 121212 1
Answer: 100207
(Need to consider different scenarios like the time slots could be very sparse)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven unsigned integer 'x', write an algorithm thet returns unsigned integer 'y' such that it has the same number of bits set as 'x' and is not equal to 'x' and the distance |x-y| is minimized.
- autoboli August 31, 2015 in United States
Example:
x: 01
y: 10
Note that one bit is set and 'x' is not equal 'y'. You may assume that x is positive integer between zero and 2^32-2;| Report Duplicate | Flag | PURGE
Google - 1of 1 vote
AnswersWrite function to determine if given unsigned 32-bit number is a power of 3
int is_power_of_3(uint32_t n)
return 1 if yes, 0 otherwise.
e.g.is_power_of_3(27) = 1 is_power_of_3(9) = 1 is_power_of_3(42) = 0 is_power_of_3(0) = 0
Expected the answer not to be straightforward loop, but something faster.
- emb August 28, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Math & Computation - 4of 4 votes
AnswersGiven an array Of integers build a new array of integers such that every 2nd element of the array is greater than its left and right element.
- Gaurav Shah March 17, 2015 in United States for Chrome Team
eg:
[1,4,5,2,3]
o/p:
[1,4,2,5,3]
Soln proposed:
Step 1:Sort The array -> O(nlogn)
Step 2:Use 2 indices: one starting at leftmost index and other at rightmost index.
and populate the new array alterntely using the left pointer(index) first and then the right pointer and then increment the pointer used. till both the pointers meet/cross each other. -> O(n).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersGiven an m x n matrix where each row element is sorted, but the columns do not appear in sorted order, write a function to print each matrix element in sorted order.
- seanchen11235 March 06, 2015 in United States
Example matrix:
matrix = [
[20, 40, 80],
[5, 60, 90],
[45, 50, 55]
]
Your function should print 5, 20, 40, 45, 50, 55, 60, 80, 90.
Add on: Assume that we are space-constrained such that we can only hold one row in memory at a time. Optimize your function to work under such constraints as efficiently as possible.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a string containing letter, digit, and other characters, write a function to check palindrome for only letter and digit. The implementation need to be in-place, no extra memory is allowed to create another string or array.
- naomi.lijing@googlemail.com February 25, 2015 in UK
For example:
"ABA" is palindrome
"A!#A" is palindrome
"A man, a plan, a canal, Panama!" is palindrome| Report Duplicate | Flag | PURGE
Facebook Software Developer - 0of 0 votes
AnswersCompletely blew it on this question today.
- jsdude January 28, 2015 in United States
1.) Given an array, find the maximum difference between two array elements given the second element comes after the first.
For example.
array = [1,2,3,4,5,6,7]
We can take the difference between 2 and 1 (2-1), but not the different between 1 and 2 (1-2).
This question is super easy, I solved it within minutes of getting of the phone. I came up with an O(n^2) solution over the phone. My improved solution was O(n).| Report Duplicate | Flag | PURGE
Facebook Software Engineer Arrays - 3of 3 votes
AnswersYou're given a dictionary of strings, and a key. Check if the key is composed of an arbitrary number of concatenations of strings from the dictionary. For example:
- davelee71047 October 25, 2014 in United States
dictionary: "world", "hello", "super", "hell"
key: "helloworld" --> return true
key: "superman" --> return false
key: "hellohello" --> return true| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 2of 2 votes
AnswersThe stepping number:
- Anon October 13, 2014 in United States
A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 8,343,545 are stepping numbers. While 890, 098 are not. The difference between a ‘9’ and ‘0’ should not be considered as 1.
Given start number(s) and an end number(e) your function should list out all the stepping numbers in the range including both the numbers s & e.| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm Data Structures Dynamic Programming Java Online Test - 3of 3 votes
Answers/**
- g April 23, 2014 in United States
* Implement a function OneEditApart with the following signature:
* bool OneEditApart(string s1, string s2)
*
* OneEditApart("cat", "dog") = false
* OneEditApart("cat", "cats") = true
* OneEditApart("cat", "cut") = true
* OneEditApart("cat", "cast") = true
* OneEditApart("cat", "at") = true
* OneEditApart("cat", "acts") = false
* Edit is: insertion, removal, replacement
*/| Report Duplicate | Flag | PURGE
Facebook Algorithm - 1of 1 vote
AnswersGiven a string, complete the given function to recursively remove the adjacent duplicate characters and return the resultant string. If there are no characters left in the resultant string, return "-1" (without quotes).
- jerinsebastian.punnamada April 08, 2014 in United States
Sample Test Cases
Sample Input: ABCCBCBA
Output: ACBA
Explanation: (ABCCBCBA --> ABBCBA --> ACBA)
Sample Input: AA
Sample Output: -1
Java solution| Report Duplicate | Flag | PURGE
Yahoo Applications Developer Algorithm Java - -3of 9 votes
AnswersMany sticks with length, every time combine two, the cost is the sum of two sticks' length. Finally, it will become a stick, what's the minimum cost?
- Vincent March 17, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 5 votes
AnswersThere are many sorted arrays. Find a minimum range, so that in each array there's at least one integer within this range.
- edcent February 25, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Intern Algorithm - 2of 2 votes
Answers// cat, actor -> T // car, actor -> F bool anaStrStr (string needle, string haystack) { }
Write a function that takes 2 strings , search returns true if any anagram of string1(needle) is present in string2(haystack)
- juny February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersDetermine whether an interger is a multiple of 5 in O(logn) time complexity. You cannot use / and %.
- xuwithsurprise January 20, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersRemove duplicates from a string inplace. The algorithm should be as efficient as possible.
- alex December 19, 2013 in India
I gave two approaches. First, the simple comparison O(n2) and second, sorting O(nlgon). But the interviewer did not seem satisfied.
Can someone please suggest a better algorithm?| Report Duplicate | Flag | PURGE
Microsoft Intern Algorithm - 8of 8 votes
AnswersQ: Design a component that will implement web browser history. the user goes to different site and once he press on history button you should display the last 5 (no duplicates allowed, and 5 can be any N later) if duplicates occur display the most recent one. so if user visit : G,A,B,C,A,Y and than press "history" we will display Y,A,C,B,G. and of course he can go later to two other websites and than press "history" we will show them than the previous 3.
- Dany November 21, 2013 in United States
A: I solved it with stack, list and hash table in O(n) but it was too complicated and I didn't like my solution. please suggest something simpler.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 11of 13 votes
AnswersThere are some glasses with equal volume 1 litre. The glasses kept as follows
1 2 3 4 5 6 7 8 9 10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..
- Vin July 17, 2013 in India
If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd - 1/| Report Duplicate | Flag | PURGE
Amazon SDE1 - 4of 6 votes
AnswersGiven a server that has requests coming in. Design a data structure such that you can fetch the count of the number requests in the last second, minute and hour.
- AVK June 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven an integer array, find pairs in an array which sum up to a given number.
- aopencv June 14, 2013 in United States
For example: Array{4,5,1,3,2} and required sum=6 then output should be [1,5] and [2,4].| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Data Structures Java - 2of 2 votes
Answerswe have given a char array like “a1b2c3″ we have to convert this array to array like this “abbccc” .This has to be done in place as we have given that array has just enough space to hold the expanded array.
- nishu9101 February 20, 2013 in India
example:
1)input: a1b1c1
output:abc
length of array will be shortened.
2)input: a2b2c2
output:aabbcc
length of array will be equal to given array.
3)input: a3b4
output:aaabbbb
length of array will be greater than given array.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersCount the number of shapes in a given (1/0) matrix. A cluster of consecutive (not diagonal) 1's defines one shape.
- iwanna February 18, 2013 in United States
eg
1 1 0 0 1
1 0 0 1 0
1 1 0 1 0
0 0 1 0 0
No of shapes = 4| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersSuppose we are detecting fraud cheques and we found the cheques with the following list of patterns are fraud:
- zahidbuet106 February 13, 2013 in United States
111122234455
1234
22334455
11111111
234567
etc.
Now if you have a new cheque and wan to detect fraud in O(1) time what data structure you want to use?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersAn array of size N is given. Array is sub divided into sub array of size K. Find maximum value of each sub array.
- Crazy Tesla January 20, 2013 in India
My ans-
While traversing the array keep on adding values to max heap of size K and keeping a virtual window of size K on array.
When element leaves the window then remove the leaving element from heap too and reheapify the heap. And max element of that window will be again on top in heap.
Any better approach?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays - 3of 3 votes
AnswersRound 3 :
- sonesh January 03, 2013 in India
Q 5 : You are given a binary search tree, and a value(data item), you need to tell the left most right cousin in as minimum time and as minimum space ?(need to minimize actual time complexity, he need minimum order of complexity as well as number of node access should be minimum)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Trees and Graphs - 1of 1 vote
AnswersFrom the set of natural integer numbers
- CameronWills October 30, 2012 in United States
Let x = 1234 = {1, 2, 3, 4}
Let y = 2410 = {2, 4, 1, 0}
Write an algorithm to compute the rearrangement of x that is closest to y but still greater than y. Both x and y have the same number of digits.
So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is greater than y = 2410 and closer than any other arrangements of x.
And whats the time complexity of this algorithm?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a ternary string, you have to count the total number of contiguous substrings (contigious set of characters), that you can form from this given string such that they comprise of either only one or two different characters.
- k.87.sharma October 30, 2012 in United States
Please note that a unique substring will be decided by its starting and ending indices. So, a substring 'ab' with starting and ending indices being 1 and 2 respectively should be considered different from a substring 'ab' with starting or ending indices (or both) other than 1 and 2 respectively.
For example:
input ternary string - aabc
output - 8
The above string comprises of the following substrings that have either one or two of the characters - a, a, b, c, aa, ab, bc and aab. So the final answer is a total of eight substrings.
input ternary string - abc
output - 5
The above string comprises of the following substrings that have either one or two of the characters - a, b, c, ab and bc. So the final answer is a total of five substrings.
input ternary string - baaccb
output - 16
The above string comprises of the following substrings that have either one or two of the characters - b, a, a, c, c, b, aa, cc, ba, ac, cb, baa, aac, acc, ccb and aacc. So the final answer is a total of sixteen substrings| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersA string s is said to be unique if no two characters of s are same.
- swati.2332 August 19, 2012 in India
A string s1 is producible from s2 by removing some of the characters from s2.
A string s1 is said to be more beautiful than s2 if length of s1 is more than s2 or if both have same length and s1 is lexicographically greater than s2( ex: ba is more beautiful than ab)
Input: is a string which can be of maximum 10^6 characters, you have to produce the most beautiful unique string out of the given string.| Report Duplicate | Flag | PURGE
Facebook Coding - 0of 0 votes
AnswersImplement rotate function for forward-only iterators.
- JacVlD July 31, 2012 in United States
Clarification: with O(1) additional memory. Rotate semantics should be that of std::rotate.
I personally know a O(n*log(n)) solution which takes O(log(n)) extra memory, and I assume it should be possible to reduce memory costs to O(1).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer