Algorithm Interview Questions
- 10of 10 votes
AnswersGiven a function KNOWS(A,B), which returns 1 if A knows B (and not necessarily the other way around) and 0 if A does not know B.
- asafiniu February 27, 2013 in United States
A Celebrity is one who does not know anyone,
and one who is known by everybody.
For a list of N people, find all celebrities in linear time.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer 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 - 10of 10 votes
AnswersYou want to create a staff to use in your martial arts training, and it has to meet some specific requirements.
- krvangala98 April 25, 2014 in United States
1. You want it to be composed of two smaller staves of equal length so that you can either use it as a single staff or as two smaller ones.
2. You want the full sized staff's center of gravity to be exactly in the middle of the staff.
You have a very, very long branch from which you can cut the pieces for your staff. The mass of the branch varies significantly throughout it, so you use just any two pieces of the same length. Given a description of the mass throughout the branch, determine the longest staff you can make, then return three integers on a single line, the first two indicating the first index of each half-staff, and the third indicating the length of each half-staff.
The input will be given on a single line as a string of digits [1-9], each digit representing the mass of a section of the branch. All sections are the same size and the maximum length of the string is 500. Here is an example:
41111921111119
11119 11119
If the indicated sections are cut from the branch they will satisfy your requirements. They are both the same length, and they can be put together as either 9111111119 or 1111991111, both of which have a center of gravity exactly in the center of the staff.
Center of gravity can be determined by taking a weighted average of the mass of each section of the staff. Given the following distances and masses:
Distance: 12345678
Mass: 22241211
Sum of the mass of each section: 2 + 2 + 2 + 4 + 1 + 2 + 1 + 1 = 15
Weighted sum of the masses:
2*1 + 2*2 + 2*3 + 4*4 + 1*5 + 2*6 + 1*7 + 1*8 = 60
Weighted sum / regular sum = 60 / 15 = 4
This means that the center of mass is in section 4 of the staff. If we wanted to use this staff the center of gravity would need to be (8+1)/2 = 4.5.
Here is an example problem:
131251141231
---- ----
If we take the sections indicated we get 1312 and 1231. By reversing the first one and putting them together we get 21311231
Sum of the mass of each section: 2 + 1 + 3 + 1 + 1 + 2 + 3 + 1 = 14
Weight sum of the masses:
2*1 + 1*2 + 3*3 + 1*4 + 1*5 + 2*6 + 3*7 + 1*8 = 63
Weighted sum / regular sum = 63 / 14 = 4.5
This puts the center of mass exactly in the center of the staff, for a perfectly balanced staff. There isn't a longer staff that can be made from this, so the answer to this problem is
0 8 4
Because the half-staves begin at indices 0 and 8 (in that order) and each is of length 4.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 10of 10 votes
AnswersGiven 3 unsorted arrays A, B and C you need to find all possible combinations such that A[i] + B[j] = B[k] + C[l].
- venkataratnamkumar7777 September 22, 2018 in United States| Report Duplicate | Flag | PURGE
Walmart Labs SDE1 Algorithm Arrays - 10of 10 votes
AnswersThere is a 2D matrix of 0s and 1s that depicts the number of rooms that can be formed by a co-working space company like WeWork based on the values. 1 means open space for room and 0 means wall. We need to group as many 1s and possible to form the largest and minimum number of rooms.
- Jigisha Aryya December 25, 2019 in India
E.g.
Number of Rows = 5, Number of Columns = 5
00010
01110
01100
01101
00011
Output: 4
Input 2:
4
3
001
111
011
100
Output: 4| Report Duplicate | Flag | PURGE
unknown Backend Developer Algorithm - 9of 11 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
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 an array of integers, find all combination of four elements in the array whose sum is equal to a given value X.
- sai September 04, 2012 in India
For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and X = 23, then your function should print “3 5 7 8″ (3 + 5 + 7 + 8 = 23).| Report Duplicate | Flag | PURGE
Amazon 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
AnswersA circus is designing an act consisting of a tower of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below her. Given the heights and weights of each person in the circus, what is the largest possible number of people in such a tower?
- algooz May 03, 2008
Input(ht wt) : (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56,90) (60,95) (65,100) (68,110) (70,150) (75,190)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 9of 9 votes
AnswersWrite a function which will return a char from a given encoded string from given index without decoding string. e.g. from “a2bc3d4” ( means “aabcbcbcdddd” ) and index value is 7 means function should return c without decoding original string ?
- kumarraju05 January 19, 2015 in India| Report Duplicate | Flag | PURGE
makemytrip Java Developer Algorithm - 9of 9 votes
AnswersWrite a program for finding a minimum element in rotated sorted array(either ascending or descending ) and array contains duplicates.
- kesar February 02, 2014 in United States| Report Duplicate | Flag | PURGE
Algorithm Arrays C Sorting C# - 9of 9 votes
AnswersGiven a random function with equal probability of getting 1 or 0 ie 50% each. write a custom function which uses the above random function such that your function should return 1 with 75% probability and 0 with 25% probability
- coolcoder3 July 22, 2016 in India| Report Duplicate | Flag | PURGE
Oracle Software Developer Algorithm Problem Solving - 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
AnswersYou are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
- King@Work March 05, 2011
Fastest way to find that single integer
-- using memory.
-- not using any external memory.
eg: [2,1,4,5,1,4,2,2,4,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 - 8of 8 votes
AnswersYou are given a list of n float numbers x_1, x_2, x_3, ... x_n, where x_i > 0.
- emb September 04, 2015 in United States
A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise)
Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting)
e.g.
2 1 1 2 -> crosses
1 2 3 4 -> doesn't cross| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 8of 8 votes
AnswersWrite code to find the next least node in a binary search tree given a node?
- mav February 20, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Algorithm - 8of 8 votes
AnswersYou are given N unique numbers a1<a2<a3<...an. Find out the count of all possible binary search tress that can be constructed using these numbers.
- ashok.singh.sairam September 13, 2012 in India
for example with 3 elements 1,2,3 there are 5 possible BST and for 1,2,3,4 there are 14 bst| Report Duplicate | Flag | PURGE
Samsung Software Engineer / Developer Algorithm - 8of 8 votes
AnswersYou are given a graph, some edges are black, some are red. Find a spanning tree with one restriction: if we take some node as root, every path from it to some leaf node must consist of alternating red-black-red-black edges. That is, no path from root to leaf must contain sequential black-black edges or red-red edges.
- emb April 12, 2016 in United States
You are guaranteed that such spanning tree exists.| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 7of 15 votes
AnswersWAP to modify the array such that arr[I] = arr[arr[I]].
- praveen February 28, 2014 in United States
Do this in place i.e. with out using additional memory.
example : if a = {2,3,1,0}
o/p = a = {1,0,3,2}
Note : The array contains 0 to n-1 integers.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 7of 11 votes
AnswersThe "surpasser" of an element in an array is defined as the number of elements that are to the "right" and bigger than itself.
- carchen2015 July 10, 2015 in United States
Example:
Array:
[2, 7, 5, 5, 2, 7, 0, 8, 1]
The "surpassers" are
[5, 1, 2, 2, 2, 1, 2, 0, 0]
Question: Find the maximum surpasser of the array.
In this example, maximum surpasser = 5| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 7of 9 votes
AnswersImagine an alphabet of words. Example:
- hani.amr June 30, 2013 in United States
a ==> 1
b ==> 2
c ==> 3
.
z ==> 26
ab ==> 27
ac ==> 28
.
az ==> 51
bc ==> 52
and so on.
Such that the sequence of characters need to be in ascending order only (ab is valid but ba is not). Given any word print its index if valid and 0 if not.
Input Output
ab 27
ba 0
aez 441
Note: Brute-force is not allowed.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm