Recent Interview Questions
- 2of 2 votes
AnswersGenerate all numbers in ascending order which are having factors as 2,3 and 5. Discuss various approaches.
- Rahul Sharma March 21, 2014 in India| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm - 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
Answersimplement your own sizeof() operator..
- ishanimahajan7 January 29, 2013 in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ - 2of 2 votes
AnswersYou have one table with a single column having three values a,b and c.
- Black Stallion July 26, 2012 in India
Current snapshot of the table is
Table :- tblTest
Values :-
tblColumn
a
a
a
b
b
b
b
c
c
We need and output in SQL Server in the format:-
Acount BCount CCount
3 4 2
Do not use temporarytable/variables/multiple queries in a single query.
Values are restricted to be a, b and c only but the count may vary and output will change accordingly.| Report Duplicate | Flag | PURGE
Oracle Applications Developer Database - 2of 2 votes
AnswersWrite a program to generate all prime numbers from 2 to N for any N value
- SHA.AN March 04, 2009| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Coding - 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
AnswersYou are given a binary search tree and a positive integer K. Return the K-th element of the tree.
- Anonymous January 27, 2015 in Israel
No pre-processing or modifying of the tree is allowed.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 2of 2 votes
AnswersYou have been given an array of int as input. Return true if there exist 2 numbers in the array whose sum is equal to the sum of the rest of the numbers in the array.
- ruhi July 05, 2014 in United States
twoSum({2,11,5,1,4,7}) = true (11+4 = 2+5+1+7)| Report Duplicate | Flag | PURGE
Amdocs - 2of 2 votes
AnswersConsider sorted singly linked list having following nodes
- msgambhir May 12, 2014 in United States
10->30->50->70->NULL
You are given pointer to node 50 and a new node having value 40. Can you inserted node 40 correctly in the list maintaining the ascending order?| Report Duplicate | Flag | PURGE
Qual Ex Software Engineer / Developer Linked Lists - 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
AnswersWrite a function to reverse the word order of String. Do this in-place. "This is a cat" -> "cat a is This". Spaces between words may not be consistent.
- Evan December 25, 2012 in United States| Report Duplicate | Flag | PURGE
Microsoft - 2of 2 votes
Answerswrite a program to perform divison operation of two numbers without using /, %, and modules operatot
- kiran November 15, 2012 in India| Report Duplicate | Flag | PURGE
ThoughtWorks Developer Program Engineer Java - 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
AnswersQuestion on Tree Data Structure: How can we fill all inorder successor pointer of all tree nodes ?
Tree node contains 3 pointers *left, *right and *Successor .Struct node{ int data; struct node *left; struct node *right; struct node *successor; };
A / \ B C / \ / \ D E F G
INORDER Traversal: **DBEAFCG**
**Note:** A inorder successors are F,C and G.
**Function prototype:** void FillSuccessorNodes( struct node *root);
Tree's root node given to us and we need to fill successor pointer for all nodes.case 1) some of the Successor pointers may be **NULL** . This case you have to fill that pointer with immediate Inorder Successor.
Example: if A->Successor == NULL, then fill A->Successor = F
case 2) some of the Successor pointers may already points to correct successors. This case You no need to modify successor pointers.
Example: 1) A->successor = F is valid
2) A->successor = C is valid
3) A-successor = G is valid . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes.case 3) Some of the successor pointers are **not NULL** but these pointers pointing to INVALID successors i.e it could be inorder successor or some garbage value. This case you have to fill these nodes with immediate successor nodes.
Example:
1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F.
2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F.**1) Interviewer asked me time efficient solution in O(n) time complexity. Extra space allowed. 2) she gave some hint i.e we can use HASHing.**
- siva.sai.2020 December 01, 2010**If you know the solution for this problem, please let me know .**
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 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
AnswersGiven two sorted linked lists of integers write an algorithm to merge the two linked lists such that the resulting linked list is in sorted order. You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.
- vkoolkatz April 28, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 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
Answers2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
- JY January 24, 2015 in -
For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.
another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 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
AnswersGiven a mapping configuration such as:
- meh March 23, 2014 in United States
1:a
2:b
...
26:z
And a string like "12632", print the number of different ways you can map such string to alphabet characters.
For example, given "111" the answer is 3 because you can make "aaa", "ak" and "ka" different mappings. However, given "101" the answer is 1 because you can only make "ja" as a possible mapping (01 is not valid).| Report Duplicate | Flag | PURGE
Software Engineer / Developer Dynamic Programming - 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