Algorithm Interview Questions
- 2of 2 votes
AnswersYou are given information about hotels in a country/city. X and Y coordinates of each hotel are known. You need to suggest the list of nearest hotels to a user who is querying from a particular point (X and Y coordinates of the user are given). Distance is calculated as the straight line distance between the user and the hotel coordinates.
- abc June 19, 2014 in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 2of 2 votes
AnswersGiven 3 Arrays of integer sorted in ascending order, get the sum of minimum difference using one element from each array.
- anonymous August 11, 2013 in India
where a, b, c are the elements from each array.
diff = |a-b| + |b-c|+|c-a|
complexitiy: worst case O(n)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersHow can we implement spell checker.
- rapirapp July 04, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Data Structures - 2of 2 votes
AnswersGiven a set of intervals, find the interval which has the maximum number of intersections.
- hello world February 27, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm Data Structures - 2of 2 votes
AnswersGiven a binary tree, implement an iterator that will iterate through its elements.
- carlosgsouza July 07, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a M * N matrix, if the element in thematrix is larger than other 8 elements who stay around it, then named thatelement be mountain point. Print all the mountain points.
- yylmaster November 13, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given an array whose each element represents the height of the tower. The width of every tower is 1. It starts raining. How much water is collected between the towers?
- mail.kshitij.jain October 06, 2013 in India
Eg. [1,5,3,7,2] – then answer is 2 units between towers 5 and 7.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersA prefix of a string S is any leading contiguous part of S. A suffix of the string S is any trailing contiguous part of S. For example, "c" and "cod" are prefixes, and "ty" and "ity" are suffixes of the string "codility". For simplicity, we require prefixes and suffixes to be non-empty and shorter than the whole string S.
A border of a string S is any string that is both a prefix and a suffix. For example, "cut" is a border of a string "cutletcut", and a string "barbararhubarb" has two borders: "b" and "barb".
We are looking for such borders of S that have at least three non-overlapping occurrences; that is, for some string that occurs as a prefix, as a suffix and elsewhere in between. For example, for S = "barbararhubarb", the only such string is "b".
In this problem we consider only strings that consist of lower-case English letters (a−z).
Write a function:class Solution { public int solution(String S); }
that, given a string S consisting of N characters, returns the length of its longest border that has at least three non-overlapping occurrences in the given string. If there is no such border in S, the function should return 0.
- onecitizen.ca July 18, 2013 in United States
For example, given a string S as follows:
if S = "barbararhubarb" the function should return 1, as explained above;
if S = "ababab" the function should return 2, as "ab" and "abab" are both borders of S, but only "ab" has three non-overlapping occurrences;
if S = "baaab" the function should return 0, as its only border "b" occurs only twice.
Assume that:
N is an integer within the range [0..1,000,000];
string S consists only of lower-case letters (a−z).
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 2of 2 votes
AnswersHow to detect cycles in a graph?
- rodrigoreis22 February 09, 2013 in United States
Don't need to write code, just your idea and complexity.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a string A consisting of n characters and a string B consisting of m characters, write a function that will return the number of times A must be stated such that B is a substring of the repeated A. If B can never be a substring, return -1.
- neer.1304 July 03, 2019 in United States
Example:
A = ‘abcd’
B = ‘cdabcdab’
The function should return 3 because after stating A 3 times, getting ‘abcdabcdabcd’, B is now a substring of A.
You can assume that n and m are integers in the range [1, 1000].| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersMarch 2018 Phone Interview FB
- aonecoding March 17, 2018 in United States
Calculate a moving average that considers the last N values.
Circular Queue (Interviewer didn't agree with the linked list queue that I suggested at first. Said the pointers took space)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersGiven an unsorted array of integers, find the length of the longest consecutive elements sequence.
- NoOne August 22, 2017 in India
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4].
Return its length: 4.
Your algorithm should run in O(n) complexity.| Report Duplicate | Flag | PURGE
Uber Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersThere's a very simple compression algorithm that takes subsequent characters and just emits how often they were seen.
- Phil September 08, 2015 in Netherland
Example:
abababaabbbaaaaa| Report Duplicate | Flag | PURGE
Booking.com Software Engineer Algorithm - 2of 2 votes
Answersstd C library has pow(x, n) function - implement that function
- kumarr.arvind June 20, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersAssume we have a very large file containing millions of lines of data. Only 2 lines are identical, rest are unique.
- Anand Barnwal June 08, 2015 in India
Each line is long enough that they may not fit in memory.
Design an efficient algorithm to determine identical lines?
And, then generalize it for 'n' identical lines.| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 2of 2 votes
AnswersThere's a new language which uses the latin alphabet. However, you don't know the order among letters.
- Victor November 27, 2014 in United States
It could be:
a b c d ...
as it could also be:
b e z a m i ...
You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 2of 2 votes
AnswersGiven a set of equalities and inequalities like A=B,B=C,F=J and A!=C, etc in two separate arrays (equalities[] and inequalities[]) and a method, separate that returns the two objects, e.g. separate(A=B) will return A and B, write an algorithm to find whether the entire set is consistent in constant time.
- addy October 25, 2014 in United States| Report Duplicate | Flag | PURGE
Yahoo SDE1 Algorithm - 2of 2 votes
AnswersGiven a N * M matrix, you have to rotate it by 90 degree.
- SK July 07, 2013 in India for Bing
I gave him solution with transpose matrix & then reverse each row.
He was satisfied but after asked that this required each element to be touched twice. Can you do it like all elements will be touched once only.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersI have one bag of bolts and another bag of nuts, need to find biggest Bolt. Condition is must not compare both bolts or both nuts. only comparison between bolt and nut allowed.
- Andi December 12, 2012 in United States| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 2of 2 votes
AnswersGiven two strings src and sch, sch is a rotation of src. Write a method to find the rotation point in src. Please provide big-O for time and space.
- IHE February 18, 2012 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGenerate a random binary tree, with equal probability.
- pb August 30, 2017 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersFind Famous person in the list of persons.
- Seeker June 01, 2017 in United States
A person is a famous person if he doesn't know anyone in the list and everyone else in the list should know this person.
The function isKnow(i,j) => true/ false is given to us. No need to worry about it.
Goal is to find the famous person in O(n) complexity.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersYou are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price.
- camiloni42 November 19, 2016 in United States
When facing each enemy you can either:
1) Fight him (if your strength is enough). You keep your money.
2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours.
Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible).
This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGiven a string with only parenthesis. Check if the string is balanced.
- teli.vaibhav October 30, 2016 in United States
ex -
1) "<({()})[]> is balanced
2) "<({([)})[]> is not balanced| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersGiven an array of positive integers(>0) , you have to insert '+','*','(',')' signs basically plus multiply and brackets such that value of resultant expression becomes maximum.
- smarthbehl August 25, 2015 in United States
Hint: Consider case of continuous ones
You have to print the resulting expression| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm - 2of 2 votes
AnswersCount triangles in an undirected graph where a triangle is a unique set of three vertices connected to one another.
- tested.candidate July 14, 2015 in Switzerland| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 2of 2 votes
AnswersThere is a compressed string eg. ”ab2c3”, the string has lowercase characters and numbers. We can uncompress the given string as follows: whenever we get a number “n” in the string, the portion of the string before the number will repeat “n” times. So in the above example, we get a 2, so string will become “ababc3”, now we get a 3, so final string will be “ababcababcababc”.
- Rahul Sharma August 28, 2014 in India
Given a compressed string and a number k, you have to output the k’th character in the uncompressed string.
1 <= length of string <= 1500
1 <= n <= 1000
1 <= k < 2^31
example:
input: ab2c3 10
output: c| Report Duplicate | Flag | PURGE
Directi SDE1 Algorithm - 2of 2 votes
AnswersIs it possible to compare two Binary trees for equality in iterative manner without using extra space?
- Algorithmist June 17, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersProblem: you are given 2 words with equal number of characters. Find an algorithm to go from first word to second word, changing one character at each step, in such a way that each intermediate word exist in a given dictionary.
- EugenDu May 24, 2013 in United States
Example:
Words are pit, map. A possible solution:
pit, pot, pet, met, mat, map| Report Duplicate | Flag | PURGE
Ebay Software Engineer in Test Algorithm