## Algorithm Interview Questions

- 2of 2 votes
Congrats on aonecode member A.P. for signing the offer with FB! Thanks for sharing the experience with us.

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

- 1of 1 vote
Airbnb: Design webbrowser back button

Your web browser supports will support three actions: back, forward and open. The init webpage is “about:blank”.

Given a sequence of commands. Return the result page.

- 0of 0 votes
You have been given a generator string ab from which any number of strings can be generated recursively by inserting ‘ab’ at any location. You have been given an input string to check if that given string is valid or not.(i.e. generated by given with given string.)

eg.

Input: aabbab

Output: valid

Input: abbaab

Output: Invalid

I could not come up with a algorithm less than O(N*N)

- 0of 0 votes
Search for a sorted integer in an integer array that has been rotated multiple times.

- 1of 1 vote
Print the bottom view of a Binary Tree.

ex-`1 2 3 4 5 7 8 9 10`

result is 4, 8, 5, 9, 7, 10

- 0of 0 votes
Given an alphabet where we do not know the order of the letters also do not know the number of letters.

We are give an input list of tuples where each entry in the list gives an ordering between the 2 letters

Determine the alphabet order.

Ex-

<A, B>

<C, D>

<C, E>

<D, E>

<A, C>

<B, C>

Order is A, B, C, D, E

- 1of 1 vote
AWS phone interview

Find the left view of binary tree

1

/ \

2 3

/\ \

4 5 6

/ /

7 8

/

9

return [1, 2, 4, 7, 9]

- 2of 2 votes
April Google Interview 1/4

A = a+b-c-a-b-c-a-b (Tree)

B = b+a+c+a+b-c+b (Tree)

is A equal to B

- 3of 3 votes
April Google Interview 4/4

Build HTML Reverser

Given

<A>(hello)(<P>ab</P>)(<S>hi</S>)</A>

Return

<A>(<S>ih</S>)(<P>ba</P>)(olleh)</A>

- 2of 2 votes
April Google Interview 3/4

Maze

N,M array

Level 1 0,0 to N-1,M-1 => Path exsits?

Level 2 if path exists then print path

Level 3 if path exists then print min cost path

Level 4 O(nm log mn) using Priority Queue.

- 3of 3 votes
April Google Interview 2/4

Count Number Given Array

Level1 Unsorted Array [1, 3, 2, 1, 2 ,3 , 4, 10]

Find occurrence of 1

Level 2 Sorted Array

Find occurrence of 1

- 0of 0 votes
Write a function that receives string with decimal number (i.e. all characters are decimal digits) and prints the sum of all possible substring-numbers, example:

sum(“123”) = 123 + 12 + 23 + 1 + 2 + 3 = 167

- 0of 0 votes
Given N number of Strings, generate all combination of these String's characters, these Strings must be N long, and must contain only one number of char from each string.

example: "abc", "def", "ghi" --> adg, adh, adi, aeg ... cfg

- 1of 1 vote
Assume courses labeled by their index in an array. Given a list of pairs where the first element represents a prerequisite course required for the second course, derive an ordered list of courses.

- 0of 0 votes
For a given set of non-negative integers get the number of subsets that add up to a target value k.

