## Algorithm Interview Questions

- 0of 0 votes

AnswersGiven a binary matrix of size M * N. You are given H and V where H denotes the number of horizontal cuts and V represents number of vertical cuts. You need to find whether you can make H and V amount of cuts such that each submatrix formed after the cuts will have equal number of 1. E.g.

- neer.1304 May 16, 2020 in United States

4 5

1 1 1 1 1

0 0 1 1 1

0 1 1 1 1

1 0 1 1 1

Given H=1 and V=3, we can make 1st horizontal cut after 2nd row and 3 vertical cuts after 2nd, 3rd and 4th column such that each of the sub matrix will have equal number of 1s.

| ----------------|

| 1 1 | 1 | 1 | 1 |

| 0 0 | 1 | 1 | 1 |

| ----------------|

| 0 1 | 1 | 1 | 1 |

| 1 0 | 1 | 1 | 1 |

| ----------------|| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswerGiven 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 is to go to all channel numbers given in array with minimum number of clicks.

- neer.1304 May 16, 2020 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersSmallest string

- sobby May 03, 2020 in India

You are given the following :

1. Two strings S and T each of Length N

2. K Pairs of integers L(i) and R(i) (0 <= l(i) < R(i) <= N-1)

You can perform any of the following two operations any number of time.

1. You can replace the character of string S at the ith position with the character of string T at the ith position

2. You can select from any provided K pairs and you are allowed to swap characters at position L(i) and R(i) in string T

Now, you are required to perform all the operations optimally so that string S can be lexographically smallest.

All characters of S and T are of lowercase English letters and there are only two ways to perform all the operations either(111...1) then (2222...2) or (2222...2) then (1111.1)

Input Format :

1. First line contains number of test cases:

2. Second line contains the lengths of string and the number of pairs of integers.

3. Next two line contains S and T two strings.

4. The next K lines contains the space separated integers.

Sample Input :

1

8 4

abagfiab

cbacbcda

0 1

1 2

3 4

4 5

sample output : aaabccaa| Report Duplicate | Flag | PURGE

PayPal SDE-3 Algorithm - 0of 0 votes

AnswersYou are given a list of n people and also a list of m pairs who know each other.

- ff987456321 April 25, 2020 in France

Here is an example input:

List of people: x1, x2, x3, . . . , xn

People who know each other: (x1, x2),(x1, x4),(x2, x4),(x2, x5),(x2, x6),(x4, x5),(x4, x6), . . .

1. Given a positive integer k, write an integer program that finds k people among the given n people with

the maximum number of pairs who know each other. How many variables and constraints are there?

2. Write an integer program that finds the maximum number of people where everyone knows each other. How many variables and constraints are there?| Report Duplicate | Flag | PURGE

Algorithm - 0of 0 votes

AnswersYou are given 2 arrays: one representing the time people arrive at a door and other representing the direction they want to go(in or out) You have to find at what time each person will use the door provided no 2 people can use the door at the same time. Constraints: the door starts with ‘in’ position, in case of a conflict(2 or more people trying to use the door at the same time), the direction previously used holds precedence. If there is no conflict whoever comes first uses the door. Also if no one uses the door, it reverts back to the starting ‘in’ position. Should be linear time complexity.

- neer.1304 April 21, 2020 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersWAP to create two threads . One threads check whether

- computersengineers43 April 01, 2020 in United States

the number is even or odd while the second threads finds factorial of a numbers.| Report Duplicate | Flag | PURGE

Algorithm - 2of 2 votes

AnswersI was asked to sort extra large file 10GB which contains single word in each line, within 4GB RAM. I told External sort and optimised it with min-heap but interviewer was asking to optimise disk I/O. As last he told that use CS fundamentals. Don't know what was he expecting. Please help.

- sulabh.shkl March 22, 2020 in India| Report Duplicate | Flag | PURGE

Microsoft Software Developer Algorithm - 0of 0 votes

AnswersGiving an array of stock prices, find an algorithm of a maximum profit of a series of transactions with a constraint of purchasing one unit at any purchasing transaction.

- fz February 14, 2020 in United States

For example, stock prices

{5, 6, 3, 5, 4, 6, 7}

The transaction sequence would be the following for a maximum profit:

buy on the first day(price 5) and sell on the second day (price 6)

buy on the third day (3) and sell on the 4th day (price 5)

buy on the 5th day and sell on the 7th day (price 7)| Report Duplicate | Flag | PURGE

Software Engineer Algorithm - 0of 0 votes

AnswersThe question is basically on trees

- Noob January 19, 2020 in United States

1

2 3

4 5 6 7

You can lock any node, Once the node is locked all the ancestors and descendents of that node are also locked. You cannot acquire a lock on a node which is already locked.

You can unlock the node on which you have acquired a lock.

Implement it using multithreading.| Report Duplicate | Flag | PURGE

AMD Algorithm - 5of 5 votes

AnswersGiven K sorted (ascending) arrays with N elements in each array, implement an iterator for iterating over the elements of the arrays in ascending order.

The constructor receives all of the input as array of arrays.

You need to implement the MyIterator class with a constructor and the following methods:`class MyIterator<T> { T next(); boolean hasNext(); }`

You are allowed to use only O(K) extra space with this class.

example:

input:`[[1,5,7], [2,3,10],[4,6,9]]`

The iterator should return:

- torchs January 13, 2020 in Israel`1,2,3,4,5,6,7,9,10`

| Report Duplicate | Flag | PURGE

Facebook Solutions Engineer Algorithm - 0of 0 votes

AnswersQ. find the number of ways a string can be formed from a matrix of characters.

- tusharrawat831 December 29, 2019 in United States

It can start forming a word from any position in mat[i][j] and can go in any unvisited direction from the 8 directions available across every cell [i][j].

sample case :

input:

N = 3 (length of string)

string = fit

matrix :

fitptoke

orliguek

ifefunef

tforitis

output: 5

explanation:

num of ways to make 'fit' from matrix chars are 5 as given below sequence:

(0,0) (0,1)(0,2)

(2,1) (2,0)(3,0)

(2,3) (1,3)(0,4)

(3,1) (2,0)(3,0)

(2,3) (3,4)(3,5)

How can we solve it efficiently without doing DFS across every position [i][j], which makes time complexity exponential?

Is there a better way possible in terms of time complexity? Maybe caching of values or something!| Report Duplicate | Flag | PURGE

Software Engineer Algorithm - 1of 1 vote

AnswersThere is a 2D matrix of 0s and 1s that depicts the number of rooms that can be formed by a co-working space company like WeWork based on the values. 1 means open space for room and 0 means wall. We need to group as many 1s and possible to form the largest and minimum number of rooms.

- Jigisha Aryya December 25, 2019 in India

E.g.

Number of Rows = 5, Number of Columns = 5

00010

01110

01100

01101

00011

Output: 4

Input 2:

4

3

001

111

011

100

Output: 4| Report Duplicate | Flag | PURGE

unknown Backend Developer Algorithm - 2of 2 votes

AnswersHere is a question from the "Cracking The Coding Interview" book with a twist.

- fz December 17, 2019 in United States

Implement a method to perform basic string compression using the counts of repeated characters. (p. 73 5th edition)

The twist: the string can also contain digits. Think of encoding and decode protocol. How the compression can be reversed properly?

For example, ab2ccccd -> ab24cd| Report Duplicate | Flag | PURGE

Amazon Algorithm - 1of 1 vote

AnswersGiven a matrix, find all its combinations by row. For example,

- fz December 11, 2019 in United States

[a, b, c]

[d, e, f]

[x, y, z]

its combinations are adx, ady, adz, bdx, …. cfy, cfz| Report Duplicate | Flag | PURGE

Algorithm - 1of 1 vote

AnswersRearrange a LinkedList:

- fz December 11, 2019 in United States

Before : a->x->b->y->c->z

After : a->b->c->z->y->x| Report Duplicate | Flag | PURGE

Algorithm - 2of 2 votes

AnswersA list of relation is given. We need to express the relation in a single line with the largest unit leftmost.

- accessdenied December 09, 2019 in United States

eg.

a = 10b

b=5c

c = 20a

e=20d

a=10b=25e=50c=500d| Report Duplicate | Flag | PURGE

Algorithm - 2of 2 votes

AnswersGiven a list of 2d points, if any two points have distance(straight line) <= k , group them together. For example. [P1,P2,P3], P1 to P2 <=k, P2 to p3<=k, p1 to p3>k. they are still in the same group. (distance relationship is chainable ) ask how many groups can you find ? I can think of N^2 time complexity with union and find. but how to do better than that? maybe NlogN or O(N)?

- laoen November 30, 2019 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersFind the first N words with the highest frequency in an array of strings. The result needs to be sorted by frequency.

- fz November 26, 2019 in United States

For example:

An array of String:

Inputs:

{"geeks", "for", "geeks", "a", "portal", "to", "learn", "can", "be", "computer", "science", "zoom", "yup", "fire", "in", "be", "data", "geeks"}

and the first 2 words with the highest frequency.

Outputs: {'geek", "be"}

where "geek" has a frequency of 3 and "be" has a frequency of 2.| Report Duplicate | Flag | PURGE

Algorithm - 0of 0 votes

AnswersGiven someone's favorite songs (as a map) and a genre category (as a map as well). Find out this person's most favorite genre. For example,

- fz November 25, 2019 in United States

"David": ["song1", "song2", "song3", "song4", "song8"],

"Emma": ["song5", "song6", "song7"]

and

"Rock": ["song1", "song3"],

"Dubstep": ["song7"],

"Techno": ["song2", "song4"],

"Pop": ["song5", "song6"],

"Jazz": ["song8", "song9"]

Output:

"David": "Rock"

"Emma": "Pop"| Report Duplicate | Flag | PURGE

Algorithm - 0of 0 votes

AnswersGiven a list of a string which is a list of words separated by a space. Sort the list in the lexicographical order. For example, given the followings:

- fz November 25, 2019 in United States

[act car]

[air dog]

[act zoo]

Result:

[act car]

[act zoo]

[air dog]| Report Duplicate | Flag | PURGE

Algorithm - 2of 2 votes

AnswerWas asked at GHCI Bangalore at their booth for a prize and perhaps hiring interns or experienced software developers.

- jaryya@hawk.iit.edu November 10, 2019 in India

Find the return value for N=100

int returnAns(int N){

int ans=0;

for(int i=0; i<N; i++){

for(int j=i+1; j<N; j++){

ans +=((i & -i) == (j & -j)?1:0); //the question missed the condition and was returning a boolean, so I added it myself

}

}

return ans;

}

My answer: 0 ; their answer: 1610, hence got it wrong.

My explanation: I assumed negative of i in binary to be

simply represented by setting the MSB to 1 e.g. for 8 bit representation of 3: +3 is 0000 0011 and -3 is 1000 0011. In the inner loop the value of ans will always evaluate to 0 since Bitwise & of these i and -i or j and -j will always result into i and j respectively. (undergrad computer organization concept.)

Negative numbers can also be represented as 1s and 2's complement and in all modern machines by architecture its 2s complement.

Now if we assume 1's complement, +3: 0000 0011 and -3: 1111 1100. so bitwise & of these two is 0 and so the value of ans will always be incremented by 1. By two loops 100+99+98+97+...+1 = 100*101/2 (i.e. n*(n+1)/2)

Then 2's complement, which is the most relevant representation of signed binary numbers.

Odd numbers:

+3: 0000 0011 -3: 1111 1101 Binary & is 0000 0001.

For all even numbers:

+4: 0000 0100 and -4: 1111 1011+0000 0001 = 1111 1100 and Bitwise & of 4 and -4 is 0000 0100 which is 4.

So, in the innermost loop ans is incremented by 1 when i is odd and j is also odd. ie. when i is 1, 3, 5, 7... 97 and j is 3, 5, 7, 9,...,99 ans is added 1(return value of true ==) when calculated it comes to 1610.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 1of 1 vote

AnswersI was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:

- Jaysun October 26, 2019 in United States

There's a list of (x,y) points and a method getCircle with the following signature:

/**

* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference

* or it returns null if no such circle is possible.

*/

Circle getCircle(point1, point2, point3);

getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.

The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?| Report Duplicate | Flag | PURGE

Google SDE-2 Algorithm - 1of 1 vote

AnswersYou have a table :

- mukesh.scorp October 23, 2019 in United States

Rule1 Rule2 Rule3 Value

A1 B2 C3 40

A1 B1 C1 20

A2 B2 C2 10

A1 B1 C1 40

* B1 * 20

A5 B2 * 10

Now if I have a condition A1 && B2 && C3 i will get output as 40.

If I input A1 && B1 && C1 I will get two results 40 and 20 here there the rule is ambiguous.

"-" in table means any rule, 5th row matches with any row with B1 as rule2, so there is also ambiguity in result.

Now given that table as input (m * n) where n is number of available rules combination (here its 6) and m rules (3 in this case) , output if the table is ambiguous i.e it will output two different result for same query.| Report Duplicate | Flag | PURGE

Google Backend Developer Algorithm - -2of 2 votes

AnswersGiving a the following:

- xi.text.xi October 22, 2019 in United States for none

A list of a store items T={t_1, t_2,...,t_n}.

A list of prices of each item P={p_1, p_2,...,p_n}.

A list of quantities of each item Q={q_1, q_2,...,q_n}, respectively.

And total bill M.

Our goal is to find any possible list of items that its total value is equal to M using dynamic problem.

Write down a recursive solution.| Report Duplicate | Flag | PURGE

Amazon Software Engineer Algorithm - 0of 0 votes

AnswersSuppose two arrays are given A and B. A consists of integers and the second one consists of 0 and 1.

- AN October 11, 2019 in India

Now a operation is given - You can choose any adjacent bits in array B and you can toggle these two bits ( for example - 00->11, 01->10, 10->01, 11->00) and you can perform this operation any number of times.

The output should be the sum of A[0]*B[0]+A[1]*B[1]+....+A[N-1]*B[N-1] such that the sum is maximum

During the interview, my approach to this problem was to get the maximum number of 1's in array B in order to maximize the sum.

So to do that , I first calculated the total number of 1's in O(n) time in B. Let count = No. Of 1's=x

Then I started traversing the array and toggle only if count becomes greater than x or based on the elements of array A(for example : Let B[i]=0 and B[i+1]=1 & A[i]=51 and A[i+1]=50

So I will toggle B[i] B[i+1] because A[i]>A[i+1])

But the interviewer was not quite satisfied with my approach and was asking me further to develop a less time complex algorithm.

Can anyone suggest a better approach with lesser time complexity??| Report Duplicate | Flag | PURGE

Software Developer Algorithm - 0of 0 votes

AnswersWrite a method that merges a fixed number of streams containing an infinite sequence of monotonically increasing integers into an output stream of monotonically increasing integers. It is important to note that the input stream are infinite, so any solution based on the length of the streams would be considered incorrect.

Note that the question was given in the context of Java with the below code given as the base contract for the method.`public void merge(List<Stream> inputStreams, Stream outputStream) { // Implement me }`

This was also provided as the definition of "Stream" in this case, and not what is defined in java.util.stream.Stream.

- gr1ml0ck October 05, 2019 in United States`interface Stream { // Retrieves but does not remove the next item from the stream int peek(); // Retrieves and removes the next item from the stream. int poll(); // Puts an item into the stream void put(int i); }`

| Report Duplicate | Flag | PURGE

Amazon Solutions Engineer Algorithm - 0of 0 votes

AnswerGiven a square (n x n) matrix which only contains 0 and

- danishm026 September 29, 2019 in India

1. Find the minimum cost to reach from left most column to rightmost column.

Constraints/rules:

a. Starting point: You can start from any cell in the left most column i.e. (i, 0) where i can be between 0 and n( number of rows/ columns)

b. Destination: You can reach any cell in the rightmost column i. e ( k, n) where k can be anything between 0 and n.

c. You cannot visit a cell marked with 0.

d. Cost is defined as the sum of cells visited in path.

e. You can move up, down, left and right but not diagonally.

For example,

take 2x2 matrix

1 | 0

1 | 1

One possible path is 00 -- 10 -- 11 with cost 3

Other one is 10 -- 11 with cost 2

so minimum cost on this case is 2.| Report Duplicate | Flag | PURGE

unknown Random Algorithm Data Structures - 0of 0 votes

AnswersN cows are standing at the origin on x-axis, each cow has some appetite, in other word hunger index. A cow can sleep of 1 unit of time or eat for one unit of time or move left or move right. There are some vessels placed on the x-axis, they are having infinite supply of fiod. Find minimum time in which all cows appetite would be filled.

- xyz September 15, 2019 in United States

Input:

cow Apetitte = {1,1}

Vessle locations = {-1,1}

Answer would be 2 since both cow can go in different direction they would eat for one seconds. One second for moving and one second for eating.

This problem looks to be similar to rotten eggs/tomatoes.| Report Duplicate | Flag | PURGE

Allegient SDE-2 Algorithm - 1of 3 votes

AnswersA special palindrome is a palindrome of size N which contains atmost K distinct characters such that any prefix between the size 2 to N-1 is not a palindrome.

- Prashanthwagle360 September 08, 2019 in India

You need to count the number of special palindromes

For example, abba is a special palindrome with N=4 and K=2 and ababa is not a special palindrome because aba is a palindrome and its a prefix of ababa.

If N=3, K=3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So answer will be 6.

Input format

Two integers N and K

Output format

Answer modulo 10^9+9

Constraints

1<=N,K<=10^9

Sample TC

3 3

Output

6| Report Duplicate | Flag | PURGE

HackerEarth Problem Setter Algorithm - 1of 1 vote

AnswersGiven a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

- Nits September 07, 2019 in United States| Report Duplicate | Flag | PURGE

Facebook Software Development Manager Algorithm

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

Open Chat in New Window