Software Engineer / Developer Interview Questions
- 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 3 votes
AnswersFind top K(1000) strings that occur frequently from a file having some billions of strings.
- Boyer Moor February 20, 2014 in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer - 0of 0 votes
AnswersGiven a list of 'N' coins, their values being in an array A[], return the minimum number of coins required to sum to 'S'
- Boyer Moor February 20, 2014 in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a BST, replace each node with the sum of the values of all the nodes that are greater than that node. Only constraint being that I was not allowed to use any global or static variable.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - -2of 2 votes
AnswerDesign a meeting scheduler. The solution I came up with was to create an array of intervals for each day, so if intervals is 15 mins, then array size would be 24*4. However, if interval is small, that will substantially increase the size of the array, and that might be considered as a waste of space, though it supports O(1) look up. I was wondering if there is any other way to do this. I think we might be able to keep a sorted array of meetings sorted by start time, so look up would be O(logn). But insertion in the middle of the array would take O(n) since it requires data shifting.
- Guy February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
Answerspublic interface Permutations {
- Anon February 19, 2014 in United States
/**
* Generate all permutations of given sequence of elements.
* Return a list of all distinct permutations.
*
* E.g.
* generate([1, 2, 3]) -> [1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]
*/
vector<vector<int>> generate(vector<int> items);
}| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Coding - 0of 0 votes
Answerspublic interface InfluencerFinder {
- Anon February 19, 2014 in United States
/**
* Given a matrix of following between N LinkedIn users (with ids from 0 to N-1):
* followingMatrix[i][j] == true iff user i is following user j
* thus followingMatrix[i][j] doesn't imply followingMatrix[j][i].
* Let's also agree that followingMatrix[i][i] == false
*
* Influencer is a user who is:
* - followed by everyone else and
* - not following anyone himself
*
* This method should find an Influencer by a given matrix of following,
* or return -1 if there is no Influencer in this group.
*/
int getInfluencer(boolean[][] followingMatrix)| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Arrays - 2of 2 votes
Answers// cat, actor -> T // car, actor -> F bool anaStrStr (string needle, string haystack) { }
Write a function that takes 2 strings , search returns true if any anagram of string1(needle) is present in string2(haystack)
- juny February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
Answerswhat is the use using 8 GB RAM in Operating System if we can manage a process with 2 GB RAM in 32 bit and 64 bit Operating System.
- premnath.velmurugan February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Morgan Stanley Software Engineer / Developer Operating System - -2of 2 votes
AnswersDesign a meeting scheduler. One way is to use an array to represent each interval, like every 15 mins. Although it provides O(1) look up, if interval is small, it seems like we are wasting a lot of space. Any alternative approach that can save space? If we keep a sorted array of meetings sorted by start time, look up will be O(logn), but inserting the new meeting in the middle of the array will require shifting elements, which is O(n).
- Guy February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 4 votes
AnswersFinding a pair of elements from two sorted lists(or array) for which the sum of the elements is a certain value. Anyway solution that can do better than O(a.length + b.length)?
- Guy February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersI/P: N, k
- poorna.chandra.akp February 19, 2014 in United States
O/P: all subset of N with exactly K elements.
eg: I/p: N = 5, K =3
O/p:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
2 3 4
2 3 5
3 4 5| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 1of 1 vote
AnswersOne of the many ways of representing a tree is to have an array(of length same as number of nodes), where each element in the node denotes the parent of that node.
- avinash February 18, 2014 in India
Eg -
{-1, 0, 0, 1, 1} would represent a tree with -
* 0 as root
* 1 and 2 as children of 0
* 3 and 4 as children of 1
Given a similar representation, you have to print reverse level order traversal of the corresponding tree.
Level order traversal of a tree is where we traverse levels of tree one by one.
Eg -
For the above given tree, level order traversal would be -
0
1 2
3 4
And hence, the reverse level order traversal is -
3 4
1 2
0
Please note -
* An element with parent = -1 is the root element.
* An element with the least index becomes the left most child. (ie. a node with always be on left of all its siblings that have higher index than it)
* When printing a level of tree you need to maintain left to right order.
Input Format -
First line of the input contains number of nodes in the tree (N)
Next line contains N (space seperated) numbers that denote where i-th number will denote the parent node of i-th node.
Output Format -
Print reverse level order traversal of the corresponding tree, with every new level starting in a different line.
Notes/Limits -
* 1 <= N <= 50
* There will be only one root element in any given test case
* Given numbers will always form a valid undivided tree
* Output should be in the exact format as specified (including whitespaces)
Sample Test Cases -
Input -
5
-1 0 0 2 1
Output -
4 3
1 2
0
Input -
9
8 7 0 5 5 8 7 0 -1
Output -
1 6
2 7 3 4
0 5
8
Input -
45
24 42 4 30 29 43 22 15 26 36 26 16 3 22 21 41 18 16 34 41 12 29 32 30 43 15 4 38 36 -1 24 42 18 6 21 38 6 17 32 17 3
34 12 14 14
Output -
1 31
20 42 9 28
12 40 33 36
3 23 37 39 6 13 27 35
0 30 11 17 22 38 7 25
5 24 16 32 15 19
8 10 43 44 18 41
2 26 14 34
4 21
29
Input -
33
17 25 0 14 7 2 5 25 18 8 16 27 10 9 19 7 31 31 19 0 8 14 9 17 18 2 30 16 30 10 5 -1 27
Output -
13 22
26 28 4 15 9 20
6 30 1 7 3 21 8 24
5 25 14 18
12 29 11 32 2 19
10 27 0 23
16 17
31| Report Duplicate | Flag | PURGE
Flipkart Software Engineer / Developer Trees and Graphs - 3of 3 votes
Answerswe have a random list of people. each person knows his own height and the number of tall people in front of him. write a code to make the equivalent queue.
- pari February 18, 2014 in United States
for example :
input: <"Height","NumberOfTall","Name">,
<6,2,"A">,<1,4,"B">,<11,0,"C">,<5,1,"D">,<10,0,"E">,<4,0,"F">
output: "F","E","D","C","B","A" --> end of queue| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiving a number T, print out all possible ways to get to T.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 17, 2014 in United States
For example
T= 5
1 + 1 + 1 +1 +1
2 + 1 + 1 + 1
3 + 1 +1
2 + 2 + 1
4 + 1
3 + 3
Note that, 3 + 2 is equal than 2 + 3, so you don´t have to print both cases.
What is the time complexity? ( VERY IMPORTANT TO ELABORATE ) Brute force is not allow.| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a string, rearrange the string to a palindrome and return the palindrome if present or -1
- user124 February 17, 2014 in India
Example:
i/p
abb
ab
o/p
bab
-1| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersSerling Enterprises buys long steel roads and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises charges for a road of length i inches. Road lengths are always an integral number of inches.
The rod-cutting problem is the following: Given a rod of length n and a table of prices V for {1,2...n} determine the maximum revenue Rn obtain by cutting up the road and selling the pieces.
Table:
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 16, 2014 in United Stateslength i 1, 2, 3 ,4 ,5 , 6 , 7 , 8 , 9, 10 price Pi 1, 5, 8, 9, 10,17,17,20,24,30
| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Algorithm - 3of 5 votes
AnswersPrint all palindromes of size greater than equal to 3 of a given string. (DP)
- amnesiac February 15, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm - 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 - 0of 4 votes
AnswersGiven an array of n elements (a1,a2,..ai,...,an). You are allow to chose any index i and j, such that (i!=j) and allow to perform increment operation on ai = ai+1 and decrements operation on aj = aj - 1 infinite number of times. How many maximum number of elements you can find that have same number.
- smit February 14, 2014 in India
example 1:
1 4 1
ans: 3
example 2:
2 1
ans : 1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 2 votes
AnswersGiven an array of n elements (a1,a2,..ai,...,an). You can allow to chose any index i and j, such that (i!=j) and allow to perform
- smit February 14, 2014 in India
increment operation on ai = ai+1 and decrement operation on aj = aj-1 infinite number of times.
How many number of elements you can find which have same numbers.
example 1:
1 4 1
ans: 3
example 2:
2 1
ans : 1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 2of 2 votes
AnswersWrite an application in Java to simulate file system. For e.g. implement commands: ls -l (list contents of director sorted by name), cd .. (to go to parent directory), pwd to return the complete path to current directory etc. It was a 2 hour remote programming test.
- techpanja February 13, 2014 in United States
Your system will have Directory and Files. A directory can contain files and other directories.| Report Duplicate | Flag | PURGE
Salesforce Software Engineer / Developer - 0of 0 votes
AnswersSubset Sum
- codeninja50 February 13, 2014 in United States
Given a target value and a list of numbers to pick from, pick numbers from the list such that the numbers picked add up to the target value.
For example, if given a target value of 150 and a list of numbers to pick from consisting of 1, 2, 100, 22 and 28, the correct answer would be 100, 22 and 28 because 100 + 22 + 28 =150. If given a target value of 30 and the sample numbers to pick from were 1, 2, 100, 22 and 28, the correct answer would be 28 and 2 because 28 + 2 = 30.
NOTE: Once you use a number from the list you cannot pick it again.
NOTE: If no combination of numbers adds up to the requested value, the correct answer is "No combination matches".
NOTE: There can be more than one correct answer. For example, for target value 3 and list 1, 2 and 3 the correct answer would be either: 1, 2 or 3. You only need to return 1 correct answer not all of them.
Write a program that takes a list of numbers from the command line. The first number is the target value and the reminder of the numbers (however many there may be) is the set of numbers you have to pick from. The program should either output a subset whose sum equals the target or "No combination matches" if no such subset exists. We would prefer you use Java or C# on this program, but you can use another procedural language if you don't know Java or C#.
For example, the following inputs should yield the following results:
SubsetSum 15 1 2 3 5 7 10
{3,7,5}
SubsetSum 9 1 2 3 5 7 10
{2,7}
SubsetSum 100 1 2 3 5 7 10
No combination matches| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersDesign a parking lot system where you need to provide a token with the parking space number on it to each new entry for the space closest to the entrance.
- duskan February 13, 2014 in United States for Sales
When someone leave you need update this space as empty.
What data structures will you use to perform the closest empty space tracking, plus finding what all spaces are occupied at a give time.| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind median from a stream of flowing numbers
- duskan February 13, 2014 in United States for Sales| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array of meetings, find out the minimum number of conference rooms required.
- animageofmine February 12, 2014 in United States
class Meeting
{
long startTime;
long endTime;
};
Got 20 minutes to think through and write the code. Too short in my opinion, but well, it seemed like the interviewer didn't understand C++ either :-).| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - -1of 1 vote
AnswersPlayer turns are stored in an array like so [1,2,1,2,1,2,1,2]. Make it so that player 1 finishes first and then player 2. i.e [1,1,1,1,2,2,2,2]
- ss123 February 11, 2014 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer - 0of 0 votes
AnswersAn array contains the following elements [9,6,-3,1,7] and a value is equal to 4. Find a pair of numbers in the array that equal the sum.
- ss123 February 11, 2014 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer - -7of 11 votes
AnswersGiven a circle with N defined points and a point M outside the circle, find the point that is closest to M among the set of N. O(LogN)
- Guy February 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -6of 6 votes
AnswersGiven a preorder traversal, create a binary search tree in optimized time
- Guy February 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm