## Algorithm Interview Questions

- 1of 1 vote

AnswersWhat's the algorithm to transform the sentence "the brown fox ran fast" in "eht nworb xof nar tsaf" (reverse any word)

- rignanese.leo November 02, 2017 in Europe| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 0of 0 votes

AnswerToday Jin has given a task to Shino, Shino has to travel from cell

- pooja.senger86 October 29, 2017 in United States

(

1

,

1

)

(1,1) to cell

(

N

,

M

)

(N,M) in a grid of size

N

∗

M

N∗M. But in order make this task interesting for Shino, Jin has decided to keep some special candies in some

K

K special cells of the grid, where each candy has an amount of happiness associated with it.

Shino can travel only in right & down direction in the grid, as he is too careful & does not want to fall out of grid. Now, we call the value of a path the happiness of all cells lying on the path. All non-special cells have happiness equal to

0

0.

Now, you need to find and print the sum of the values of all paths from

(

1

,

1

)

(1,1) to

(

N

,

M

)

(N,M), traveling only right and down to an adjacent cell.

As Shino is not good at counting help him find the answer.

Input Format

The first Line contains a single integer

T

T denoting number of test cases

The next line contains

3

3 space separated integers,

N

N,

M

M and

K

K where N * M is the size of grid & K denoting number of special cells

The next

K

K lines contains three integers

X

i

,

Y

i

,

H

i

Xi,Yi,Hi where

(

X

i

,

Y

i

)

(Xi,Yi) is cell coordinate &

H

i

Hi is the amount of happiness Shino will get from a candy at cell

(

X

i

,

Y

i

)

(Xi,Yi)

Constraints

1

≤

T

≤

3

1≤T≤3

1

≤

N

,

M

,

K

≤

10

5

1≤N,M,K≤105

1

≤

X

i

≤

N

,

1

≤

Y

i

≤

M

1≤Xi≤N,1≤Yi≤M

1

≤

H

i

≤

10

5

1≤Hi≤105

Output Format

For each test case you will output a single integer denoting the total amount of happiness Shino will get. As the answer can be quiet large you can output answer modulo

10

9

+

7

109+7

Sample Input

1

2 2 2

1 2 4

2 1 7

Sample Output

11| Report Duplicate | Flag | PURGE

A9 abc .Net/C Algorithm Java - 1of 1 vote

AnswersYou are a game developer working on a game that randomly generates levels. A level is an undirected graph of rooms, each connected by doors. The player starts in one room, and there is a treasure in another room. Some doors are locked, and each lock is opened by a unique key. A room may contain one of those unique keys, or the treasure, or nothing.

- robert October 24, 2017 in United States

Implement a representation for a level and write code that, given a level and starting room, returns true if the treasure can be reached by the player—likely requiring them to find certain other keys first—or false if there is no solution.| Report Duplicate | Flag | PURGE

Google Software Engineer Intern Algorithm - 0of 0 votes

AnswersFind the distance between the farthest two elements in a binary tree.

- nra October 19, 2017 in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm - 0of 0 votes

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

- akira October 19, 2017 in United States

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

*

***

**| Report Duplicate | Flag | PURGE

Nutanix Software Developer Algorithm - 0of 0 votes

Answers

- Anonymous October 13, 2017 in United States for Seattle`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.`

| Report Duplicate | Flag | PURGE

Uber Software Engineer Algorithm - 0of 0 votes

AnswersGiven an unsorted array of unique integers, find two numbers in the array whose sum is equal to a given number.

- CoolGuy October 13, 2017 in India| Report Duplicate | Flag | PURGE

Algorithm - 2of 2 votes

AnswerAirbnb Online Assessment Paginate List

- aonecoding October 13, 2017 in United States

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

Airbnb Software Engineer Algorithm - -2of 6 votes

AnswersHow will you test "Hello world" program?

- gagan.ping October 12, 2017 in India| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 2of 2 votes

AnswersFind the indices of all anagrams of a given word in a another word.

- aonecoding October 09, 2017 in United States

For example: Find the indices of all the anagrams of AB in ABCDBACDAB (Answer: 0, 4, 8)| Report Duplicate | Flag | PURGE

Amazon Software Engineer Algorithm - 1of 1 vote

AnswersAll jumbled numbers of n digits in max (worst case) O(n) and min (avg case) O(log n) time.

- mani0119 October 08, 2017 in India

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

Amazon Software Engineer / Developer Algorithm - 1of 1 vote

AnswersGiven two list of unsorted intervals V1 and V2 write 2 functions 'OR ' and 'And' to return a new list

- sachin323 October 05, 2017 in United States

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

Uber Software Engineer Algorithm - 0of 0 votes

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

- lkjhgfdsa September 30, 2017 in United States

Test Case I: ["ab", "ab", "abc", "bca"]

Answer: 3

Test Case II: ["ab","aqb"]

Answer: 0| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 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 - 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

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

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

Open Chat in New Window