Algorithm Interview Questions
- 2of 4 votes
AnswerCongrats to aonecode's member F.L.
- aonecoding November 03, 2017 in United States
Got offers from - Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!
Thanks for sharing the interview experience with us.
Youtube Interview
- Phone: Find anagrams of string A from string B (sliding window)
- Phone: Find if two frames in a screen are equal. Frames may overlap. (equal method)
Onsite:
- LC41 first missing positive
- LC499+LC505 The maze
- LC161 one edit distance
- Similar to hangman but make guesses based on a dictionary.
Assume a dictionary has words - {house, morse, jesus} and ‘morse’ is the answer. If your first guess is ‘house’, output will be ‘_o_se’, which indicates 3 letters are correct. (Here the arrangement of letters does not matter. Your guess can be ‘co’ and if answer is ‘ok’ then the output is gonna be ‘_o’ which indicates letter ‘o’ in answer. )
Try to get the answer with minimum guesses.
(Interviewer expects pre-processing the dictionary. Key: letter; Value: frequency. Begin with combinations of most frequent letters first)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 3 votes
AnswerCongrats to F.L.
- aonecoding November 03, 2017 in United States
Got offers from - Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!
Thanks for sharing the interview experience with us.
LinkedIn
Phone:
- Questions from LC tagged LinkedIn.
Onsite:
- Get sqrt(x). Output a floored integer if result is not a perfect square. sqrt(18) = 4
- Implement BST, insert, delete, search.
- Design a dashboard for service logs stats (sort and aggregate). Scale from 1 to more machines. Discuss async and realtime as different scenarios.| Report Duplicate | Flag | PURGE
Linkedin Software Engineer Algorithm - 2of 2 votes
AnswerFacebook
- aonecoding November 03, 2017 in United States
-Phone: LC304 & longest arithmetic sequence. Return the sequence.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 4of 4 votes
AnswerWish Interview
- aonecoding November 03, 2017 in United States
-Phone: Two sum, Three sum, N sum(recursion)
Onsite:
-Implement merge sort (recursion&iteration)
-Merge two sorted arrays: one of length m+n, the other n; store the result in the longer array
-Given a number print diamond:
Given 1
Pirnt 1
Given 3
Print
1
121
1
Given 5
Print
1
121
12321
121
1
- Rank N people in a game. There may be a tie among participants. How many possible ways of ranking there is.
- Design: Define a bot as an IP that hits the web app over M times in the past T seconds (not necessarily hits on the same page. Also take into account different API calls.) How to design a bot detector layer and where to place it in the system.| Report Duplicate | Flag | PURGE
Wish Solutions Engineer Algorithm - -2of 2 votes
AnswerWhat is the Big O of that algorithm? What happens at runtime?
- rignanese.leo November 02, 2017 in Europe| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWhat's the algorithm to transform the sentence "the brown fox ran fast" in "eht nworb xof nar tsaf" (reverse any word)
- rignanese.leo November 02, 2017 in Europe| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswerToday Jin has given a task to Shino, Shino has to travel from cell
- pooja.senger86 October 29, 2017 in United States
(
1
,
1
)
(1,1) to cell
(
N
,
M
)
(N,M) in a grid of size
N
∗
M
N∗M. But in order make this task interesting for Shino, Jin has decided to keep some special candies in some
K
K special cells of the grid, where each candy has an amount of happiness associated with it.
Shino can travel only in right & down direction in the grid, as he is too careful & does not want to fall out of grid. Now, we call the value of a path the happiness of all cells lying on the path. All non-special cells have happiness equal to
0
0.
Now, you need to find and print the sum of the values of all paths from
(
1
,
1
)
(1,1) to
(
N
,
M
)
(N,M), traveling only right and down to an adjacent cell.
As Shino is not good at counting help him find the answer.
Input Format
The first Line contains a single integer
T
T denoting number of test cases
The next line contains
3
3 space separated integers,
N
N,
M
M and
K
K where N * M is the size of grid & K denoting number of special cells
The next
K
K lines contains three integers
X
i
,
Y
i
,
H
i
Xi,Yi,Hi where
(
X
i
,
Y
i
)
(Xi,Yi) is cell coordinate &
H
i
Hi is the amount of happiness Shino will get from a candy at cell
(
X
i
,
Y
i
)
(Xi,Yi)
Constraints
1
≤
T
≤
3
1≤T≤3
1
≤
N
,
M
,
K
≤
10
5
1≤N,M,K≤105
1
≤
X
i
≤
N
,
1
≤
Y
i
≤
M
1≤Xi≤N,1≤Yi≤M
1
≤
H
i
≤
10
5
1≤Hi≤105
Output Format
For each test case you will output a single integer denoting the total amount of happiness Shino will get. As the answer can be quiet large you can output answer modulo
10
9
+
7
109+7
Sample Input
1
2 2 2
1 2 4
2 1 7
Sample Output
11| Report Duplicate | Flag | PURGE
A9 abc .Net/C Algorithm Java - 1of 1 vote
AnswersYou are a game developer working on a game that randomly generates levels. A level is an undirected graph of rooms, each connected by doors. The player starts in one room, and there is a treasure in another room. Some doors are locked, and each lock is opened by a unique key. A room may contain one of those unique keys, or the treasure, or nothing.
- robert October 24, 2017 in United States
Implement a representation for a level and write code that, given a level and starting room, returns true if the treasure can be reached by the player—likely requiring them to find certain other keys first—or false if there is no solution.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 0of 0 votes
AnswersFind the distance between the farthest two elements in a binary tree.
- nra October 19, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersGiven a non-negative integer n, check if it is possible to build a pyramid of '*' and empty spaces where first row has one '*' and second has three '*' and so on.
- Shilpi_Roy October 19, 2017 in United States
For example-
Input: n =4 Output: True
Explanation : The pyramid can be build
*
***
Input: n = 9 Output: True
Explanation : The pyramid can be build
*
***
*****
Input: n = 6 Output: False
Explanation : The pyramid cannot be build as last row will be incomplete
*
***
**| Report Duplicate | Flag | PURGE
Nutanix Software Developer Algorithm - 0of 0 votes
Answers
- Anonymous October 13, 2017 in United States for SeattleA text file contains {candidateID,voterID} details of an ongoing voting. Read this file in real time and report top 5 candidates. Also report a fraud if a Voter tries to vote twice or try to vote more then one candidate. Assume that the database is offline.
| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
AnswersGiven an unsorted array of unique integers, find two numbers in the array whose sum is equal to a given number.
- CoolGuy October 13, 2017 in India| Report Duplicate | Flag | PURGE
Algorithm - 2of 2 votes
AnswerAirbnb Online Assessment Paginate List
- aonecoding October 13, 2017 in United States
5
13
1,28,310.6,SF
4,5,204.1,SF
20,7,203.2,Oakland
6,8,202.2,SF
6,10,199.1,SF
1,16,190.4,SF
6,29,185.2,SF
7,20,180.1,SF
6,21,162.1,SF
2,18,161.2,SF
2,30,149.1,SF
3,76,146.2,SF
2,14,141.1,San Jose
Here is a sample input. It’s a list generated by user search.
(1,28,100.3,Paris) corresponds to (Host ID, List ID, Points, City).
5 in the first row tells each page at most keeps 5 records.
13 in the second row is the number of records in the list.
Please paginate the list for Airbnb by requirement:
1. When possible, two records with same host ID shouldn’t be in a page.
2. But if no more records with non-repetitive host ID can be found, fill up the page with the given input order (ordered by Points).
Expected output:
1,28,310.6,SF
4,5,204.1,SF
20,7,203.2,Oakland
6,8,202.2,SF
7,20,180.1,SF
6,10,199.1,SF
1,16,190.4,SF
2,18,161.2,SF
3,76,146.2,SF
6,29,185.2,SF -- 6 repeats in page bec no more unique host ID available
6,21,162.1,SF
2,30,149.1,SF
2,14,141.1,San Jose| Report Duplicate | Flag | PURGE
Airbnb Software Engineer Algorithm - -2of 6 votes
AnswersHow will you test "Hello world" program?
- gagan.ping October 12, 2017 in India| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersFind the indices of all anagrams of a given word in a another word.
- aonecoding October 09, 2017 in United States
For example: Find the indices of all the anagrams of AB in ABCDBACDAB (Answer: 0, 4, 8)| Report Duplicate | Flag | PURGE
Amazon 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 - 1of 1 vote
AnswersGiven two list of unsorted intervals V1 and V2 write 2 functions 'OR ' and 'And' to return a new list
- sachin323 October 05, 2017 in United States
OR Function (union of list ): Input V1 = (2,4) (6,8) (1,3) V2 = (7,9) (2,5)
output = (1,5) (6,9)
And function : This will be intersection function and will return intersection of the lists| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 0of 0 votes
AnswersGiven an array of strings, find out in how many cases is any of the anagrams of the string at location i, a substring of the string at location i+1.
- lkjhgfdsa September 30, 2017 in United States
Test Case I: ["ab", "ab", "abc", "bca"]
Answer: 3
Test Case II: ["ab","aqb"]
Answer: 0| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 0of 0 votes
AnswersCheck if two DOM Trees have the same text.
- wtcupup2017 September 28, 2017 in United States
e.g. <html><p>hello</p></html>, <html><p><b>h</b>ello</p></html> should be the same text
DOMNode class definition (string tag, string text, bool isText, vector<DOMNode*> children)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 3 votes
AnswersA message containing letters from A-Z is being encoded to numbers using the following mapping:
- MM September 26, 2017 in United States
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).| Report Duplicate | Flag | PURGE
SDE-2 Algorithm - 0of 0 votes
AnswersGiven two sorted integer arrays, find the median element. Note that for an even sized collection, median element is to be defined as the average of the central two elements.
- NoOne September 25, 2017 in India| Report Duplicate | Flag | PURGE
Goldman Sachs Software Architect Algorithm - 0of 0 votes
AnswersGiven two strings s1, s2, write a function that returns true if s2 is a special substring s1. A special substring s2 is such that the s1 contains s2 where each character in s2 appears in sequence in s1, but there can be any characters in s1 in between the sequence.
- tnutty2k8 September 22, 2017 in United States
Example:
isSpecialSubstring('abcdefg', 'abc') => true
isSpecialSubstring('abcdefg', 'acg') => true
isSpecialSubstring('abcdefg', 'acb') => false;
The first two are abc and acg appears in 'abcdefg' in that order, although there might be multiple chars between the next character in s2.
The last one is false, because in 'acb' the character 'b' appears before the character 'c' in 'abcdefg'
Hope thats clear.| Report Duplicate | Flag | PURGE
Algorithm - 1of 1 vote
Answerscreate a class of integer collection,
- aonecoding September 22, 2017 in United States
3 APIs:
append(int x),
get(int idx),
add_to_all(int x),
in O(1) time。
Follow-up:
implement
multiply_to_all(int x)
e.g.
insert(1)
insert(2)
add_to_all(5)
insert(3)
get(0) -> returns 6
get(2) -> return 3
multiply_to_all(10)
insert(4)
get(1) -> returns 70
get(2) -> returns 30
get(3) -> returns 4| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersLonely Pixel
- aonecoding September 22, 2017 in United States
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersSuperCity consists of a single line of n buildings, where each building i is heighti units tall; however, SuperCity is under attack by two supervillains looking to show off their superpowers! The supervillains are standing on opposite ends of the city, unleashing their powers in an attempt to destroy all n buildings. In a single move, a supervillain unleashes their power and destroys the nearest contiguous block of buildings in which the respective heights of each building are nondecreasing. In other words:
- new September 22, 2017 in United States
If a supervillain is standing on the left end of the city and the nearest intact building is building i, then performing a move will destroy each consecutive building i, i + 1, i + 2, … satisfying heighti ≤ heighti+1 ≤ heighti+2 ≤ … until there are either no more buildings in their path or there is some building j satisfying heightj > heightj+1.
If a supervillain is standing on the right end of the city and the nearest intact building is building i, then performing a move will destroy each consecutive building i, i − 1, i − 2, … satisfying heighti ≤ heighti-1 ≤ heighti-2 ≤ … until there are either no more buildings in their path or there is some building j satisfying heightj > heightj-1.
Once a supervillain destroys a building, the building's height becomes 0.
Complete the function in the editor below. It has one parameter: an array of integers, height, where each heighti denotes the height of building i. The function must return an integer denoting the minimum number of total moves needed for two supervillains standing on opposite ends of the city (as described by the array of building heights) to destroy all n buildings.
Input Format
The first line contains an integer, n, denoting the number of elements in height.
Each line i of the n subsequent lines contains an integer describing heighti.
Constraints
1≤ n ≤ 105
1 ≤ heighti ≤ 105, where 0 ≤ i < n.
Output Format
Return an integer denoting the minimum number of total moves needed for two supervillains on opposite ends of the array to destroy all n buildings.
Sample Input 0
8
1
2
3
4
8
7
6
5
Sample Output 0
2
Explanation 0
The respective heights of each building are given as height = [1, 2, 3, 4, 8, 7, 6, 5]. The supervillains can perform the following minimal sequence of moves:
Sample Case 0
The diagram above depicts the changes to SuperCity's skyline after each move by a supervillain.
In the first move, the supervillain on the left destroys buildings 0 through 4, because height0 ≤ height1 ≤ height2 ≤ height3 ≤ height4; note that the destruction stops at this point, as height4 > height5.
In the second move, the supervillain on the right destroys buildings 7 through 5, because height7 ≤ height6 ≤ height5.
As it took a minimal two moves for the supervillains to level all the buildings, the function returns 2.
Sample Input 1
6
1
2
1
2
10
9
Sample Output 1
3
Explanation 1
The respective heights of each building are given as height = [1, 2, 1, 2, 10, 9]. The supervillains can perform the following minimal sequence of moves:
Sample Case 1
The diagram above depicts the changes to SuperCity's skyline after each move by a supervillain.
In the first move, the supervillain on the left destroys buildings 0 through 1, because height0 ≤ height1.
In the second move, the supervillain on the right destroys buildings 5 through 4, because height5 ≤ height4.
In the third move, the supervillain on the left destroys buildings 2 through 3, because height2 ≤ height3.
As it took a minimal three moves for the supervillains to level all the buildings, the function returns 3.| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersGiven a binary tree that complies to the following rule:
The parent node value is always the the result of the AND operator of its children values.
You modify one of the LEAF nodes value (e.g. if it was 1 it is now 0). Write a function that fixes the tree
so it complies with the above rule.
- PenChief September 19, 2017 in Israel// // 0 1 // / \ / \ // 1 0 =====> 1 1 // / \ / \ / \ / \ // 1 1 0 1 1 1 1 1 // // The parent node value is always children value's LOGICAL AND // & //
| Report Duplicate | Flag | PURGE
Facebook Algorithm - 0of 0 votes
AnswersGiven an array of integers, return the index of the max value in this array.
Note:
If the max value appears more than once, the function should return one the indexes, but make it so that the next call will return different index.
Important: you are not allowed to store state between calls
Example: given this input array// 0 -1 6 4 5 6 6 // | | | // 2,1/3 5,1/3 6,1/3
Function signature:
int getIndex(const std::vector<int>& numbers);
Example output:
2 5 6 5 2
Extension:
What if you knew how many times the max value appears in the array, can you improve the function performance?
So using the given example array, the function signature is now:
- PenChief September 19, 2017 in Israelint getIndex(const std::vector<int>& numbers, int maxCount);
| Report Duplicate | Flag | PURGE
Facebook Algorithm - 0of 0 votes
AnswerWrite a function to generate Random Number without using any library functions.
- CodeNinja September 15, 2017 in United States for Solutions Engineering Team
Extension: Write an overloaded method for the above function which accepts a Range.| Report Duplicate | Flag | PURGE
Google Web Developer 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 - 0of 0 votes
AnswersGiven an unsorted array. for example [2, 3, 1, 4, 5].
- OldChang September 12, 2017 in United States
Sort the array, we have new array [1, 2, 3, 4, 5],
if we draw the line between the 2 arrays for the same number, for example:
[3, 2, 1,4,5]
\ | /
\|/
/|\
[1, 2, 3,4,5]
then we have 3 line-cross:
line (1 to 1) cross line (2 to 2)
line (1 to 1) cross line (3 to 3)
line (2 to 2) cross line (3 to 3)
Note: the line between two 4s and the line between two 5s don't cross any other lines;
Implement the algorithm to calculate the how many line crosses for an unsorted array.| Report Duplicate | Flag | PURGE
Software Engineer Algorithm