Algorithm Interview Questions
- 75of 77 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 - 32of 34 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 - 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 - 21of 37 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 - 21of 25 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 - 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 - 17of 17 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 - 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 - 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
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 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 14 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 - 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 - 10of 10 votes
AnswersA tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes that node with id k is the root. For ex:
3 3 3 -1 2 0 1 2 3 4
In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4.
- Murali Mohan July 22, 2013 in India for Bangalore
Given such an array, find the height of the tree.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 10of 10 votes
AnswersYou are given with an array of 1s and 0s. And you are given with an integer m, which signifies number of flips allowed.
- Hitman October 22, 2014 in United States
find the position of zeros which when flipped will produce maximum continuous series of 1s.
e.g.
input:
arr={1 1 0 1 1 0 0 1 1 1 } m=1
output={1 1 1 1 1 0 0 1 1 1} position=2
arr={1 1 0 1 1 0 0 1 1 1 } m=2
output={1 1 0 1 1 1 1 1 1 1} position=5,6| Report Duplicate | Flag | PURGE
Amazon Algorithm - 10of 10 votes
AnswersGiven a Binary Search tree of integers, you need to return the number of nodes having values between two given integers. You can assume that you already have some extra information at each node (number of children in left and right subtrees !!).
- abc June 19, 2014 in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 10of 10 votes
Answershow to merge two binary search tree into balanced binary search tree.. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time with in constant space.
- vivek August 11, 2013 in United States
Examples:
A Balanced BST 1
90
/ \
70 110
A Balanced BST 2
60
/ \
5 800
output :-->
70
/ \
60 90
/ \
5 800| Report Duplicate | Flag | PURGE
Google Computer Scientist Algorithm - 9of 9 votes
AnswersGiven an array of integers, sort the array into a wave like array, namely
- Zen April 22, 2014 in United States
a1 >= a2 <= a3 >= a4 <= a5.....| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven a string (1-d array) , find if there is any sub-sequence that repeats itself.
- for.anonymous.usa October 22, 2014 in United States
Here, sub-sequence can be a non-contiguous pattern, with the same relative order.
Eg:
1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice
The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time.
In the sense, it should be checked for every pair of characters in the string.| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm Brain Teasers C C++ Coding Data Structures Dynamic Programming Problem Solving String Manipulation - 9of 9 votes
AnswersGiven a number N, write a program that returns all possible combinations of numbers that add up to N, as lists. (Exclude the N+0=N)
- ootah November 14, 2013 in United States
For example, if N=4 return {{1,1,1,1},{1,1,2},{2,2},{1,3}}| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 9of 9 votes
AnswersQuestion was "Given a pattern and a string input - find if the string follows the same pattern and return 0 or 1.
- David_Maxwell November 24, 2014 in United States
Examples:
1) Pattern : "abba", input: "redbluebluered" should return 1.
2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.
I can think of a brute-force solution for this question where we add the character in the pattern and n length of the string to a hashmap and recurse over the pattern array and string. But is there anything more efficient? This was a pretty difficult question in my opinion.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
Answersyou are given n-strings 1you have to find whether a chain can be termed with all the strings given number n? A chain can be formed b/w strings if last char of the 1st string matches with 1st char of second string. For example you are given
- Rahul Sharma October 03, 2013 in India
number of strings = 3
first string=sdfg
second string=dfgs
third string=ghjhk
they can be concatenated as ->
second first third
dfgs sdfg ghjhk (characters at concatenation points are same)
so concatenated string is-dfgsdfghjhk| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven a timer time() with nanosecond accuracy and given the interface
interface RealTimeCounter: void increment() int getCountInLastSecond() int getCountInLastMinute() int getCountInLastHour() int getCountInLastDay()
implement the interface. The getCountInLastX functions should return the number of times increment was called in the last X.
- peachandpotato January 29, 2014 in United States
(My note: an ideal solution will have space usage which does *not* grow unbounded with the number of calls to increment(). It seems to me that a solution involving a round-robin database could be good, but it sacrifices accuracy.)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 9of 9 votes
AnswersGiven a huge N*N matrix, we need to query the GCD of numbers in any given submatrix range(x1,y1,x2,y2). Design a way to preprocess the matrix to accelerate the query speed. extra space should be less than O(N^2) and the preprocess time complexity should be as litte as possible.
- mario87 December 18, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 8of 10 votes
AnswersRearrange an array using swap with 0.
- cm29xm August 14, 2013 in Australia
You have two arrays src, tgt, containing two permutations of the numbers 0..n-1. You would like to rearrange src so that it equals tgt. The only allowed operations is “swap a number with 0”, e.g. {1,0,2,3} -> {1,3,2,0} (“swap 3 with 0”). Write a program that prints to stdout the list of required operations.
Practical application:
Imagine you have a parking place with n slots and n-1 cars numbered from 1..n-1. The free slot is represented by 0 in the problem. If you want to rearrange the cars, you can only move one car at a time into the empty slot, which is equivalent to “swap a number with 0”.
Example:
src={1,0,2,3}; tgt={0,2,3,1};| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 8of 8 votes
AnswersGiven the array of digits (0 is also allowed), what is the minimal sum of two integers that are made of the digits contained in the array.
- azil November 28, 2013 in United States
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207| Report Duplicate | Flag | PURGE
Google Algorithm
Open Chat in New Window