Recent Interview Questions
- 2of 2 votes
AnswersGiven MxN matrix which contains 1s and 0s, find the largest sub matrix which contains most number of 1s. condition is that each row in the sub matrix must contain at-least one 1.
- Nascent May 04, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 2of 2 votes
AnswersThe buildings of an office are numbered sequentially. Person A is in building 1 and person B is in building 106. If A crosses 5 offices in a minute and B crosses 10 offices in a minute, at which office number will they both meet?
- pkala April 25, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer - 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
AnswersGiven an NxM (N rows and M columns) integer matrix with non-negative values (0..MAX_INT inclusive). What is the maximum sum from going top left (0, 0) to bottom right (N-1, M-1) ? The condition is that when you're at point (p, q), you can only move to either right (p, q+1) or down (p+1, q).
- math.matt July 03, 2013 in United States
Expected time complexity O(N*M)
Expected space complexity O(N+M)
From the space complexity it looks like there is a DP solution, but I couldn't figure it out.| Report Duplicate | Flag | PURGE
Samsung Java Developer Matrix - 2of 2 votes
AnswersThis question was asked in todays interview's written test. According to me it should go into infinite waiting, but when I run this code on my computer, it safely ends up printing the value. I executed n number of times but still it finishes without without going into infinite waiting.
Can someone explain.
- Anon June 01, 2013 in Indiastatic class Job extends Thread { private int counter; @Override public void run() { synchronized(this) { for(int i = 0; i < 100000; i++) counter++; this.notifyAll(); } } } public static void main(String[] args) throws InterruptedException { Job job = new Job(); job.start(); synchronized(job) { job.wait(); } System.out.println(job.counter); }
| Report Duplicate | Flag | PURGE
Goldman Sachs Software Engineer / Developer Java - 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
Answersswap alternate bits of a given number
- ruddermechanic February 07, 2013 in India
eg: n=5 (0101)
output: 10(1010)
n=8(1000)
output:4(0100)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 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
Answersnode {
- ajay.raj October 23, 2017 in United States
node * left, * right;
}
Given a list of node to determine whether the node in the list can form a valid binary tree. several points of judgment
1. need to ensure that all left, right pointer point to the node inside list
2. no cycle
3. All node must be connected
Boolean isValidTree(List<Node> list){}| Report Duplicate | Flag | PURGE
Facebook Software Developer - 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
AnswersGiven an int array without repeated elements and a target, count the total number of subset that can be generated from the array such that min (subset) + max (subset) < target
- ajay.raj March 13, 2017 in United States
public int countSubSet(int[] nums, int target){
}| Report Duplicate | Flag | PURGE
Google SDE1 - 2of 2 votes
AnswersFind the length of maximum number of consecutive numbers jumbled up in an array.
- mrityunjay21 July 26, 2016 in India for Payments
e.g.: 1, 94, 93, 1000, 2, 92, 1001 should return 3 for 92, 93, 94| Report Duplicate | Flag | PURGE
Amazon SDE-2 Arrays - 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
AnswersA bear have to climb a 60.5 feet long hill. It climbs 3 feet in every minute before it fall down for 2 feet. How long it will take to climb the hill?
- nafisah.islam October 26, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Math & Computation - 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
Answerswhat does this code do?
- determinedgal89 October 01, 2014 in United Statesunsigned mystery(unsigned x) { unsigned i=0; while(x) { x=x&(x-1); i++; } return i; }
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Bit Manipulation - 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
AnswersGiven a tree with n nodes. Each node has k coins, where 0 <= k <= n . There are total n coins on the tree.
- aonecoding4 November 18, 2018 in United States
The goal is to move the coins such that each node has exactly one coin. What's the minimum moves required?
Each move can only move one coin to an adjacent node.| Report Duplicate | Flag | PURGE
Google Software Engineer - 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
AnswersGiven an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.
- Anon April 29, 2017 in United States
Ex: "bedbathandbeyond" would be "bed bath and beyond" which are all dictionary words.| Report Duplicate | Flag | PURGE
Facebook Software Engineer String Manipulation - 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