## Algorithm Interview Questions

- 77of 79 votes

AnswersYou have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

- ericaturner0 April 01, 2013 in United States

For example,

List 1: [4, 10, 15, 24, 26]

List 2: [0, 9, 12, 20]

List 3: [5, 18, 22, 30]

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 44of 48 votes

AnswersPots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to "maximize" the number of coins collected by A, assuming B also plays optimally. A starts the game.

- 352905 February 12, 2013 in United States

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

At the end I was asked to code this strategy!| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 33of 39 votes

AnswersGiven an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.

- LAP June 10, 2013 in United States

* The sub-arrays should not overlap.

eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16

I gave him o(n^2) algorithm but he was not satisfied.| Report Duplicate | Flag | PURGE

Google Algorithm - 33of 35 votes

AnswersA k-palindrome is a string which transforms into a palindrome on removing at most k characters.

- sc.shobhit August 28, 2013 in India

Given a string S, and an interger K, print "YES" if S is a k-palindrome; otherwise print "NO".

Constraints:

S has at most 20,000 characters.

0<=k<=30

Sample Test Case#1:

Input - abxa 1

Output - YES

Sample Test Case#2:

Input - abdxa 1

Output - No| Report Duplicate | Flag | PURGE

Facebook Intern Algorithm - 29of 29 votes

AnswersGiven string say ABCGRETCABCG and substring length let us take length as 3, find the count of possible substrings, for example in above string ABC => 2 and BCG => 2 , where CGR and other 3 word length substrings has a count of 1.

- softwaregeek December 08, 2015 in India for Not known| Report Duplicate | Flag | PURGE

Linkedin Software Developer Algorithm - 28of 28 votes

AnswersYou are given a binary tree with the following node structure:

`struct Node { int data; // some data struct Node *left, *right; // References to left and right children struct Node *previous, *next; // References to previous and next nodes };`

The tree is initialized with previous = next = NULL for all the nodes.

- codebuddy November 21, 2010

Using the previous and next pointers construct a doubly linked list such that each node's next is the node to its right at the same level and the last node's next is the first node at the next level.(similarly previous). The algorithm should have space complexity O(1). i.e., should be done without using extra data structures.You are given a binary tree with the following node structure| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm - 27of 27 votes

AnswersWrite a program to check if the given string is repeated substring or not.

- Lakshman July 27, 2016 in India

ex 1: abcabcabc - yes - abc is repeated.

2: abcdabababababab - no.| Report Duplicate | Flag | PURGE

Ivycomptech Algorithm - 25of 25 votes

AnswersThere is an island which is represented by square matrix NxN.

- amnesiac March 01, 2013 in India

A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.

Let island is represented as (0,0) to (N-1,N-1) (i.e NxN matrix) & person is standing at given co-ordinates (x,y). He is allowed to move n steps on the island (along the matrix). What is the probability that he is alive after he walks n steps on the island?

Write a psuedocode & then full code for function

" float probabilityofalive(int x,int y, int n) ".| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 23of 23 votes

AnswersYou have a complete graph with N vertices. You know that all edges have a cost of A and you are given a set of K edges whose cost is B. Find the shortest (cheapest) path from node 0 to node N - 1.

- f.v.anton April 12, 2014

0 < N, K < 500k

1 < A, B < 500k| Report Duplicate | Flag | PURGE

Java Developer Algorithm - 22of 38 votes

AnswersGive you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.

- lxfuhuo August 23, 2013 in CHINA

eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.

o(n)time complexity and o(1) space complexity is perfect.| Report Duplicate | Flag | PURGE

Google Intern Algorithm - 22of 22 votes

AnswersImplement binary addition of two strings.

- fruktoed August 14, 2020 in UK, London

For example "101101" and "111101" equal "1101010"

You cannot use any type conversion, operate only with strings.| Report Duplicate | Flag | PURGE

Facebook Android Engineer Algorithm - 21of 27 votes

AnswersYou are given two array, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in term of height and forming a queue. Ex

- grave August 04, 2013 in India

A: 3 2 1

B: 0 1 1

It means in front of person of height 3 there is no person standing, person of height 2 there is one person in front of him who has greater height then he, similar to person of height 1. Your task to arrange them

Ouput should be.

3 1 2

Here - 3 is at front, 1 has 3 in front ,2 has 1 and 3 in front.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 21of 23 votes

AnswersGiven a undirected graph with corresponding edges. Find the number of possible triangles?

- redsanket March 25, 2014 in United States

Example:

0 1

2 1

0 2

4 1

Answer:

1| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 19of 19 votes

AnswersHow do you parse a phone number from a huge database of a 'n' billion webpages in 30 minutes ?

- Yashwanth January 30, 2013 in United States| Report Duplicate | Flag | PURGE

Apple Software Engineer in Test Algorithm - 18of 22 votes

AnswersGiven a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree

- pavel.em January 26, 2013 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 18of 18 votes

AnswersIf a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

- diffuser78 June 07, 2013 in United States

For example:

Input: "1123". You need to general all valid alphabet codes from this string.

Output List

aabc //a = 1, a = 1, b = 2, c = 3

kbc // since k is 11, b = 2, c= 3

alc // a = 1, l = 12, c = 3

aaw // a= 1, a =1, w= 23

kw // k = 11, w = 23| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer Algorithm Coding - 17of 17 votes

AnswersFind the intersection of two linked list given their head pointer.

- Punit Jain March 29, 2012 in India

Constraint: You can only traverse a linked list only once.| Report Duplicate | Flag | PURGE

Algorithm - 16of 20 votes

AnswersGiven two object arrays of "id,weight" (sorted by weight), merge them together and create a one single array. If the "id"s are same values should be merged. Final resulting array should be sorted by weight. Result should be O(nlogn) in time complexity.

- dee707 July 28, 2016 in Switzerland| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 16of 16 votes

Answers Given Two array with the preference of two developers say Ying and Ming, both need to create a team according to the preference, you need to return the String containing the Initial of the team the developers got selected it Note: Ying will always got the chance to make a first pick? {{{Example says Ying Preference table [1,2,3,4] and Ming Preference table is [1,2,3,4] than the Output should be 'YMYM' 2nd Example Ying Preference input array [1,3,2] and Ming Preference input array is [3,1,2] than the String return would be 'YYM'. - sam21088 June 22, 2020 in India for PWM| Report Duplicate | Flag | PURGE

Morgan Stanley Java Developer Algorithm - 15of 15 votes

AnswersGiven a set of 2D points, some integer k, find the k points closest to the origin, (0,0).

- peetonn March 09, 2013 in United States| Report Duplicate | Flag | PURGE

Facebook iOS Developer Algorithm - 15of 15 votes

AnswersThere is a graph which has 1 source and 1 sink(destination node)

- student1234 August 28, 2015 in United States

In between those 2 nodes there are n levels of nodes. At each level there are exactly m nodes.

Every node of level i is connected to every node of level i+1 (All edges go in forward direction)

Find total no. of paths between source and sink.

This was basic question. Then he tweaked it by adding few more edges.

Now there were some additional edges. Now sdges can go from any lower level to any higher level. That is not just from i to i+1..

can be from i to i+2 or i +3 so on...

(such bouncing edges were added only in the n levels not from or to (to src or sink)

Now find number of paths?| Report Duplicate | Flag | PURGE

Google Algorithm - 14of 14 votes

AnswersWrite a program to check whether it is a valid binary tree or not. Check all test cases (e.g. No left Node case).

- Neelavan October 02, 2016 in United States| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 13of 13 votes

AnswersYou are given a directed cyclic graph represented by an adjacency matrix. The graph has at least one terminal node (i.e. the node with no outgoing edges).

Each edge of the graph is assigned a positive integer representing a probability of taking this edge. E.g. if you have 3 outgoing edges with numbers 3, 2, and 4, this means that the prob. of taking these edges are: 3/9, 2/9 and 4/9, respectively.

You need to find the probability of reaching each terminal node from the starting node 0.

Example:

adjacency matrix 5x5:`m = {{0 1 0 0 1}, {0 0 3 2 0}, {4 0 0 1 0}, {0 0 0 0 0}, {0 0 0 0 0}}`

so we have two terminal nodes here: 3 and 4

- pavel.emeliyanenko@toptal.com May 11, 2021 in United States

we can take the following paths:

0 -> 1 -> 3 = probability: 1/2*2/5 = 1/5

0 -> 1 -> 2 -> 3 = probability: 1/2*3/5*1/5 = 3/50

0 -> 1 -> 2 -> 0 -> 1 -> 3 ... and so on

or to the node 4:

0 -> 4: probability: 1/2

0 -> 1 -> 2 -> 0 -> 4: probability 1/2*3/5*4/5*1/2 = 3/25

and so on, summing up probabilities of all possible paths we get:

total probability to reach node 3: 13/38

total probability to reach node 4: 25/38| Report Duplicate | Flag | PURGE

Microsoft SDE-2 Algorithm - 12of 14 votes

Answerswe will name a number "aggregated number" if this number has the following attribute:

- holmespanda November 16, 2012 in United States

just like the Fibonacci numbers

1,1,2,3,5,8,13.....

the digits in the number can divided into several parts, and the later part is the sum of the former parts.

like 112358, because 1+1=2, 1+2=3, 2+3=5, 3+5=8

122436, because 12+24=36

1299111210, because 12+99=111, 99+111=210

112112224, because 112+112=224

so can you provide a function to check whether this number is aggregated number or not?| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 12of 12 votes

AnswersGiven a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest.

- lxfuhuo September 09, 2015 in -

i.e:

bcabc

You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest.

ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case:

cbacdcbc. answer is acdb not adcb

I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 11of 15 votes

AnswersGiven an int array which might contain duplicates, find the largest subset of it which form a sequence.

- learner October 06, 2011 in -

Eg. {1,6,10,4,7,9,5}

then ans is 4,5,6,7

Sorting is an obvious solution. Can this be done in O(n) time| Report Duplicate | Flag | PURGE

Google Software Engineer in Test Software Engineer / Developer Arrays Algorithm - 11of 13 votes

AnswersGiven s string, Find max size of a sub-string, in which no duplicate chars present.

- sanjay05iitr November 10, 2013 in India for Cyllas Experience| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 11of 11 votes

AnswersThere are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?

- CodeKaur August 04, 2014 in United States

Ex:

Servers capacity limits: 8, 16, 8, 32

Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8

For this example, the program should say 'true'.

Ex2:

Server capacity limits: 1, 3

Task capacity needs: 4

For this example, program should return false.

Got some idea that this needs to be solved using dynamic programming concept, but could not figure out exact solution.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 10of 12 votes

AnswersGiven an equation in the form 2^i * 3^j * 5^k * 7^l where i,j,k,l >=0 are integers.write a program to generate numbers from that equation in sorted order efficiently.

- Rohit July 29, 2013 in United States

for example numbers from that equation will be in the order 2,3,5,6,7,8,9.....and so on..| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 10of 12 votes

AnswersGiven a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.

- lilzh4ng June 10, 2015 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm

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