Algorithm Interview Questions
- 7of 7 votes
AnswersGiven a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.
- pennepalli May 30, 2014 in United States
Example:
Input : a?b?c?
Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm C# C++ Java - 7of 7 votes
AnswersGiven a very long list of URLs, find the first URL which is unique ( occurred exactly once ).
- AK December 06, 2011 in India
I gave a O(n) extra space and O(2n) time solution, but he was expecting O(n) time, one traversal.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Large Scale Computing - 7of 7 votes
AnswersDetermine minimum sequence of adjacent values in the input parameter array that is greater than input parameter sum.
- bootcat April 20, 2014 in United States
Eg
Array 2,1,1,4,3,6. and Sum is 8
Answer is 2, because 3,6 is minimum sequence greater than 8.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 7of 7 votes
AnswersYou are given a list of word. Find if two words can be joined to-gather to form a palindrome. eg Consider a list {bat, tab, cat} Then bat and tab can be joined to gather to form a palindrome.
- um01 May 14, 2015 in United States
Expecting a O(nk) solution where n = number of works and k is length
There can be multiple pairs| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 7of 7 votes
AnswersGiven an array of integers.
- Victor November 27, 2014 in United States
Move all non-zero elements to the left of all zero elements.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 7of 7 votes
AnswersGiven a regular expression with characters a-z, ' * ', ' . '
- kevin October 13, 2013 in United States
the task was to find if that string could match another string with characters from: a-z
where ' * ' can delete the character before it, and ' . ' could match whatever character. ' * ' always appear after a a-z character.
Example:
isMatch("a*", "") = true;
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 7of 7 votes
AnswersFind missing element in the A.P.
- poojaarora014 December 22, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm - 7of 7 votes
AnswersGiven a binary N X N matrix, return the size of the largest '+' of ones.
- zaxven August 19, 2015 in United States
input:
0 0 0 0
1 1 0 1
1 1 1 1
1 1 1 0
output:
5
(binary search is not allowed)| Report Duplicate | Flag | PURGE
Google Algorithm - 7of 7 votes
AnswersYou need to develop the game Snake. What data structures will you use? Code your solution.
- GeorgyBoy December 30, 2013 in Israel| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Coding Java Problem Solving - 7of 7 votes
AnswersCount number of strings of length N with following properties:
- oaashifo April 08, 2019 in India for India
A. Consists of char 'A' and 'B' only.
B. There is atleast one occurrence of 3 consecutive Bs.
Input: Only line having integer N.
Output: Number of string with given properties. As then number can be very large print it with modulo 10^9+7.
Sample Input 1:
3
Sample Input 2:
1
Explanation: Only possible string "BBB"| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 7of 7 votes
AnswersFacebook Senior Engineer On-site 2017
- aonecoding April 17, 2017 in United States
1st Round
Question 1: Binary tree to doubly linked list.
Question 2: Read 4 (Given the read4 API, read an entire file)
2nd Round
Culture fit. No coding.
3rd Round
Question: System Design POI (Point of Interest. Given a point, find things within a radius).
Lunch
4th Round
Question 1: Decode way
Question 2: Random max index
5th Round
Question: System design + component-wise design on download manager| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 6of 12 votes
AnswersGiven a list of integers, find out the biggest interval that has all its members in the given list. e.g. given list 1, 7, 4, 6, 3, 10, 2 then answer would be [1, 4]. Develop algorithm and write code for this
- prongs July 08, 2013 in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm Arrays C++ Coding - 6of 8 votes
AnswersGiven a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.
- talktomenow July 14, 2014 in United States
ex:
1 5 9
2 3 8
4 6 7
should print
6 7 8 9| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 6of 8 votes
AnswersGiven an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.
- dreamchaser1984 March 25, 2015 in United States
For Ex:
Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]
n -> 2
Out put -> [100, 0] or [100, 2]
Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 6of 6 votes
AnswersGiven an array of ages (integers) sorted lowest to highest, output the number of occurrences for each age.
- streamer December 31, 2014 in United States
For instance:
[8,8,8,9,9,11,15,16,16,16]
should output something like:
8: 3
9: 2
11: 1
15: 1
16: 3
This should be done in less than O(n).| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 6of 6 votes
AnswersWrite a function for retrieving the total number of substring palindromes.
- Andrew November 04, 2013 in United States
For example the input is 'abba' then the possible palindromes= a, b, b, a, bb, abba
So the result is 6.
Updated at 11/11/2013:
After the interview I got know that the O(n^3) solution is not enough to go to the next round. It would have been better to know before starting implementing the solution unnecessarily ...| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 6of 6 votes
AnswersIn a certain language which has same alphabets as in english language (ie. a-z), but the order of the alphabets is different (for eg 's' is the first character, 'g' is second, and likewise). Given a dictionary of this new language (which has words arranged according to new alphabetical order), FInd out the order of alphabets in this language.
- sgarg June 09, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Google SDE1 Software Engineer / Developer SDE-2 Algorithm - 6of 6 votes
AnswersYou are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.
Find number of 0-s in the given matrix.
Example:0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4
Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).
- emb June 26, 2016 in United States
Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N-1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).
Nice job, @gen-y-s :)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 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 - 6of 6 votes
AnswersYou visited a list of places recently, but you do not remember the
- UserOne November 05, 2013 in United States
order in which you visited them. You have with you the airplane
tickets that you used for travelling. Each ticket contains just the
start location and the end location. Can you reconstruct your journey?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 6of 6 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
Without modifying original structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 6of 6 votes
AnswersGiven an array such that every next element differs from the previous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The interviewer mentioned one more condition that the min or max should be non-edge elements of the array
- xyz March 30, 2015 in United States
Example: 1 2 3 4 5 4 3 2 1 -> Local max is 5
1 2 3 4 5 -> No local max or min exists
5 4 3 2 1 -> No local max or min exists| Report Duplicate | Flag | PURGE
Facebook Software Developer Algorithm - 6of 6 votes
AnswersFB On-site March
- aonecoding April 21, 2018 in United States
Q: Find number of Islands.
XXXOO
OOOXX
XXOOX
Return 3 islands.
1 1 1OO
OOO2 2
3 3OO 2
Followup: If the board is too big to fit in memory, how to get the number?| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 6of 6 votes
AnswersWrite a function that accepts two or more strings and returns the longest common substring in all of them.
- Barry Fruitman March 20, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 6of 6 votes
Answers/**
- aonecoding January 27, 2017 in United States
Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.
eg: coins(10, 15, 55)
print:
10
15
20
25
30
.
.
.
1000
*/| Report Duplicate | Flag | PURGE
Facebook Software Developer Algorithm - 6of 6 votes
AnswersQ: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
- aonecoding January 27, 2017 in United States
and then another series [A != C, D != H, ..., F != A ]
Check whether the equations combined is valid.
For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 6of 6 votes
Answers5th Round
- aonecoding April 13, 2017 in United States
Open-ended question What happens when you type a url in the browser and hit enter?
Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 6of 6 votes
AnswersGiven a non-directed, strongly connected graph where the node values are letters of the alphabet, write an algorithm that prints out all possible permutations of strings. What is this called?
- william.brandon.lee83 January 18, 2016 in United States
For example:
V = A,B,C
Printout
ABC
ACB
BAC
BCA
CAB
CBA
BAC etc.| Report Duplicate | Flag | PURGE
IBM Software Engineer / Developer Algorithm - 6of 6 votes
AnswersYou are given a 2d rectangular array of positive integers representing the height map of a continent. The "Pacific ocean" touches the left and top edges of the array and the "Atlantic ocean" touches the right and bottom edges.
- JD March 14, 2015 in United States
- Find the "continental divide". That is, the list of grid points where water can flow either to the Pacific or the Atlantic.
Water can only flow from a cell to another one with height equal or lower.
Example:
Pacific ~ ~ ~ ~ ~ |__
~ 1 2 2 3 (5) ~
~ 3 2 3 (4)(4) ~
~ 2 4 (5) 3 1 ~
~ (6)(7) 1 4 5 ~
__ (5) 1 1 2 4 ~
|~ ~ ~ ~ ~ Atlantic
The answer would be the list containing the coordinates of all circled cells:
[(4,0), (3,1), (4,1), (2,2), (0,3), (1,3), (0,4)]| Report Duplicate | Flag | PURGE
Facebook Algorithm