## Algorithm Interview Questions

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

AnswersGiven a pre-order traversal, construct a binary search tree in O(n) time.

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

Microsoft SDE-2 Algorithm - 0of 0 votes

AnswersGiven a large text file, find an efficient algorithm to find the least distance(measured in number of words) between any two given words.

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

Microsoft SDE-2 Algorithm - 0of 0 votes

Answershere are tuples given for each users of a website (Si,Ei) where Si denotes the when the user entered the website and Ei denotes when the user exits the website .Find the maximum number of users active of website at any time duration.

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

Adobe MTS Algorithm - 0of 0 votes

AnswersThere is a binary stream coming . You need to print true or false based on the fact whether the number formed is divisible by 5 or not.

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

Adobe MTS Algorithm - -1of 3 votes

AnswerI am looking for a good resource to learn lossy counting sticky sampling.Can anyone point me towards good resource?I am ready for a one-to-one session too.

- koustav.adorable September 01, 2017 in United States| Report Duplicate | Flag | PURGE

Adobe Algorithm - 1of 1 vote

AnswersYou are given a text file. You have to return the list of starting index of the given word in text file. Design an efficient DS for that.

- neer.1304 September 01, 2017 in United States

Example :-

Text file content : “geeks for geeks”

word : “geeks”

List : {0,10}| Report Duplicate | Flag | PURGE

Microsoft SDE-2 Algorithm - 0of 0 votes

AnswersIn a file, there are two columns, first column has some word (String) and 2nd column has some value (Double).

- neer.1304 September 01, 2017 in United States

Example :-

ABC 23.4

ERF 34.89

WERT 122.9

Now user wants some arithmetic operations like

1) ABC + ERF = 23.4 + 34.89 = 58.29

2) ABC – WERT = 23.4 – 122.9 = -99.5

Design an efficient DS for these kind of operations.| Report Duplicate | Flag | PURGE

Microsoft SDE-2 Algorithm - 0of 0 votes

AnswersGiven a remote having 0-9 digits, plus button (to increase channel), minus (to decrease) and previous channel button (to go to previous channel). We were given 2 numbers stating start and end channel number and an array having various channel numbers. The task was to go to all channel numbers given in array with minimum number of clicks.

- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE

Goldman Sachs Backend Developer Algorithm - 0of 0 votes

AnswersGiven MxN binary matrix, find the largest sub-square matrix with all 1’s.

- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersGiven an array of integers. We need to answer two types of queries point update and range sum in minimum time.

- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersPut the given random pointers in linkedlist to point to next greater node such that if you transverse the list using random pointers, list become sorted. duplicates are allowed.

- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 1of 1 vote

AnswersFind third highest value in a binary tree

- neer.1304 August 31, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersThere are n Thread , n/2 thread are producer and n/2 are consumer, number produced by producer-1 thread must be consumed by consumer-1 thread. Thread must also run in order, producer 1, then consumer 1, again producer 2 and then consumer 2…so on…..

- neer.1304 August 31, 2017 in India| Report Duplicate | Flag | PURGE

One97 SDE-2 Algorithm - 0of 0 votes

AnswerImplement function which add n days to given date without using inbuilt library.

- neer.1304 August 31, 2017 in India| Report Duplicate | Flag | PURGE

One97 SDE-2 Algorithm - 0of 0 votes

AnswersYou are given a set of N horizontal lines which are connected by equal number of vertical lines to form squares of size 1x1. Now some segments are removed. You need to count the number of squares of all sizes (1x1, 2x2, ..., NxN) with all sides present.

- imunique August 30, 2017 in India

Image : https://he-s3.s3.amazonaws.com/media/uploads/1ce3516.png

In the above example you see four horizontal and vertical lines and few missing segments. Now you need to count the number of squares of all sizes with all sides.

Input :

First line is a positive integer N, number of horizontal and vertical lines.

Second line is positive integer M, number of segments removed.

Then there are m lines, each containing V,i,j or H,i,j where i and j are positive integers. H,i,j indicates a horizontal missing segment in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in ith vertical line between the jth and (j+1)th point on the line.

Output :

Is the total number of squares in the figure with all sides along the remaining lines in the figure.

Sample Input :

4

4

H,2,1

H,3,1

V,2,2

V,2,3

Output :

5

Explanation : Here in this figure we have 4 squares of size 1x1 and 1 square of size 3x3, hence total is 5.| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm Data Structures Dynamic Programming Online Test Problem Solving - 1of 1 vote

AnswerIII. Square root of a number?

- aonecoding August 30, 2017 in United States

IV. Expression operators? Add signs (+, -, *, /) to a string to form target

V. Top trending posts in last 5m, 1H, 1Day?| Report Duplicate | Flag | PURGE

Linkedin Software Engineer Algorithm - 0of 0 votes

AnswersI. Closest K nodes to a target in BST? (Do it in O(n)?)

- aonecoding August 30, 2017 in United States

II. Nested List sum?| Report Duplicate | Flag | PURGE

Linkedin Software Engineer Algorithm - 2of 2 votes

AnswersGenerate a random binary tree, with equal probability.

- pb August 30, 2017 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven data of millions of people, (name, age, M/F etc.) Develop an API that will have age range as input and yield the count of people under this range as output.

- neer.1304 August 30, 2017 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 1of 1 vote

AnswerA T20 match is going on. You’re in Team B. First innings is over, they have scored “teamARuns” runs. Your team has scored “teamBRuns” runs at the end of “balls” balls. A ball can have multiple possibilities like [0, 1, 2, 3, 4, 5, 6, Wicket, No ball, Wide ball]. What is the probability that your team (Team B) will win?

- neer.1304 August 30, 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