Recent Interview Questions
- 2of 2 votes
AnswersCode a function that receives an array with duplicates and returns a new array keeping the original order of the elements but with the duplicates removed.
For example, if the input were@[ @"dog", @"cat", @"dog", @"fish" ]
the output would be
@[ @"dog", @"cat", @"fish" ]
Tell the complexity of the solution.
- diegum June 06, 2014 in United States for iOS| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Arrays - 2of 2 votes
AnswersWrite a function, for a given number, print out all possible way to make up that number eg: 2 - 1 1,2
- sLion May 25, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersIn an array of unsorted integers (you may assume the array may contain +ve, -ve and 0s), write a function
- Jeanclaude June 28, 2013 in United States
int returnNthMax(int[] arr, int n)
which will return the nth Max number. For e.g. if this is given array {2, -4, 5, 6, 0, 7, -1, 10, 9} and n=1, it should return the max number, 10 and if n=3, it should return 3rd max number, which is: 7.| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Arrays - 2of 2 votes
AnswersWrite a function that takes a string and returns true if the entire string is a palindrome, otherwise return false. The function should be case-insensitive and ignore any whitespace or punctuation.
- Barry Fruitman March 20, 2013 in United States
For example, return true for:
"A man, a plan, a canal: Panama."| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 2of 2 votes
Answerstwo BST are given find common elements in both....
- abhishek September 09, 2012 in India for idc| Report Duplicate | Flag | PURGE
Microsoft Intern Trees and Graphs - 2of 2 votes
AnswersYou are given a set of points on x axis (consumers)
- emb October 22, 2015 in United States
Also you are given a set of points on a plane (producer)
For every consumer print the nearest producer.
Wanted something better than O(n^2) time.
Example:
consumers: 1 5 7
producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100)
Answer:
for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2)
Follow-up question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm?| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersThere is a large file( 1TB) containinig braces. Question is to check for their balance. I said will use a counter, will increment on an open brace and decrement on an close brace. If counter goes negative or counter is non zero at the end of the file, braces are not balanced. Otherwise balanced. Followup question was to make this process parallel ( meaning to see if this problem can be solved through parallelism, like dividing the the problem into sub problem....) Remember the file is very large.
- gns January 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Problem Solving - 2of 2 votes
Answersc program to find square root of an interger without using in built functions
- saran August 12, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Intern C - 2of 2 votes
AnswersOutput the leftmost element of each level of a tree
- 3139a1m August 01, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Intern - 2of 2 votes
AnswersConsider a city (visualize a circle). It has n petrol stations in it. You are given the maximum amount of petrol that can be filled at each of these stations. You are also given the distance between one station to the next one. The aim is to cover the entire city and come back to the start point. Assume that 1 liter of petrol will last for 1km.
- D March 27, 2013 in India
Q: List out all the possible petrol stations from where the journey can be started, so as to cover the city.| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Algorithm - 2of 2 votes
AnswersFind all Subsets that sum upto 10. example
- ariesgirl069 March 02, 2012 in United States
int [] arr ={1,2,3,4,5,6}
Subsets are :
4,5,1
4,6
2,3,5 etc.
Any Suggestions ?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test C# - 2of 2 votes
AnswersGiven number N, Find the least number of perfect square number sum needed to get N.
- itsvks February 01, 2017 in Netherlands
Example :
n=5 (4+1) i.e. 2
n=7 (4+1+1+1) i.e. 4
n=12 (4+4+4) i.e 3
n=20 (16+4) i.e. 2| Report Duplicate | Flag | PURGE
Booking.com Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X
- falkon June 29, 2016 in United States
[1, 3, 5, 18] X = 8 Output: True
X = 9 Output: True
X = 10 Output: False
X = 40 Output :False| Report Duplicate | Flag | PURGE
Facebook - 2of 2 votes
AnswersDefine a function that can detect whether the characters of a string can be shuffled without repeating same characters as one other's neighbors. E.g. :
- fahmida.hamid February 11, 2016 in United States
apple >> alpep, so valid
a >> a, valid
aa >> aa, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid
etc.
You do not have to find one representation, just have to detect if it is possible or not!| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersA string can contain 0 to n(input) number in sorted form find all the transition point.
- Nascent June 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon - 2of 2 votes
AnswersWrite a Java code that take a string of parenthesis as input and return if the string is valid or not . The input will have '(' and ')' and also '*' and * serves as wild card and can be used in place of both '(' and ')' or it can be null.
- ryanray1512 October 16, 2017 in United States
For example,the String (*)(*)(** is a valid String.
Follow up: What if '[]' and '{}' are also in the string along with '()' and * can be used in place of any of them or can be considered as null?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 2of 2 votes
AnswersReverse this string 1+2*3-20. Note: 20 must be retained as is.
- annu025 September 21, 2017 in United States
Expected output: 20-3*2+1| Report Duplicate | Flag | PURGE
String Manipulation - 2of 2 votes
AnswersYou are given a range [first, last], initially white. You need to paint it black.
For this purpose you have a set of triples
[(f, l, cost), ...] - where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers).
Find minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible
Example:[first, last] = [0, 5] and set of triples is [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]
Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.
Another example:[first, last] = [0, 5] triples are [[1,4, 10], [2, 5, 6]]
answer is -1, because it's impossible to color whole range.
- emb June 05, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersYou are given an array, divide it into 2 equal halves such that the sum of those 2 halves are equal. (Imagine that such division is possible for the input array and array size is even)
- gulusworld1989 January 13, 2014 in United States for Android| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersThere is a matrix which contains white cells , black cells and only one gray cell, need to go from (0,0) to (N-1, N-1) if Arra[N][N]
- jyotinder1.pec October 22, 2013 in United States for advance algorithm
constraints:
a. The path should cover only white cells and should go via grey cell.
b. The node once visited cannot be visited again.
White cells are represented by 0, black cells by 1 and grey cell by 2.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersYou are given a doubly linked list and an array of references to nodes on the linked list. How many "blocks" are there present in the linked list?
- Aasen May 27, 2013 in United States
A "block" is defined as a group of nodes on the list with references directed at them and adjacent to eachother.
For example
[node #0] -><-[node#1] -><-[node#2] -><-[node#3]
node[] nodes = {ref_to_node#0, ref_to_node#2, ref_to_node#3};
Is two blocks because the first block is at node #0.
Node #1 has no incomming reference. Node #2 and Node #3 have references are are adjacent so it's just one block.
Implement using JAVA: Hint: You can try using a HashMap.
Thanks.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 2of 2 votes
AnswersCalculate number of zeros in a given integer.
- test222 March 29, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Intern Bit Manipulation - 2of 2 votes
AnswersReverse the words in string eg. 'The Sky is Blue'. then print 'Blue is Sky The'.
- purva7 July 24, 2017 in United States| Report Duplicate | Flag | PURGE
Expedia Software Developer String Manipulation - 2of 2 votes
Answers"Given an array of strings, find the string which is made up of maximum number of other strings contained in the same array.
- mail.kshitij.jain October 10, 2013 in India
e.g. “rat”, ”cat”, “abc”, “xyz”, “abcxyz”, “ratcatabc”, “xyzcatratabc”
Answer: “xyzcatratabc”
“abcxyz” contains 2 other strings,
“ratcatabc” contains 3 other strings,
“xyzcatratabc” contains 4 other strings"| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersGiven a monotonically sorted 2D array, explain an algorithm to search for a given input element.
- maytas92@yahoo.com February 11, 2013 in United States
A monotonically sorted array is one in which each row and column has elements in ascending order.
E.g. [ 1 2 10; 4 6 11; 5 7 12;] and [1 2 5; 4 6 7; 10 12 13] are both monotonically sorted.| Report Duplicate | Flag | PURGE
IBM Software Engineer / Developer Algorithm - 2of 2 votes
Answersgiven preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?
- Raj February 16, 2017 in United States
@Anonymous Thanks for the reply!
Please try other use cases like, only single leaf node| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 2of 2 votes
AnswersMr. Kim has to deliver refrigerators to N customers. From the office, he is going to visit all the customers and then return to his home. Each location of the office, his home, and the customers is given in the form of integer coordinates (x,y) (0≤x≤100, 0≤y≤100) . The distance between two arbitrary locations (x1, y1) and (x2, y2) is computed by |x1-x2| + |y1-y2|, where |x| denotes the absolute value of x; for instance, |3|=|-3|=3. The locations of the office, his home, and the customers are all distinct. You should plan an optimal way to visit all the N customers and return to his among all the possibilities.
- Loser September 03, 2016 in India
You are given the locations of the office, Mr. Kim’s home, and the customers; the number of the customers is in the range of 5 to 10. Write a program that, starting at the office, finds a (the) shortest path visiting all the customers and returning to his home. Your program only have to report the distance of a (the) shortest path.
You don’t have to solve this problem efficiently. You could find an answer by looking up all the possible ways. If you can look up all the possibilities well, you will get a perfect score.
[Constraints]
5≤N≤10. Each location (x,y) is in a bounded grid, 0≤x≤100, 0≤y≤100, and x, y are integers.
[Input]
You are given 10 test cases. Each test case consists of two lines; the first line has N, the number of the customers, and the following line enumerates the locations of the office, Mr. Kim’s home, and the customers in sequence. Each location consists of the coordinates (x,y), which is reprensented by ‘x y’.
[Output]
Output the 10 answers in 10 lines. Each line outputs the distance of a (the) shortest path. Each line looks like ‘#x answer’ where x is the index of a test case. ‘#x’ and ‘answer’ are separated by a space.
[I/O Example]
Input (20 lines in total. In the first test case, the locations of the office and the home are (0, 0) and (100, 100) respectively, and the locations of the customers are (70, 40), (30, 10), (10, 5), (90, 70), (50, 20).)
5 ← Starting test case #1
0 0 100 100 70 40 30 10 10 5 90 70 50 20
6 ← Starting test case #2
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
10 ← Starting test case #3
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
...
Output (10 lines in total)
#1 200
#2 304
#3 366| Report Duplicate | Flag | PURGE
Samsung Software Engineer Algorithm - 2of 2 votes
Answersthere are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)
- srcnaks February 02, 2015 in -
Write two methods called "getNumber" and "requestNumber" as follows
Number getNumber();
boolean requestNumber(Number number);
getNumber method should find out a number that did not assigened than marks it as assiged and return that number.
requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.
design a data sturucture to keep those numbers and implement those methods| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Hash Table - 2of 2 votes
AnswersFind the 90th percentile of a stream of numbers between 1 and 10^6.
- addy October 16, 2014 in United States
Followup: What if there is not enough memory to store all numbers and no upper bound.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm