Algorithm Interview Questions
- 1of 1 vote
AnswersGiven an array of "array range", return an optimized array by deleting subarrays.
- dark_knight October 19, 2015 in United States
NOTE: Array range (2,6) represents (2,3,4,5,6)
INPUT: [(2,6),(3,5),(7,21),(20,21)]
OUTPUT: [(2,6),(7,21)]
Reason: (3,5) is a subarray of (2,6) and (20,21) is a subarray of (7,21)| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 1of 1 vote
AnswersWrite a program that gives count of common characters presented in an array of strings..(or array of character arrays)
- satya June 16, 2014 in United States
For eg.. for the following input strings..
aghkafgklt
dfghako
qwemnaarkf
The output should be 3. because the characters a, f and k are present in all 3 strings.
Note: The input strings contains only lower case alphabets| Report Duplicate | Flag | PURGE
Linkedin Algorithm - 1of 1 vote
Answers
- BVarghese July 26, 2013 in United StatesSearch for an element in a matrix. Rows and columns of the matrix are sorted in ascending order. eg. matrix [1 14 25 35] [2 16 28 38] [5 20 28 40] [16 22 38 41] search for 38. The interviewer was looking for a solution better than O(n+m). He didn't want a solution which starts searching from the left bottom and go to right or above according to the key value to search. That solution has O(n+m) worst complexity, where n is row count and m is column count.
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a array of positive integers, find all possible triangle triplets that can be formed from this array.
- Aspire November 25, 2014 in United States
eg: 9 8 10 7
ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10
Note : array not sorted, there is no limit on the array length| Report Duplicate | Flag | PURGE
Linkedin SDE1 Algorithm - 1of 1 vote
AnswersIf you're given a list of countries and its corresponding population, write a function that will return a random country but the higher the population of the country, the more likely it is to be picked at random.
- Curious September 05, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of 2n elements of which n elements are same and the remaining n elements are all different. Write a C program to find out the value which is present n times in the array
- Jamob May 22, 2011| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
Answersyou are given 2 arrays sorted in decreasing order of size m and n respectively.
- SA August 29, 2010
Input: a number k <= n*n and >= 1
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven two String, s1 and s2.
- niraj.nijju October 15, 2013 in India
to find the longest substring which is prefix of s1, as well as suffix of s2.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 1of 1 vote
Answers/* In "the 100 game," two players take turns adding, to a running
- you.win September 24, 2014 in United States for Mobile
total, any integer from 1..10. The player who first causes the running
total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, if two players might take turns drawing from a common pool of numbers
of 1..15 without replacement until they reach a total >= 100. This problem is
to write a program that determines which player would win with ideal play.
Write a procedure, "Boolean canIWin(int maxChoosableInteger, int desiredTotal)",
which returns true if the first player to move can force a win with optimal play.
Your priority should be programmer efficiency; don't focus on minimizing
either space or time complexity.
*/
Boolean canIWin(int maxChoosableInteger, int desiredTotal) {
// Implementation here. Write yours
}| Report Duplicate | Flag | PURGE
Linkedin Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersQ3. Written Exam Amazon(Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a singly linked list which may or may not contain loop and loop may or may not start from the head node. Count the number of elements in the linked list.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 1of 1 vote
AnswersWrite a function to remove the duplicated characters from a string, and maintain the order of the characters.
- 4661 July 11, 2014 in United States
ex. “abracadabra” ? “abrcd”| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 1of 1 vote
AnswersImagine you have a sequence of the form 0123456789101112131415... where each digit is in a position, for example the digit in the position 5 is 5, in the position 13 is 1, in the position 19 is 4, etc.
- 352905 February 04, 2013 in United States
Write a function that given a position returns the digit in that position.
(You could think that this sequence is an array where each cell only holds one digit so given an index return what digit is in that index, however you cannot really create an array since the sequence is infinite, you need a way to based on the index calculate the digit that goes there).
The function has to return a single digit.
Other examples:
index = 100, result = 5
index = 30, result = 2
index = 31, result = 0
index = 1000, result = 3| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGenerate a number is range (1,n) but not in a list (i,j)
- superffeng September 27, 2012 in United States for Site reliabilty
for example range is (1,1000), list is [2,3,5,9,199,200,344]| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Algorithm - 1of 1 vote
AnswersThere is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum. As for how to compute the cost of moving one group to another point, please see the following example.
- xiaoc10 March 11, 2012 in United States
Group1: (0, 1), 4
Group2: (1, 3), 3
Group3: (2, 0), 5
. 4 . .
. . . 3
5 . . .
If all of these three groups moving to (1, 1), the cost is: 4*((1-0)+(1-1)) + 5*((2-1)+(1-0))+3*((1-1)+(3-1))
My idea is :
Firstly, this two dimensional problem can be reduced to two one dimensional problem. In the one dimensional problem, I can prove that the best spot must be one of these groups. In this way, I can give a O(G^2) algorithm.(G is the number of group).
Use iterator's example for illustration:
{(-100,0,100),(100,0,100),(0,1,1)},(x,y,population)
for x, {(-100,100),(100,100),(0,1)}, 0 is the best.
for y, {(0,100),(0,100),(1,1)}, 0 is the best.
So it's (0, 0)
Is there any better solution for this problem.
Thanks,| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersGiven integer k and a subset S of set {0, 1, 2, ..., 2^k - 1}
- emb December 13, 2015 in United States
Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a)
& here is bit-wise and.
Do it faster than O((2^k)^2), assume k <= 16
Example:
0b111
0b101
0b010
Answer: 2
0b110
0b011
0b101
Answer: 0| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven a Tree:
A /\ B C /\ /\ D E F G
Write a function that prints:
- santidltp January 05, 2015 in United States
A
BC
DEFG| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are given an unsorted integer array of size N. This array contains integer from range 0 - N (not necessarily distinct and same integer can appear multiple time in an array).
- Rajat January 30, 2013 in India
You need to find pair of all the elements in array which sum up to N.
First i gave a solution using an extra array of size N to keep count of each integer in original array and was able to give solution in O(n) Time complexity and O(n) space complexity.
Then interviewer asked me to decrease space complexity, for which i gave solution as sorting the given array (in nlogn time) and then find the pairs in O(n) time, and hence total time complexity was O(nlogn) and space complexity as O(1).
But interviewer kept pressing for a better time complexity (than O(nlogn)) with O(1) space complexity.
How is it possible, i could not think of any way.| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm Arrays - 1of 1 vote
AnswersGiven an array of n numbers in which all the members are less than or equal to k (k<n). device an algorithm of order O(k) to find the first repeating element.
- Ramesh January 14, 2010| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Brain Teasers Data Structures Ideas Math & Computation Sorting - 1of 1 vote
AnswersPrint all subset of a given set which sums up to ZERO
- apurohit.in January 09, 2015 in India
{8,3,5,1,-4,-8}
so ans will be : {8,-8}
{3,5,-8}
{3,1,-4}
size of set can be upto 50 but elemet of set can be as big as 18 digit number| Report Duplicate | Flag | PURGE
Amazon Dev Lead Dev Lead Algorithm - 1of 1 vote
AnswersPermutate a list of string
- HBY April 17, 2015 in United States
this question is supposed permutate the characters instead of who string,
as input example {"red", "fox", "super" }, the expected output is
rfs
rfu
rfp
rfe
rfr
ros
rou
rop
roe
ror
rxs
rxu
rxp
rxe
rxr
efs
efu
efp
efe
efr
eos
eou
eop
eoe
eor
exs
exu
exp
exe
exr
dfs
dfu
dfp
dfe
dfr
dos
dou
dop
doe
dor
dxs
dxu
dxp
dxe
dxr| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven an 8x8 chess board, you have a bishop that moves from the current to the target position. write a code to find the minimum path from the current to the target position.
- AVK June 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersThere are 2 sorted sets.Find the common elements of those sets
- anonymous February 22, 2013 in United States
e.g.
A={1,2,3,4,5,6}
B={5,6,7,8,9}
o/p C={5,6}
Complexity should ne 0(n+m) where n and m is the size of the first and second set respectively
Which data structure should be used to store the output| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm Data Structures - 1of 1 vote
AnswersQ1) Write a program to calculate height of a binary tree non - recursively ?
- Decipher August 13, 2011
Q2) Asked which data structure should be used to store browser history.
Q3) Find the anagrams with a huge list of words .
Q4) Mirror a tree iteratively.
Q5) Compute a+bx2+cx3+dx4+... efficiently (a,b,c...given)
Q6) Find one missing alphabet in an array of 26 alphabets(one alphabet repeated twice).| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer 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 - 1of 1 vote
AnswersYou are given large numbers of logs, each one of which contains a start time (long), end time (long) and memory usage (int). The time is recorded as MMDDHH (100317 means October 3rd 5PM) Write an algorithm that returns a specific time (hour) when the memory usage is the highest. If there are multiple answers, return the first hour.
- aijackmoore September 21, 2015 in United States
e.g. 100207 100208 2
100305 100307 5
100207 100209 4
111515 121212 1
Answer: 100207
(Need to consider different scenarios like the time slots could be very sparse)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersGiven a string, complete the given function to recursively remove the adjacent duplicate characters and return the resultant string. If there are no characters left in the resultant string, return "-1" (without quotes).
- jerinsebastian.punnamada April 08, 2014 in United States
Sample Test Cases
Sample Input: ABCCBCBA
Output: ACBA
Explanation: (ABCCBCBA --> ABBCBA --> ACBA)
Sample Input: AA
Sample Output: -1
Java solution| Report Duplicate | Flag | PURGE
Yahoo Applications Developer Algorithm Java - 1of 1 vote
AnswersFrom the set of natural integer numbers
- CameronWills October 30, 2012 in United States
Let x = 1234 = {1, 2, 3, 4}
Let y = 2410 = {2, 4, 1, 0}
Write an algorithm to compute the rearrangement of x that is closest to y but still greater than y. Both x and y have the same number of digits.
So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is greater than y = 2410 and closer than any other arrangements of x.
And whats the time complexity of this algorithm?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersA log of wood has n marks on it. Cost of cutting wood at a particular mark is proportional to the length of the log. The log of wood can be cut at all the marks. Find the optimal order of the marks where the log should be cut in order to minimize the total cost of cutting.
- brahmasani99 May 02, 2012 in India| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersGiven a positive integer N, arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers. For example, for a[i] and a[j], if b = (a[i] + a[j])/2, then if a[k] = b, k < i or k > j.
- lyra_vega November 09, 2011 in -
Hint :- If the average of two numbers is not an integer then we can assume that they do not have an average.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm