Algorithm Interview Questions
- 2of 2 votes
AnswersYou are given a range [first, last], initially white. You need to paint it black.
For this purpose you have a set of triples
[(f, l, cost), ...] - where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers).
Find minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible
Example:[first, last] = [0, 5] and set of triples is [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]
Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.
Another example:[first, last] = [0, 5] triples are [[1,4, 10], [2, 5, 6]]
answer is -1, because it's impossible to color whole range.
- emb June 05, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersYou are given an array, divide it into 2 equal halves such that the sum of those 2 halves are equal. (Imagine that such division is possible for the input array and array size is even)
- gulusworld1989 January 13, 2014 in United States for Android| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersThere is a matrix which contains white cells , black cells and only one gray cell, need to go from (0,0) to (N-1, N-1) if Arra[N][N]
- jyotinder1.pec October 22, 2013 in United States for advance algorithm
constraints:
a. The path should cover only white cells and should go via grey cell.
b. The node once visited cannot be visited again.
White cells are represented by 0, black cells by 1 and grey cell by 2.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersYou are given a doubly linked list and an array of references to nodes on the linked list. How many "blocks" are there present in the linked list?
- Aasen May 27, 2013 in United States
A "block" is defined as a group of nodes on the list with references directed at them and adjacent to eachother.
For example
[node #0] -><-[node#1] -><-[node#2] -><-[node#3]
node[] nodes = {ref_to_node#0, ref_to_node#2, ref_to_node#3};
Is two blocks because the first block is at node #0.
Node #1 has no incomming reference. Node #2 and Node #3 have references are are adjacent so it's just one block.
Implement using JAVA: Hint: You can try using a HashMap.
Thanks.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 2of 2 votes
Answers"Given an array of strings, find the string which is made up of maximum number of other strings contained in the same array.
- mail.kshitij.jain October 10, 2013 in India
e.g. “rat”, ”cat”, “abc”, “xyz”, “abcxyz”, “ratcatabc”, “xyzcatratabc”
Answer: “xyzcatratabc”
“abcxyz” contains 2 other strings,
“ratcatabc” contains 3 other strings,
“xyzcatratabc” contains 4 other strings"| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersGiven a monotonically sorted 2D array, explain an algorithm to search for a given input element.
- maytas92@yahoo.com February 11, 2013 in United States
A monotonically sorted array is one in which each row and column has elements in ascending order.
E.g. [ 1 2 10; 4 6 11; 5 7 12;] and [1 2 5; 4 6 7; 10 12 13] are both monotonically sorted.| Report Duplicate | Flag | PURGE
IBM Software Engineer / Developer Algorithm - 2of 2 votes
AnswersMr. Kim has to deliver refrigerators to N customers. From the office, he is going to visit all the customers and then return to his home. Each location of the office, his home, and the customers is given in the form of integer coordinates (x,y) (0≤x≤100, 0≤y≤100) . The distance between two arbitrary locations (x1, y1) and (x2, y2) is computed by |x1-x2| + |y1-y2|, where |x| denotes the absolute value of x; for instance, |3|=|-3|=3. The locations of the office, his home, and the customers are all distinct. You should plan an optimal way to visit all the N customers and return to his among all the possibilities.
- Loser September 03, 2016 in India
You are given the locations of the office, Mr. Kim’s home, and the customers; the number of the customers is in the range of 5 to 10. Write a program that, starting at the office, finds a (the) shortest path visiting all the customers and returning to his home. Your program only have to report the distance of a (the) shortest path.
You don’t have to solve this problem efficiently. You could find an answer by looking up all the possible ways. If you can look up all the possibilities well, you will get a perfect score.
[Constraints]
5≤N≤10. Each location (x,y) is in a bounded grid, 0≤x≤100, 0≤y≤100, and x, y are integers.
[Input]
You are given 10 test cases. Each test case consists of two lines; the first line has N, the number of the customers, and the following line enumerates the locations of the office, Mr. Kim’s home, and the customers in sequence. Each location consists of the coordinates (x,y), which is reprensented by ‘x y’.
[Output]
Output the 10 answers in 10 lines. Each line outputs the distance of a (the) shortest path. Each line looks like ‘#x answer’ where x is the index of a test case. ‘#x’ and ‘answer’ are separated by a space.
[I/O Example]
Input (20 lines in total. In the first test case, the locations of the office and the home are (0, 0) and (100, 100) respectively, and the locations of the customers are (70, 40), (30, 10), (10, 5), (90, 70), (50, 20).)
5 ← Starting test case #1
0 0 100 100 70 40 30 10 10 5 90 70 50 20
6 ← Starting test case #2
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
10 ← Starting test case #3
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
...
Output (10 lines in total)
#1 200
#2 304
#3 366| Report Duplicate | Flag | PURGE
Samsung Software Engineer Algorithm - 2of 2 votes
Answersthere are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)
- srcnaks February 02, 2015 in -
Write two methods called "getNumber" and "requestNumber" as follows
Number getNumber();
boolean requestNumber(Number number);
getNumber method should find out a number that did not assigened than marks it as assiged and return that number.
requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.
design a data sturucture to keep those numbers and implement those methods| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Hash Table - 2of 2 votes
AnswersFind the 90th percentile of a stream of numbers between 1 and 10^6.
- addy October 16, 2014 in United States
Followup: What if there is not enough memory to store all numbers and no upper bound.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersWrite a function that finds out if any two numbers within that array add up to a target.
- Bheesham March 27, 2013 in United Statesbool addsUp(Array<int> input, int target);
| Report Duplicate | Flag | PURGE
Amazon Intern Algorithm Problem Solving - 2of 2 votes
AnswersGiven a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).
- ankit3600 June 14, 2016 in India
Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.
Note: all coordinates are real numbers
(a,b)
|----------------------------------------------|
|.......................................................|end
|.......................................................|
|start................................................|
|.......................................................|
|----------------------------------------------|(c,d)
Edit: You have to avoid sensors.
Also u can move in any direction any time.| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
AnswersThere's a function that concatenates two strings and returns the length of the resultant string. When called upon a series of strings how do we minimize the cost of using this function. Let's say we have 3 strings, A= "abc", B="def", C = "gh".
- Spectral July 07, 2015 in United States
Now cost of merging AB = 6 and cost of merging the resultant string with C is 8. Thus the total cost is 6 + 8 = 14. However, if we merge A and C, then the cost is 5 and then merge B with this, the cost is 8, so the total cost is 13.
Find an algorithm that minimizes the cost of adding such a series of strings.| Report Duplicate | Flag | PURGE
Bloomberg LP SDET Algorithm - 2of 2 votes
AnswersWrite a function which gives the length of the largest palindrome found within a string.
- grekogecko October 01, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven two string S1 and S2. S1 contains from A-Z and S2 contains A-Z, * and ?
- darklight December 28, 2012 in India
Where * means any character 0 or any number of times
Where ? means any character 0 or 1 number of times
Write a program to determine whether S2 matches S1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 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 - 2of 2 votes
AnswersGiven a string "2-4a0r7-4k", there are two dashes which we can split into 3 groups of length 1, 5, 2.
- J@sper October 20, 2016 in United States
If we want each group to be length 4, then we get "24A0-R74k"
Given a String A and an int K, return a correctly formatted string.
IF A is "2-4A0r7-4k" and B is 4, string is "24A0-R74K"
IF K is 3, string is "24-A0R-74K" as the first grp could be shorter.| Report Duplicate | Flag | PURGE
Google Algorithm - 2of 2 votes
AnswersWrite a function that takes the following inputs and gives the following outputs.
- forfron December 19, 2014 in United States
Input: A list of points in 2-dimensional space, and an integer k
Output: The k input points closest to (5, 5), using Euclidean distance
Example:
Input: {(-2, -4), (0, 0), (10, 15), (5, 6), (7, 8), (-10, -30)}, k = 2
Output: {(5, 6), (7, 8)}| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 2of 2 votes
AnswersGiven an n x n matrix A(i,j) of integers, find maximum value A(c,d) - A(a,b) over all choices of indexes such that both c > a and d > b.
- vik October 07, 2013 in United States
Required complexity: O(n^2)| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Arrays Data Structures Ideas Matrix - 2of 2 votes
AnswersRound 1 :
- sonesh January 03, 2013 in India
Q 2 : longest palindrome in a string ? (Need to tell in O(n) time complexity + O(1) space complexity)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Coding Dynamic Programming String Manipulation - 2of 2 votes
AnswersCount the number of set bits for an 32 bits integer. How to improve the process for the second time use if the memory is unlimited?
- Andy2000 September 04, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
Answersfind first not-repeating character by iterating through the length of the string only once and by using constant space.
- Raj October 28, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm - 2of 2 votes
Answers[redacted]
- tohhubeta September 02, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersSwap the elements in Kth position from the start and end of a link list.
- Aussie July 27, 2016 in United States
ex:
input: list: 1,2,4,5,7,8 & K=2
output: 1,7,4,5,2,8| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 2of 2 votes
Answers|X XX | | X X | | X | | |
X = land.
- HumbleLearner February 20, 2016 in United States
Empty space = Water.
Find the number of islands present. (Upto you how you want to represent land and water in the array above)
Answer for the above example: 3
I wish I could draw the diagram better!
Explanation: 3 because:
The three islands are:
X
X
X
XX
X| Report Duplicate | Flag | PURGE
Amazon Software Engineer Intern Algorithm - 2of 2 votes
AnswersFind the longest common prefix in a list of phrases. For instance; "i love all dogs", "i love cats" should return "i love".
- tamaracmike July 08, 2015 in United States| Report Duplicate | Flag | PURGE
Google Algorithm - 2of 2 votes
Answersn mice are playing in the desert, when one of them notices some hawks flying in the sky. It alerts the other mice who now realize that the hawks are going to attack them very soon. They are scared and want to get inside holes to ensure their safety.
- chhipababa September 27, 2014 in United States
Mice and holes are placed on a straight line. There are m holes on this line. Each hole can accommodate only 1 mouse. A mouse can either stay at its position, or move one step right from x to x+1, or move one step left from x to x-1. Any of these movements takes 1 minute.
Assign mice to holes so that the time required for all the mice to move inside the holes is minimized.
Input Format
The first line contains an integer T, the number of test cases. This is followed by T blocks of input:
First line contains 2 positive integers n and m separated by a single space.
Next line contains n space separated integers, denoting the positions of the mice.
Next line contains m space separated integers, denoting the positions of the holes.
Note: No two holes have the same position.
Output Format
For each testcase, print the minimum time taken by all the mice to reach inside the holes.
Constraints
1 ≤ T ≤ 17
1 ≤ n ≤ 131072
1 ≤ m ≤ 131072
n ≤ m
-108 ≤ mouse[i] ≤ 108
-108 ≤ hole[j] ≤ 108
Sample Input
1
3 4
2 0 -4
3 1 2 -1
Sample Output
3
Explanation
One possible solution is :
Assign mouse at position x=-4 to hole at position x=-1 -> 3 minutes
Assign mouse at postion x=2 to hole at position x=2 -> 0 minutes
Assign mouse at postion x=0 to hole at postion x=3 -> 3 minutes
So the answer is 3, after 3 minutes all of the mice are in the holes.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
Answers(To write in Objective-C; I will write the EXACT question)
- matteogobbi.jobs August 26, 2014 in United States
Given a dictionary of words, return an array of the words whose match. (i.e. pattern "c.t" match with "cat", "cut", etc. because the dot notation stand for ANY character).
SUGGEST: use suffix tree, for(for()) is not a good solution.| Report Duplicate | Flag | PURGE
Facebook iOS Developer Algorithm - 2of 2 votes
AnswersGenerate all numbers in ascending order which are having factors as 2,3 and 5. Discuss various approaches.
- Rahul Sharma March 21, 2014 in India| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm