Algorithm Interview Questions
- 4of 4 votes
AnswersQuestion: Two players A and B are playing a game. Pots of gold, each with
- kiran.sanni October 28, 2014 in United States
varying number of coins are placed in a single line. The rules of the game are:
1) Players play turn by turn.
2) On each turn a player can pick a pot of gold from either end of the line. He
gets all the gold in that pot. The next pot of gold on that end is now available
for picking.
What is the maximum number of gold can the first player get ?| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 4of 4 votes
AnswersWrite algorithm for java grep command for word matching in the following context.Given a file containing n words.Given a word w and a number k.Find k words in the file occuring before occurence of w.Assume that the average word size is m in the file
- prashant.tah September 12, 2017 in India
eg.
aaa
bbb
ccc
booking
alpha
beta
gamma
for k=3 and w = booking
the output should be [aaa,bbb,ccc,booking]
similarly for k =2 and w = beta
output should be [booking,alpha,beta]
Assume that the file size can grow very large
and try to get solution with space complexity lesser than O(n)
I suggessted solution for iterating through file until the word w is found and maintaiining a queue of size K
The time complexity of my solution was O(nm)
and space complexity was O(k) .Any answers to improve the time and space complexity
Apparently they were looking for a better implementation of grep| Report Duplicate | Flag | PURGE
Booking.com Software Developer Algorithm - 4of 4 votes
AnswersWrite a program to process the matrix. If an element is 0 at ith row and jth column, then make the whole ith row and jth column to 0.
- codealtecdown September 17, 2015 in United States
Constraints:
Space complexity should be O(1)
Time complexity - Only single pass is allowed. Note that single pass is not O(n). This is single pass : An element will read and written only ones.
Edit:
Recursion is not allowed since it is O(n) space on stack| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 4of 4 votes
AnswersGiven an array of integer nos. All numbers are distinct.
- pavel.em May 22, 2015 in United States
WAP to find the two longest non-intersecting continuous subarrays
of equal size s.t. *all* elements of one of them are smaller than that of the other subarray:
a[i..i + k - 1] and a[j..j+k-1] where i + k <= j
s.t. a[i..i + k - 1] < a[j..j+k-1] or a[i..i + k - 1] > a[j..j+k-1]
and k is maximal
Example: a = {1,2,3, 7, 9, 8} then we have: {1, 2, 3} and {7, 9, 8}
a = {6, 5, 4, 1, 3, 7} then we have:
{6, 5} and {4, 1} or
{6, 5} and {1, 3} or
{5, 4} and {1, 3} ...| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 4of 4 votes
AnswersGiven the following hashmap for numeric to alpha translation of a telephone keypad:
- valheru April 23, 2014 in United States
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
Write a method that takes a phone number as input and returns all possible letter combinations for that phone number.| Report Duplicate | Flag | PURGE
Facebook iOS Developer Algorithm - 4of 4 votes
AnswersGiven a string return the longest palindrome that can be constructed by removing or shuffling characters.
- enkadi13 July 22, 2016 in United States
Example:
'aha' -> 'aha'
'ttaatta' -> ' ttaaatt'
'abc' -> 'a' or 'b' or 'c'
'gggaaa' -> 'gaaag' or 'aggga'
Note if there are multiple correct answers you only need to return 1 palindrome.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersYou are given two arrays of length M and N having elements in range 0-9.Your task is to create maximum number of length K from elements of these two arrays such that relative order of elements is same in the final number as in the array, they are taken from i.e. If two elements a,b are taken from array1 and and a comes before b in array1 so in the final number a should come before b (Relative order kept same) .
- Rahul Sharma November 18, 2015 in United States
Example: N=4 and M =6
Array1 = { 3 , 4 , 6,5}
Array2 ={9,1,2,5,8,3}
Suppose K = 5, then number will be {9,8,6,5,3}
You can see {9,8,3} are taken from array2 in the same order as they are in Array2. Similarly {6,5} are taken from Array1 in the same order and number 98653 is maximum possible number.| Report Duplicate | Flag | PURGE
Google Research Scientist Algorithm - 4of 4 votes
AnswersWrite code to generate all possible case combinations of a given lower-cased string. (e.g.
- An Enthusiast March 25, 2014 in United States"0ab" -> ["0ab", "0aB", "0Ab", "0AB"])
| Report Duplicate | Flag | PURGE
Yelp Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible
- geekofthegeeks November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersWAP a program to find a contineous subset whose sum is divisible by 7. We are given a array of number (negative+positive).
- yogi.rulzz October 26, 2013 in India
calculate the complexity of your algorithm| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|+|b-c| +|c-a| is minimum.
- Rahul Sharma September 16, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 4of 4 votes
AnswersCar parking problem. An array given represents actual order of cars need to be parked. Like for example order is 4,6,5,1,7,3,2,empty. If cars are parked in some order like empty,1,2,3,7,6,4,2. Some person needs to get them into correct order, list out all instructions to the person to get in correct order with least number of swaps.
- hulk April 16, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 4of 4 votes
AnswersGiven a singly linked list: 1->2->3->4->5
- rainnyforeverluv December 09, 2016 in United States
Change it to 1->5->2->4->3 using O(1) space| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 4of 4 votes
Answersgiven an 2D matrix M, is filled either using X or O, you need to find the region which is filled by O and surrounded by X
- smit February 14, 2014 in India
and fill it with X.
example 1:
X X X X X
X X O O X
X X O O X
O X X X X
Answer :
X X X X X
X X X X X
X X X X X
O X X X X
example 2:
X X X X X
X X O O X
X X O O O
O X X X X
answer 2:
X X X X X
X X O O X
X X O O O
O X X X X| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersThis is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution.
- satish1987 August 12, 2015 in United States
Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property.
For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further.
Input:
A Single number N for which we want to produce the sequence.
Output:
A space separated list of sequence or NA if there is no possible sequence.
Example Input:
3
Example Output:
2 3 1 2 1 3
Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 4of 4 votes
AnswersGiven two strings, find that the if the letters in both the strings are same? i.e. can we be able to make string2 out of string1 by shuffling the words and vice versa.
- saikrishna chunchu April 17, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 4of 4 votes
Answersinput - 2D array of characters and a text pattern. program to find if pattern is present in array or not. a cell can't be used twice for pattern matching. return 1 if true or 0 otherwise.
- pop_front September 11, 2013 in United States
eg :
Matrix
{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i', 't'}
and search for "microsoft"| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 4of 4 votes
AnswersGiven a matrix with 1's and 0's, a rectangle can be made with 1's. What is the maximum area of the rectangle.
- bharadwaj.tanikella23 March 05, 2014 in United States
00010
11100
11110
11000
11010 In this test case the result needs to be 8.
How:
00010 00010
11100 11 100
11110 11 110
11000 11 000
11010 11 010
If you see above the 11's are used from the first two columns and last four rows making the area or count of 1's to be 8.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 4 votes
Answers# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
- aonecoding February 08, 2017 in United States
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
# > 11| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 4of 4 votes
AnswersPrints all unique subsets of the string.
- mabodx February 11, 2014 in United States
Given a string write a function which prints all the subsets of the string. Now make the function to return only unique solutions.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 4of 4 votes
AnswersYou have a number L and N distinct integers between 1 and 100.
- BingBang February 10, 2013 in United States
You can use each number as many times as you want. Print the minimum subset size of these numbers which add up to L and how many ways are there to choose them (the order does not matter).
0<L,N<=100
examples:
input1:
L=7 N=6
2 1 5 4 3 6
output1:
2 3 (minimum 2 numbers, 3 ways to choose: 1 and 6, 2 and 5, or 2 and 4
input2:
L=7 N=3
4 2 6
output2:
0 0 (can't get 7 from 4,2 or 6)
input3:
L=14 N=3
8 7 1
output3:
2 1 (we choose 7 twice)
input4:
L=100 N=3
2 97 1
output4:
3 1| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 4of 4 votes
AnswersYou have given height array of array. Generate the original array.
- sandeepmnit35 November 20, 2017 in India
Input: [6,3,0,2,2,0,0]
Output : [ 1,5,7,3,2,6,4]
A[i] value in input array is the number of greater element on right side.| Report Duplicate | Flag | PURGE
Goldman Sachs Developer Program Engineer Algorithm - 4of 4 votes
AnswersLets say someone accidentally deleted all the whitespaces from a sentence. Write a program to reconstruct the sentence from that stripped out string. Assume you have access to a dictionary function that returns if a given string is a valid word or not.
- NS August 23, 2016 in United States
Example input: thisisavalidsentence
Output: this is a valid sentence
If multiple solutions are possible, any one valid solution should be given. Assume there is always a valid solution. No invalid input will be given.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 4of 4 votes
AnswersGiven an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven a big rectangular plot of land that has rectangular or square sized buildings (all sides of every building are parallel to the big rectangular plot)... find the location and dimensions of the largest square that can be built in this rectangular plot
- JSDUDE May 18, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 4of 4 votes
AnswersGiven an array of integers and a number. WAP to find the pairs which sum of upto given number.
- Nitin Gupta May 15, 2015 in India for Cloud & Enterprise team
I solved it. Then he asked about writing test cases for this function.
I wrote below test cases
1.) All the elements should be number.
2.) Length of array should not be 0.
3.) Array itself should not be null.
4.) Given number, arrayLength can be represented by 32bits or 64 bits.
5.) number should not be negative.
6.) Input does not has pair, It should return false
7.) Input has pair, It should return true
8.) Input has all negative values and pair exists, then function should return true
9.) Input has all negative values and pair does not exists, function should return false
He told that he is looking for more test cases. Can you guys think of some more complex test cases.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm Arrays C++ Data Structures - 4of 4 votes
AnswersYou have an array of numbers. You have to give the range in which each number is the maximum element. For Example, If array is 1, 5, 4, 3, 6 The output would be
- neer.1304 July 12, 2020 in United States
1 [1, 1]
5 [1, 4]
4 [3, 4]
3 [4, 4]
6 [1, 5]| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 4of 4 votes
AnswersYou have rand2() function which returns 0 or 1 with equal probability. You should implement rand3() using rand2().
- nfokin June 20, 2016 in Russia| Report Duplicate | Flag | PURGE
Yandex Software Engineer Algorithm - 4of 4 votes
AnswersAll jumbled numbers of n digits in max (worst case) O(n) and min (avg case) O(log n) time.
- mani0119 October 08, 2017 in India
A number is a jumbled number if the _absolute_ difference between adjacent digits is <=1.
For an input n=3
output should be
100
101
110
111
121
122
...
and so on.
The problem is similar to the one listed here https://www.careercup.com/question?id=5729332770111488
But this problem also has a O(n or log n) limitation and the solutions listed in the above mentioned problem at the time of posting this question, do not satisfy the criteria
PS: 001 is not a 3 digit number.
210 is absolutely fine as the absolute difference between adjacent digits is <=1.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm