Recent Interview Questions
- 0of 0 votes
AnswersYou have a room-full of balances and weights. Each balance weighs ten pounds and is
- sanjeevmehtaubi December 26, 2011 in India
considered perfectly balanced when the sum of weights on its left and right sides are
exactly the same. You have placed some weights on some of the balances, and you have placed
some of the balances on other balances. Given a description of how the balances are arranged
and how much additional weight is on each balance, determine how to add weight to the balances
so that they are all perfectly balanced.
There may be more than one way to balance everything, but always choose the way that places additional weight on the lowest balances.
The input file will begin with a single integer, N, specifying how many balances there are.
Balance 0 is specified by lines 1 and 2, balance 1 is specified by lines 3 and 4, etc...
Each pair of lines is formatted as follows:
WL <balances>
WR <balances>
WL and WR indicate the weight added to the left and right sides, respectively.
<balances> is a space-delimited list of the other balance that are on that side of this balance.
<balances> may contain zero or more elements.
Consider the following input:
4
0 1
0 2
0
0 3
3
0
0
0
Balance 0 has balance 1 on its left side and balance 2 on its right side
Balance 1 has balance 3 on its right side
Balance 2 has three pounds on its left side
Balance 3 has nothing on it
Since balance 3 has nothing on it it is already perfectly balanced, and weighs a total of 10 pounds.
Balance 2 has no other balance on it, so all we need to do is balance it by putting three pounds on its right side. Now it weighs a total of 16 pounds.
Balance 1 has balance three on its right side, which weighs 10 pounds, so we just put 10 pounds on its left side. Balance 1 weighs a total of 30 pounds.
Balance 0 has balance 1 on its left side (30 pounds), and balance 2 on its right side (16 pounds), we can balance it by adding 14 pounds to the right side.
The output should be N lines long, with the nth line listing the weight added to the nth balance, formatted as follows:
<index>: <weight added to left side> <weight added to right side>
So the output for this problem would be:
0: 0 14
1: 10 0
2: 0 3
3: 0 0| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 1of 1 vote
AnswersGiven a big unsorted list of 64-bit integers, find an element not in list
- novice September 15, 2011 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 0of 0 votes
AnswersA number is given as a palindrome, write a function to return the next largest palindrome.
- Anonymous April 08, 2011| Report Duplicate | Flag | PURGE
Flipkart Software Engineer / Developer Algorithm - 0of 0 votes
Answers3. Given a number of nodes N of a binary tree , how many structurally different full binary trees are possible.
A binary tree is said to be full binary tree , if for every node in the tree there exists exactly zero or 2 children.
Example: When N = 5 , No. of possible trees = 2
- arun February 19, 2011o o / \ / \ o o o o / \ / \ o o o o
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
Answersproblem of binary matrix
- SDE February 01, 2011
Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays
eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an input array of integers of size n, and a query array of integers of size k, find the smallest window of input array that contains all the elements of query array and also in the same order.
- Ankul Garg August 28, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm - 2of 2 votes
Answerssort an array of 0's and 1's in a most efficient way.
- mahi December 23, 2009| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Arrays - 0of 0 votes
AnswersHow to completely delete a linked list with circle?
- uterus October 07, 2009| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 2of 0 votes
AnswersThere are hundred prisoners each standing in a column. Each one is given a hat and there are two possible colors of hat which are red and white. The 100th person can see the hats of 99 people in front of him and the 99th person can see 98 people in front of him but can't see his own and the previous hat. The number of hats aren't known and the hats are placed in random order. Starting with the 100th person, each person is asked what color hat they have. If they guess wrong, they die. Come up with a strategy such that maximum people are alive. How many people are alive? (Do not use probability constraint given)
- preethi natarajan October 31, 2008| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Brain Teasers - 0of 0 votes
AnswersBag A = 10 Red balls.
- Satish October 22, 2008
Bag B = 10 Green balls.
Shuffle bag A move three balls from A => B then
Shuffle bag B move three balls from B => A
Which bag is likely have more number of balls of other color.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Brain Teasers - 0of 0 votes
AnswersYou are given an array of length 99 that contains all the numbers between 1 and 100, except for one number that has been removed. Find the missing element.
- kunal chopra November 03, 2005| Report Duplicate | Flag | PURGE
Amazon Testing / Quality Assurance Arrays - 5of 5 votes
AnswersGiven K sorted (ascending) arrays with N elements in each array, implement an iterator for iterating over the elements of the arrays in ascending order.
The constructor receives all of the input as array of arrays.
You need to implement the MyIterator class with a constructor and the following methods:class MyIterator<T> { T next(); boolean hasNext(); }
You are allowed to use only O(K) extra space with this class.
example:
input:[[1,5,7], [2,3,10],[4,6,9]]
The iterator should return:
- torchs January 13, 2020 in Israel1,2,3,4,5,6,7,9,10
| Report Duplicate | Flag | PURGE
Facebook Solutions Engineer Algorithm - 2of 2 votes
AnswersVerify if S2 = {5,8,2} is a subset of S1 = {1,5,4,6,8,2} and S3 = {5,8,2,7} is not a subset of S1.
- hadeebataj May 10, 2019 in India| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer String Manipulation - 1of 1 vote
AnswersGiven an integer 'n', create an array such that each value is repeated twice. For example
- robb.krakow May 09, 2019 in United States
n = 3 --> [1,1,2,2,3,3]
n = 4 --> [1,1,2,2,3,3,4,4]
After creating it, find a permutation such that each number is spaced in such a way, they are at a "their value" distance from the second occurrence of the same number.
For example: n = 3 --> This is the array - [1,1,2,2,3,3]
Your output should be [3,1,2,1,3,2]
The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.
Return any 1 permutation if it exists. Empty array if no permutation exists.
Follow up: Return all possible permutations.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 1of 1 vote
Answers// For a given vector of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K
- samayragoyal990 February 24, 2019 in United States
// For example, for K = 8 and vector [2, 4, 5, 7], the solution is 5 ([2], [4], [2, 4], [2, 4, 5], [2, 5])
The time complexity should be O(n2). Approach and code was asked| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersGiven an ODD number, print diamond pattern of stars recursively.
n = 5, Diamond shape is as follows: * *** ***** *** *
void print(int n){
- ajay.raj May 20, 2017 in United States
}| Report Duplicate | Flag | PURGE
Facebook SDE1 - 1of 1 vote
AnswersYou have an array of unique integer numbers and only one operation: MoveToFront(x) that moves given number to the beginning of the array.
- emb July 02, 2016 in United States
Write a program to sort the array using the minimum possible number of MoveToFront() calls.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - -1of 1 vote
AnswersConsider a string, s = "abc". An alphabetically-ordered sequence of substrings of s would be {"a", "ab", "abc", "b", "bc", "c"}. If we reduce this sequence to only those substrings that start with a vowel and end with a consonant, we're left with {"ab", "abc"}. The alphabetically first element in this reduced list is "ab", and the alphabetically last element is "abc". As a reminder:
- guptasunny158 June 12, 2016 in India
Vowels: a, e, i, o, and u.
Consonants: b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, and z.
Complete the findSubstrings function in your editor. It has 1 parameter: a string, s, consisting of lowercase English letters (a − z). The function must find the substrings of s that start with a vowel and end with a consonant, then print the alphabetically first and alphabetically last of these substrings.
Input Format
The locked stub code in your editor reads a single string, s, from stdin and passes it to your function.
Constraints
3 ≤ length of s ≤ 5 × 105
Output Format
Your function must print two lines of output denoting the alphabetically first and last substrings of s that start with a vowel and end with a consonant. Print the alphabetically first qualifying substring on the first line, and the alphabetically last qualifying substring on the second line.
Sample Input 1
aba
Sample Output 1
ab
ab
Explanation 1
"ab" is the only possible substring which starts with a vowel (a) and ends with a consonant (b). Because we only have 1 qualifying substring, "ab" is both the alphabetically first and last qualifying substring and we print it as our first and second lines of output.
Sample Input 2
aab
Sample Output 2
aab
ab
Explanation 2
There are 2 possible substrings which start with a vowel and end with a consonant: "aab" and "ab". When ordered alphabetically, "aab" comes before "ab". This means that we print "aab" (the alphabetically first qualifying substring) as our first line of output, and we print "ab" (the alphabetically last qualifying substring) as our second line of output.
Sample Input 3
rejhiuecumovsutyrulqaeuouiecodjlmjeaummaoqkexylwaaopnfvlbiiiidyckzfhe
Sample Output 3
aaop
utyrulqaeuouiecodjlmjeaummaoqkexylwaaopnfvlbiiiidyckzfh
Explanation 3
There are 4830 substrings of s, but only 676 of them start with a vowel and end with a consonant. When ordered alphabetically, the first substring is "aaop" and the last substring is "utyrulqaeuouiecodjlmjeaummaoqkexylwaaopnfvlbiiiidyckzfh".| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm - 3of 3 votes
AnswersGiven a string e.g. ABCDAABCD. Shuffle he string so that no two smilar letters together.
- rajnikant12345 March 13, 2016 in India for Office
E.g. AABC can be shuffled as ABAC.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 String Manipulation - 2of 4 votes
AnswersWe have a long string. We label some substrings with tags.
- Bill December 10, 2015 in United States
- A tag entry is [startIndex, endIndex, tag].
- Query: 1 or more tags
- Output: all blocks/ranges with all queried tags.
Example tag entries:
[23, 72, 0] // label [23, 72) with tag 0
[34, 53, 1] // label [34, 53) with tag 1
[100, 128, 0]
Query and Output:
0 => [23, 72], [100, 128]
0,1 => [34,53] // [34, 53) matches both tag 0 and 1
Give an efficient algorithm. Please describe your algorithm before posting code.
**Edit**: To add some difficulties, partial overlap is treated the same as full overlap, ONLY the overlapped part matches both tags. E.g. if we have entries:
[23, 72, 0] // label [23, 72) with tag 0
[10, 53, 1] // label [34, 53) with tag 1
Query and Output:
0,1 => [23,53] // [23, 53) matches both tag 0 and 1
Minor detials: Note in the comments we used open range on the right, i.e. if the string named "str", [23, 72, 0] includes str[23] but NOT str[72]; and there's no overlap between the following entries:
[23, 72, 0]
[10, 23, 0]| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersFace to Face
- siva.sai.2020 November 29, 2015 in United States
Q4) two arrays given to you. First array contains number s. Second array contains key values.
We need to find smallest window in first array which covers all second array elements.
e.g:
Input= {6,7,1,3,2,4,5,2,3,1,2,5}
Keys = {2,5,1}
answer: from 9th index to 11th index is the smallest window.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven 2D Array of only 0s and 1s, Find the row which gives max decimal value.
- Rajarathinam Antony November 22, 2015 in India
Input: int array[3][3] = {{0,1,0,}{1,1,0},{1,0,1}};
Output : 2(second row)...decimal value is 6| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersGiven predicted stock prices for next n days for a stock e.g : 10, 30, 42, 15, 20, 50, 10, 25 find the maximum profit that can be made with a single buy-sell transaction. If no profit can be made return 0. In the example buying at 15 and selling at 50 gives maximum profit. Note that the two prices are neither minimum nor maximum in the array.
- Kiara October 27, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 2of 4 votes
AnswersYou are given a matrix n rows, m columns where each row is sorted in increasing order. Find median of the overall elements. What is the time complexity?
- emb September 07, 2015 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersGiven two strings, return true if they are one edit away from each other, else return false. An edit is insert/replace/delete a character.
- codewarrior September 07, 2015 in United States
Ex. {"abc","ab"}->true, {"abc","adc"}->true, {"abc","cab"}->false| Report Duplicate | Flag | PURGE
Amazon SDE1