Software Engineer / Developer Interview Questions
- 6of 6 votes
AnswersGiven an input array
- gowthamganguri August 30, 2013 in India
a={1,2,3,6,2,8----}
product of all numbers=p=a[0]*a[1]*---a[n-1] where n is size of array
output arrau should be b={p/a[0],p/a[1],p/a[2]-----}. you should not use division operator.Time complexity should be less than o(n2).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 6of 6 votes
AnswersWrite a function that accepts two or more strings and returns the longest common substring in all of them.
- Barry Fruitman March 20, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 6of 6 votes
AnswersGiven a non-directed, strongly connected graph where the node values are letters of the alphabet, write an algorithm that prints out all possible permutations of strings. What is this called?
- william.brandon.lee83 January 18, 2016 in United States
For example:
V = A,B,C
Printout
ABC
ACB
BAC
BCA
CAB
CBA
BAC etc.| Report Duplicate | Flag | PURGE
IBM Software Engineer / Developer Algorithm - 6of 6 votes
AnswersWhen a child is forked then it inherits parent's file descriptors, if child closes the file descriptor what will happen ? If child starts writing what shall happen to the file at the parent's end ? Who manages these inconsistencies , kernel or user ?
- cinderella April 09, 2012 in United States for 3D graphics| Report Duplicate | Flag | PURGE
Intel Software Engineer / Developer - 6of 0 votes
AnswersImagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;
- Edde May 12, 2007| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 5of 15 votes
AnswersGiven a function
- mabid.mahmood July 15, 2014 in United States
getRandomTripplet()
which returns a random triplet of letters from a string. You don't know the string using calls to this function you have to correctly guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will return things like
hlo
hew
wld
owo
the function maintains the relative order of the letters. so it will never return
ohl since h is before o in the string.
owe since w is after e
The string is not known you are only given length of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 13 votes
AnswersGiven n, output the numbers from 0 to 2^n-1 (inclusive) in n-bit binary form, in such an order that adjacent numbers in the list differ by exactly 1 bit.
- xxyyzz February 23, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 9 votes
AnswersQ: Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?
- pdoggeth October 18, 2013 in United States
The obvious and naive way that I thought of was to convert the entire array into a 1D and do a mergesort on it, but there must be a better way than that. I'm wondering what the better and more efficient way is.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 9 votes
AnswersWrite a Program for Dictionary which has functionality of lookup and insert . This program should be able to add words on the fly
- Guy February 05, 2014 in United States
I wrote simple code using HashTable
follow up
1) Now we are getting too many words what happens
me: Hashtable will dynamically resize resulting into performance hit . Also they might get hashed to same location as well as we might run out of main memory
2) Okay you are out of main memory , How will you scale this program
me: I will create buckets of HashTable lets say 26 buckets for one for each alphabet and would put them on different machines
3) Lets say you are out of memory on those machines too
me: Okay I need to put them on secondary storage . Here we can have fileSystem or Database . I chose database . I will create simple DB schema of BucketNumber and word .
I will use buckets on main memory as cache , if we are not able to find a word in the bucket then query databse with bucket number and words then remove the least number times looked up word (every time we lookup a word we increament the count i.e value in key,value pair on hashtable) from that bucket and add this word .
I mentioned that bottleneck in this case will be every time a word is not present we need to query DB which usually has high latency which will result into performance hit
4) Lets say we are okay with latency but what if we are getting inserting words between that are only between only in two buckets ex. words starting from a and b only.
Now that I think about it, is it better to do this in a trie? What do you guys think?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer System Design - 5of 7 votes
AnswersGiven the English alphabet, 'a' through 'z' (lowercase), and an imaginary onscreen keyboard with the letters laid out in 6 rows and 5 columns:
a b c d e f g h i j k l m n o p q r s t u v w x y z
Using a remote control - (up - 'u', down 'd', left 'l', right 'r' and enter '!'), write a function that given a word will produce the sequence of key presses required to type out the word on the onscreen keyboard. The function should return the sequence string.
- superduper March 01, 2013 in United States
NOTE: This was an actual question. I didn't pull this from TopCoder.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 7 votes
AnswersGiven N strings, find the smallest string in lexicographic order which contains all the given strings as subsequences
- geekofthegeeks November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven a N*N Matrix.
- 646 November 23, 2010
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven two sorted array in ascending order with same length N, calculate the first K min a[i]+b[j]. time complexty O(N).
- mario87 December 18, 2013 in United States
some misunderstood first K, to put it straight, to find the Kth min, not the first min| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven a array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]. Best possible is a O(n) algorithm.
- kingKode October 26, 2012 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven two strings, return boolean True/False, if they are only one edit apart.Edit can be insert/delete/update of only one character in the string. Eg:
- abkr990 October 31, 2014 in United States
-True
xyz,xz
xyz, xyk
xy, xyz
-False
xyz, xyz
xyz,xzy
x, xyz| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersLet's say you have 10,000 servers, each with a billion integers. How do you find the median?
- 352905 July 03, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven two strings .Print all the interleavings of the two strings.
- grave July 10, 2012 in India
Interleaving means that the if B comes after A .It should also come after A in the interleaved string.
ex-
AB and CD
ABCD
ACBD
ACDB
CABD
CADB
CDAB| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm String Manipulation - 5of 5 votes
AnswersGiven three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum
- Greg September 04, 2014 in United States
Please provide as efficient code as you can.
Can you better than this ???| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C++ Coding - 5of 5 votes
AnswersSay you have a keypad that has keys for the numbers 0 through 9 and the correct code is some sequence of 5 digits. This keypad does *not* reset after entering an incorrect sequence of 5 digits. ie. If the correct sequence is 12345, entering 7512345 will succeed in opening it because it ends in the correct sequence. If the keypad actually resets after every 5 digits pressed, then it would not succeed b/c it would interpret the above sequence as "75123" then "45".
- Jason May 30, 2015 in United States
1. Write an algorithm that will try to find the correct code for this keypad. Assume you have an API similar to KeyPad.pressKey(int n) where you pass in a number (0...9) and it returns true if the keypad unlocks and false if it's still locked.
Note that you could easily enter all digits of all numbers 00000 through 99999 resulting in 5*100000 key presses, but remember that the panel does not reset after every sequence of 5 digits, so find a way to do this more efficiently. Notice for example that entering the stream 3791283780 will test the length 5 sequences 37912, 79128, 91283, 12837, 28378, 83780; not only the two disjoint sequences 37912 and 83780.
Think of this keypad as remembering the last 4 keys pressed (and the order pressed); when the next key is pressed, if the last 4 keys + the current key equal the correct code, the keypad will unlock. Assume the keypad does all this internally, so you can just keep feeding it keypresses and it will eventually unlock if the last 5 keypresses entered is the correct code.
2. Generalize your algorithm to work for a keypad where you don't know the length of the correct sequence in advance.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 5of 5 votes
AnswersHad my first and second phone interview with Amazon. I was dropped. This site has been a great help towards my preparation and most questions are based on what you find here.
- S July 01, 2008
Posting my Questions is a small way of saying Thanks!
Interview 1:
1. What is polymorphism.
2. Design an OO parking lot. What classes and functions will it have. It should say, full, empty and also be able to find spot for Valet parking. The lot has 3 different types of parking: regular, handicapped and compact.
3. Coding: I have an integer array where every number appears even number of times and only one appears odd times. Find the number.
(I said hashtable and he asked me to write code with Hashtable)
4. What data structure would you use to look up phone numbers for customer names.
(I said Hashtable. Asked why hashtable, why not a tree. I said HT has O(1). Asked is order always 1, when more than O(1) in HT.
Second Interview:
1. Starter: Describe your college projects.
2. OO Design: Design a deck of cards. What classes, data structures will you use? How will you shuffle the cards? How will you divide (deck) among players. What class/function do you need to denote players and where will you add them? What class/function do you need to deck? What if I need to add 2 jokers to the deck of 52 cards.
3. Data Structures: How will you use a hashtable to find data in a tree. (Then he rephrased) suppose I have a hashtable, I want to store the data in a tree instead of a bucket. How will I do it. What complexity to find an element.
4. Bits & Bytes: Find if a binary representation of a number is palindrome. The function should work irrespective of number of bytes for an integer. Suppose if our machine is 4 bytes for an int, how will you use the program for 8 byte machine.
5. Unix: Suppose I have 100's of html files in many directories. I want to find the files having phone numbers.
b) Suppose I have 2 files having phone numbers, find the repeating phone numbers. (I said sort and grep). Then he asked what if the lines cannot be sorted.
All the best guys. I think the second interview was challenging since the interviewer was prodding until he heard a leave me alone. So it means that though they are based on questions in cc, be prepared for extensions. I think this site is all you need to prepare for Amazon interview.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Java Data Structures Object Oriented Design Coding - 5of 5 votes
AnswersInitially there is a number n written on board. Two players start playing a game turn by turn. Each player has to replace the number n written on the board by n-2^k (for some k >= 0 such that 2^k < n)?
- ACP Pradyuman October 03, 2013 in United States
Also the number n-2^k has to be as beautiful as n (The beauty of a number depends on the number of one's in its binary representation). The player loses the game when he can't select any such k.
Given the initial number n, determine which player will win the game if both players play optimally. n > 0 and n <= 10^9.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Bit Manipulation - 5of 5 votes
Answersint fun() { /*write code here.*/ } int main() { int i=10; fun(); printf("%d",i); }
change the value of the i without changing code of the main function, assign 20 to i ?
- mohit sharma October 28, 2014 in India| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer C - 5of 5 votes
AnswersGiven a hashmap M which is a mapping of characters to arrays of substitute characters, and an input string S, return an array of all possible mutations of S (where any character in S can be substituted with one of its substitutes in M, if it exists).
What is the time complexity? What is the space complexity? Can you optimize either?
- trunks7j February 15, 2013 in United StatesExample input: M = { f: [F, 4], b: [B, 8] } S = fab Expected output: [fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersYou have a link list with the following structure:
- francisco.gutierrez.91 January 24, 2013 in United States for Office
struct Node{ Node*next; Node*other; }
next pointer points to next node, but "other" pointer points to any node in the list, it can be itself or null.
you receive the header of a list with this structure.
you have to copy it(allocate new memory) , you cannot modify the structure, you can not modify the list you are given.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Linked Lists Algorithm Data Structures - 5of 5 votes
AnswersA link list contains following elements
struct node{ int data; node* next; node* random; }
Given head of such a linked list write a function who copies such a linked list and returns the head of the new list. So if in the original list first node points to fourth node in random the copy should have the same relation. The random pointer can point to any node including itself and more than two nodes can have random pointer to the same node.
- vik September 13, 2013 in United States
Required time complexity O(n) and no extra space can be used (apart from the newly allocated memory which you will need to create the new list)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ Data Structures - 5of 5 votes
AnswersThe closest common ancestor in a tree forest.
class Node { Node* parent; // == null for root of tree Node* left; Node* right; } Node* tree_forest[]; // array of pointers which points to roots of each tree respectively Node* closest_common_ancestor(Node* n1, Node* n2) { // your solution }
Example:
| a | j | / \ | / | b c | h | / / \ | |d e f |
for e and d CCA is a
- Sergey January 17, 2015 in United States
for e and f CCA is c
for e and c CCA is c
for h and d CCA is null
Constrains: O(1) additional memory| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersWe have words and there positions in a paragraph in sorted order. Write an algorithm to find the least distance for a given 3 words.
- pqrabcd November 14, 2014 in United States
eg. for 3 words
job: 5, 9 , 17
in: 4, 13, 18
google: 8, 19, 21
...
...
Answer: 17, 18, 19
Can you extend it to "n" words?
Context: In Google search results, the search terms are highlighted in the short paragraph that shows up. We need to find the shortest sentence that has all the words if we have word positions as mentioned above.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm