## Algorithm Interview Questions

- 1of 1 vote
You have given height array of array. Generate the original array.

Input: [6,3,0,2,2,0,0]

Output : [ 1,5,7,3,2,6,4]

A[i] value in input array is the number of greater element on right side.

- 0of 0 votes
How to print nested array ?

Input : [1, 5, 8, [9, 10, 24, 20, [39, 48], 89], 105, 99]

Output : 1, 5, 8, 9, 10, 24, 20, 39, 48, 89, 105, 99.

Which data structure you will use to store the values?

- 0of 0 votes
Write code to find unmatched parentheses and return it in the below format:

((a) -> -10a1

(a)) -> 0a1-1

(((abc))((d))))) -> 000abc1100d111-1-1

- 0of 0 votes
Given an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.

Example : Array : 2,5,6,7,8,8,9

Target number : 5

Output : 5

Target number : 11

Output : 9

Target Number : 4

Output : 5

- 0of 0 votes
Suppose 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.

Example:

Input String: 011100010

Pattern 1: 011

Pattern 2: 010

Output:

011 => 1

010 => 1

- 0of 0 votes
Count number of ways to paint a fence with N posts using K colors, where no FOUR consecutive fences can have the same color.

- 0of 0 votes
Robot hand movement

Given a (1) string message (consisting of only upper case alphabets), and (2) width of keyboard, output the movements required by an automated robot hand to print out the string message.

The robot hand can move right, left, up or down. It cannot move diagonally.

Ex 1:

String message: “HI”

Width: 26

Output: R8, T, R1, T

Ex2:

String message: “HELLO”

Width: 13

Output: R8, T, L3, T, R7, T, T, D1, L10, T

- 0of 0 votes
Given two strings containing only numbers, return product of the two strings. Strings are large so conversion to interger is not possible.

- 0of 0 votes
Your code is inside a service that receives a large stream of integers, large enough that it can't be stored on any disk. You don't know the how many integers will be there on the stream. You have to write a sampler which selects K integers such that likelihood of selecting any integer from the stream is equal.

- 0of 0 votes
Given a linked list with next and random pointer, deepcopy the linked list and return new head.

Node {

char val,

Node next,

Node random }

A {

val: ’a’

next: D

random: G}

D {

val: ’d’

next: G

random: A}

G {

val: ’g’

next: null

random: D}

-----------

| |

| V

A -> D -> G -> null

-------------

| |

| V

A' -> D' -> G' -> null

- 1of 3 votes
Congrats to aonecode's member F.L.

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)

- 1of 3 votes
Congrats to F.L.

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.

- 2of 2 votes
Facebook

-Phone: LC304 & longest arithmetic sequence. Return the sequence.

- 3of 3 votes
Wish Interview

-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.

- 0of 0 votes
What is the Big O of that algorithm? What happens at runtime?

- 0of 0 votes
What's the algorithm to transform the sentence "the brown fox ran fast" in "eht nworb xof nar tsaf" (reverse any word)

- 0of 0 votes
Today Jin has given a task to Shino, Shino has to travel from cell

(

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

- 1of 1 vote
You 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.

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.

- 0of 0 votes
Find the distance between the farthest two elements in a binary tree.

- 0of 0 votes
Given 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.

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

*

***

**

- 0of 0 votes
`A 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.`

- 0of 0 votes
Given an unsorted array of unique integers, find two numbers in the array whose sum is equal to a given number.

- 1of 1 vote
Airbnb Online Assessment Paginate List

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

- -2of 6 votes
How will you test "Hello world" program?

- 2of 2 votes
Find the indices of all anagrams of a given word in a another word.

For example: Find the indices of all the anagrams of AB in ABCDBACDAB (Answer: 0, 4, 8)

- 2of 2 votes
Amazon OA2

Implement a round robin scheduler.

Each process has an arrival time Atime[i], execute time Etime[i].

Q is the maximum time that a process gets executed in its turn. If the process isn't finished after q, it waits till the next round.

Output average wait time for the processes.

- 0of 0 votes
All jumbled numbers of n digits in max (worst case) O(n) and min (avg case) O(log n) time.

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.

- 0of 0 votes
Given two list of unsorted intervals V1 and V2 write 2 functions 'OR ' and 'And' to return a new list

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

- 0of 0 votes
Given 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.

Test Case I: ["ab", "ab", "abc", "bca"]

Answer: 3

Test Case II: ["ab","aqb"]

Answer: 0

- 0of 0 votes
Check if two DOM Trees have the same text.

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)