Algorithm Interview Questions
- 5of 5 votes
AnswersGiven K sorted (ascending) arrays with N elements in each array, implement an iterator for iterating over the elements of the arrays in ascending order.
The constructor receives all of the input as array of arrays.
You need to implement the MyIterator class with a constructor and the following methods:class MyIterator<T> { T next(); boolean hasNext(); }
You are allowed to use only O(K) extra space with this class.
example:
input:[[1,5,7], [2,3,10],[4,6,9]]
The iterator should return:
- torchs January 13, 2020 in Israel1,2,3,4,5,6,7,9,10
| Report Duplicate | Flag | PURGE
Facebook Solutions Engineer Algorithm - 5of 5 votes
AnswersGiven a Sorted integer array which is rotated N number of times. You have no idea what that N is. An element in the array can occur more for any number of time. Write a method to search the position of a given element. If there are more than one of the same element, return the position of the first element.
- jeevanus September 04, 2014 in India for Microsoft CRM| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm Data Structures Sorting - 5of 5 votes
AnswersGiven two sorted arrays, we can get a set of sums(add one element from the first array and one from the second). Find the Nth element in the set of sums. Suppose that array A is {1,3,4,8,10}, array B is {20, 22, 30, 40}. then the sum set will be{21(1+20),23(1+22 or 3+20), 25(3+22), 24(4+22)...} the 3rd element in the sum set is 25.
- ophis.W October 28, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Intern Algorithm - 5of 5 votes
AnswersGiven a hashmap M which is a mapping of characters to arrays of substitute characters, and an input string S, return an array of all possible mutations of S (where any character in S can be substituted with one of its substitutes in M, if it exists).
What is the time complexity? What is the space complexity? Can you optimize either?
- trunks7j February 15, 2013 in United StatesExample input: M = { f: [F, 4], b: [B, 8] } S = fab Expected output: [fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersYou have a link list with the following structure:
- francisco.gutierrez.91 January 24, 2013 in United States for Office
struct Node{ Node*next; Node*other; }
next pointer points to next node, but "other" pointer points to any node in the list, it can be itself or null.
you receive the header of a list with this structure.
you have to copy it(allocate new memory) , you cannot modify the structure, you can not modify the list you are given.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Linked Lists Algorithm Data Structures - 5of 5 votes
AnswersGiven N balloons, if you burst ith balloon you get Ai−1∗Ai∗Ai+1 coins and then (i-1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather.
- dp November 25, 2015 in United States
Assume that we have extra 1 at left most and right most positions. (don't take in answer just for boundary positions)
Hence if we have left or right boundary positions we multiply 1.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersGiven an integer, find the next highest and next lowest integers, with equal number of 1s in their binary representation as the original number.
- gulusworld1989 January 13, 2014 in United States for Android| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 5of 5 votes
AnswersGiven a binary tree.
Print nodes of extreme corners of each level but in alternate order.10 5 11 9 20 - 15 14 - - - 25 30
then output should be 10,11,9,25,30
- SK June 09, 2013 in India
left most of 0th level
right most of 1st level
left most of 2nd level
& like this| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm Trees and Graphs - 5of 5 votes
AnswersGiven an infinite stream of characters and a list L of strings, create a function that calls an external API when a word in L is recognized during the processing of the stream.
- ragmo2223 November 05, 2015 in United States
Example:
L = ["ok","test","one","try","trying"]
stream = a,b,c,o,k,d,e,f,t,r,y,i,n,g.............
the call to external API (let's call it some function callAPI()) would be called when the 'k' is encountered, again when the 'y' is encountered, and again at 'g'.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersA plumber working for a company as a contractor. His job is attend services and submit the bill to get his salary on basis of daily work including his service charge 500 rupees. For a typical plumbing work he need pipes with different lengths. But in market he will get new pipe with standard size 100m of cost 100 rupees. (no small or large sized pipes available) Now , he need 10 , 40 , 60, 70 lengths of pipes for a jobwork.
- bhupal February 22, 2015 in India
Generally company gives him (4 pipes * 100 rupees) + 500rupees as service charge = 900 rupees.
but plumber bought only 2 pipes cut as follows and get his job done...
1st pipe => 40+60
2nd pipe => 10+70 + extra left(20)
By buying only 2 pipes he get his job done. remaining 2 pipes money saved.
write an efficient algorithm to calculate minimum number of standard size pipes required for given number of different pipes lengths:
Input:
N => total pipes for jobwork
arr[N] => lengths of pipes. (for simplicity, pipe size will be either smaller or equal to standard size)
outpud:
minimum statdard sized(100m) pipes required
constraint: you can only cut them can not join them back as follows
say he need 10 95 95,
with two pipes 100 100 = > 95+5 95+5 => 95 95 (5+5)// this is not accepted
EX:
Input:
5
20 30 50 60 80
output:
3
Input:
5
10 10 10 15 20 35 55 60 70 75 75 80
output:
6| Report Duplicate | Flag | PURGE
NVIDIA Dev Lead Algorithm - 5of 5 votes
AnswersThe closest common ancestor in a tree forest.
class Node { Node* parent; // == null for root of tree Node* left; Node* right; } Node* tree_forest[]; // array of pointers which points to roots of each tree respectively Node* closest_common_ancestor(Node* n1, Node* n2) { // your solution }
Example:
| a | j | / \ | / | b c | h | / / \ | |d e f |
for e and d CCA is a
- Sergey January 17, 2015 in United States
for e and f CCA is c
for e and c CCA is c
for h and d CCA is null
Constrains: O(1) additional memory| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersWe have words and there positions in a paragraph in sorted order. Write an algorithm to find the least distance for a given 3 words.
- pqrabcd November 14, 2014 in United States
eg. for 3 words
job: 5, 9 , 17
in: 4, 13, 18
google: 8, 19, 21
...
...
Answer: 17, 18, 19
Can you extend it to "n" words?
Context: In Google search results, the search terms are highlighted in the short paragraph that shows up. We need to find the shortest sentence that has all the words if we have word positions as mentioned above.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven stock price of Amazon for some consecutive days. Need to find the maximum span of each day’s stock price. Span is the amount of days before the given day where the stock price is less than that of given day
- Rahul Sharma April 04, 2014 in India
E.g i/p = {2,4,6,9,5,1}
o/p= { -1,1,2,3,2,-1}| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 5of 5 votes
AnswersIf a linkedlist is having loop, how to find the last node of the loop .
- zammer May 28, 2013 in India for SDET| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 5of 5 votes
AnswersGiven an array of 0s and 1s, find out:
- HauntedGhost March 05, 2013 in United States
1. all the subsequences where number of 0s = number of 1s
2. max length subsequence where number of 0s = number of 1s
Update:
We need to find subarrays, not subsequences. Sorry for the confusion.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 5of 5 votes
AnswersWe have a day to work and we have different kinds works do to which has start-time and end-time. We have to choose the different works so that we can achieve the maximum number of minutes in a day to work. Chosen works should not overlaps to each other.
- Rahul August 22, 2013 in India
Ex-1:
Start-Time End-Time
W1: 6:00 9:30
W2: 9:00 12:30
W3: 12:00 14:30
W4: 10:00 10:30
W5: 11:00 13:30
Solution: W1 + W4 + W3(or W5)
Ex-2:
Start-Time End-Time
W1: 6:00 8:30
W2: 9:00 11:00
W3: 12:30 14:00
W4: 8:00 9:00
W5: 10:30 14:00
W6: 9:00 11:30
Solution : W1 + W6 + W3 = 390min| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 5of 5 votes
AnswersAs input, you are given two sets:
- kbex07 February 11, 2013 in United States
1) set R of n1 non-overlapping rectangles, whose sides are parallel to the x- and y-axes (ie: not rotated rectangles). Each rectangle denoted by bottom left & top right corner coordinates.
2) set P of n2 points
- let n = n1 + n2
For each point 'p' in set P, find the rectangle 'r_p' in set R that contains 'p'. If 'p' is not enclosed by any rectangle, then 'r_p' is undefined. Otherwise, 'r_p' is unique because of the non-overlapping set.
Goal: come up with a divide-and-conquer pseudocode to solve the general problem in O(n(logn)^2) time.
Asked about points that are on the edge of the rectangle, and they said it was up to me whether to include those or not, just a matter of "<" vs "<=", etc. comparisons. Because it's just pseudocode they were looking for, they were not too concerned with the actual structure of the return value, just that the D&C algorithm showed the logic.
Struggled with it for awhile and they simplified the problem to a ~special case with the constraint where all rectangles of R intersected a horizontal line 'L', and instead give a O(nlogn) algorithm to solve the same problem. I suspect this would've been a subproblem/subroutine of the more general case, but again got a bit lost.| Report Duplicate | Flag | PURGE
Facebook Algorithm - 5of 5 votes
AnswersLet A = A[1], . . . , A[n] be an array of n positive integers. Let s = A[1] + · · · + A[n] be the sum of all the numbers in the array. For 1 ≤ i ≤ n, let S(i) = s − A[i].
- Denjar June 01, 2013 in United States
Design a linear time algorithm (O(n)) to compute S[1], . . . , S[n] only with plus operations (you are not allowed to use the minus operation)| Report Duplicate | Flag | PURGE
Algorithm - 5of 5 votes
Answersyou have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray.
- SK January 21, 2015 in India
You have to return sum of max M subarray of size K (non-overlapping)
N = 7, M = 3 , K = 1
A={2 10 7 18 5 33 0} = 61 — subsets are: 33, 18, 10 (top M of size K)
M=2,K=2
{3,2,100,1} = 106 - subsets are: (3,2), (100,1) 2 subsets of size 2| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer Algorithm Dynamic Programming - 5of 5 votes
Answerswrite a program to give an array such that:
- doctorking5891 April 29, 2014 in United States
1. the data value is from 1 to n
2. the length of it is 2*n
3. the two elements with same value keep the same number distance.
for example, when n = 3, the length of array is 6, the array should be like: 2, 3, 1, 2, 1, 3. there are two elements between "2" pair, and three elements between "3" pair and one element between "1" pair| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 5of 5 votes
AnswersYou are given an array of n elements. The elements have are n-bit long too.
- Anon123 January 04, 2014 in United States
Now n here represents the number of employees in a company. Element with index 0 is information about employee 0, at index 1 is information of employee 1....
For each element, the bits represent whether that employee works (not same team... just works) with employee at that index.
Ex. element 0 = 0110 => emplyee 0 works with employee 1 and 2
element 1 = 1001 => emplyee 1 works with employee 0 and 3
...
Put employees in groups in which they work. The transitive property is applicable here i.e. if A works with B and B works with C, ABC will be in one group.
The solution needs to efficient in terms of run time and memory. I hope the above is clear.| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 5of 5 votes
AnswersYou are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.
Campus map:
- john August 29, 2018 in United States. - Free path/road # - Building B - Google bike Employee location - (x, y) - (1, 2) . . . . . # . . E . . # # # # # . # . B . . . . . . . . . B
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersWrite a program to print all the permutations of the given input string.
- chandan.jc May 10, 2012 in United States for Software| Report Duplicate | Flag | PURGE
NetApp Intern Algorithm - 5of 5 votes
AnswersWrite the code for a change vending machine.
- Java Coder October 12, 2008| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersSuppose you have an input character stream (StreamReader) and you have a list of pattens like ABCAS, ASGKT. KHTSD etc. You need to read the stream one by one character and you need to keep count on number of each pattern found so far and when EOF occures just print all the patterns along with count.
- Hitesh November 16, 2017 in India
Example:
Input String: 011100010
Pattern 1: 011
Pattern 2: 010
Output:
011 => 1
010 => 1| Report Duplicate | Flag | PURGE
Freight Tiger Software Developer Algorithm - 5of 5 votes
AnswersCongrats on aonecode member A.P. for signing the offer with FB! Thanks for sharing the experience with us.
- aonecoding May 24, 2018 in United States
phone:
postorder tree traversal recursive -> iterative
add two binary number
on-site:
1 ring buffer
2 merge intervals
3 Leetcode alien dictionary
4.sort list of words| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 5of 5 votes
AnswersGiven a stream of integers where probability of a smaller number being first in stream is more than probability of larger number in stream.
- James March 17, 2021 in United States
Implement a method that returns true if you have already seen that element in stream otherwise return false.
eg. stream could look like 1,2,3,5,6,11,7,3......
more examples - 3,4,1,2,5,9,22,12
---
I explained using a hashset but that solution was not viable because of the space requirement.
I don't think I handled this question well. So would love people's opinion on it.| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 5of 5 votes
AnswersGoogle On-site in May
- aonecoding June 15, 2017 in United States
Create a class with a collection of integers.
Enable 3 APIs:
void append(int x),
int get(int idx),
void add_to_all(int x),//add x to all numbers in collection
These methods should run in O(1) time.
Follow-up
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm