Amazon Interview Questions
- 4of 4 votes
AnswersIf [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn] , solution should be in-place
- Anonymous February 05, 2011| Report Duplicate | Flag | PURGE
Amazon Microsoft Developer Program Engineer Software Engineer / Developer Algorithm Arrays - 2of 2 votes
AnswersRound 1: Q2:
- Abee July 20, 2011
Puzzle
Given 25 horses, find the best 3 horses with minimum number of races. Each race can have only 5 horses. You don't have a timer.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Brain Teasers Highbridge Capital Deshaw Inc - 2of 2 votes
Answersfind the longest palindrome in a string?
- handiaya November 09, 2009| Report Duplicate | Flag | PURGE
Microsoft Amazon Software Engineer / Developer Algorithm Arrays C++ Coding String Manipulation C - 0of 0 votes
AnswersDesign an ATM machine system..
- TechPrep December 20, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon System Design - 2of 2 votes
Answersgive me the code for :
Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.
Eg: O/p should be "I ma a namuh gnieb"
I somewhat wrote the code, but i was asked what if there are extra spaces etc.
(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)
let me know the best and optimised way of writing this code.
Also i suggest people to aviod using inbuilt functions as much as possible
My Answer is as below in perl
- i_learn April 11, 2014 in India#i want the reverse of the letters of all words in a string #eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb" $str="I am a human being"; @arr=split(' ',$str); print @arr; for($i=@arr-1;$i>=0;$i--) { $_=@arr[$i]; ####intead of above for loop if we use foreach(@arr) then it will reverse the whole string @word=split('',$_); { foreach $n (@word) { unshift(@final,$n); } } } print "\n @final \n";
| Report Duplicate | Flag | PURGE
Amazon Testing / Quality Assurance Algorithm Android Application / UI Design Arrays Automata Coding Data Structures Dynamic Programming Perl - 3of 3 votes
Answersone unsorted array is given.Find out the index i and j ,j> i for which a[j] - a[i] is maximum.perform in linear time complexity
- rahul baid February 17, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Data Structures Arrays - 1of 1 vote
AnswersYou are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
- Anonymous August 25, 2010
algorithm to find the maximum sub sequence which has equal number of 1s and
0s.
Examples
1) 10101010
The longest sub sequence that satisfies the problem is the input itself
2)1101000
The longest sub sequence that satisfies the problem is 110100| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 0 votes
AnswersSimulate a seven-sided die using only five-sided
- vodangkhoa March 23, 2008| Report Duplicate | Flag | PURGE
Amazon Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random.
- geekonomics January 19, 2012 in United States| Report Duplicate | Flag | PURGE
A9 Software Engineer / Developer Brain Teasers Amazon - 3of 3 votes
AnswersQ1.- Written exam (Amazon, Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.
Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8
Sample Input: 1->2->3->4->5->6->7->8 and K = 10
Sample Output: print error "LIST IS OF LESSER SIZE".| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 0of 0 votes
AnswersCompress a given string "aabbbccc" to "a2b3c3"
- john January 22, 2011
constraint: inplace compression, no extra space to be used
assumption : output size will not exceed input size.. ex input:"abb" -> "a1b2" buffer overflow.. such inputs will not be given.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 11of 13 votes
AnswersGiven s string, Find max size of a sub-string, in which no duplicate chars present.
- sanjay05iitr November 10, 2013 in India for Cyllas Experience| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersString Reduction
- sf engineer February 20, 2012 in United States
Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?
Input:
The first line contains the number of test cases T. T test cases follow. Each case contains the string you start with.
Output:
Output T lines, one for each test case containing the smallest length of the resultant string after applying the operations optimally.
Constraints:
1 <= T <= 100
The string will have at most 100 characters.
Sample Input:
3
cab
bcab
ccccc
Sample Output:
2
1
5
Explanation:
For the first case, you can either get cab -> cc or cab -> bb, resulting in a string of length 2.
For the second case, one optimal solution is: bcab -> aab -> ac -> b. No more operations can be applied and the resultant string has length 1.
For the third case, no operations can be performed and so the answer is 5.| Report Duplicate | Flag | PURGE
Facebook Amazon Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a circular single linked list.Write a program that deletes every kth node until only one node is left.
- Aashish August 01, 2012 in India
After kth node is deleted, start the procedure from (k+1)th node.
e.g.list is 1->2->3->4->5->1
k=3
1. You are at 1, delete 3.
List is: 1->2->4->5->1
2. You are at 4, delete 1
List is: 2->4->5->2
3. You are at 2,delete 5
List is: 2->4->2
4. You are at 2, delete 2
List is: 4
Return 4.
How efficient you can do it?| Report Duplicate | Flag | PURGE
Amazon Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are given two numbers in the form of linked list.Add them without reversing the linked lists. linked lists can be of any length.
- manjunath426jc December 26, 2011 in India
Ex:123 1->2->3
10234 1->0->2->3->4
ans: 10357 1->0->3->5->7| Report Duplicate | Flag | PURGE
Amazon Qualcomm Software Engineer / Developer Linked Lists - 1of 1 vote
AnswersConsider a series in which 8 teams are participating. each team plays twice with all other teams. 4 of them will go to the semi final.How many matches should a team win, so that it will ensure that it will go to semi finals.?
- putta.sreenivas May 11, 2011| Report Duplicate | Flag | PURGE
Amazon Google Developer Program Engineer Software Engineer / Developer Algorithm Brain Teasers - 11of 11 votes
AnswersGiven a sequence of non-negative integers find a subsequence of length 3 having maximum product with the numbers of the subsequence being in ascending order.
- Bhavi Jagwani April 06, 2013 in India
Example:
Input: 6 7 8 1 2 3 9 10
Ouput: 8 9 10| Report Duplicate | Flag | PURGE
Amazon - 1of 1 vote
AnswersWith a linked list data structure, find if a given string is palindrome or not.
- sathish.leo May 26, 2012 in United States| Report Duplicate | Flag | PURGE
Expedia Amazon Software Engineer / Developer Linked Lists - 2of 4 votes
AnswersA string contains a-z, A-Z and spaces. Sort the string so that all lower cases are at the beginning, spaces in the middle and upper cases at the end. Original order among lower and upper cases needs to remain the same. For example: a cBd LkmY becomes ackm BLY. Is there a way in O(n) without extra space?
- chad August 13, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm Arrays - 0of 0 votes
AnswersYou have given a positive number you have to find a number which is bigger than that by using same digits available in the number .
- Nitin September 19, 2011 in India
Example :-
You have given a number 7585 , your output should be 7855 .| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 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 - 3of 3 votes
AnswersCheck if an integer array is arithmetic sequence.
- PS February 08, 2016 in United States
Example: 1, 2, 3, 4, 5, 6, 7, 8 => true
1, 3, 5, 7, 9 => true
Array may not be sorted.| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 23of 23 votes
AnswersYou are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .
- Kavish Dwivedi July 15, 2013 in India for Bangalore
NOTE: The array isn't necessarily sorted.| Report Duplicate | Flag | PURGE
Amazon SDE1 Arrays - 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