Algorithm Interview Questions
- 3of 3 votes
AnswersGiven two unsorted integer arrays A & B of unequal length.
- vikas.singh.nitj December 05, 2013 in India
Find an element from A(say 'X') and another element from B(say 'Y') such that |X-Y| is minimum.
Note: A & B can contain positive/negative numbers.
How can you find this without sorting both arrays?
How can you find this by sorting both arrays?| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 3of 3 votes
AnswersGiven a string, you need to find super string by word match. i.e. all words in the input string has to occure in any order in output string.
- zc51 March 29, 2013 in India
e.g. given data set:
"string search"
"java string search"
"manual c++ string search equals"
"java search code"
"c++ java code search"
...
input: "java search"
output:
1) "java string search"
2) "java search code"
3) "c++ java code search"
input: "c++ search"
output:
1) "manual c++ string search equals"
2) "c++ java code search"
There are millions of records in given data set and you need to process few million as input.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Mining - 3of 3 votes
AnswersGiven a sorted array, find all the numbers that occur more than n/4 times.
- alisonlee659 March 24, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven list of pounds, the pounds that can be measured using a balance should be displayed.
- premkumar1989.ss March 13, 2013 in India for Dev
For Ex: 100,250
The output will be 100,250,150
The number of pounds which will be given in input might vary. Can someone please help with an algorithm for this?| Report Duplicate | Flag | PURGE
Kpro Solutions Analyst Algorithm - 3of 3 votes
AnswersGiven an array of object A, and an array of object B. All A's have
- hao.liu0708 October 30, 2014 in United States
different sizes, and all B's have different sizes. Any object A is of the
same size as exactly one object B. We have a function f(A, B) to compare the
size of one A and one B. But we cannot compare between two A's or two B's.
Give an algorithm to match each A with each B.| Report Duplicate | Flag | PURGE
Google Software Development Manager Algorithm - 3of 3 votes
AnswersGiven 'n' circles (each defined by center and radius)
- sheva November 12, 2016 in United States
Write an algorithm to detect if circles intersect with any other circle in the same plane
Better than O(n^2) complexity| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersLet's say there is a double square number X, which can be expressed as the sum of two perfect squares, for example, 10 is double square because 10 = 3^2 + 1^2
- baudday November 17, 2014 in United States for Emerging Markets
Determine the number of ways which it can be written as the sum of two squares| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersA standard chess knight (it moves in its standard way i.e. L shaped OR 2.5 moves) is sitting at the position a1 on an N x N chess board. What is the minimum number of moves it will take to reach the diagonally opposite corner?
- Saurabh Singhal August 17, 2013 in India
P.S. - If it were a 8 x 8 chess board, the final destination for the knight would be h8| Report Duplicate | Flag | PURGE
Goldman Sachs Intern Algorithm Coding Data Structures Trees and Graphs - 3of 3 votes
AnswersTask schedule: given a sequence of task like A B C(means 3 different tasks), and a coldtime, which means you need to wait for that much time to start next [same] task. Now----
- songty11 January 27, 2016 in United States
Input: string, n
Output: the best task-finishing sequence.
eg. input: AAABBB, 2
Output: AB_AB_AB
( "_" represents do nothing and wait)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 3of 3 votes
AnswersGiven a matrix containing 0 and 1. Consider 1 as 'Land' and 0 as 'Water'. Find out the number of 'Islands' in the matrix. That is, set of all adjacent 1 will make up for an island.
- prajakta mahamuni July 17, 2015 in India
For example:
[ 0 1 1 0 1 ]
[ 1 1 1 0 0 ]
[ 0 0 0 1 1 ]
[ 1 0 0 1 0 ]
This problem has 4 islands. ( consider set of 1s, vertically, horizontally and diagonally ).| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 3of 3 votes
AnswersI was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:
- Jaysun October 26, 2019 in United States
There's a list of (x,y) points and a method getCircle with the following signature:
/**
* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference
* or it returns null if no such circle is possible.
*/
Circle getCircle(point1, point2, point3);
getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.
The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 3of 3 votes
AnswersGiven a linked list consisting of String in each Node . Given just a pointer to the head Node find whether the resultant String formed by combining all the Nodes of the linked list is a palindrome or not in O(1) space and O(n) time.
- neer.1304 November 29, 2015 in United States
eg – Consider this linked List structure
“aba” -> “cd” -> “efe” -> “d” -> “caba”
Hence this structure is palindrome .| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 3of 3 votes
AnswersRound4
- aonecoding August 09, 2017 in United States
Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}.
Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>
- wtcupup2017 December 08, 2016 in United States-AAA -BBB -CCC -DDD -EEE
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven 4 teams and 3 gamedays, create an algorithm such that each team plays another team every gameday and by the end of the 3 game days each team should have played one game with every other team.
- popeye123 January 03, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm Problem Solving - 3of 3 votes
AnswersGiven a string and a dictionary. Break the string into meaningful words.
- RXH February 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
Answersvery large bytestream (PB)
- Yashwanth January 08, 2013 in United States for Youtube
synchronization algorithm
given:
unsigned char read_byte(); ← side effect that it advances a byte pointer in the stream
write:
unsigned char read_sync_byte(); ← may result in >1 calls to read_byte()
remove byte '03' from the stream if the stream is in pattern 00 00 03
Example:
read_byte():
00 0f 42 17 00 00 03 74 00 00 00 00 14 ...
read_sync_byte():
00 0f 42 17 00 00 74 00 00 00 00 14 ...| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a staircase that has 'n' step, and you climb the staircase by jumping over the steps. You can cover at max of 'k' steps in a single jump. List all the possible sequence of jumps you could take to climb the staircase.
- NEO December 16, 2014 in India
input:
n=4, k=2
output:
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm - 3of 3 votes
AnswersGiven a board made of 2 x n squares, and boards made of 2 x 1 squares, write a function that will calculate the number of possible ways to arrange the 2 x 1 boards on the 2 x n board, in a way that will fill it completely.
- GeorgyBoy December 30, 2013 in Israel
(Asked to refine the solution to be more efficient)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Coding Problem Solving - 3of 3 votes
AnswersGiven a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.
- md.lisul.islam November 22, 2017 in United States
[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersWrite a function to label connected components (using 4-connected neighbors) in a binary image.
- davydany August 01, 2014 in United States
You may use any language or data structures, but you may not use any existing APIs/libraries to find the components.
Example:
Input image
0 0 0 0 0 1 1 0 0 0
1 1 0 0 1 1 0 0 0 0
1 1 1 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0
Output Image
0 0 0 0 0 1 1 0 0 0
2 2 0 0 1 1 0 0 0 0
2 2 2 0 0 1 1 0 0 0
0 0 0 3 3 0 0 0 0 0| Report Duplicate | Flag | PURGE
Amazon Research Scientist Algorithm - 3of 3 votes
AnswersGiven an array of 1 billion numbers with just a few 100 missing, find all the missing numbers. you have only enough memory to store only 10k elements
- PS October 07, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 3of 3 votes
AnswersStarting at the 0 (zero) index, you need to "jump" through a one-dimensional array (zero based index) of true/false values. True is a place you can land on (if desired) and false is a place you must jump over (cannot land on). The array can be very very long.
- intervyou May 25, 2014 in United States
Your "velocity" indicates how many spots (or array indexes) you advance with every jump. For example, if you have a velocity of 2 and are currently at index 4, after the jump, you will be at index 6. Before each jump you can increase your velocity by 1, decrease your velocity by 1, or keep the same velocity. You can only go forwards.
You start at index 0 (zero), with a velocity of 1. This means that for the very first jump, you can keep the same velocity and move to index 1, or increase velocity by 1 (to a velocity of 2) to move to index 2. On this first jump, you can't decrease your velocity as that would make your velocity 0 (zero) and you wouldn't move. Now that you've jumped, you can again increase, decrease, or keep your velocity the same, then jump again.
As an example, let's say you increased your velocity to 2 and jumped. You're now at index 2 with a velocity of 2. You can:
1) decrease your velocity to 1 and jump to index 3.
2) keep your velocity at 2 and jump to index 4.
3) increase your velocity to 3 and jump to index 5.
Remember, you can only and on an index if it's "true". You are successful if you can get past the last index. Implement a function to determine if the rabbit can make it across given the field (array).
Here is a field that the rabbit cannot cross:
$field = array(true, true, false, true, false, true, false, false, false, true);
Here is a field that the field can cross:
$field = array(true, true, false, true, false, true, true, false, false, true, false);| Report Duplicate | Flag | PURGE
Algorithm - 3of 3 votes
AnswersGiven two sorted arrays find the element which would be N-th in their merged and sorted combination.
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersFind whether string S is periodic.
- aonecoding January 20, 2018 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
follow up:
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven the root of a Binary Tree along with two integer values. Assume that both integers are present in the tree.
- teli.vaibhav October 30, 2016 in United States
Find the LCA (Least Common Ancestor) of the two nodes with values of the given integers.
2 pass solution is easy. You must solve this in a single pass.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 3of 3 votes
AnswersImagine a man reading a book.
- zr.roman November 16, 2015 in Russia
He can perform only 2 possible actions of reading:
1) read a page in a minute (careful reading),
2) read two pages in a minute (look through).
Nothing else is permitted.
Calculate the number of all possible combinations of book reading ways with given number of pages.
Example: given 3 pages.
Answer is 3 combinations, as follows:
1st: Careful reading (1) - careful reading (1) - careful reading (1),
2nd: Careful reading (1) - look through (2),
3rd: Look through (2) - careful reading (1).| Report Duplicate | Flag | PURGE
SDE-2 Algorithm - 3of 3 votes
AnswersGiven a sorted array. Now following operations may be applied on even position elements:
- NIC October 03, 2014 in India
swap elements on even position. An element may be swap only once.
eg. 1 2 3 4 5 6 7 8 9 10
modified array:
1 2 3 8 5 10 7 4 9 6.
Find any given element in less than o(n) complexity.| Report Duplicate | Flag | PURGE
Josh Software Engineer / Developer Algorithm