Amazon Interview Questions
- 1of 1 vote
AnswersYou are a hunter in the forest. A monkey is in the trees, but you don't know where and you can't see it. You can shoot at the trees, you have unlimited ammunition. Immediately after you shoot at a tree, if the monkey was in the tree, he falls and you win. If the monkey was not in the tree, he jumps (randomly) to an adjacent tree (he has to).
- Glude August 03, 2012 in United States
Find an algorithm to get the monkey in the fewest shots possible.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 1of 1 vote
AnswersFind the first non-repeating character in a stream of characters?
- samotgun November 18, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Hash Table Software Engineer / Developer Algorithm - 1of 1 vote
Answersthere are two arrays named A and B , both of them with k size, they are sorted in acsending order. could you find k-th smallest combinations of ai, bj -->(ai+bj) . 0<=i,j <k.
- yingsun1228 January 16, 2013 in United States
for example: a = {1, 3, 6} b = {4, 5, 6} then we will get 1 + 4 = 5, 1 + 5 = 6, and 1 + 6 = 7,the result is 5,6,7. does it make you understood? and could anybody do it with less time and space complexity.
Hi guys, thanks for all your suggestions and idea, and finally I get my answer and here are my c++ codes, time complexity is O(k*lgk), and space complexity is O(k):
#include<iostream>
using namespace std;
typedef struct node{
int row;
int col;
int data;
}Node, *PNode;
void swap(PNode &a, PNode &b) {
PNode temp = a;
a = b;
b = temp;
}
void adjust_min_heap(PNode *bin, int i, int k) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int min_index;
if(left < k && bin[left]->data < bin[i]->data) {
min_index = left;
} else {
min_index = i;
}
if(right < k && bin[right]->data < bin[min_index]->data) {
min_index = right;
}
if(min_index != i) {
swap(bin[i], bin[min_index]);
adjust_min_heap(bin, min_index, k);
}
}
void build_min_heap(PNode *bin, int k) {
for(int i = k / 2; i >= 0; i--) {
adjust_min_heap(bin, i, k);
}
}
int *get_k_th_minimum(int *a, int *b, int k) {
PNode *bin = (PNode*)malloc(sizeof(PNode) * k);
int *result = (int*)malloc(sizeof(int) * k);
memset(result, 0, sizeof(int) * k);
int i;
int count = 0;
for(i = 0; i < k; i++) {
bin[i] = (Node*)malloc(sizeof(Node));
bin[i]->row = i;
bin[i]->col = 0;
bin[i]->data = a[i] + b[0];
}
build_min_heap(bin, k);
while(count < k) {
result[count++] = bin[0]->data;
bin[0]->col += 1;
bin[0]->data = a[bin[0]->row] + b[bin[0]->col];
adjust_min_heap(bin, 0, k);
}
for(i = 0; i < k; i++) {
free(bin[i]);
}
free(bin);
return result;
}
void main() {
int a[] = {1, 2, 4};
int b[] = {5, 9, 11};
int k = 3;
int *p = get_k_th_minimum(a, b, k);
for(int i = 0; i < k; i++) {
cout << p[i] << " ";
}
free(p);
getchar();
}| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 1of 1 vote
Answersprint all the characters present in the given string only once in a reverse order. Time & Space complexity should not be more than O(N).
- anonymous May 31, 2016 in United States
e.g.
1)Given a string aabdceaaabbbcd
the output should be - dcbae
2)Sample String - aaaabbcddddccbbdaaeee
Output - eadbc
3)I/P - aaafffcccddaabbeeddhhhaaabbccddaaaa
O/P - adcbhef
Answer :
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;
public class StringQAmazon {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
String inputStr = sc.nextLine();
System.out.println(stringManipulation(inputStr));
}
static String stringManipulation(String str) {
if(str.isEmpty())
return "";
else if(str.length()==1)
return str;
else {
str.toLowerCase();
StringBuilder strBuilder = new StringBuilder();
strBuilder.append(str);
strBuilder.reverse();
Set<Character> set = new LinkedHashSet<Character>();
for(int i =0; i<strBuilder.length(); i++){
set.add(strBuilder.charAt(i));
}
Iterator<Character> iter = set.iterator();
strBuilder=new StringBuilder();
while(iter.hasNext()){
strBuilder.append(iter.next());
}
return strBuilder.toString();
}
//return null;
}
}| Report Duplicate | Flag | PURGE
Amazon SDE-2 String Manipulation - 1of 1 vote
AnswersYou are given a huge log file which holds the entry and exit time of each person entering and exiting the office on a given day
- evolution monkey June 03, 2012 in United States
format of file:
entry time exit time
09:12:23 11:14:35
10:34:01 13:23:40
10:34:31 11:20:10
.
.upto N entries for a given day
Design a function which returns the total number of persons in the office at any given time. e.g input to function is 11:05:20.
The interviewer said he could call the function every second with input 11:05:20, 11:05:21,11:05:22, 11:05:23..........14:30:30
I really did not understand how to optimize the function.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersFind if a binary tree is bst
- anonym October 10, 2011 in -| Report Duplicate | Flag | PURGE
Amazon Flipkart Groupon Software Engineer / Developer Trees and Graphs - 1of 1 vote
AnswersThere is a given linked list where each node can consist of any number of characters :- For example
- vibsy October 25, 2012 in India
a-->bcd-->ef-->g-->f-->ed-->c-->ba.
Now please write a function where the linked list will return true if it is a palindrome .
Like in above example the linked list should return true| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Software Engineer in Test Data Structures - 1of 1 vote
AnswersGiven a number in an array form, Come up with an algorithm to push all the zeros to the end.
- kiranpm86 February 24, 2014 in India
Expectation : O(n) solution| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Algorithm Arrays C++ Coding - 1of 1 vote
AnswersGiven a dictionary of strings [ strings are in sorted order] you have to find the precedence of characters according to the dictionary..
- Anton April 21, 2012 in India
eat
bxy
e is ranked above b according to the dictionary.| Report Duplicate | Flag | PURGE
Google Amazon Software Engineer / Developer Algorithm Data Structures Trees and Graphs Brain Teasers - 1of 1 vote
Answersgiven a binary tree ,find the largest sub-tree which is a BST...(largest means subtree having largest no of nodes in it)...this is a wonderful question.....
- psp.reachable@gmail.com October 13, 2008| Report Duplicate | Flag | PURGE
Amazon Development Support Engineer Trees and Graphs - 1of 1 vote
AnswersReverse an array in subset of N. Example:
- Prashant May 22, 2016 in India for Kindle
input: Array = [1,2,3,4,5,6,7,8,9], N = 3
output: [3,2,1,6,5,4,9,8,7]| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer - 1of 1 vote
AnswersGiven an array of 0s and 1s, and k, Find the longest continuous streak of 1s after flipping k 0s to 1s.
- neer.1304 February 14, 2016 in United States
E.x array is {1,1,0,0,1,1,1,0,1,1}
k = 1 (which means we can flip âkâ one 0 to 1)
Answer: 6 (if we flip 0 at index 7, we get the longest continuous streak of 1s having length 6)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
Answers
- BVarghese July 26, 2013 in United StatesSearch for an element in a matrix. Rows and columns of the matrix are sorted in ascending order. eg. matrix [1 14 25 35] [2 16 28 38] [5 20 28 40] [16 22 38 41] search for 38. The interviewer was looking for a solution better than O(n+m). He didn't want a solution which starts searching from the left bottom and go to right or above according to the key value to search. That solution has O(n+m) worst complexity, where n is row count and m is column count.
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersFind the substring of length 3 which is present in the reverse order from the string.
- swethas17 November 22, 2011 in United States
Ex: if the string is abcdcba (cba is the reverse of abc) so we should return cba.
And was asked to improve upon the complexity.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer String Manipulation - 1of 1 vote
AnswersSuppose that we have a sorted singly linked list with integer values. For example:
- snass005@ucr.edu February 05, 2013 in United States
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
We want to change the pointers of this linked list so that it becomes:
7->1->6->2->5->3->4
I did not have enough time left to finish my code and I could not think of a good solution.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 1of 1 vote
AnswersGiven two String, s1 and s2.
- niraj.nijju October 15, 2013 in India
to find the longest substring which is prefix of s1, as well as suffix of s2.| Report Duplicate | Flag | PURGE
Amazon Algorithm - 1of 1 vote
AnswersFind the second most repeating number in an array without using extra storage. (I had given solution using a hash table)
- xyz_coder April 02, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Intern - 1of 1 vote
AnswersQ3. Written Exam Amazon(Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a singly linked list which may or may not contain loop and loop may or may not start from the head node. Count the number of elements in the linked list.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 1of 1 vote
AnswersGiven a set of unique numbers from 1 to 1000, propose a data structure that allows you to perform the following operations in constant time.
- Fab February 10, 2012 in United States for Instant Video
1- Insertion,
2- Deletion,
3- Searching,
4- Get any random number.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 1 vote
AnswersYou are given an array of integers(with all valid input) You have to write a function which will produce another array, where the value in each index of the array will be the product of all values in the given array accept that index.
- Azarbaizan January 10, 2017 in United States for Market Place
Example
Array 1: 1 2 3 4 5
Array 2: 120 60 40 30 24.
Come up with a solution of O(n^2) can you improve it?| Report Duplicate | Flag | PURGE
Amazon Software Engineer Arrays - 1of 1 vote
AnswersWrite program for the following scenario
- APV July 25, 2015 in India for Amazon Wireless
Input Array :- {1,2,3,4,5,5,5,6,7,7}
Output:- 5 is repeated 3 times
7 is repeated 2 times| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Arrays - 1of 1 vote
AnswersPrint all subset of a given set which sums up to ZERO
- apurohit.in January 09, 2015 in India
{8,3,5,1,-4,-8}
so ans will be : {8,-8}
{3,5,-8}
{3,1,-4}
size of set can be upto 50 but elemet of set can be as big as 18 digit number| Report Duplicate | Flag | PURGE
Amazon Dev Lead Dev Lead Algorithm - 1of 1 vote
AnswersGiven a String "abcxrrxabcrr"
- vigneshselvakumar January 10, 2013 in United States
Find the first repeated string with minimum 3 character?
Answer is "abc" min 3 characters.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer C++ - 1of 1 vote
AnswersDetermine whether an interger is a multiple of 5 in O(logn) time complexity. You cannot use / and %.
- xuwithsurprise January 20, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 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 - 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 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 - 1of 1 vote
Answersgenerate permutations of a string without duplicates and without using hashtable to memorize the permutations.
- Andi December 05, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersA = "ffgggtvshjsdhjfffffffhvjbjcharu"
- SPS March 14, 2017 in India
Find the max consecutive repitative chracter
Output : f -> 7| Report Duplicate | Flag | PURGE
Amazon Testing / Quality Assurance Online Test