## Algorithm Interview Questions

- 0of 0 votes

AnswersCheck if two DOM Trees have the same text.

- wtcupup2017 September 28, 2017 in United States

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)| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 3 votes

AnswersA message containing letters from A-Z is being encoded to numbers using the following mapping:

- MM September 26, 2017 in United States

'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).| Report Duplicate | Flag | PURGE

SDE-2 Algorithm - 0of 0 votes

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

- NoOne September 25, 2017 in India| Report Duplicate | Flag | PURGE

Goldman Sachs Software Architect Algorithm - 0of 0 votes

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

- tnutty2k8 September 22, 2017 in United States

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.| Report Duplicate | Flag | PURGE

Algorithm - 1of 1 vote

Answerscreate a class of integer collection,

- aonecoding September 22, 2017 in United States

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| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersLonely Pixel

- aonecoding September 22, 2017 in United States

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))| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 1of 1 vote

AnswersSuperCity 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:

- new September 22, 2017 in United States

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.| Report Duplicate | Flag | PURGE

Google Algorithm - 0of 0 votes

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

- Interviewer September 19, 2017 in India`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 } }`

| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - 0of 2 votes

AnswerGiven an array A of integers, having N elements.

- Interviewer September 19, 2017 in India

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.| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - 0of 2 votes

AnswersComplete the following Java function

- Interviewer September 19, 2017 in India`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.* }`

| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - 0of 0 votes

AnswersThe candidate had listed Chess as his hobby, and was asked the following question.

- Interviewer September 19, 2017 in India

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.| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - 0of 2 votes

AnswerDesign a specialized stack which supports ALL of these operations in exactly O(1) time.

- Interviewer September 19, 2017 in India`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 } }`

| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - 0of 2 votes

AnswersTwo words are called anagrams if one word can be formed by shuffling the letters of another word.

- Interviewer September 19, 2017 in India

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.| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - 0of 0 votes

AnswerThere are billions and billions of stars in the universe. Which data structure would you use to answer the query

- Interviewer September 19, 2017 in India

"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.| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer Algorithm - 0of 0 votes

AnswersDetect if a given 2D matrix is a valid solution to a valid Sudoku puzzle or not.

- Interviewer September 19, 2017 in India

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.| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - 0of 0 votes

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

- Interviewer September 19, 2017 in India

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.| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - -1of 1 vote

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

- Interviewer September 19, 2017 in India`public boolean isSortedArray(int[] A) { // complete this code ... }`

| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer / Developer Algorithm - 0of 0 votes

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

- Interviewer September 19, 2017 in India

Write a C/C++/Java function to get the k-th smallest element from this matrix.| Report Duplicate | Flag | PURGE

Kony India Private Limited Software Engineer Algorithm - 1of 1 vote

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

- PenChief September 19, 2017 in Israel`// // 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 // & //`

| Report Duplicate | Flag | PURGE

Facebook Algorithm - 0of 0 votes

AnswersGiven 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:

- PenChief September 19, 2017 in Israel`int getIndex(const std::vector<int>& numbers, int maxCount);`

| Report Duplicate | Flag | PURGE

Facebook Algorithm - 0of 0 votes

AnswersWrite a function to generate Random Number without using any library functions.

- CodeNinja September 15, 2017 in United States for Solutions Engineering Team

Extension: Write an overloaded method for the above function which accepts a Range.| Report Duplicate | Flag | PURGE

Google Web Developer Algorithm - 0of 0 votes

AnswersWrite 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

- prashant.tah September 12, 2017 in India

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| Report Duplicate | Flag | PURGE

Booking.com Software Developer Algorithm - 0of 0 votes

AnswersGiven an unsorted array. for example [2, 3, 1, 4, 5].

- OldChang September 12, 2017 in United States

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.| Report Duplicate | Flag | PURGE

Software Engineer Algorithm - 0of 0 votes

AnswersConsider 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:

- johanson1 September 06, 2017 in Netherlands`getState (x, y) == Black, White, Out Of Bound, Empty`

| Report Duplicate | Flag | PURGE

Booking.com Software Developer Algorithm - 0of 0 votes

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

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Cisco Systems Software Developer Algorithm - 0of 0 votes

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

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Cisco Systems Software Developer Algorithm - 0of 0 votes

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

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 1of 1 vote

AnswersFind the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersMaximum difference between node and its ancestor in Binary Tree in O(n) time.

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersGiven 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'

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Microsoft SDE-2 Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window