## Amazon Interview Questions

- 2of 2 votes

AnswersLucky numbers are those numbers which contain only "4" and/or "5". For example 4, 5, 44, 54,55,444 are lucky numbers while 457, 987 ,154 are not.

- sunny.010203045 January 29, 2014 in India

Lucky number sequence is one in which all lucky numbers exist in increasing order for example 4,5,44,45,54,55,444,445,454,455...

Now we concatenate all the lucky numbers (in ascending order) to make a lucky string "4544455455444445454455..."

Given n, your task is to find the nth digit of the lucky string. If the digit is 4 then you have to print "Hacker" else you have to print "Earth".

Input:

first line contain number of test cases T , next T line contain a single interger n.

Output:

For each test case print "Hacker"(without quotes) if nth digit of lucky string is "4" else print "Earth"(without quotes) if nth digit of lucky string is "5".

Constraints:

1<=t<=10^5

1<=n<=10^15| Report Duplicate | Flag | PURGE

Amazon SDE1 - 1of 1 vote

AnswersProblem Statement

- sunny.010203045 January 29, 2014 in India

There are three types of tickets and stations available in CodeCountry A, B and C. Tickets of type A can only be bought at stations of type A and end at a station of type B. Tickets of type B can only be bought at stations of type B and end at a station of type C. Similarly, tickets of type C can only be bought at stations of type C and end at a station of type A. Also, you can only travel from station i to station j if j > i, i.e. you can only move forward and if the ticket type bought at station i ends at station j.

The cost of a ticket is j x j if you travel a distance of j. For example if you start at Station 3 and end at station 5 the cost is 2 x 2=4.

Now, you want to travel from Station 1 to Station N using trains in CodeCountry. You are given the type of each station. Output the minimum cost of the journey.

Note that station N will also have a type and you must reach it using a ticket of compatible type. Output -1 if it is not possible to reach from station 1 to station N

Input Format

The first line contains the number of test cases T. This is followed by T lines one for each test case.

Each test case consists of a string representing the types of each station. The i-th character of the string represents the i-th station's type.

Output Format

Output the minimum cost of the journey, one line per test case.

Constraints

The number of test cases is atmost 50.

There will be atleast 2 stations and atmost 15 stations.

The first station (station 1) is always of type A.| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 2 votes

AnswersYou are given an array A with elements 0 to n-1, numbers can be repeated in the array. Create n sets where

- sunny.010203045 January 27, 2014 in United States

S[i]={a[i],a[a[i]],a[a[a[i]]]…}. Set has all elements unique. Find the size of the largest set.

Input:

First line contains n, size of the array. n<1000

Next lines contains n numbers, each element of the array

Output

Prints one number: Size of the largest set.

Sample Test Case:

Input: {3,1,2,0}

Output: 2

Explanation:

Four possible sets are

{3,0},{1},{2}{0,3}| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGiven an array of integers. Remove minimum number of elements from the array such that the largest and the smallest number does not differ by more than two times.In other words if x is the minimum of the remaining elements in the array and y is the maximum than y<=2x.

- sunny.010203045 January 27, 2014 in United States

Find the minimum number of numbers that has to be removed from the array so that the largest and the smallest number differed in no more than two times.

Input:

First line contains n(2<=n<=10^5), the size of the array

Second line contains n integers, the elements of the array.

Output:

Single integer - the minimum number of elements to be removed from the array.

Sample Test Case:

Input: {4,5,3,8,3,7}

Output: 2

Note: In the above sample you can remove the fourth and the sixth measurement results (values 8 and 7). Then the maximum of the remaining values will be 5, and the minimum one will be 3. Or else, you can remove the third and fifth results (both equal 3). After that the largest remaining result will be 8, and the smallest one will be 4.

You do not need to write full code. Just fill out the given function.| Report Duplicate | Flag | PURGE

Amazon SDE1 - -1of 1 vote

Answersyou have a array which says the order of alphabets say [abcdef....z]. now use this array to sort, constraint is 'a' can be swapped one time 'b' two times, and for sorting you can use only swap.

- sameer.careercup January 26, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 - -1of 1 vote

Answeryou have n different array, all are sorted. form one array of size n whose range is min. meaning in resultant array diff of a[0] to a[n-1] is min.

- sameer.careercup January 26, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 2 votes

AnswersSuppose there is array contains 100 unsorted elements ...say a[1] to a[100].

- Ruhan January 25, 2014 in India

find out the minimum and maximum value in the range of a[25] to a[75].| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 2of 2 votes

AnswersThere is a large file( 1TB) containinig braces. Question is to check for their balance. I said will use a counter, will increment on an open brace and decrement on an close brace. If counter goes negative or counter is non zero at the end of the file, braces are not balanced. Otherwise balanced. Followup question was to make this process parallel ( meaning to see if this problem can be solved through parallelism, like dividing the the problem into sub problem....) Remember the file is very large.

- gns January 23, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Problem Solving - 0of 0 votes

AnswersGiven a tree, generate all paths. Note : all paths..not just the ones starting from root

- anon123 January 22, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 1of 1 vote

AnswersImplement a function which returns list of all nodes in a binary tree having a given number of leaves, say k . Also mention complexity.

- batradiva January 22, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 1of 1 vote

AnswersOnline assessment:

- 2013renting2013 January 12, 2014 in United States

There are N points on a 2D plane, find the k closest points.| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersYou are given an array of integers, sorted, but rotated. Find an better than O(n) algorithm to find an element in an array. Write code for this.

- GSheld January 11, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersYou are given a long list of integers, so long that you can not fit the entire list into memory, implement an algorithm to get the max 100 elements in the list.

- GSheld January 11, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersSecond question is Implement a boolean method for returning whether an appointment with a doctor is possible or not. Given that we have a set of start and end time frames already scheduled with the doctor.

- lks January 10, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersFind the longest common substring between 2 string in O(n) complexity

- lks January 10, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersPrint a 2D array in spiral order.

- GSheld January 10, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersYou are standing at 0 0 and you have to get to i, j. Find the number of ways. Did that with recursion then with DP. Then he extended the question saying some edges are not traversible. Then edges have weights, find min weight path.

- anonymous January 09, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersYou are standing at 0 0 and you have to get to i, j. Find the number of ways.. Then he extended the question saying some edges are not traversible. Then edges have weights, find min weight path.

- anonymous January 09, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersAn array is given representing the colors of n jars, colors have values 0-99. When two jars are mixed the resulting volume is same as volume of one jar. Smoke is color1*color2… and resulting color is (color1+color2)% 100. Keep on mixing colors such that you end up with just one jar with minimum smoke.

- anonymous January 09, 2014 in India| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 0of 0 votes

AnswersSecond Question is to Encode a String

- lks January 09, 2014 in United States

aaaabbccdd -> a4b2c2d2

In minimun space and time complexity| Report Duplicate | Flag | PURGE

Amazon SDE1 Data Structures - 0of 0 votes

AnswersFirst question is You have two numbers represented by a linked list, where each node contains a single digit. Write a function that adds the two numbers and returns the sum as a linked list

- lks January 09, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 Data Structures - 0of 0 votes

AnswersImplement stack with findMiddle and deleteMiddle() in constant time.

- lks January 09, 2014 in United States

Can you please explain and write code for it| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGiven a binary search tree whose nodes are integers, find the frequency of occurrence of each digit in the tree.tr

- lks January 07, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 Trees and Graphs - 0of 0 votes

AnswersYou have a single string which contains all the positive numbers upto N concatenated together. If you are given an input number then how would you find the index position of the number in the string.

Eg:`String str = "12345678910111213141516171819202122232425......upto 10000"; input = 20 should return the index of 20 in the string which is 29`

The example string is upto 10000. The actual string can be upto any number N.

- anonymous January 06, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 String Manipulation - 0of 0 votes

AnswersHow would you represent a graph with million nodes ?

- lks January 06, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 Data Structures - 1of 1 vote

AnswersThere are two questions that I want to ask.

- lks January 06, 2014 in United States

Q1) divide two numbers without “/”

Q2) judge if there are two numbers in an array add to a given number

For both the questions please consider minimum space and time complexity| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGiven a collection of 3-set sequences, where a 3-set sequence is defined as a list of 3 different pages (for example: mouse-keyboard-printer is a 3-set sequence, while printer-mouse-keyboard is another) accessed sequentially on amazon.com, find the most common 3-set sequence with minimum space and time complexity

- lks January 06, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 Data Structures - 1of 1 vote

AnswersWrite a function to remove all redundant characters in a given string with minimum space and time complexity

- lks January 06, 2014 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 Data Structures - 2of 2 votes

Answersint sum = 0;

- nirupam.astro January 04, 2014 in India

for (int i = 0; i < m; i++)

for (int j = i + 1; j < n; j++)

for (int k = j + 1; k < l; k++)

sum++;

what will be the value of sum?| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm - 1of 1 vote

AnswersGiven a linked list of integers, write a function to determine whether the given list has a loop or cycle anywhere in the list. The integer values may not be relied upon to be distinct.

- outside09 December 30, 2013 in United States

You may use the JDK or the standard template library. The solution will be evaluated on correctness, runtime complexity (big-O), and adherence to coding best practices. A complete answer will include the following:

Document your assumptions

Explain your approach and how you intend to solve the problem

Provide code comments where applicable

Explain the big-O run time complexity of your solution. Justify your answer.

Identify any additional data structures you used and justify why you used them.

Only provide your best answer to each part of the question.

Use one of the following skeletons for your solutions.

Java:

public class ListLoopQuestion {

public static class ListNode {

public int value;

public ListNode next;

}

public static boolean hasLoops( ListNode myList ) {

}

}

C++:

struct ListNode {

int value;

ListNode * next;

}

bool hasLoops( ListNode * myList ) {

}| Report Duplicate | Flag | PURGE

Amazon SDE1 Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window