Recent Interview Questions
- 3of 3 votes
AnswersLet's assume that there's an array that has nonzero natural numbers where all the numbers repeat an even number of times, except for one value that repeats an odd number of times. Can you write me a function that takes this array, and returns the value that occurs the odd number of times?
- danny April 17, 2015 in United States for Amazon Music
Ex : - [ 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 ]| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 3of 3 votes
AnswersFind a given element in sorted array.
- tazo February 10, 2015 in United States
arr= [1, 2, 3, 4, 5, 6]
follow up: If the sorted array is shifted left by unknown number, modify existing binary search to find a element in modified array
arr = [4, 5, 6, 1, 2, 3]| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Arrays - 3of 3 votes
AnswersThere is rotated sorted array.Write the program to find any element in that array
- akash.patel06@sjsu.edu February 22, 2013 in United States
Original Array A={1,2,3,5,6,7,8}
Rotated Array B={5,6,7,8,1,2,3}
Write the program to find any element in array B| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven an array and an integer k, find the maximum for each and every contiguous subarray of size k.(Using DP)
- HimanshuP January 21, 2016 in United States| Report Duplicate | Flag | PURGE
SDE1 Algorithm - 3of 3 votes
AnswersHow can you design a data structure that can do the following operations in O(1) time:
- Masumbuet December 29, 2014 in United States for International expansion
Insert, Delete, Search, Max which returns the maximum number
I know delete, search and insert can be done O(1) time in a hashmap with a proper hash function. But not sure Max is even possible in O(1) with the presence of delete operation?| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 3of 3 votes
AnswersHow many occurrences of a given search word can you find in a two-dimensional array of characters given that the word can go up, down, left, right, and around 90 degree bends?
- lueikhong June 07, 2014 in Australia
Ex:
Count of occurrences of SNAKES
S N B S N
B A K E A
B K B B K
S E B S E
The answer is 3.
Write a program for that question.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersConsider the following array {1,2,3,4,5,2,5,4,4};
In the above array, index 4 could be considered as breaking point where summation of 0 to 4 in the array is equal to summation of 5 to end of array. We need to find the breaking point for the given array. I solved this. But follow up was for this array{1,0,-1,-1,1};
. Mathematically the later array's breaking point is 2.
- Madan January 23, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 - 3of 3 votes
AnswersWrite a function that takes a list L and returns a random sublist of size N of that list. Assume that the indexes must be in increasing order. That is, you cannot go backwards.
- neer.1304 July 03, 2019 in United States
Example:
L = [1, 2, 3, 4, 5]
N = 3
The function should return one of these lists:
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersQuestion 1.
- anonymous October 24, 2017 in India
You are given a string composed of uppercase English letters (‘A’ through ‘Z’).
Set of letters (‘A’, ‘E’, ‘I’, ‘O’, ‘U’) are called vowels. Other letters are called consonants.
We define foo value of a string as number of pairs of exactly same consecutive vowel letters.
For example,
Ex.1: BCDEEIOU - This has a foo value of 1 (because of EE). Note that although I is next to E, and O is next to I, and U is next to O, they aren’t exactly same neighbours, so they don’t contribute to foo value
Ex.2: BCDEEEIOU - This has foo value of 2. Because of first pair of EE and immediately next pair of EE
Ex.3: ABCDEFG - This has foo value of 0. There are no consecutive vowels
Ex.4: ABEUUOUOO - This has foo value of 2, because of UU and OO
You are given 2 inputs, N and K.
How many strings of length N can you form such that they all have foo value of K?
Let’s assume the constraints as:
1<=N<=15
0<=K<N| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersThis was a 3 hours coding round in which we had to code 1 problem having 50 test cases. Only those students were selected for the next round who passed all the test cases. Here is the question:
- jatinbansal321 September 08, 2017 in India
You’ll be given a grid as below:
0 1 0 2 0
0 2 2 2 1
0 2 1 1 1
1 0 1 0 0
0 0 1 2 2
1 1 0 0 1
x x S x x
In the grid above,
1: This cell has a coin.
2: This cell has an enemy.
0: It contains nothing.
The highlighted(yellow) zone is the control zone. S is a spaceship that we need to control so that we can get maximum coins.
Now, S’s initial position will be at the center and we can only move it right or left by one cell or do not move.
At each time, the non-highlighted part of the grid will move down by one unit.
We can also use a bomb but only once. If we use that, all the enemies in the 5×5 region above the control zone will be killed.
If we use a bomb at the very beginning, the grid will look like this:
0 1 0 2 0
0 0 0 0 1
0 0 1 1 1
1 0 1 0 0
0 0 1 0 0
1 1 0 0 1
x x S x x
As soon as, the spaceship encounters an enemy or the entire grid has come down, the game ends.
For example,
At the very first instance, if we want to collect a coin we should move left( coins=1). This is because when the grid comes down by 1 unit we have a coin on the second position and by moving left we can collect that coin. Next, we should move right to collect another coin( coins=2).
After this, remain at the same position( coins=4).
This is the current situation after collecting 4 coins.
0 1 0 2 0 0 1 0 0 0
0 2 2 2 1 -->after using 0 0 0 0 1
x x S x x -->bomb x x S x x
Now, we can use the bomb to get out of this situation. After this, we can collect at most 1 coin. So maximum coins=5.| Report Duplicate | Flag | PURGE
Samsung Software Engineer - 3of 3 votes
AnswersGiven a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only right pointers. During modification you can use right as well as left pointers. Write complete code and dry run it for some test cases
- behinddwalls December 08, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 3of 3 votes
AnswersGiven estimated stock quotes, in an array, print the maximum profit from a buy and sell. i.e [19, 22, 15, 35, 40, 10, 20] would show a profit of 25(40 -15). The sale must come after the buy. Solve this in O(N) time.
- mcg1coding February 13, 2017 in United States<?php function print_max_profit($arr){ if(count($arr) < 1) return 0; $len = sizeof($arr); $profit = 0; $least = $arr[0]; for($i = 0; $i < $len; $i++){ $least = min($least,$arr[$i]); $profit = max($profit, $arr[$i] - $least); } return $profit; }
| Report Duplicate | Flag | PURGE
Facebook Solutions Architect - 3of 3 votes
AnswersA program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35
- gadha July 21, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures Java Object Oriented Design - 3of 3 votes
Answerswe have a random list of people. each person knows his own height and the number of tall people in front of him. write a code to make the equivalent queue.
- pari February 18, 2014 in United States
for example :
input: <"Height","NumberOfTall","Name">,
<6,2,"A">,<1,4,"B">,<11,0,"C">,<5,1,"D">,<10,0,"E">,<4,0,"F">
output: "F","E","D","C","B","A" --> end of queue| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersCoding:
Public void TransferAccount(AccountID id1, AccountID id2){ Account a1 = id1.GetAccount(); Account a2 = id2.GetAccount(); //Swap amounts. Temp = a1.Balance; a1.Balance = a2.Balance; a2.Balance = Temp; }
Q1: How do you make it thread safe?
I said use “public void synchronized” Good. But terrible performance since the entire method is synchronized.
Q2: Can you not lock on the entire method? I said used nested locks:Synchonized(a1) Synchronized(a2) { //swap }
His q: This will lead to a deadlock if in another thread I call Transfer (id2, id1) and Transfer (id1, id2).
Synchonized(a1) Synchronized(a2) { //swap }
Synchonized(a2) Synchronized(a1) { //swap }
How do you prevent this then? How do you design your code to not to get in to deadlock? (stumbled here)
- xankar March 16, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Java Threads - 3of 3 votes
AnswersYou have two sorted arrays, where each element is an interval. Now, merge the two array, overlapping intervals can be merged as a single one.
- Seetha November 11, 2018 in United States
I/P :
List 1 [1,2] , [3,9]
List 2 [4,5], [8, 10], [11,12]
O/P [1,2], [3,10], [11,12]| Report Duplicate | Flag | PURGE
Facebook Software Developer - 3of 3 votes
AnswersPrint all possible palindromes(of length >2) for a given string.
- Anonymous January 24, 2011| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a singly connected linked list, find the largest palindrome in the list in O(1) space.
- neer.1304 November 29, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 3of 3 votes
AnswersGiven an array A with n integers.
- smarthbehl August 01, 2015 in United States
Rearrange array such that
A[0]<=A[1]>=A[2]<=A[3]>=A[4]<=A[5] and so on
Edit: Array is not sorted
You have to do it in linear time O(N)| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm - 3of 3 votes
Answers/*
- dingdong April 16, 2015 in United States
For each node in a binary tree find the next right node on the same depth. Write a function that takes root node and populates "next" with the answer for each node.
A
/ \
B -> C
/ / \
D -> F-> G
/ \
H -> I
class Node {
Node left;
Node right;
Node next; // <-- answer should be stored here
};
B.next = C
D.next = F
F.next = G
H.next = I
{A, C, G, I}.next = null
*/| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersHow to find efficiently the minimum of an array of integers that is the maximum of other arrays?
- wingchun0511 January 31, 2015 in France
Example:
A = [126, 110, 130]
B = [125]
C = [105, 115]
The minimum element of array A that is the maximum of B and C is 126| Report Duplicate | Flag | PURGE
Java Developer Algorithm Coding Java Online Test - 3of 3 votes
AnswersImplement a stack with O(1) push, pop, and min
- msito October 14, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Stacks - 3of 3 votes
AnswersDefine amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.
- wtcupup2017 November 13, 2016 in United States
Example 1: 0, 1, 2, 3
Ouptut: 0. When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number.
Example 2: 1, 0 , 0
Output: 1. When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number.
If there are multiple positions, return the smallest one.
should get a solution with time complexity less than O(N^2)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersRotate a array by N. N can be smaller of greater than the array length.
- someone June 10, 2015 in United States
e.g {0,1,2,4,5,6,7} N =4 should return {5,6,7,4,0,1,2}.
1) I did this using extra array but next I was asked to do without extra array and in o(n) time.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 3of 3 votes
AnswersN queen problem.
- animageofmine April 08, 2015 in United States
In NXN chess board, you have to arrange N queens such that they do not interfere each other. Following is how you define interference of queens.
1. Two queens cannot be on the same diagonal
2. Two queens cannot be in same horizontal or vertical line
3. Queen can jump like a knight. So, two queens cannot be at a position where they can jump two and half steps like a knight and reach the other queen.
You should return the possible ways to arrange N queens on a chess board.
This was a tech screen, but since I was local, they called me in their office rather than phone interview.
Hint: Don't try too hard, the best solution is n!| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersGiven a 2 dimensional matrix where some of the elements are filled with 1 and rest of the elements
- mknarayan1711 August 02, 2014 in India for Media Experience Team
are filled. Here X means you cannot traverse to that particular points. From a cell you can either traverse to left, right, up or down
Given two points in the matrix find the shortest path
between these points
For example if the matrix is
1 1 1 1 1
S 1 X 1 1
1 1 1 1 1
X 1 1 E 1
1 1 1 1 X
Here S is the starting point and E is the Ending point| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 3of 3 votes
AnswersDevelop an algorithm and write code to break a sentence without spaces into a sentence of valid words separated by spaces.
- Murali Mohan July 16, 2013 in India for Bangalore
For ex: thissentenceisseparated needs to be broken into: this sentence is separated
Assume that you have a dictionary to check for valid words. Your algorithm should return false if the sentence cannot be separated into valid words.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 3of 3 votes
AnswersGiven an array of length N and an integer K, sort the array as much as possible such that no element travels more than k positions to its left - an element however can travel as much as it likes to its right.
- testing@123 June 01, 2016 in United States| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 3of 3 votes
AnswersYou have given n numbers from 1 to n. You have to sort numbers with increasing number of set bits.
- pradegup September 29, 2012 in India
for ex: n=5.
output: 1,2,4,3,5
Note: If you have two number with equal number of set bits, then number with lowest value come first in the output.| Report Duplicate | Flag | PURGE
Microsoft Algorithm - 3of 3 votes
AnswersGiven two sorted arrays A and B. Find the first K pairs (a, b) from A and B which have the smallest sum of a & b. Supposed K is small compared to |A| x |B|
- anonymous August 05, 2017 in United States
For example:
A = [1, 2, 3, 6, 10]
B = [1, 4, 5, 7]
K = 5
Result [(1,1), (1,4), (1,5), (2,1), (3,1)]| Report Duplicate | Flag | PURGE
Google Intern