## Algorithm Interview Questions

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

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

- 2of 2 votes
Twitter

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

- 2of 2 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

- 1of 1 vote
Adobe (phone)

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

- 2of 2 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, ...

- 0of 0 votes
You have a 2 Dimensional Array.

1 2 3

4 5 6

7 8 9

Write code to generate all the 7 character strings without any duplicates starting from 4. You can move one block at a time and you can move either horizontally and diagonally. So for example, valid moves from 4 are 4 -> 1 and 4 -> 7. You can visit any node any number of times. so 4141414 is a valid string.

- 0of 0 votes
Given a string as input, return the list of all the patterns possible:

`'1' : ['A', 'B', 'C'], '2' : ['D', 'E'], '12' : ['X'] '3' : ['P', 'Q']`

Example if input is '123', then output should be [ADP, ADQ, AEP, AEQ, BDP, BDQ, BEP, BEQ, CDP, CDQ, CEP, CEQ, XP, XQ]

- 0of 0 votes
Language : Java

Given a binary tree, print boundary nodes of the binary tree counter-clockwise starting from the root.

For example, boundary traversal of the following tree is “20 8 4 10 14 25 22”

20

8 22

4 12 25

10 14

- -1of 1 vote
Question 2: Given a number 'k', return the corresponding row, given the pattern:

k => output

0 => []

1 => ["0", "1", "8"]

2 => ["00", "11", "69", "96", "88"]

3 => ["000", "111", "101", "888", ...] // and so on ...

- 0of 0 votes
Question 1: Given an input of an array of string, verify if, turned 180 degrees, it is the "same".

For instance:

[1, 6, 0, 9, 1] => return true

[1, 7, 1] => return false

- 2of 2 votes
Jet.com

Print a matrix in zigzag traversal (diagonally).

For matrix

1 2 3 4 5 6

7 8 9 10 11 12

13 14 15 16 17 18

19 20 21 22 23 24

Print

1 2 7 13 8 3 4 9 14 19 20 15 10 5 6 11 16 21 22 17 12 18 23 24

- 0of 0 votes
We say that a character is unique in string S if it occurs exactly once in it. For example, in string S = "ACAX", the only unique characters are "C" and "X".

Let's define UNI(S) as the number of unique characters in string S. For example, UNI("ACAX") equals 2.

Given a string S, calculate the sum of UNI(S') over all non-empty substrings S'. If there are two or more equal substrings at different positions in S, we consider them different.

Since the answer can be very large, provide it modulo 1,000,000,007 (109 + 7).

Write a function:

class Solution { public int solution(String S); }

that, given a non-empty string S consisting of uppercase letters, returns the sum of UNI(S') over all non-empty substrings S' of S modulo 1,000,000,007.

For example, given "ACAX", your function should return 16, as explained visually as follows:

UNI("A") = 1

UNI("AC") = 2

UNI("ACA") = 1

UNI("ACAX") = 2

UNI("C") = 1

UNI("CA") = 2

UNI("CAX") = 3

UNI("A") = 1

UNI("AX") = 2

UNI("X") = 1

Total: 16

Given "CODILITY", your function should return 96.

Assume that:

the length of S is within the range [4..100,000];

string S consists only of uppercase letters (A−Z).

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

- 1of 1 vote
Dropbox

Grid Illumination: Given an NxN grid with an array of lamp coordinates.

Each lamp provides illumination to every square on their x axis,

every square on their y axis, and every square that lies in their diagonal

(think of a Queen in chess).

Given an array of query coordinates,

determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,…

- 1of 1 vote
March 2018 Phone Interview FB

Calculate a moving average that considers the last N values.

Circular Queue (Interviewer didn't agree with the linked list queue that I suggested at first. Said the pointers took space)

- 0of 0 votes
Given two positive integers represented as linked lists, provide the sum of the numbers as a linked list.

`1->2->3 4->5->6 ----------- 5->7->9 1->2->3 4->5 ----------- 1->6->8 4->5->6 7->8->9 ----------- 1->2->4->5`

- 0of 0 votes
A bus has to travel from A to B and the distance is d miles. There are many gas stations between A and B.

The bus has initially g gallon of gas in tank. 1 gallon of gas travels 1 mile.

Gas stations have inforamtion of remaining distance from station to destination b and max gas that can be filled from the station.

Find the minimum number of stops for bus without running out of gas ever.

eg: gas = 10 , distance = 20

gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

o/p = 1

If bus stops at the stop{14,11} that is 14 miles away from destination and fills 11 gallon then it can reach destination with 1 gallon spare.

It can also stop as {16,3} and {10,7} but its 2 stops and at destination it runs out of gas.

Similarly {11, 5}, {7, 6} has 2 stops but has 1 gallon spare at destination.

- 2of 2 votes
Feb On-site Google

DP Problem. Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.

You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.

Follow-up: optimize 2d DP to 1d DP of linear extra space.

Follow-up: what if some cells are blocked

System Design

Availability test/debug on distributed system. Discussed and drafted about failover, replication, NoSQL etc.

Interviewer seemed to be expecting more but time ran out.

- 2of 2 votes
Feb On-site Google

Print all numbers satisfying the expression 2^i * 5^i (where i, j are integers i >= 0 and j >= 0) in increasing order up to a given bound N.

2^i stands for power(2, i).

- 0of 0 votes
Given a biased coin whose probability for Heads is 0.67 and Tails is 0.33, write an algorithm which will print the Heads and Tails with this probability.

- 0of 0 votes
Aisles contain products. Product is only going to be in one Aisle.

Product{

AisleID: string

ProductID: string

Price: float

}

Given Array<Product>, find the N highest price combinations. Combination is 1 product from each aisle. You can choose only one instance of each product.

So if you had two aisles

1: {$5,$4,$2}

and

2: {$6,$1)

And they asked for the 2 highest combos you would give $6,$5 and $6,$4

- 0of 0 votes
We have two sequences A and B consisting of integers, both of length N, and you would like them to be (strictly) increasing, i.e. for each K (0 ≤ K < N − 1), A[K] < A[K + 1] and B[K] < B[K + 1]. Thus, you need to modify the sequences, but the only manipulation you can perform is to swap an arbitrary element in sequence A with the corresponding element in sequence B. That is, both elements to be exchanged must occupy the same index position within each sequence.

For example, given A = [5, 3, 7, 7, 10] and B = [1, 6, 6, 9, 9], you can swap elements at positions 1 and 3, obtaining A = [5, 6, 7, 9, 10], B = [1, 3, 6, 7, 9].

Your goal is make both sequences increasing, using the smallest number of swaps.

Write a function:

public int minswaps(int[] A, int[] B);

that, given two zero-indexed arrays A, B of length N, containing integers, returns the minimum number of swapping operations required to make the given arrays increasing. If it is impossible to achieve the goal, return −1.

For example, given:

A[0] = 5 B[0] = 1

A[1] = 3 B[1] = 6

A[2] = 7 B[2] = 6

A[3] = 7 B[3] = 9

A[4] = 10 B[4] = 9

your function should return 2, as explained above.

Given:

A[0] = 5 B[0] = 2

A[1] = -3 B[1] = 6

A[2] = 6 B[2] = -5

A[3] = 4 B[3] = 1

A[4] = 8 B[4] = 0

your function should return −1, since you cannot perform operations that would make the sequences become increasing.

Given:

A[0] = 1 B[0] = -2

A[1] = 5 B[1] = 0

A[2] = 6 B[2] = 2

your function should return 0, since the sequences are already increasing.

Assume that:

N is an integer within the range [2..100,000];

each element of arrays A, B is an integer within the range [−1,000,000,000..1,000,000,000];

A and B have equal lengths.

Complexity O(N)

- 0of 0 votes
A and B are playing a perfect 8-9 game. The rules are pretty simple. At each point, you can either insert an 8 at the end of the previous number or a 9. one 8 and one 9 forms a pair. a 9 can only be inserted if there is an 8 which does not form a pair. Perfect solution is the one which has all its numbers in pair. Find out all the possible perfect outcomes of the game in lexicographic order.

Input-

Input 1: Max length of number

Output-

Your array must return an array of string s containing all possible outcomes.

Example 1:

Input: 4

Output: {"8899", "8989"}

Explanation: There can be only 2 possible outcomes out of 4 as nine must follow eight.

Example 2:

Input: 6

Output:{"888999","889899","889989","898899","898989"}

Explanation: The possible outcomes are 5.

- 0of 0 votes
Assume there is no software like google maps. you are given a map of world. Suppose you are somewhere in the hyderabad.

You will have to figure out all the paths from your location to Hyderabad airport.

I have given DFS approach. But the problem is that by doing DFS, a path can cross boundaries of Hyderabad and go so long away from Hyderabad

airport. DFS will take some much time. How to solve this problem?

- 2of 2 votes
Convert a string with digits into a literal representation of the number like: 1001 to one thousand one

- 0of 0 votes
`We encode a string, s, by performing the following sequence of actions: Replace each character with its ASCII value representation. Reverse the string. For example, the table below shows the conversion from the string "Go VMWare" to the ASCII string "711113286778797114101": // Character G o V M W a r e // ASCII Value 71 111 32 86 77 87 97 114 101 // // We then reverse the ASCII string to get the encoded string 101411797877682311117. // // For reference, the characters in s are ASCII characters within the range 10 - 126 which include special characters. // // Complete the decode function in the editor below. It has one parameter: // encoded - A reversed ASCII string denoting an encoded string s. // // The function must decode the encoded string and return the list of ways in which s can be decoded. static Collection<String> decode(String encoded) { }`

- 2of 2 votes
Given the list of the numbers. In this list, there are the numbers from the Fibonacci sequence.

Write the algorithm that retrieves all the numbers which belong to the Fibonacci sequence of numbers.

- 2of 2 votes
Decompress string - string (s) followed by {n} denotes s repeating n times

"a(b(c){2}){2}d" decompresses to "abccbccd"

"((x){3}(y){2}z){2}" decompresses to "xxxyyzxxxyyz"