Recent Interview Questions
- 5of 5 votes
AnswersI came across this problem online.
- xiaoc10 August 07, 2015 in United States
> Given an integer:N and an array int arr[], you have to add some
> elements to the array so that you can generate from 1 to N by using
> (add) the elements in the array.
Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the count of the least adding numbers.
For example:
N=6, arr = [1, 3]
1 is already in arr.
add 2 to the arr.
3 is already in arr
4 = 1 + 3
5 = 2 + 3
6 = 1 + 2 + 3
So we return 1 since we only need to add one element which is 2.
Can anyone give some hints?| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 5of 5 votes
AnswersWrite a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1
- 3139a1m July 02, 2014 in India
e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28
ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1
I gave the obvious o(n^2) solution. He asked to optimize it.| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm - 5of 5 votes
AnswersWrite a function which, given two integers (a numerator and a denominator), prints the decimal representation of the rational number "numerator/denominator".
- loganwol August 18, 2014 in United States
Since all rational numbers end with a repeating section, print the repeating section of digits inside parentheses; the decimal printout will be/must be
Example:
1 , 3 = 0.(3)
2 , 4 = 0.5(0)
22, 7 = 3.(142857)
etc..| Report Duplicate | Flag | PURGE
Google SDET Coding - 5of 5 votes
Answerswhy strings are immutable ?
- tare.rohan November 11, 2013 in India
how many objects will be created in
String temp = "A" + "B" + "C" ;
explain your answer in detail.| Report Duplicate | Flag | PURGE
Goldman Sachs Java Developer Java - 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
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 - 5of 5 votes
AnswersGiven a Sorted integer array which is rotated N number of times. You have no idea what that N is. An element in the array can occur more for any number of time. Write a method to search the position of a given element. If there are more than one of the same element, return the position of the first element.
- jeevanus September 04, 2014 in India for Microsoft CRM| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm Data Structures Sorting - 5of 5 votes
AnswersGiven two sorted arrays, we can get a set of sums(add one element from the first array and one from the second). Find the Nth element in the set of sums. Suppose that array A is {1,3,4,8,10}, array B is {20, 22, 30, 40}. then the sum set will be{21(1+20),23(1+22 or 3+20), 25(3+22), 24(4+22)...} the 3rd element in the sum set is 25.
- ophis.W October 28, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Intern Algorithm - 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
AnswersGiven N balloons, if you burst ith balloon you get Ai−1∗Ai∗Ai+1 coins and then (i-1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather.
- dp November 25, 2015 in United States
Assume that we have extra 1 at left most and right most positions. (don't take in answer just for boundary positions)
Hence if we have left or right boundary positions we multiply 1.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
Answersfind the no of possible patterns in android lock screen. write a program to count them.
- h3dnvb January 04, 2016 in United States| Report Duplicate | Flag | PURGE
Google - 5of 5 votes
AnswersGiven an integer, find the next highest and next lowest integers, with equal number of 1s in their binary representation as the original number.
- gulusworld1989 January 13, 2014 in United States for Android| Report Duplicate | Flag | PURGE
Google Intern Algorithm - 5of 5 votes
AnswersGiven a string, find the longest substring with k distinct characters.
- getPDat February 03, 2017 in United States
e.g - “aaaabbbb”, k = 2, “aaaabbbb”
“asdfrttt” k = 3, “asd”, “frttt”
[Telephonic Question]| Report Duplicate | Flag | PURGE
Google Software Developer Java - 5of 5 votes
AnswersHow to find median of a stream of integers....
- Kavita July 08, 2014 in India
interviewer was not interested using insertion sort....
Any better way to do this??| Report Duplicate | Flag | PURGE
Microsoft Computer Scientist - 5of 5 votes
AnswersGiven a binary tree.
Print nodes of extreme corners of each level but in alternate order.10 5 11 9 20 - 15 14 - - - 25 30
then output should be 10,11,9,25,30
- SK June 09, 2013 in India
left most of 0th level
right most of 1st level
left most of 2nd level
& like this| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm Trees and Graphs - 5of 5 votes
AnswersGiven an infinite stream of characters and a list L of strings, create a function that calls an external API when a word in L is recognized during the processing of the stream.
- ragmo2223 November 05, 2015 in United States
Example:
L = ["ok","test","one","try","trying"]
stream = a,b,c,o,k,d,e,f,t,r,y,i,n,g.............
the call to external API (let's call it some function callAPI()) would be called when the 'k' is encountered, again when the 'y' is encountered, and again at 'g'.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 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
AnswersA plumber working for a company as a contractor. His job is attend services and submit the bill to get his salary on basis of daily work including his service charge 500 rupees. For a typical plumbing work he need pipes with different lengths. But in market he will get new pipe with standard size 100m of cost 100 rupees. (no small or large sized pipes available) Now , he need 10 , 40 , 60, 70 lengths of pipes for a jobwork.
- bhupal February 22, 2015 in India
Generally company gives him (4 pipes * 100 rupees) + 500rupees as service charge = 900 rupees.
but plumber bought only 2 pipes cut as follows and get his job done...
1st pipe => 40+60
2nd pipe => 10+70 + extra left(20)
By buying only 2 pipes he get his job done. remaining 2 pipes money saved.
write an efficient algorithm to calculate minimum number of standard size pipes required for given number of different pipes lengths:
Input:
N => total pipes for jobwork
arr[N] => lengths of pipes. (for simplicity, pipe size will be either smaller or equal to standard size)
outpud:
minimum statdard sized(100m) pipes required
constraint: you can only cut them can not join them back as follows
say he need 10 95 95,
with two pipes 100 100 = > 95+5 95+5 => 95 95 (5+5)// this is not accepted
EX:
Input:
5
20 30 50 60 80
output:
3
Input:
5
10 10 10 15 20 35 55 60 70 75 75 80
output:
6| Report Duplicate | Flag | PURGE
NVIDIA Dev Lead Algorithm - 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 - 5of 5 votes
AnswersGiven a self-balancing tree (AVL), code a method that returns the median.
- Diego May 16, 2014 in United States
(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is
2, 7, 4, 9, 1, 5, 8, 3, 6
then the median is 5.)| Report Duplicate | Flag | PURGE
Facebook iOS Developer Trees and Graphs - 5of 5 votes
AnswersGiven stock price of Amazon for some consecutive days. Need to find the maximum span of each day’s stock price. Span is the amount of days before the given day where the stock price is less than that of given day
- Rahul Sharma April 04, 2014 in India
E.g i/p = {2,4,6,9,5,1}
o/p= { -1,1,2,3,2,-1}| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 5of 5 votes
AnswersIf a linkedlist is having loop, how to find the last node of the loop .
- zammer May 28, 2013 in India for SDET| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 5of 5 votes
AnswersGiven an array of 0s and 1s, find out:
- HauntedGhost March 05, 2013 in United States
1. all the subsequences where number of 0s = number of 1s
2. max length subsequence where number of 0s = number of 1s
Update:
We need to find subarrays, not subsequences. Sorry for the confusion.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm