Algorithm Interview Questions
- 2of 2 votes
AnswersCheck if the given binary tree is BST or not.
- aopencv June 14, 2013 in United States| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Algorithm Data Structures Java - 2of 2 votes
AnswersGiven an Array A with n elements. Pick maximum number of elements from given array following the rule:
- chan alex September 25, 2016 in United States
1. We cannot pick A[i] and A[j] if absolute value of (A[i] - A[j]) > absolute value of (i - j)
Example: {13,5,4}
Ans: 2
Pick 5 and 4.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersA museum was represented by a square matrix that was filled with O, G, and W where O represented open space G represented guards, and W represented walls. Write a function that accepts the square matrix and returns another square matrix where all of the O's in the matrix are replaced with the number of how many spaces they are away from a guard, without being able to go through any walls.
- fire May 17, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Android Engineer Algorithm - 2of 2 votes
Answers{{
- skc25pma February 02, 2015 in India
There are 3 machines M1, M2 and M3. Each machine is 90% full of its capacity with integers. Now you have to sort all the integers combined and then store the first 1/3rd in M1, second 1/3rd in M2 and last 1/3rd in M3.
Your objective is to minimize the number of sort operations and number of data transfer operations.
Each sort operation/data transfer operation is counted as 1 irrespective of the count of values that are being sorted/transferred.
}}| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Coding Sorting - 2of 2 votes
AnswersGiven an expression (in single variable) like 4x+13(x-(4x+x/3)) = 9, evaluate x
- chochim February 18, 2013 in India
The expression is a string and the variable is always x.| Report Duplicate | Flag | PURGE
Facebook Algorithm - 2of 2 votes
AnswersGiven a stack.
- BlackMath June 26, 2012 in India for KDK - Kindle Development Kit
Can we find range of numbers in the stack ?
Range is Max value in stack - Min value in stack.
Q > How will we design the stack to get Range in O(1) ?
Ans > I answered this one saying we have max variable and min variable defined in the stack. Whenever we push any number into stack, we compare with the current max and update, if necessary. Same with min.
Q > Then, he asked me what happens when we pop ?
If the element to be popped is the max element, how do we find the second max to be the new max element.
Ans > This, i answered we maintain two different stacks inside a stack called maxStack and minStack for max and min elements. He asked me to code everything. I did.
Then, he asked me if there are duplicates in the stack, can we optimise our solution so that the max element doesn't get inserted into the maxStack more than once and still we get all the above functionalities in optimised way ?
Ans > I answered we maintain a map of integer and it count. When we push into the stack, if the element is already there in the stack, we increase its count and update the maxStack or minStack, if necessary. When we pop, we decrease the count. If count becomes 0, then we update the maxStack and minStack, if necessary.
I coded everything then.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersAn array of integers of size n-1, all the elements are form [1,n]. Find the missing number. You can read only one bit in one operation, ie, to read A[i], you need to perform log(A[i]) operations.
- binu May 28, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Arrays Bit Manipulation - 2of 2 votes
AnswersGiven the root of a binary tree, print the nodes column wise and row wise.
..............6 ............/....\ ...........9......4 ........../..\......\ .........5....1.....3 ..........\........./ ...........0.......7
The answer would be 5 9 0 6 1 4 7 3.
- Champaklal October 26, 2018 in United States| Report Duplicate | Flag | PURGE
Facebook Software Developer Algorithm - 2of 2 votes
AnswersGiven a Pattern and a dictionary, print out all the strings that match the pattern.
- ad09 August 02, 2016 in United States
where a character in the pattern is mapped uniquely to a character in the dictionary ( this is what i was given first).
e.g 1. ("abc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "cdf"
2. ("acc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "too", "paa"| Report Duplicate | Flag | PURGE
Google Algorithm - 2of 2 votes
Answers1. Balanced Parentheses
- siva.sai.2020 October 18, 2015 in India
Given a string s of parentheses (ex: “(()”), return the minimum number of parentheses that need to be inserted to make it into a well formed string
A well formed (balanced) string of parentheses is defined by the following rules: ● The empty string is well formed. ● If s is a well formed string, (s) is a well formed string. ● If s1 and s2 are well formed strings, their concatenation s1s2 is a well formed string.
Implement
int MinNumInsersertionsForBalancing(const string& s)| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 2of 2 votes
AnswersYou have String array like{'cat','good','tac','act''....} like some 1000 words.
- pogiriykirankumar January 10, 2015 in India
So if i give input tac ,output should be cat and act..
How can we implement with less complexity| Report Duplicate | Flag | PURGE
Goldman Sachs Software Engineer / Developer Algorithm - 2of 2 votes
AnswersYou are given a text file that has list of dependencies between (any) two projects in the soure code repository. Write an algorithm to determine the build order ie. which project needs to be build first, followed by which project..based on the dependencies.
- enok August 18, 2014 in United States
Bonus point: If you can detect any circular dependencies and throw an exception if found.
EX: ProjectDependencies.txt
a -> b (means 'a' depends on 'b'..so 'b' needs to be built first and then 'a')
b -> c
b -> d
c -> d
Then the build order can be
d , c, b, a in that order| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
Answersgiven a string determine which character appears the most and the number of times that character appeared.
- Glenwright327 April 25, 2014 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 2of 2 votes
AnswersFor a given node in binary search tree find a next largest number in search tree.
- zealswap March 11, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersA soda water machine,press button A can generate 300-310ml, button B can generate 400-420ml and button C can generate 500-515ml, then given a number range [min, max], tell if all the numers of water in the range can be generated.
- mario87 December 18, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersEngineers at Google have decided to call any integer (+ve, -ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) as Walprimes. Thus -21, -30, 0, 5, 14 etc are Walprimes, while -121, 1, 143 etc. are not Walprimes.
- geekofthegeeks October 26, 2013 in India
Now, consider a n-digit integer d1d2d3..dn. Between any 2 consecutive digits you can place either a (+) sign, a (-) sign or nothing. So, there are 3n-1 different expressions that can be formed from it. Some of the expressions so formed may evaluate to a Walprime. For example, consider the 6 digit integer 123456: 1 + 234 - 5 + 6 = 236, which is a Walprime, but 123 + 4 - 56 = 71, which is not a Walprime.
Your task is to write a program to find the no. of expressions (out of the possible 3n-1 expressions) that evaluate to a Walprime, for a given input. Note that leading zeroes are valid. For example, if the input is 1202004, it can be split as 12 + 020 - 04 etc. Also, the input itself can contain leading zeroes.
Input format: (Read from stdin)
The first line of input contains a single integer 'T' denoting the no. of test cases.
Each of the following 'T' lines contain a single string 's' (of length 'n') denoting an input for which you need to find the no. of valid expressions evaluating to a Walprime.
Output format: (Write to stdout)
Output exactly 'T' integers (one per line), where the ith line denotes the no. of valid expressions that evaluate to a Walprime for the ith input string. Since the output can be large, print all the quantities modulo 1000000007.
Sample testcase:
Input:
2
011
12345
Output:
6
64
Explanation:
For the first test case, s = "011". There are 32 = 9 valid expressions that can be formed from this string, namely {0+11, 0-11, 0+1+1, 0+1-1, 0-1+1, 0-1-1, 01+1, 01-1, 011} . Out of these 9 expressions, only the following 6 of them evaluate to a Walprime: {0+1+1, 0+1-1, 0-1+1, 0-1-1, 01+1, 01-1}.
Constraints:
There are 3 data sets.
For the first data set (5 points) -
1
For the second data set (10 points) -
1
For the third data set (15 points) -
1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersQuestion 1 / 3 (Odd even level difference)
- Harjit Singh September 27, 2013 in India for TCS
You are given a function calcDifference which takes in the root pointer of a binary tree as it's input. Complete the function to return the sum of values of nodes at odd height - sum of values of node at even height. Consider the root node is at height 1
Sample Input:
Sample Output
-74
Explanation:
[ (1 + 4 + 5 + 6 + 7 ) ? (2 + 3 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = -74 ]| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C++ Trees and Graphs - 2of 2 votes
AnswersUser inputs a sequence of digits. Every digit is a keystroke, that is equivalent to some character out of a sequence of characters. Digit zero and five mean NULL. The table is given below
- ranechabria July 14, 2012 in United States
0 - NULL
1 - v, t, f, r, q
2 - f, t, k
3 - w, z, b, g
4 - r, s
5 - NULL
6 - f, i, r
7 - p
8 - l, o
9 - p
Generate all possible character sequence for a given sequence of digits.
Ex - If the user input 9801, your program should generate
{plv, plt, plf, plr, plq, pov, pot, pof, por, poq} (not necessarily in this order).
This problem is somewhat similar to the SMS problem. It basically boils down to generating a cartesian product of the character sets corresponding to keys.| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm Coding Data Structures - 2of 2 votes
AnswersI have two arrays A and B(each containing 8 bit integers). Find the common elements between them.
- puneet.sohi April 28, 2014 in United States for AWS
The questions started out as a general discussion with the most inefficient method. Then the interviewer asked me to improve the solution (to give a NlogN and finally a linear time solution)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
Answersimplement division without using division operator in log(n) time.
- !@# April 22, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven an integer, print out all the prime numbers smaller than that integer.
- tielongs October 31, 2013 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer Intern Algorithm - 2of 2 votes
AnswersGiven a set of numbers from 1 to n squared, generate unique sub-sets consisting of n numbers such that each subset has one and only one matching number from any other sub-set
- msjob99 April 11, 2012 in United States
The max number of sub-sets is n squared + n
An example is as follows:
n = 3
n squared set = 1, 2, 3, 4, 5, 6, 7, 8, 9
sub-set 1 = 1, 2, 3
sub-set 2 = 1, 4, 7
sub-set 3 = 1, 5, 9
sub-set 4 = 1, 6, 8
sub-set 5 = 2, 5, 8
sub-set 6 = 2, 4, 9
sub-set 7 = 2, 6, 7
sub-set 8 = 3, 6, 9
sub-set 9 = 3, 5, 7
sub-set 10 = 3. 4, 8
sub-set 11 = 4, 5, 6
sub-set 12 = 7, 8, 9
Write the C++ algorithm that will work for any arbitrary integer value n. The n-squared set can be placed into any built in C++ data structure eg 2d array.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 2of 2 votes
AnswersFind the largest substring palindrome in a given string.
- revanthpobala October 01, 2015 in United States
ex: input: abbac output: abba
Solution: Use Hashmap| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm - 2of 2 votes
AnswersPrint a tree in Level Order with a newline after each depth
- PrateekS. July 29, 2014 in United States/** * Sample input: * * 1 * / \ * 3 5 * / \ \ * 2 4 7 * / \ * 9 8 * * Expected output: * 1 * 3 5 * 2 4 7 * 9 8 * ========== */
| Report Duplicate | Flag | PURGE
Linkedin Algorithm - 2of 2 votes
AnswersYou are given numbers from 1 through 100 in an array, there is one number missing, find that one
- juny January 26, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersYou can swap only two consecutive elements. You have to show all steps to convert a string into another string (both strings will be anagrams of each other). E.g. GUM to MUG
- codr December 21, 2013 in United States
GUM
GMU
MGU
MUG| Report Duplicate | Flag | PURGE
Epic Systems SDE1 Algorithm - 2of 2 votes
Answers1000 elements in one bag and 1 million elements in another. how do you find common elements among them. Also give the complexity of your solution.
- sivaji8 September 27, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersFollowing sequence is given:
- SK July 07, 2013 in India
1,2,3,4,5,6,8,9,10,12,15,16,18,20,24
In this sequence, each number is multiple of 2,3 or 5 only.
This sequence does not contain 7 & 14 as these number has sequence 7 as multiple.
So, if you are given N find the Nth number of this sequence.| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersIn a BST, I want to replace all nodes with value which is the sum of all the nodes which are greater than equal to the current node.
- Abhishek Shrivastava April 20, 2013 in United States
5
2 10
Output -->
15
17 10| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersGiven an array of length N. How will you find the minimum length
- abhishek October 19, 2010
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.
was asked in YAHOO CODING ROUND interview| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm