Amazon Interview Questions
- 1of 1 vote
AnswersSuppose we are detecting fraud cheques and we found the cheques with the following list of patterns are fraud:
- zahidbuet106 February 13, 2013 in United States
111122234455
1234
22334455
11111111
234567
etc.
Now if you have a new cheque and wan to detect fraud in O(1) time what data structure you want to use?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersAn array of size N is given. Array is sub divided into sub array of size K. Find maximum value of each sub array.
- Crazy Tesla January 20, 2013 in India
My ans-
While traversing the array keep on adding values to max heap of size K and keeping a virtual window of size K on array.
When element leaves the window then remove the leaving element from heap too and reheapify the heap. And max element of that window will be again on top in heap.
Any better approach?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays - 0of 0 votes
AnswersGiven a ternary string, you have to count the total number of contiguous substrings (contigious set of characters), that you can form from this given string such that they comprise of either only one or two different characters.
- k.87.sharma October 30, 2012 in United States
Please note that a unique substring will be decided by its starting and ending indices. So, a substring 'ab' with starting and ending indices being 1 and 2 respectively should be considered different from a substring 'ab' with starting or ending indices (or both) other than 1 and 2 respectively.
For example:
input ternary string - aabc
output - 8
The above string comprises of the following substrings that have either one or two of the characters - a, a, b, c, aa, ab, bc and aab. So the final answer is a total of eight substrings.
input ternary string - abc
output - 5
The above string comprises of the following substrings that have either one or two of the characters - a, b, c, ab and bc. So the final answer is a total of five substrings.
input ternary string - baaccb
output - 16
The above string comprises of the following substrings that have either one or two of the characters - b, a, a, c, c, b, aa, cc, ba, ac, cb, baa, aac, acc, ccb and aacc. So the final answer is a total of sixteen substrings| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersQ1) Given that there are n players and each one of them has played exactly one game with every
- words&lyrics July 12, 2012 in India
other player. Also given is an API that tells whether player ‘a’ won or lost to player ‘b’, where ‘a’ and
‘b’ could be any of the players. Arrange the n players in a length n array such that player at position
‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’
Interested in linear time solution
PS: Its not a sorting problem. Please notice that problem is not asking for ranking in decreasing order..| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersGiven a paragraph of text, write a program to find the first shortest sub-segment that contains each of the given k words at least once. A segment is said to be shorter than other if it contains less number of words.
- manishs747 June 24, 2012 in India
Ignore characters other than [a-z][A-Z] in the text. Comparison between the strings should be case-insensitive.
If no sub-segment is found then the program should output “NO SUBSEGMENT FOUND”.
Input format :
First line of the input contains the text.
Next line contains k , the number of words given to be searched.
Each of the next k lines contains a word.
Output format :
Print first shortest sub-segment that contains given k words , ignore special characters, numbers.If no sub-segment is found it should return “NO SUBSEGMENT FOUND”
Sample Input :
This is a test. This is a programming test. This is a programming test in any language.
4
this
a
test
programming
Sample Output :
a programming test This
Explanation :
In this test case segment "a programming test. This" contains given four words. You have to print without special characters, numbers so output is "a programming test This". Another segment "This is a programming test." also contains given four words but have more number of words.
Constraint :
Total number of character in a paragraph will not be more than 200,000.
0 < k <= no. of words in paragraph.
0 < Each word length < 15| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThere are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.
- doomguy January 20, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWrite a program to remove duplicate elements from array.(Array contains elements in range 1...N). Algorithm must be O(N) in time and O(1) in space. Come up with as many test cases as you can.
- omkar November 02, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 0of 0 votes
AnswersHow will you determine if a loop exists in a link list?
- Philip July 24, 2006| Report Duplicate | Flag | PURGE
Expedia Amazon NVIDIA Knoa Software Apple Software Engineer / Developer Intern Algorithm Linked Lists - 2of 2 votes
AnswersGiven some resources in the form of linked list you have to canceled out all the resources whose sum up to 0(Zero) and return the remaining list.
- ganesh.eng2015 July 24, 2016 in India
E.g-->> 6 -6 8 4 -12 9 8 -8
the above example lists which gets canceled :
6 -6
8 4 -12
8 -8
o/p : 9
case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25
O/P : 20 25| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 2 votes
AnswersWrite all jumbled number which is >0 && <N, where N is provided by the user.
- Harsh123 June 12, 2016 in India
A jumbled number is a number whose neighbour digit (either left or right) max differ by 1 value.
e.g.:
8987 is a jumbled number.
13 is not a jumbled number.
123456 is a jumbled number.
287 is not jumbled number.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 0of 0 votes
AnswersGiven an array of positive and negative numbers(no zeroes),i have to arrange them in such a way that the positive and negative numbers should be arranged consecutively.The number of positive and negative numbers may not be equal i.e. if there is no positive number(or negative) left,then all the remaining negative numbers(or positive) are appended to the end of the array.The order is important i.e.if input array is { 2,-1,-3,-7,-8,9,5,-5,-7},then the output array should be {2,-1,9,-3,5,-7,-8,-5,-7}.The code is done in O(n) without using another array.I came up with a solution in which i chose 0 as pivot element and separate the numbers (using quicksort) but in this case the order is not preserved.
- sudeep.chauhan24 September 01, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 4of 4 votes
Answersgive an algorithm for finding duplicate parenthesis in a expression.
example :
- rahul May 02, 2014 in United States(( a + b ) + (( c + d )))
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Stacks - 0of 0 votes
AnswersGiven an array of +ve as well as -ve numbers, find out whether it is possible or not to convert it to 0 by adding/subtracting operations on all the elements.
- prateeksinghal January 17, 2014 in India
e.g arr[]={1,2,3}
YES (1+2-3)
arr[]={3,6,2}
3+6-2 != 0
3-6-2 !=0
-3-6-2 !=0
-3-6+2 !=0
-3+6-2 !=0
-3+6+2 !=0
3-6+2 !=0
3+6+2 !=0
Hence ans= NO| Report Duplicate | Flag | PURGE
Amazon Intern Algorithm - 1of 1 vote
AnswersIt was a pretty interesting question.
- b2010 September 25, 2013 in United States
Assume that you are given a fixed set of floating point numbers. Now given a new floating point number 'x', the goal is to efficiently find the number that is closest to 'x' from the fixed set. Question is: what data structure will you actually use for storing the fixed set of floating point numbers to achieve this?
Edit:
I missed to add. The interviewer further mentioned that I can not sort and that I can use any amount of time for creating the data structure (meaning this need not be efficient).
Since, I am not allowed to 'sort', I assumed that I can not use BST as I will have to compare numbers while populating the tree. But I didn't clarify it with him; I should have in hindsight.| Report Duplicate | Flag | PURGE
Amazon Research Scientist Data Structures - 1of 7 votes
AnswersGiven an array of numbers, arrange it such that all the numbers less than a given key should come before the key and all the numbers greater than the key should come after it.
- Vasily_Zaytsev June 30, 2013 in United States
For example: arr = { 0, -1, -2, 2, 0, 3, 5}, given key = 0
answer should be {-1, -2, 0, 0, 2, 3, 5}
Order of elements that are smaller or greater than key does not matter i.e. sorting is not expected. So, {-1,-2, 0, 0, 5, 2, 3} is also a correct answer.
Time complexity should not be more than O(n).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 1of 1 vote
AnswersGiven an array of positive integers, find the max no that can be formed by any permutation of the arrangement.
- Vin June 26, 2013 in India
input {21,9,23}, output = 92321| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
AnswersIn a series of 1 to N, two numbers are missing. Find the missing numbers? Quickest way?
- xankar March 16, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
Answersgiven an ASCII string, return the longest substring with unique characters. Ex: dabcade => Ans: bcade.
- bharat November 16, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersFind the minimum element in a stack in O(1) time complexity and O(n) space complexity
- debajyoti2510 August 04, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Stacks - 0of 0 votes
AnswersGiven an array of integers, return the first integer which occurs only once in O(n).
- Evan May 01, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space
- dev February 19, 2012 in India
I cud think of this algo..Do two inorder traversals, one in the usual (descend to the left
before descendung to the right) direction and the other in the
reversed(descend to the right before descending to the left)
direction.and compare the sum with x..
But i am unable to code it properly..(in C)
Need help| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
Answersyou have given 2n+1 numbers in which 2n numbers are repeated means every number is having duplicate value.find that non repeating number in constant space and o(n) time.i told him using XOR.
- time February 03, 2012 in India
then he gave me 2n+2 numbers in which 2n numbers are repeating like above now you have 2 different number.find both number in constant space and o(n) time.(f2f 4th round)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow do you find a shortest connection between two persons on Facebook(if the same exists)?
- shwetank2003819 November 28, 2011 in India
You are provided with an API which returns the list of friends of a particular persons| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersGiven a doubly linked list containing only three integers 1,2,3. Sort the list without exchanging the values.
- Puzzle November 19, 2011 in India
Eg- 1->3->2->1->2->3->2->1->1
output: 1->1->1->1->2->2->2->3->3| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Data Structures Linked Lists - 0of 0 votes
AnswersGiven an array A[] and a integer num. Find four no.s in the array whose sum is equal to given num.
- Abhi August 26, 2011
Brute force :- O(n^4)
I solved it in O(n^3)
But the interviewer was insisting on a better solution.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersCard shuffle problem. I have a card pack of 313 cards. I remove the topmost card from card pack and place it on desk and I remove the next one and put it below the pack of cards(that you are holding). keep doing this till all the cards are on desk. Pick up the card stack from desk and repeat these steps till you find retrieve the original cards orderd. I was asked to code to find how many rounds it will take to retrieve initial order.
- puzzle_math February 17, 2011| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersCheck if two given strings are anagrams?
- CGB (2nd Telephone Interview) February 14, 2011| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer String Manipulation - 0of 0 votes
AnswersYou are given a sorted array such that all the number is repeated except one.
- Nitin October 30, 2010
Find that non repeated number in O(n)| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
AnswersGiven a variation of a binary tree(not BST) in which each node has a parent, left and right pointer. The nodes do not have any key elements or any other data to identify itself. The root is the node that has a null parent pointer. You are given the pointers to two random nodes in the tree which may or may not be at the same level. Find the first common ancestor to the two random nodes given in the tree.
- Anonymous November 16, 2009| Report Duplicate | Flag | PURGE
Amazon Microsoft Software Engineer / Developer Trees and Graphs