- 0of 0 votes
Write a function to compute n^k. (don't forget negative exponents)

- 0of 0 votes
Imagine a horizontal corridor bounded by y = y1 and y = y2 lines on a 2D-plane. There are N sensors with centers (x, y) each of which operates in a range (r) on the plane . So, they cover some circular areas on the plane. See the figure below.

`o | _____o___o__|____________ y = y1 o |OOO __________oo|_____O______ y = y2 O | O _ _ _ _ _ _ | _ _ _ _ _ _ | o O | o O O | | O | |`

The question is whether a path exist from x=-inf to x=+inf via corridor without being detected any radar.

Constraints:

1. You are free to move any direction only if you stay in the corridor.

2. You are free to go through corridor borders.

3. N sensors are given as list of (x, y, r) like [(1, 3, 2), (-1, -3, 4)]. x and y are signed integers. r is a unsigned integer.

4. y1 and y2 are integers.

My solution:

1. Create an intersection graph of N sensors by comparing them each other via Euclidean distance`(x1 - x2)^2 + (y1 - y2)^2 <= (r1 + r2)^2`

2. If there is a path between y=y1 and y=y2 through intersected sensors, there do not exist any path from x=-inf to x=+inf. Otherwise, there do exist a path. So, I used BFS to search such a path.

Worst Case Complexity:

1. O(n^2)

2. O(V + E) = O(n + intersection_count)`Total: O(n^2)`

My Best Case Optimization for Intersection Graph:

1. For each sensor, create two events for start and end of circles vertically. y = (y1 - r) and y = (y1 + r)

2. For each sensor, register those two events into an array.

3. Use a line sweep algorithm over 2, which is O(nlogn + intersection_count) and intersection_count may be n^2 at worst case.

I wonder if I should have had a better solution with the worst case < O(n^2).

- 0of 0 votes
You are given the length and time of occurrence of packet and Queues which process packets. Total processing time for a packet is equal to the length of packet plus the waiting time in queue. For eg lets say we have only one queue for now, and A packet of length 5 comes at t = 1, and another packet of length 4 comes at t = 3. Total processing time for first packet is 5( no waiting time as queue is empty at t = 1) and at t = 3, 2 units of first packet is processed and 3 units remaining so, for second packet 3 units will be waiting time in queue plus 4 units for its length. Total processing time for 2nd packet is 7 units. If there are multiple queues you can add new packet in any of the other queues. Given the time and length of all incoming packets, we need to find the minimum no. of queues required such that total processing time of each packet is less than 10 units. Maximum possible no. of queues are 5. If you require more than 5 queues print -1.

Test Cases Format: First Line contains the number N, the total no. of packets and N following line contains two numbers ti, li where li is length of packet coming at time = ti units.

Test case1:

2

2 7

5 8

Test Case 2:

3

1 3

2 3

3 5

Test Case 3:

3

1 5

2 4

3 8

Output:

Case1: 2

Case2: 1

Case3: 2

Consider the following time table of incoming packets:`time packets-length 1 8 2 5 3 2 4 6`

If you put the packet in queue with minimum time then this will lead to 3 queues:

t = 1:

q1: 8

t = 2:

q1: 7

q2: 5

t = 3:

q1: 6

q2: 4, 2

t = 4:

q1: 5

q2: 3, 2

q3: 6

But its output should be 2 queues:

1) 8 in queue 1

2) 5 in queue 2

3) 2 in queue 1

4) 6 in queue 2

- 0of 0 votes
Given a bar chart which the heights of bars are notated as an array of positive integers. Rectangles can be formed in areas covered by one or more bars. Find the largest rectangle.

- 5of 5 votes
FB On-site March

Q: Find number of Islands.

XXXOO

OOOXX

XXOOX

Return 3 islands.

1 1 1OO

OOO2 2

3 3OO 2

Followup: If the board is too big to fit in memory, how to get the number?

- 0of 0 votes
.

- 3of 3 votes
Find the median of a very big array of integer. Only iterator of array is given

- 0of 0 votes
Given list of schedules for different flights in a month, determine maximum number of flights that can be in the air anytime in that month.

Input : list of schedules for flights.- spread over a month.

output: a number - maximum flights that can be in the air

Assumptions: 1. All the given times are in a specific timezone( like GMT).

2. Given Schedules can be any time in the month

- 0of 0 votes
Given a list of N threads detect a deadlock in the system.

- 3of 3 votes
Google

Given two lowercase strings, S1 and S2, sort S1 in same order as S2.

If a character in S1 doesn't exist in S2, put them at the end. If S1 is "program" and S2 is "grapo", then return "grrapom".

- 3of 3 votes
Twitter

Count number of each character in a string and print out the counts from highest to lowest.

- 3of 3 votes
Search for a target value from a sorted array with unknown size.

- 0of 0 votes
A sample state of ‘a’:

[[2, NULL, 2, NULL],

[2, NULL, 2, NULL],

[NULL, NULL, NULL, NULL],

[NULL, NULL, NULL, NULL]]

FUNCTION foo()

FOR y = 0 to 3

FOR x = 0 to 3

IF a[x+1][y] != NULL

IF a[x+1][y] = a[x][y]:

a[x][y] := a[x][y]*2

a[x+1][y] := NULL

END IF

IF a[x][y] = NULL

a[x][y] := a[x+1][y]

a[x+1][y] := NULL

END IF

END IF

END FOR

END FOR

END FUNCTION

- 2of 2 votes
Adobe (phone)

Return the value of the item k away from the end of a linked list

- 3of 3 votes
Find a byte array in a byte file.

For e.g.

finding arr = bytearray([3,4,5,3]) in byte file ([24,3,4,5,3,4,5,3,9, 255,...])

output: 1, 4, ...

since arr is found at idx 1, 4, ...