Software Engineer / Developer Interview Questions
- 2of 2 votes
AnswersI have 10 million 10-bit integers to sort, how would you sort them and what's the time complexity?
- chriscareercup November 12, 2012 in United States
Follow-on question: Instead of sorting integers, I now have 10 million pairs to sort. Each pair consists of a 10-bit integer and an object, the sort order is determined by the 10-bit integer. Will your original sort algorithm hold or do you need sort it differently?
(A word of advice: Ask as many questions as you want during the interview, but you MUST be quick. Also, don't mention anything until you've thought it through clearly, otherwise you're just inviting more questions. Time is of essence, you're too slow if this question takes you more than 15 minutes to come up with the optimal solution, because remember, you have to leave time for explanations and other questions)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Sorting - 2of 2 votes
Answersgiven two integers and two bit positions. Set the first integer between the two bit positions to be that of the second integer.
- Lively May 06, 2012 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Bit Manipulation - 2of 2 votes
AnswersAn efficient way to sort patient files in an array of just 3 types 'High-importance', 'Mid-importance', 'Low-importance' which are in an arbitrary order (unsorted).
- Ipalibo December 19, 2014 in United States
The output preference should start with the highest.
1. High-importance
2. Mid-importance
3. Low-importance
[high,low,low,med,high,low]
ps I was told to take advantage of the fact that they are just only 3 types.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Sorting - 2of 2 votes
AnswersRound 1 :
- sonesh January 03, 2013 in India
Q 2 : longest palindrome in a string ? (Need to tell in O(n) time complexity + O(1) space complexity)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Coding Dynamic Programming String Manipulation - 2of 2 votes
AnswersCount the number of set bits for an 32 bits integer. How to improve the process for the second time use if the memory is unlimited?
- Andy2000 September 04, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer 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
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
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
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 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
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 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
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
AnswersFrom a given integer array values, find if a Total value is possible or not? The numbers in the array can be used more than once.
- struggler July 29, 2013 in United States
example
int[] points = {3, 7};
isScorePossible(points, 10) => true
isScorePossible(points, 9) => true| Report Duplicate | Flag | PURGE
Yelp Software Engineer / Developer - 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
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
AnswersDesign a data structure where the following 3 functions are optimised:
- P October 28, 2011 in India
1. Insert(n)
2. GetRandomElement()
3. Remove(n)
Write a class, and implement the functions. Give complexity of each of these ..| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Application / UI Design - 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 - 2of 2 votes
AnswersYou have 81 balls. 80 balls have the same weight. 1 ball is the lightest one. What would be the minimum possible way to find the lightest ball ?
- AlgoBaba November 23, 2014 in United States
(Use Dynamic Programming)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Dynamic Programming - 2of 2 votes
AnswersFind the largest sum contiguous sub array. The length of the returned sub array must be at least of length 2.
- phoenix September 19, 2014 in United States| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm