## Algorithm Interview Questions

- 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 // & //`

- 0of 0 votes
Given 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:`int getIndex(const std::vector<int>& numbers, int maxCount);`

- 0of 0 votes
Write a function to generate Random Number without using any library functions.

Extension: Write an overloaded method for the above function which accepts a Range.

- 0of 0 votes
Write 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

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

- 0of 0 votes
Given an unsorted array. for example [2, 3, 1, 4, 5].

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.

- 1of 1 vote
Tweet Recommendation

Twitter Interview Online Test

On Twitter, millions of tweets are posted on a daily basis. Help Twitter write a simple ranking algorithm to find the best of all tweets. It works as follows: A good tweet receives many “likes” from people on Twitter, either from people you follow, or people you do now follow. A tweet is more relevant to you if people you follow also liked the tweet. If enough people you follow have liked that tweet, we recommend that tweet to you.

Your task is to complete the function

getRecommendedTweets(followGraph_edges, likeGraph_edges, targetUser, minLikeThreshold), which returns a list of tweet IDs in sorted order that should be recommended for a certain user. It takes 4 parameters:

followGroup_edges stores follow relationships as an array of tuple of integers.

For example, followGraph_edges = Array{(A, B), (A, C), (B, C)} represents 3 follow relationships:

A follows B

A follows C

B follows C

likeGraph_edges stores like relationships, also in an array of tuple of integers.

For example, likeGraph_edges = Array{(A, T1), (B, T2), (A, T2)} means:

A liked tweet T1

B liked tweet T2

A liked tweet T2

targetUser is the user ID for which we generate recommended tweets

minLikeThreshold is the minimum number of likes a tweet mush receive from people you follow to be recommended

For example, if minLikeThreshold = 4, only tweets that received at least 4 likes from people you follow should be recommended

Note: If you cannot find a single tweet that meets our requirement, simply return an empty list. You may also use any functions provided by the standard library.

- 0of 0 votes
Consider an N*N game board, with a black and white pieces that can be placed on it. You are given a board with placed pieces around it in a random spots.

You need to implement a function that determines if a piece (black or white) is captured on a given coordination (x, y).

A piece is defined as captured by the following rules:

1. If all sides (up, down, left & right) contains an opposite piece that surrounds/blocking it.

2. If some of the sides are blocked (for example, right and down) and the other ones are out of bound (OOB defined for coords: x: <= 0, y: <= 0) it's considered as blocked.

3. If one of the sides is empty, it's free.

4. If one of the sides contains the same piece type, and that piece is not captured (by the rules above), it's free.

5. Note that pieces may be captured in a clustered way (related to #4).

For example, consider the following coordinates:

coord(1,1) = B

coord(1,2) = W

coord(2,1) = W`X | 1 | 2 1 | B | W 2 | W |`

For the given coordination 1,1 the result would be `captured` (true).

Another example, consider the following coordinates:

coord(2,2) = W

coord(2,3) = W

coord(3,1) = W

coord(3,2) = B

coord(3,3) = B

coord(3,4) = W

coord(4,2) = W

coords(4,3) = W`X | 1 | 2 | 3 | 4 | 5 | 2 | E | W | W | W | E 3 | W | B | B | B | W 4 | E | W | W | W | E`

For the given coordination 3,2 (or 3,3) the result would be `true` (captured).

If we would either remove one of the W coords (thus making it empty), or change it to be a B piece, the result would be `false` (not captured).

As basic primitive, you are provided with a function that translates coordination into its state:`getState (x, y) == Black, White, Out Of Bound, Empty`

- 2of 2 votes
Hacking Time

Twitter Interview Online Test

Alice and Bob are avid Twitter users and tweet to each other every day. One day, Alice decides to send Bob a secret message by encrypting it and tweeting it publicly to Bob. They had anticipated a scenario like this, and exchanged a shared secret key some time in the past. Unfortunately, Alice isn’t very familiar with encryption algorithms, so she decides to make her own. Her encryption algorithm works as follows:

1. Choose a key entirely composed of digits 0 - 9, for example: 12345.

2. Iterate each letter of the plaintext message and rotate the letter forward a number of times equal to the corresponding digit in the key. If the rotation of the letter passes Z, start back at A.

3. If the message is longer than the key, loop back to the first digit of the key again, as many times as needed.

4. If a non-alphabetical character is encountered, leave it as it is and don’t move to the next digit in the key.

5. Characters should maintain their upper or lowercase orientation after rotation.

Here is an example message and its encrypted output using Alice’s algorithm:

Original message: Hi, this is an example

Example Key: 4071321

Encrypted message: Li, ailu jw facntll

Where H was rotated forward 4 letters to L, i rotated 0 to i, t rotated forward 7 letters to a, etc.

Satisfied with the security of her algorithm, Alice tweets the following ciphertext to Bob:

Otjfvknou kskgnl, K mbxg iurtsvcnb ksgq hoz atv. Vje xcxtyqrl vt ujg smewfv vrmcxvtg rwqr ju vhm ytsf elwepuqyez. -Atvt hrqgse, Cnikg

Uh oh! Unfortunately for Alice and Bob, you are “Eve”, the world’s greatest hacker. You’ve been intercepting Alice’s messages for some time now, and know she always ends her messages with the signature “-Your friend, Alice”. You job is now as follows:

Determine the key Alice is using.

Using this key, write a function to decrypt any future communications from Alice. This method should take the encrypted string as an input and return the original unencrypted string.

- 0of 0 votes
Unsorted array and a position ‘P’. Return the element that is likely to come to the given location upon sorting the array. TC in O(n).

- 0of 0 votes
A thief trying to escape from a jail has to cross ‘N’ walls each with varying heights. He climbs ‘X’ feet every time. But, due to the slippery nature of those walls, every times he slips back by ‘Y’ feet. Now the input is given as (N, {H1, H2, H3,….Hn}, X, Y}. Calculate the total number of jumps required to cross all walls and escape from the jail.

- 0of 0 votes
Add a digit to a number that is represented by a linked list, where each node is a digit of the number. The linked list couldn’t be modified, except the digits to be modified in answer and the number could be infinitely long. Need to do it in O(1) space.

- 1of 1 vote
Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

- 0of 0 votes
Maximum difference between node and its ancestor in Binary Tree in O(n) time.

- 0of 0 votes
Given a very large binary number which cannot be stored in a variable, determine the remainder of the decimal equivalent of the binary number when divided by 3. Then generalize to remainder of any number 'k'

- 0of 0 votes
Given a pre-order traversal, construct a binary search tree in O(n) time.