Algorithm Interview Questions
- 5of 5 votes
AnswersTree Game
- aonecode May 17, 2019 in United States
class TreeNode {
TreeNode parent; //parent node
TreeNode left; //left child
TreeNode right; //right child
}
Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.
The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.
Follow up: if player B takes the first hand instead, which node should he pick?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 0 votes
AnswersGiven a string where there are numbers and some numbers are repeated, e.g. 13413124...,
- Anonymous December 29, 2008
design a data structure for it and the data structure should store positions of each number.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 5of 0 votes
AnswersGive an efficient algorithm to solve this problem. Given "N" files as input, find the common text fragments that occurs in all the files in input and remove them from the files.
- Anonymous September 16, 2008
(A fragment is a piece of text that has at least 3 words)
E.g.
Input
=====
File1
------
It is snowing and I want to drive home.
File2.txt
----------
It is snowing and I want to go skiing.
File3.txt
----------
It is hot and I want to go swimming.
Output
=======
Out.File1.txt
---------------
It is snowing drive home.
Out.File2.txt
-----------------
It is snowing go skiing.
Out.File3.txt
----------------
It is hot go swimming.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 4of 14 votes
AnswersGiven two aligned sequences `a` and `b`. Write a function "findCommon", that finds the longest substring of the longer sequence that align to the smaller sequence in such a way that the alignment length (matching length) can be maximized. Sequences initially were of different lengths but the smaller one is padded with hyphen ('-') after alignment to make it equal to the longer sequence. The length of longer sequence is known in advance (m, which is same for the smaller padded sequence). The output is always the subsequence of the longer string.
- mary.kindall November 19, 2013 in United States
The total number of such operations to be done is in billions.
findCommon(a, b, m)
Example 1:
a = ------bixg--
b = xxxxxxbi-gzz
m = 12
output: big
Example 2:
a = xxxxxxbxigxx
b = ------b-ig--
m = 12
output = bxig
Example 3:
a = bigxxxxxxxxx
b = bi-x--------
m = 12
output = bigx| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 10 votes
AnswersSuppose we are given a set L of n line segments in the plane, where the endpoints of each
- polo November 01, 2014 in United States
segment lie on the unit circle x^2 + y^2 = 1, and all 2n endpoints are distinct. Describe
and analyze an algorithm to compute the largest subset of L in which no pair of segments
intersects.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 8 votes
AnswersDesign an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )
- Aashish June 27, 2012 in India
You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 8 votes
AnswersGiven a set top box:
- Guy January 18, 2014 in United States
a, b, c, d, e,
f, g, h, i, j,
k, l, m, n, o
p, q, r, s, t
u, v, w, x, y
z
Write code to give the character sequence given a word, For example, if the word is "CON", the function will print this:
Right//now we're at B
Right//now we're at C
OK//to select C
Down
DOwn
Right
Right
OK//to select O
Left//now at N
OK//to select N
note: Be careful when you're at Z. if you go to the right, you will get stuck.
Afterwards, the interviewer adds a space to the right of 'Z' to test the code.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 6 votes
Answersgiven an int array with no duplicate numbers, write a function to return number of ways to calculate a target number.
- cooldog March 15, 2013 in United States
example: given {2,4,6,8} Target = 12
2 + 4 + 6 = 12,
4 + 8 = 12,
6 + 8 - 2 = 12,
2 - 4 + 6 + 8 = 12,
return 4| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Software Engineer in Test - 4of 6 votes
AnswersYou have two integer arrays. Treat these arrays as if they were big numbers, with one digit in each slot. Perform addition on these two arrays and store the results in a new array.
- Aasen October 24, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 4of 6 votes
AnswersHow to find duplicates in an array
- shivam sharma January 06, 2014 in United States| Report Duplicate | Flag | PURGE
Algorithm - 4of 4 votes
AnswersIf [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn] , solution should be in-place
- Anonymous February 05, 2011| Report Duplicate | Flag | PURGE
Amazon Microsoft Developer Program Engineer Software Engineer / Developer Algorithm Arrays - 4of 4 votes
AnswersGiven a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles
- nikki December 31, 2018 in United States
Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 4of 4 votes
AnswersGiven a large string T (up to 10M characters) and a large input stream of strings S(up to 1M strings), find for each Si in S if it is a subsequence of T.
- PrincessMaja November 17, 2013 in United States
String Si is a subsequence of T iff some letters from T can be omitted to obtain Si.
Example:
T - abbebcd
Si - bbcd
return true
T - abbeced
Si - bbbced
return false| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 4of 4 votes
AnswersYou are given a large set of integers, which are not sorted. Figure out a method to retrieve the largest 1000 elements, in O(n) run time
- varunumesh77 March 12, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Intern Algorithm Data Structures - 4of 4 votes
AnswersYou are given a set of unique characters and a string.
- francisvm February 04, 2015 in United States
Find the smallest substring of the string containing all the characters in the set.
ex:
Set : [a, b, c]
String : "abbcbcba"
Result: "cba"| Report Duplicate | Flag | PURGE
Facebook Intern Algorithm - 4of 4 votes
AnswersGiven an unordered array of positive integers, create an algorithm that makes sure no group of integers of size bigger than M have the same integers.
- Fred_Castro January 22, 2014 in United States
Input: 2,1,1,1,3,4,4,4,5 M = 2
Output: 2,1,1,3,1,4,4,5,4| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 4 votes
AnswersRearrange characters in a string so that no character repeats twice.
- pcinterview October 10, 2015 in United States
Input: aaabc
Output: abaca
Input: aa
Output: No valid output
Input: aaaabc
Output: No valid output| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersGiven a polygon with N vertexes and N edges. There is an int number(could be negative) on every vertex and an operation in set(*,+) on every edge. Every time, we remove an edge E from the polygon, merge the two vertexes linked by the edge(V1,V2) to a new vertex with value: V1 op(E) V2. The last case would be two vertexes with two edges, the result is the bigger one.
- zilchistDeepblue January 15, 2013 in United States
Return the max result value can be gotten from a given polygon.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven a list of strings, return a list of lists of strings that groups all anagrams.
- tirelative December 13, 2014 in United States
Ex. given {trees, bike, cars, steer, arcs}
return { {cars, arcs}, {bike}, {trees, steer} }
m = # of words
n = length of longest word
I solved this in O(m * n * log n) time.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 4of 4 votes
AnswersTwo finite, strictly increasing, integer sequences are given. Any common integer between the two sequences constitute an intersection point. Take for example the following two sequences where intersection points are
- blackfever June 29, 2014 in India
printed in bold:
First= 3 5 7 9 20 25 30 40 55 56 57 60 62
Second= 1 4 7 11 14 25 44 47 55 57 100
You can ‘walk” over these two sequences in the following way:
1. You may start at the beginning of any of the two sequences. Now start moving forward.
2. At each intersection point, you have the choice of either continuing with the same sequence you’re currently on, or switching to the other sequence.
The objective is finding a path that produces the maximum sum of data you walked over. In the above example, the largest possible sum is 450 which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62
this is the same problem which I saw in SPOJ Problem Set| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 4of 4 votes
AnswersGiven a random generator rand(5) which generates numbers between 0 to 4. How do u generate numbers between 0 to 6, I.e. Implement rand(7).
- hulk April 16, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Brain Teasers - 4of 4 votes
AnswersGiven a current absolute path, e.g., "/usr/bin/mail", and a relative one, e.g, "../../../etc/xyz/../abc" return the absolute path created from the combination of the first two paths. In the example strings, the answer should be "/etc/abc".
- meh March 24, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 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 - 4of 4 votes
Answersgive an algorithm for finding duplicate parenthesis in a expression.
example :
- rahul May 02, 2014 in United States(( a + b ) + (( c + d )))
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Stacks - 4of 4 votes
AnswersReplace element of an Array with nearest bigger number at right side of the Array in O(n)
- SachinG2 October 23, 2013 in India
For example if the input Array is
7, 5, 6, 3, 4, 1, 2, 9, 11
output array should be
9, 6, 9, 4, 9, 2, 9, 11, 11| Report Duplicate | Flag | PURGE
PayPal Member Technical Staff Algorithm - 4of 4 votes
AnswersReturn the length of longest possible chunked palindrome string.
- AlgoBaba December 08, 2016 in United States
Examples :
Input : VOLVO
Output : 3
Explanation :
(VO)L(VO)
Input : merchant
Output : 1
Explanation : No chunks possible.
Input :
ghiabcdefhelloadamhelloabcdefghi
Output : 7
Explanation :
(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersWe are given a set of integers with repeated occurences of elements. For Example, S={1,2,2}.
- sc.shobhit September 14, 2013 in India
We need to print the power set of S ensuring that the repeated elements of the power set are printed only once.
For the above S, the power set will be {NULL, {1}, {2}, {2}, {1,2}, {1,2}, {2,2}, {1,2,2}}. So, as per the question requirements, we need to print {NULL, {1}, {2}, {1,2}, {2,2}, {1,2,2}}| Report Duplicate | Flag | PURGE
Facebook Intern Algorithm Coding Trees and Graphs - 4of 4 votes
AnswersGiven the relative positions (S, W, N, E, SW, NW, SE, NE) of some pairs of points on a 2D plane, determine whether it is possible. No two points have the same coordinates.
- united November 02, 2014 in United States
e.g., if the input is "p1 SE p2, p2 SE p3, p3 SE p1", output "impossible".| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersImplement a method called printNonComments() which prints out a extract of text with comments removed.
- Ash June 30, 2014 in UK
For example, the input:
hello /* this is a
multi line comment */ all
Should produce:
hello
all
You have access to a method called getNextLine() which returns the next line in the input string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm