## Algorithm Interview Questions

- 0of 0 votes

AnswersIts farewell day, there are total N students, every student has bought a gift to give. He/She will give this gift to some other student. After gifting process is over, you are given an array, representing number of gift student receive i.e. ith number denoting number of gift he/she got. Your task is to find, whether given gift count array is valid or not. If it is valid print any of possible way of gifting that lead given array.

- oaashifo April 08, 2019 in India for India

PS: Student can't gift to himself. Student has exactly one gift with himself.

Input: First line will have one integer M, denoting number of students. Next line wil have N spaced integers denoting number of gift student gets.

Ouput: -1, if given gift received array is not valid else print N spaced integers denoting ith gifted to jth.

Sample Input 1:

3

1 1 1

Sample Output 1:

2 3 1| Report Duplicate | Flag | PURGE

Amazon Software Developer Algorithm - 1of 1 vote

AnswersYou have a bit pattern and an infinite stream of bits coming in. You need to raise an alarm whenever the given pattern comes. Storing the stream is not allowed.

- neer.1304 April 07, 2019 in United States| Report Duplicate | Flag | PURGE

Uber SDE-3 Algorithm - 1of 1 vote

AnswersThere is a notepad which accepts only four operations:

- neer.1304 April 07, 2019 in United States

1. Character X

2. select all

3. copy

4. paste

Given n number of operations, provide the sequence of choices that gives maximum characters in the notepad.| Report Duplicate | Flag | PURGE

Uber SDE-3 Algorithm - 0of 0 votes

AnswerGiven an array find if array gets sorted by reversing any subarray of this array. Ex: In {1, 2, 3, 4, 8, 7, 6, 9} we can reverse subarray from index 4 to 6.

- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersFind the sum of n elements after a kth smallest element in BST. Tree is very large, you are not allowed to traverse the tree.

- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersConsider an infinite stream of numbers. At any point print smallest k elements.

- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersGiven an array of integers(duplicates allowed) return if it is a set of contiguous integers or not?

- neer.1304 April 06, 2019 in United States

Input: 5,2,3,6,4,4,6,6 Output: Yes (as it is from set of [2,3,4,5,6])| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersGiven an array of integers with the property that arr[j] – arr[j-1] is either 1,0,-1 and a search value, provide an efficient search mechanism.

- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersGiven coin denomination of 3, 6 and 17, find the number of ways in which you can form a sum 'n'. How will do it for large numbers?

- neer.1304 April 06, 2019 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersThere is a huge road. Given are the following

- neer.1304 April 06, 2019 in United States

- Array D that stores the distance from a starting point where billboard can be installed.

- Array C that stores the profit. C[i] -> profit if the billboard is installed at distance D[i].

- dist -> minimum distance to maintain between the billboards.

Assume you can install any number of billboards while maintaining a given minimum distance 'dist' between each of them. Find the maximum profit you can achieve.| Report Duplicate | Flag | PURGE

Amazon SDE-3 Algorithm - 0of 0 votes

AnswersGiven two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.

- nemishsangani96 March 23, 2019 in India

Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?

Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?| Report Duplicate | Flag | PURGE

Algorithm Coding Computer Science Data Structures Dynamic Programming String Manipulation - 0of 0 votes

AnswersC program for the given two array as point of x and y

- Rising star March 18, 2019 in United States

int x[] = { 2,3,2,4,2};

int y[] = {2, 2, 6,5,8}; count the pair

maximum area coverd in x y plane

Ouput:3

From the above input there are five coordinates possible (2,2)(3,2)(2,6()(4,5)and (2,8) in which (2,2)(2,6)(2,8)that is three coodinaters covers the maximum area in x y plane

Input: x[] ={1,2,3}

Y[] = {1,2,3}

Output: 1

there are three coordinates (1,1)(2,2)(3,3)in which only one coordinates covers maximum distancethat is (1,3)| Report Duplicate | Flag | PURGE

Amazon Software Developer Algorithm - 3of 3 votes

AnswersGiven a dictionary of words & a miss-spelled input, write a function which will find 3 words from the dictionary which are closest (by difference of 1-character) to the given input.

- vinzee93 February 28, 2019 in United States

eg - dict = {vil, sit, flick, pat, pluck, sat, vat}, input = vit, ans = {sit, vil, vat}| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersI am given an array of Transactions in a ledger. A Transaction object has three things.

- goyalshub February 16, 2019 in United States

1. Sender (which means who started this transaction)

2. Receiver (means who is the destination of transaction)

3. Timestamp (at what time this transaction was executed)

Now I need to write a method findIfTransactionIsValid() which will have the array of all transactions, one sender, one receiver. A transaction is valid is following cases:

1. if sender and receiver are same

2. The timestamp should be increasing (what I mean here is if A -> B happens at Time 2 and B-> C happens at Time 1, then A->C is not a valid transaction, however if B -> C happens at Time 3 then A--> C is a valid transaction)

Example:

Transaction

{

Sender;

Receiver;

Timestamp;

}

Example: [T is timestamp here]

A -> B (T=0)

B -> C (T=1)

C -> F (T=0)

findIfTransactionIsValid(A, C) -> this should return true

findIfTransactionIsValid(B,F) -> false (time is backwards)

If the question is still not clear, please see the solution I wrote. I have written a recursive solution and is working but I am seeing help to improve the solution.| Report Duplicate | Flag | PURGE

unknown Software Engineer Algorithm - 0of 0 votes

AnswersThere are N countries, each country has Ai players. You need to form teams of size K such that each player in the team is from a different country.

- crowdx February 12, 2019 in India

Given N and number of players from each country and size K. Find the maximum number of teams you can form.| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 0of 0 votes

AnswersGiven 2 trees T1 & T2 (both can have > 2 childs), write an algorithm to find if T2 is a subtree of T1.

- sanjos February 09, 2019 in United States

Follow up question, for any branch in T1

a->b->c->d

the following is a valid branch in tree T2(i.e. the isSubTree() algorithm mush evaluate to true in below circumstances)

a->d

a->c->d

c->d| Report Duplicate | Flag | PURGE

Senior Software Development Engineer Algorithm - 1of 1 vote

AnswersYou are given a 2d grid where each grid item has a value of 1 or 0, you can only move horizontally or vertically and if both blocks have value of 1. You are also given a starting index, the output should have the "connected" grid items property to true.

For example:`input = [ [{value: 0}, {value: 1}, {value: 1}], [{value: 0}, {value: 0}, {value: 1}], [{value: 1}, {value: 1}, {value: 1}] ]; startRowIndex = 2; startColumnIndex = 0; output = [ [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}], [{value: 0}, {value: 0}, {value: 1, connected: true}], [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}] ];`

This is the first part of the question, this can be easily solved using either DFS or BFS.

The second part is you are given the output of the first function and the same start indices. Along with these two input arguments, you are also given a flipIndex. The grid item at the given flip index will have the value flipped. Now give the updated matrix with the updated "connected" path.

- noobtiger February 09, 2019 in United States`input = [ [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}], [{value: 0}, {value: 0}, {value: 1, connected: true}], [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}] ]; startRowIndex = 2; startColumnIndex = 0; flipRowIndex = 1; flipColumnIndex = 2; output = [ [{value: 0}, {value: 1}, {value: 1}], [{value: 0}, {value: 0}, {value: 0}], [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}] ];`

| Report Duplicate | Flag | PURGE

Software Engineer Algorithm - 0of 0 votes

AnswersGiven a list of sorted lists each of size maximum size M, implement an iterator (maintain the order of items as in the original list of lists).

- sanjos February 04, 2019 in United States

I had a solution requiring extra space using minHeap; However, the interviewer was looking for a constant space solution.| Report Duplicate | Flag | PURGE

Microsoft Software Developer Algorithm - 0of 0 votes

AnswersGiven an array of edges between any two points in 2 dimensional space. A single edge is represented by the co-ordinates of two points it is connecting for example (2,3),(4,5) represents and edge connecting points (2,3) and (4,5).Find out the total number of squares possible if all edges are parallel to X or Y axis.

- jadonv January 26, 2019 in United States

NOTE : Include overlapping squares, squares having one side in common and squares contained within another square. Co-ordinates can have float values.

Example below -

I have considered a very simple input and output combination to keep it short.

Input

{

(0,0),(0,3)

(0,0),(3,0)

(0,3),(3,3)

(3,0),(3,3)

}

Output : 1

Possible Approach : Create a map as below -

Key(Slope of Edge in Degrees) - Value(Array of Edges)

0 - {(0,0),(3,0)},{(0,3),(3,3)}

90 - {(0,0),(0,3)},{(3,0),(3,3)}

While inserting edges in the map, make sure the edges are sorted by max(x1,x2) first and then max(y1,y2).

Pick 2 edges from one slope let's say slope 0, then pick 2 edges from slope 90 and see if square is formed or not. If square not formed, then look at next 2 edges of slope 90 and so on.

Sorting here is an expensive operation.

Please share any better solutions.| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersYou have a bunch of shops. Each shops sells a bundle of chocolates at a fixed cost. You are given an amount and the price sheet of shops. Find the maximum number of chocolates that you can buy with the amount.

`Int Calculate(Int Amount, []Int Quantities, []Int Cost) { // Implement }`

Other points: (1) You cannot use 'sort' (2) The costliest shop need not sell the maximum number of chocolates. (3) Tricky cases exist. For example: Shop 1 sells 10 chocolates in a 10 $ bundle. Shop 2 sells 9 chocolates in a 1$ bundle. If you have 10$ in your hand, Here the maximum number of chocolates that you can buy is not 10 but 90.

- git January 24, 2019 in United States| Report Duplicate | Flag | PURGE

Numeric Backend Developer Algorithm - 0of 0 votes

AnswersGiven a graph in which there is an edge between (u,v) if gcd(u,v)>g . Given queries of u,v find if a path from u,v exists

- manaranjanfav January 17, 2019 in United States| Report Duplicate | Flag | PURGE

Algorithm - 1of 1 vote

AnswersGiven an integer S, you have to count the total number of integral solutions of the equation a+b^2+c^3+d^4<=S, such that 0<=a,b,c,d<=10000 and 0<S<10^15

- Ankita January 13, 2019 in United States

Edit: Here value can be less than or equal to S, so if input S= 2 ,then output=12

i.e we can consider 0,0,0,1 and 0,0,0,0 etc also as sum will be less than S(i.e 2)| Report Duplicate | Flag | PURGE

SDE1 Algorithm - 0of 0 votes

AnswersGiven two strings Y and Z , return True if y beats z or z beats y .

- saurabh January 10, 2019 in India

Beating Criteria : for i in [1,N] y[i]>=z[i] , if this condition is true for any of permutations of y for any of the permutations of z .| Report Duplicate | Flag | PURGE

Directi Software Engineer Algorithm - 0of 0 votes

AnswerHow to divide a circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array.

- him4211 January 05, 2019 in India

For e.g If the array is as follow. [6 13 2 10] and k=2 then o/p should be 16(6+10)-15(13+2)=1. As array is circular 6,10 are contiguous element of array.

For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29| Report Duplicate | Flag | PURGE

Samsung Software Developer Algorithm - 0of 0 votes

AnswersGiven a target number and a single number, write a program to find the shortest path to calculate the target number by applying "+-*/" operations to the single number. No parentheses. For example, if we have target number=26 and single number=3 return 3 * 3 * 3 - 3 / 3.

- morfysster January 03, 2019 in United States| Report Duplicate | Flag | PURGE

Algorithm - 3of 3 votes

AnswersGiven a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles

- nikki December 31, 2018 in United States

Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm - 0of 0 votes

Answerscode Bubble sort, and modify it to return if the array is already sorted.

- reshma.dhotre November 30, 2018 in India

2.If single swap is needed perform and break without going through o(n2) looping| Report Duplicate | Flag | PURGE

Bloomberg LP Senior Software Development Engineer Algorithm - 0of 0 votes

AnswerIn a hashtable you can only ask for the most recent value for a key. We are going to build a hashtable where you can ask for a key at any time in the past.

- SwampNight November 29, 2018 in United States

API is:

get(k, t) // get the value for k at time t

put(k, v) // insert k, v at time()

time is given as a monotonically increasing version of unix system time.| Report Duplicate | Flag | PURGE

Software Engineer / Developer Algorithm - 0of 0 votes

AnswersGiven a string S of length N. Now, you need to cut the string S into K+1 non-empty substrings by performing K cuts.

- Jatin November 25, 2018 in India for 3

There are lots of ways of performing the cuts in the string S. For every way of performing the cuts, you need to count how many substrings will be a palindrome in that way of cut. You need to sum this count over all possible ways of cutting the string S. Input Format

The first line contains two integers N and K as input. The second line contains the string S as input. Output Format

In the output, you need to print the sum modulo

10^9+7. Constraints

2≤N≤5000

1≤K≤N−1

String S contains only lowercase english alphabets

Sample Input

5 2

aabbc

Sample Output

12

Explanation

In the given test case there are

6 ways to perform the cuts. All the ways are described below.

a | a | bbc = 2 substrings are palindrome

a | ab | bc = 1 substring is palindrome

a | abb | c = 2 substrings are palindrome

aa | b | bc = 2 substrings are palindrome

aa | bb | c = 3 substrings are palindrome

aab | b | c = 2 substrings are palindrome

So, the output is

2+1+2+2+3+2=12| Report Duplicate | Flag | PURGE

Backend Developer Algorithm

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

Open Chat in New Window