Recent Interview Questions
- 1of 1 vote
AnswersGiven three strings str1, str2 and str3; complete the function to find the smallest subsequence in str1 which contains all the characters in str2 (in any order) and not those in str3.
- ankur.emailid April 21, 2014 in India
Sample Test Case:
Sample Input:
str1: spqrstrupvqw
str2: sprt
str3: q
Sample Output: strup
Explanation: In the given string str1, the smallest subsequence that contains the characters in str2 ( 's' , 'p' , 'r' , 't' ) and does not contain the character in str3 ( 'q' ) is 'strup'.| Report Duplicate | Flag | PURGE
Morgan Stanley Java Developer String Manipulation - 1of 1 vote
AnswersGiven a huge file 100 million integers. He further divided the file into 100 files with 1 million integers in each and each file is sorted. Needed to find the k smallest integers.
- pulkit.mehra.001 April 07, 2014 in India
I used the concept of min-heap. Take the first element from each file and construct a min-heap. Take the root,as it is the smallest element and insert the next element from the file which contains the root root element. Heapify the tree and repeat k times.
The interviewer asked if another efficient method exists?| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 3of 3 votes
AnswersGiven a set of intervals like 5-10, 5-10, 8-12, 9-15
- blackfever April 03, 2014 in India
Find the ith smallest number in these intervals.
for eg:-
Suppose we have intervals like 5-10, 8-12.
Then total numbers in these two intervals would be: {5,6,7,8,8,9,9,10,10,11,12}
So, 1st smallest number: 5
4th smallest number: 8
5th smallest number: 8 (here is the
change since now we have duplicate elements also) and so on.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 2 votes
AnswersFind the k-th Smallest Element in Two Sorted Arrays. I followed the algorithm from this post, http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
But it does not handle the case where there are duplicates? Does anyone know how to do that? Also, in Java, how should we reduce the size of the arrays? I used the code below, but did not work.
- Guy February 20, 2014 in United Statespublic static int kthSmallest2(int[] a, int[] b, int k, int a_left, int a_right , int b_left, int b_right) { if (a_left==a_right) return b[k-1]; else if (b_left==b_right) return a[k-1]; int m = a_right-a_left, n=b_right-b_left; int i = (int)((double)m / (m+n) * (k-1)); // i can be any number // make sure i + j = k - 1 // int i = (a_left+a_right)/2 + k/2; // i can be any number int j = k - 1 - i; int bj_1 = 0, ai_1 = 0; if (i==0) { ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound else { ai_1 = a[i-1]; } if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound else { bj_1 = b[j-1]; } if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j] return a[i]; if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i] return b[j]; if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must // reside before kth smallest, so also update k. // also exclude b's upper bound, since they are all greater than kth element. return kthSmallest2(a, b, k, i+1, a.length-1, 0,j-1); else return kthSmallest2(a, b, k, 0, i-1, j+1, b.length-1); }
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
AnswersThere is a string , where a character is missing.Print the missing character.The range is present in the string and the characters are case sensitive.
- write2bikash February 19, 2014 in India
For example:-If input is "baADfc".
Here the range is a to f.
The missing character to be printed is e.
.| Report Duplicate | Flag | PURGE
Morgan Stanley Java Developer Coding - 2of 2 votes
AnswersThere is a large file( 1TB) containinig braces. Question is to check for their balance. I said will use a counter, will increment on an open brace and decrement on an close brace. If counter goes negative or counter is non zero at the end of the file, braces are not balanced. Otherwise balanced. Followup question was to make this process parallel ( meaning to see if this problem can be solved through parallelism, like dividing the the problem into sub problem....) Remember the file is very large.
- gns January 23, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Problem Solving - 3of 3 votes
AnswersSuppose you are supplied with a file containing a list of words like ABC, BCD , CAB ( say each word in new line ). now you have to suggest algorithm for this problem -
- ajitpec November 21, 2013 in India
When a user type some character, we have to suggest him next character and basis of suggestion is that the character you are going to suggest should have maximum occurrence at that position among all these words.
For example , Let's say words are
ABC
BCD
CBA
Now if user types 'A' we have to suggest him 'B' as next character because if you see at second position in all words 'B' is occurring most number of times ( 2 times ).
similarly if he types 'AB' then we need to suggest him third character as 'C' as in third index all words have same occurrence but 'C' comes first.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 5of 7 votes
AnswersInput - array of integers size N, integer Threshold. Output - the number of pairs (x, y) of distinct elements with condition x + y <= Threshold. Is that possible to implement it with O(n) ?
- anonymous October 04, 2013 in United States| Report Duplicate | Flag | PURGE
Google Java Developer - -4of 6 votes
AnswersRotate a M*N matrix by 90 degree.
- sivaji8 October 02, 2013 in United States
Is this answer right?
public void rotateMN(int[][] input){
int i = input.length;
int j = input[0].length;
int m = j;
int n = i;
int[][] newArray = new int[m][n];
for(int j = input[0].length-1, m=0; ;i--, m++ ){
for(int i = input.length-1, n=0; i >= 0 ; i--, n++){
newArray[m][n] = input[i][j];
}
}
}
Will this also work for N*N matrix rotation by 90 degrees?
The time complexity is O(N) since it just traverse the input matrix and copy it to the new matrix. The space complexity is (MN) + (MN) = So MN.
Is it possible to do rotation for M * N matrix in space? If so please provide that answer
Whats this space and time complexity?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 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 - 3of 13 votes
AnswersPrint the numbers between 30 to 3000.
- Anonymous September 25, 2013 in United States
CONSTRAINT:
The numbers shouldnt contain digits either in incresing order or decreasing order.
FOLLOWING NOT ALLOWED
##123,234,345,1234,2345##increasing order,
##32,21,321,432,3210 etc##decresing order.
FOLLOWING ALLOWED:
243,27,578,2344 etc.,
Now see who ll code ths....| Report Duplicate | Flag | PURGE
Microsoft Developer Program Engineer - 2of 2 votes
Answersc program to find square root of an interger without using in built functions
- saran August 12, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Intern C - 2of 2 votes
AnswersOutput the leftmost element of each level of a tree
- 3139a1m August 01, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Intern - 0of 0 votes
AnswersGiven +ve numbers in an array . Put the even #s to the left of the array and the odd to the right side of the array . Don't use extra array.
- meek June 05, 2013 in United States| Report Duplicate | Flag | PURGE
VMWare Inc Java Developer Coding Java Probability - 3of 3 votes
AnswersThere are exactly N advertising boards on the highway. Now a company want to advertise on some of these advertising boards (each advertising board costs some money).
- Naveen Reddy Mandadi May 24, 2013 in United States
Company strategy is that, they want at least 'K' advertisement should be there among M consecutive advertising boards. But at the same time Company want to pay minimum for its advertisement.
Now, what is the total number of ways Company can advertise meeting its minimum cost strategy.
Also 1 <= K <= M <= 50 and M <= N <= 10^9
As for Example: N = 3, M = 2, K = 1 ==> there is only one way for minimum cost, ie. 0C0 , where '0' denotes No company advertisement, and 'C' denotes company advertisement board.
Similarly, for N = 4, M = 2, K = 1 ==> there are 3 possible ways, ie. C0C0, 0C0C, 0CC0.| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 2of 2 votes
AnswersConsider a city (visualize a circle). It has n petrol stations in it. You are given the maximum amount of petrol that can be filled at each of these stations. You are also given the distance between one station to the next one. The aim is to cover the entire city and come back to the start point. Assume that 1 liter of petrol will last for 1km.
- D March 27, 2013 in India
Q: List out all the possible petrol stations from where the journey can be started, so as to cover the city.| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Algorithm - 0of 0 votes
AnswersSay there are 3 array lists l1, l2 & l3 of same length. Thress threads accessing three lists. Say T1 -> l1, T2 ->l2 & T3 ->l3. It should print in the order say first element of 1st then first element of 2nd list and then first element of 3rd list. Then second element of 1st then second element of 2nd list and then second element of 3rd list.
- rizwan.amd March 26, 2013 in India| Report Duplicate | Flag | PURGE
Novell Tech Lead Threads - 1of 3 votes
AnswersWrite a program to find the element in an array that is repeated more than half number of times. Return -1 if no such element is found.
- Expressions March 19, 2013 in India| Report Duplicate | Flag | PURGE
Linkedin SDE1 Arrays - 0of 0 votes
AnswersHow can I find if a String exists in a double dimension Array. For eg. Does CAT exist in
- Abhi March 04, 2013 in United States
'c','b','k'
'd','a','l'
'g','t','i'
It does exist. What will be an optimal way to do it ?
Assume you don't have to move upwards in the Array.
So in the below Array cat does not exist.
'c','b','t'
'd','a','l'
'g','J','i'| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm - 0of 0 votes
AnswersGiven a BST and a node, write a function to find the next biggest element in the BST in preferred language.
- Srikanth February 15, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersFlip a monochrome bitmap around its centre-line, where input is: char *bytes, int width, int height .
- kbex07 January 25, 2013 in United States
Example:
Input
0101 0110
1111 0011
Output
0110 1010
1100 1111| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 0of 0 votes
AnswersGiven an integer, return all sequences of numbers that sum to it. (Example: 3 -> (1, 2), (2, 1), (1, 1, 1)). Interview was for a php position.
- AnthonyKiedis January 23, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm PHP - 1of 1 vote
AnswersReverse Linked list in parts iteratively.
- praveen January 11, 2013 in United States for Bing-Appex
ex 1->2->3->4->5->6->7->8 and if 'parts' is 3.
o/p = 3->2->1->6->5->4->8->7.| Report Duplicate | Flag | PURGE
Microsoft Intern - -1of 1 vote
AnswersRound 2 :
- sonesh January 03, 2013 in India
Q 3 : you are given some nodes, and for each node a probability is given which will tell its importance, you need to design an efficient data structure such that the expected search time as minimum as possible. (Hint : Use dynamic programming + binary tree).| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Dynamic Programming Trees and Graphs - 0of 0 votes
AnswersGiven a matrix of n X n. You need to find any local minima.
- Anonmyous September 30, 2012 in India
Local Minima is defined as an element covered (neighboured) by the greater numbers.
For example - a[i][j]=4, then a[i+1][j] >4 and a[i-1][j]>4 and a[i][j+1]>4 and a[i][j-1]>4.
If it is a boundary element, only compare with its watever the available sides.
Complexity that they want is less than O(n2)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a binary tree and 3 nodes x,y,z, write a function which returns true if y lies in the path between x and z and false otherwise. Its been posted couple of times in past in careercup blogs, still couldn't find an apt solution which considers corner cases like
- novice12 August 29, 2012 in India
y
/ \
z x| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersDynamic programming problem: Coin change problem: Find the minimum number of coins required to make change for a given sum (given unlimited cumber of N different denominations coin)
- Anonymous July 19, 2012 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm - 0of 0 votes
AnswersInput:
- Nikhita July 18, 2012 in India
3
3 1 2
nny
nnn
ynn
output:
2 1 3
n size of permutation P.First line of input is n.Second line is the permutation P.A Permutation X is said to be lexicographically smaller than Y if for all digits till i X[i]=Y[i] and for i+1 X[i]<=Y[i]so you can exchange the integers in the given permutation P if character j of line i+2 is 'y' then i th and j th integer in P can be exchanged .
Output:Lexicographically smallest premutation of the given P using rule| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Coding - 0of 0 votes
AnswersGiven an array of positive integers, print out all the numbers which are repeated an even
- chad July 18, 2012 in United States
number of times? Can you do this without using additional storage?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind the kth smallest element in an array. How can we do it without sorting the array.
- samant.bit July 13, 2012 in India| Report Duplicate | Flag | PURGE
Amdocs Software Engineer / Developer