## Algorithm Interview Questions

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

- 1of 3 votes
A message containing letters from A-Z is being encoded to numbers using the following mapping:

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

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

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

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.

- 1of 1 vote
create a class of integer collection,

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

- 0of 0 votes
Lonely Pixel

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

- 1of 1 vote
SuperCity 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:

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.

- 0of 0 votes
Design an efficient hash function to perform 2D hashing.

Your function should be O(1) time and should minimize the probability of hash collisions as far as possible.

Basically, complete the following Java code ...`class TwoDData { private int x, y; public TwoDData(int x, int y) { this.x = x; this.y = y; } public int getX() { return this.x; } public int getY() { return this.y; } @Override public int hashCode() { // COMPLETE THIS METHOD } }`

- 0of 2 votes
Given an array A of integers, having N elements.

It is desired to compute the sum of elements from index i to index j. This query is to be executed millions of times for any i, j values.

Give an O(1) implementation of this query.

You are allowed to do only one-time O(N) pre-processing.

- 0of 2 votes
Complete the following Java function

`boolean isValidIPv4Address(String input) { // true if "input" is a valid IPv4 address // false if not // Free to use any methods from these classes String/StringBuffer/StringBuilder only // Not allowed to use anything from java.net.* }`

- 0of 0 votes
The candidate had listed Chess as his hobby, and was asked the following question.

Design a data structure to represent the game of Chess.

Follow up : Write a function which returns true if enemy king is currently under Check, else returns false.

- 0of 2 votes
Design a specialized stack which supports ALL of these operations in exactly O(1) time.

`class SpecializedStack { void push(int x) { // Adds an element to this stack in O(1) time } int pop() { // removes the topmost element in O(1) time } int getMax() { // gets the largest element of this stack in O(1) time } }`

- 0of 2 votes
Two words are called anagrams if one word can be formed by shuffling the letters of another word.

e.g. "hello" and "ollhe" are anagrams.

"listen" and "silent" are anagrams.

But, "cab" and "bag" are NOT anagrams.

Problem : Given a list of English words (all lowercase), write a function to "group" the anagrams together.

e.g. Input = {"abc", "def", "cab", "money", "bca", "yomen"}

Output =

{"abc", "cab", "bca"}

{"def"}

{"money", "yomen"}

Within each "group", the anagrams can occur in any sequence.

Also, sequence of groups is irrelevant.

Expected time complexity = O(NK^2), for N words with longest word length = K.

- 0of 0 votes
There are billions and billions of stars in the universe. Which data structure would you use to answer the query

"Give me the k stars nearest to Earth".

Expectation is to come up with the list of parameters/fields in the data structure as well.

- 0of 0 votes
Detect if a given 2D matrix is a valid solution to a valid Sudoku puzzle or not.

Basically, you are given a (N^2) x (N^2) matrix where every cell has an integer value. Check if it is a valid Sudoku or not.

- 0of 0 votes
There are N number of houses in a straight line. House at index i has valuables worth V[i].

A thief is planning to rob as many houses as possible on this straight line.

Constraint : If he robs house at index i, then he cannot rob houses at indices (i - 1) and (i + 1).

Maximize the total value of valuables which he can rob.

- -1of 1 vote
Give an O(N) time and O(1) memory function to check whether an array of integers is sorted in ascending order or not.

`public boolean isSortedArray(int[] A) { // complete this code ... }`

- 0of 0 votes
Given a 2D matrix A of size m x n, m > 0, n > 0 such that A[i][j] <= A[i][j + 1] and A[i][j] <= A[i + 1][j].

Write a C/C++/Java function to get the k-th smallest element from this matrix.

- 1of 1 vote
Given 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.`// // 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 // & //`