Algorithm Interview Questions
- 2of 2 votes
AnswersYou have a function rand5(). This function returns numbers between 1 and 5 randomly with equal probability. Implement a function rand7() which makes use of rand5 to return a number between 1 and 7 randomly with equal probability.
- reddygokul.i7 February 27, 2015 in India| Report Duplicate | Flag | PURGE
Intern Algorithm Arrays Java Python - 2of 2 votes
Answersyou have given 2n+1 numbers in which 2n numbers are repeated means every number is having duplicate value.find that non repeating number in constant space and o(n) time.i told him using XOR.
- time February 03, 2012 in India
then he gave me 2n+2 numbers in which 2n numbers are repeating like above now you have 2 different number.find both number in constant space and o(n) time.(f2f 4th round)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
Answers0 1 ?
- .netDecoder May 08, 2015 in United States
? wildcard for 0 or 1
"01?"
010 011
Example:
01?0?
Will produce
01000
01100
01001
01101| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
Answersint sum = 0;
- nirupam.astro January 04, 2014 in India
for (int i = 0; i < m; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < l; k++)
sum++;
what will be the value of sum?| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersSort an array which only has 0's and 1's. Do not use count sort.
- CodeNameEagle May 10, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm Arrays - 2of 2 votes
AnswersGiven an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO], please reconstruct the itinerary in order,
- blah_blah May 18, 2015 in United States
for example: [ CDG, MUC, LHR, SFO, SJC ].
//tickets can be represented as nodes| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven an array of values, design and code an algorithm that returns whether there are two duplicates within k indices of each other? k indices and within plus or minus l (value) of each other? Do all, even the latter, in O(n) running time and O(k) space.
- fbrubacher May 19, 2013 in United States for Engineer| Report Duplicate | Flag | PURGE
Palantir Technology Software Engineer / Developer Algorithm - 2of 2 votes
AnswersU have a number, don't know how long it is, do not know how many digits, don't know when number ends, do not know which is the last number. There is a function to increment the number by 1, but function can take only stream of digits and not the complete number e.g if you have 878999 as a number, you could input this number into the function only as single digit e.g 8,7,8,9,9,9. The output should be the whole number incremented by 1 i.e 879000, remember only single digits you can send to function as input. You can use any data structure, but need to tell why you are using that particular data structure. No need to worry about Time complexity.
- algoram November 29, 2012 in United States for Site Reliability Engineering Team
Kindly, suggest how to approach this problem ?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersImplement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
- abhishek January 01, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};
- emb October 05, 2015 in United States
Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, k-th order statistic on slice [a:b] of arr.
E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it - get [0,1,5] and take k-th element, that is - 5.
Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersGiven nxn boolean matrix (0's and 1's) .
- thebiker925 September 11, 2013 in United States
Find out whether there exist a row i and column j such that
1) all elemets of row i are zero's and
2) all elements of column j are 1's and
3)(i,j)th entry of the matrix can be either 0 or 1
Find out such a i and j exist or not .
complexity :O(n)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.
- Anonymous November 21, 2011 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven two arrays/Lists (choose whatever you want to) with sorted and non intersecting intervals. Merge them to get a new sorted non intersecting array/list.
- HumbleLearner February 12, 2016 in United States
Eg:
Given:
Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];
Wanted:
Arr3 = [3-25, 40-47, 58-73];| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 2of 2 votes
AnswersGiven a list/array of names(String) sort them such that each name is followed by a name which starts with the last character of the previous name.
- anurag.11feb January 07, 2014 in Netherlands
# input
[
Luis
Hector
Selena
Emmanuel
Amish
]
# output:
[
Emmanuel
Luis
Selena
Amish
Hector
]| Report Duplicate | Flag | PURGE
Booking.com Developer Program Engineer Algorithm - 2of 2 votes
Answersgiven a vector of integers, v[i] represent the stock price on day i. Now you may do at most K transactions. you must sell your stock before you buy it again and that means you can NOT have two stocks at the same time. write a program to find max profit you can get.
- rjrush December 17, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersWrite code to sum 2 integer but u cant use a+b method, you have to use either ++ or --. How you will handle negative numbers.
- newbee October 10, 2014 in United States| Report Duplicate | Flag | PURGE
Apple Software Engineer in Test Algorithm - 2of 2 votes
AnswersAssume I have a log file with list of people with their arrival and departure time at an event that happened in the past.
- Bevan March 02, 2013 in United States
My task is to find out the maximum number of people present at any time during the entire event? I am not given query time.
ai = Arrival time of person i
di = Departure time of person i
I have a list of pairs like (a1,d1), (a2,d2), (a3,d3).... (an,dn)... It's not in a database.
I apologize as I cannot edit my previous question. I think it had a incomplete description.
Please let me know if you guys still need clarification. Thanks| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersTech Screening
- sonesh July 02, 2015 in United States
Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry.
Interviewer was expecting O(N) solution for N asks.
Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks.
and integers are not given in a array, every time only one integer will be passed as input to your method.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Data Structures - 2of 2 votes
Answershow to implement a queue using one integer. this should store value 0 to 9. example suppose queue has first value 2 then insert 4 then 6 so it should look like 246. first value should be popped as 2. then it should be 46. program should support 0 in all the levels also. example queue should handle like 01235 also, 0 as first value in queue. remember 0 just to use integer, nothing else as data storage.
- Justin January 13, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
Answers/**
- duskan February 22, 2014 in United States
* Returns a^b, as the standard mathematical exponentiation function
*/
public double pow(double a, int b) {}
Interviewer looking for log(n) solution, right on first attempt.| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm - 2of 2 votes
Answersgiven y bytes and you can transfer only x bytes at once..give a mathematical expression having only + - / * which gives the number of iterations to copy y bytes. ( dont try giving modulo operator answers )
- rahulbmv October 25, 2012 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven N pair of parenthesis. Write an algorithm which would print out all possible permutations possible with those parenthesis given that parenthesis are in correct order (i.e. every open parenthesis is matched with closed parenthesis)
- shadykiller March 06, 2012 in India
For .e.g. .. N =3 should give:
()()()
(()())
()(())
(())()
((()))| Report Duplicate | Flag | PURGE
Flipkart Algorithm - 2of 2 votes
AnswersGiven an array of integers, return true if there're 3 numbers adding up to zero (repetitions are allowed)
- fatenuller January 09, 2015 in United States
{10, -2, -1, 3} -> true
{10, -2, 1} -> true -2 + 1 +1 =0| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 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
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
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
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
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
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