Recent Interview Questions
- 4of 4 votes
Answersdesign a method which consumes an integer and output the corresponding column number in Microsoft Excel ( ex. A, B, C......Z, AA, AB....ZZ....)
- chandeepsingh85 September 25, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersWrite algorithm for java grep command for word matching in the following context.Given a file containing n words.Given a word w and a number k.Find k words in the file occuring before occurence of w.Assume that the average word size is m in the file
- prashant.tah September 12, 2017 in India
eg.
aaa
bbb
ccc
booking
alpha
beta
gamma
for k=3 and w = booking
the output should be [aaa,bbb,ccc,booking]
similarly for k =2 and w = beta
output should be [booking,alpha,beta]
Assume that the file size can grow very large
and try to get solution with space complexity lesser than O(n)
I suggessted solution for iterating through file until the word w is found and maintaiining a queue of size K
The time complexity of my solution was O(nm)
and space complexity was O(k) .Any answers to improve the time and space complexity
Apparently they were looking for a better implementation of grep| Report Duplicate | Flag | PURGE
Booking.com Software Developer Algorithm - 4of 4 votes
Answersin a tree any root can have any number of children. Every node has an integer value. Find the maximum length on consecutive number sequence anywhere in the tree. For example if root is 2 and one child is 3, its child is 4 its child is 6 then max length will be 3. I was able to write the code the find of one sequence but when one sequence ends and other starts I was not able to handle that case. I think its hard to do by recursion. Is there any other trick or algorithm for this??
- ajrules2105 March 10, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 4of 4 votes
AnswersFind the latest version of released software. For e.g1. 2 and 2.2.. latest is 2.2.
- techpanja October 02, 2013 in United States
eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed as string in above format.| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Java - 4of 4 votes
AnswersWrite a program to process the matrix. If an element is 0 at ith row and jth column, then make the whole ith row and jth column to 0.
- codealtecdown September 17, 2015 in United States
Constraints:
Space complexity should be O(1)
Time complexity - Only single pass is allowed. Note that single pass is not O(n). This is single pass : An element will read and written only ones.
Edit:
Recursion is not allowed since it is O(n) space on stack| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 4of 4 votes
AnswersGiven an array of integer nos. All numbers are distinct.
- pavel.em May 22, 2015 in United States
WAP to find the two longest non-intersecting continuous subarrays
of equal size s.t. *all* elements of one of them are smaller than that of the other subarray:
a[i..i + k - 1] and a[j..j+k-1] where i + k <= j
s.t. a[i..i + k - 1] < a[j..j+k-1] or a[i..i + k - 1] > a[j..j+k-1]
and k is maximal
Example: a = {1,2,3, 7, 9, 8} then we have: {1, 2, 3} and {7, 9, 8}
a = {6, 5, 4, 1, 3, 7} then we have:
{6, 5} and {4, 1} or
{6, 5} and {1, 3} or
{5, 4} and {1, 3} ...| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 4of 4 votes
AnswersGiven the following hashmap for numeric to alpha translation of a telephone keypad:
- valheru April 23, 2014 in United States
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
Write a method that takes a phone number as input and returns all possible letter combinations for that phone number.| Report Duplicate | Flag | PURGE
Facebook iOS Developer Algorithm - 4of 4 votes
AnswersTwo tables. Country and City
- sunny smart June 16, 2013 in Netherlands
country --> countryid, country name
city --> countryid, city name
1. how do you get the countries that has no cities?
2. how do you get the countries that has less than 3 cities and also make sure the countries with no cities also show up.| Report Duplicate | Flag | PURGE
Booking.com None None Database SQL - 4of 4 votes
AnswersGiven a string return the longest palindrome that can be constructed by removing or shuffling characters.
- enkadi13 July 22, 2016 in United States
Example:
'aha' -> 'aha'
'ttaatta' -> ' ttaaatt'
'abc' -> 'a' or 'b' or 'c'
'gggaaa' -> 'gaaag' or 'aggga'
Note if there are multiple correct answers you only need to return 1 palindrome.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 4of 4 votes
AnswersYou are given two arrays of length M and N having elements in range 0-9.Your task is to create maximum number of length K from elements of these two arrays such that relative order of elements is same in the final number as in the array, they are taken from i.e. If two elements a,b are taken from array1 and and a comes before b in array1 so in the final number a should come before b (Relative order kept same) .
- Rahul Sharma November 18, 2015 in United States
Example: N=4 and M =6
Array1 = { 3 , 4 , 6,5}
Array2 ={9,1,2,5,8,3}
Suppose K = 5, then number will be {9,8,6,5,3}
You can see {9,8,3} are taken from array2 in the same order as they are in Array2. Similarly {6,5} are taken from Array1 in the same order and number 98653 is maximum possible number.| Report Duplicate | Flag | PURGE
Google Research Scientist Algorithm - 4of 4 votes
AnswersGiven a binary tree where all the right nodes are leaf nodes, flip it upside down and turn it into a tree with left leaf nodes.
Keep in mind: ALL RIGHT NODES IN ORIGINAL TREE ARE LEAF NODE.
- PrateekS. July 29, 2014 in United States/* for example, turn these: * * 1 1 * / \ / \ * 2 3 2 3 * / \ * 4 5 * / \ * 6 7 * * into these: * * 1 1 * / / * 2---3 2---3 * / * 4---5 * / * 6---7 * * where 6 is the new root node for the left tree, and 2 for the right tree. * oriented correctly: * * 6 2 * / \ / \ * 7 4 3 1 * / \ * 5 2 * / \ * 3 1 */
| Report Duplicate | Flag | PURGE
Linkedin - 4of 4 votes
AnswersWrite code to generate all possible case combinations of a given lower-cased string. (e.g.
- An Enthusiast March 25, 2014 in United States"0ab" -> ["0ab", "0aB", "0Ab", "0AB"])
| Report Duplicate | Flag | PURGE
Yelp Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible
- geekofthegeeks November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersWAP a program to find a contineous subset whose sum is divisible by 7. We are given a array of number (negative+positive).
- yogi.rulzz October 26, 2013 in India
calculate the complexity of your algorithm| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|+|b-c| +|c-a| is minimum.
- Rahul Sharma September 16, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 4of 4 votes
AnswersCar parking problem. An array given represents actual order of cars need to be parked. Like for example order is 4,6,5,1,7,3,2,empty. If cars are parked in some order like empty,1,2,3,7,6,4,2. Some person needs to get them into correct order, list out all instructions to the person to get in correct order with least number of swaps.
- hulk April 16, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 4of 4 votes
AnswersGiven a singly linked list: 1->2->3->4->5
- rainnyforeverluv December 09, 2016 in United States
Change it to 1->5->2->4->3 using O(1) space| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 4of 4 votes
AnswersDesign a data structure that supports kind of full text search but in numbers.
- coredo July 14, 2015 in United States
We are given file with lot of 10-digits numbers, for example:
1234 567 890
4124 123 123
3123 123 322
On a given number X we should return all numbers that contain X.
For example, if the number 123 was given, we should return all numbers (from the list above) because 123 is in all of them.
If the number 41 was given we should return only the middle number - because the number 41 is only in it.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Data Structures - 4of 4 votes
AnswersConsider the array 3 5 7 6 3.
- Gaile April 10, 2014 in United States
Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= 2.
Output:
(0,0) (1,1) (2,2) (3,3) (4,4) (5,5)
(0,1) (1,2) (1,3) (2,3)
Example slices: 3 5, 5 7, 1 3, 2 3.
The following link
https://codility.com/media/train/solution-count-bounded-slices.pdf
has O ( n ) solution. But couldn't understand the O (n ) solution. Could some one explain with an example?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 4of 4 votes
AnswersAn application given to you, but you dont have any documents for that appln. You need to test that application... How will you do??
- Nisha May 29, 2012 in India
Also, if you analyze the appln and find the flow for it how will you ensure that the flow u found is the right one??| Report Duplicate | Flag | PURGE
Aspire Systems Testing / Quality Assurance Testing - 4of 4 votes
Answersgiven an 2D matrix M, is filled either using X or O, you need to find the region which is filled by O and surrounded by X
- smit February 14, 2014 in India
and fill it with X.
example 1:
X X X X X
X X O O X
X X O O X
O X X X X
Answer :
X X X X X
X X X X X
X X X X X
O X X X X
example 2:
X X X X X
X X O O X
X X O O O
O X X X X
answer 2:
X X X X X
X X O O X
X X O O O
O X X X X| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersSuppose you have to maintain the stock values of various companies during various periods and return minimum stock value of a particular company over a given period of time.what data structure is best for this.
- nishu November 07, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Intern Data Structures - 4of 4 votes
Answersthere is a bunch of tasks, each have different time to complete, task is independent, and then there are some workers,
- ajay.raj March 18, 2017 in United States
How to allocate tasks to these workers to minimize the total time to complete all the task. The tasks can be randomly picked from the task list.
Example
Task: 2,2,3,7, 1
Worker: 2.
Return 8, because the first worker can work on the first three tasks : 2 + 2 + 3 = 7, and the second worker can work on the last two tasks : 7 + 1 = 8, so the total time to finish all the task is 8.
public int getMini(int[] tasks, int k)| Report Duplicate | Flag | PURGE
Facebook SDE1 - 4of 4 votes
AnswersGiven a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.
Example:Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5
Edit: Thanks, wangchenClark0512, forgot about C to D
- djway August 18, 2016 in United States
Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.
Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 4of 4 votes
AnswersThis is one of the interview questions during the Amazon SDE interview. Request your help in providing the solution.
- satish1987 August 12, 2015 in United States
Question - We are interested in building a special type of sequence. for a given number N, we want to arrange the numbers {1,1,2,2,3,3,... N,N} such that they have the following property.
For each number / in (1,N) there should be exactly / numbers between the first appearance of the number and the second appearance. Below example would clarify further.
Input:
A Single number N for which we want to produce the sequence.
Output:
A space separated list of sequence or NA if there is no possible sequence.
Example Input:
3
Example Output:
2 3 1 2 1 3
Explanation : There is 1 number between 1s(2). There are 2 numbers between the 2's(3 1 ). There are 3 numbers between the 3's(1 2 1 ).| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 4of 4 votes
AnswersImplement a simple regex parser which, given a string and a pattern, returns a boolean indicating whether the input matches the pattern. By simple, we mean that the regex can only contain one special character: * (star). The star means what you'd expect, that there will be zero or more of any character in that place in the pattern. However, multiple consecutive stars are allowed. Some examples of valid input (and expected output):
- DJ April 20, 2013 in United States
f(a*b, acb) => true
f(abc*, abbc) => false
f(**bc, bc) => true| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Coding - 4of 4 votes
AnswersGiven two strings, find that the if the letters in both the strings are same? i.e. can we be able to make string2 out of string1 by shuffling the words and vice versa.
- saikrishna chunchu April 17, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 4of 4 votes
Answersinput - 2D array of characters and a text pattern. program to find if pattern is present in array or not. a cell can't be used twice for pattern matching. return 1 if true or 0 otherwise.
- pop_front September 11, 2013 in United States
eg :
Matrix
{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i', 't'}
and search for "microsoft"| Report Duplicate | Flag | PURGE
Microsoft Algorithm