## Amazon Interview Questions

- 0of 0 votes
You are to concatenate n strings (concatenate in any order) and a function:

int strCat(str1, str2); // returns the concatenated str length

Concatenate all strings in any order so that total cost is minimum.

Example: Strings A="abc", B="wxyz", C="a"

Cost of strCat(A,B) = (3+4) = 7

Cost of strCat(AB,C) = 7+1 = 8

Total cost = 7+8 =15

Other way:

Cost of strCat (A,C) = 3+1 = 4,

Cost of strCat (AC,B) = 4+4 = 8

Total Cost = 4+8 = 12

In this case, min(12,15) = 12 so Ans=12.

- 1of 3 votes
Given a Integer, find the maximum number that can be formed from the digits.

Input : 8754365

output : 8765543

I told solution in nlogn. He asked me optimize further.

- 0of 0 votes
Write test cases for,

Testing a API , which takes URL as input which points to a html page, finds a specific TAG and extracts all integers between the tags, sorts the numbers in ascending order and writes it to a file

- 0of 0 votes
Tell the following 3 letter in the sequence

A E F H I K _ _ _

- 1of 1 vote
Check if the given binary tree is a unival tree. (all nodes have same value)

Follow up- Count the number of unival subtrees in a binary tree.

- 0of 0 votes
Given an integer of a certain bit length, does it have an even or odd number of parity bits?

Optimization - Can you do this recursively in one line of code?

- 2of 2 votes
You are given a function: List<TimeSlot> getTimeSlots (String friend)

Assume getTimeSlots() returns available times for a friend, sorted in order, with no overlap.

Assume TimeSlot has comparable function

You want to schedule a meeting among all of your friends, such that all can attend.

Implement a function to get the first 3 common TimeSlots among all your friends:

List<TimeSlot> get3CommonTimeSlots (List<String> friends)

user1 1-2pm, 3-4pm, 7-8pm

user2 1-2pm, 5-6pm

- 0of 2 votes
Given an array of random integers and a sum value, find two numbers from the array that sum up to the given sum.

eg. array = {2,5,3,7,9,8}; sum = 11

output -> 2,9

Implement in O(n) time complexity. Find all distinct pairs. (2,9) and (9,2) are not distinct.

- 0of 0 votes
What are the advantages of an array over a linked list? and vice versa.

- 0of 0 votes
Design Twitter Timeline

- 4of 4 votes
in a tree any root can have any number of children. Every node has an integer value. Find the maximum length on consecutive number sequence anywhere in the tree. For example if root is 2 and one child is 3, its child is 4 its child is 6 then max length will be 3. I was able to write the code the find of one sequence but when one sequence ends and other starts I was not able to handle that case. I think its hard to do by recursion. Is there any other trick or algorithm for this??

- 0of 0 votes
Given a 1D array with integers,print vertical bars of # such that if a[i] = n, then print # n times from the bottom.

For eg, {1,4,3,2}

o/p : #

# #

# # #

# # # #

- 0of 0 votes
Give a path get it's canonical form. So for example if you have path in the form e/../../a/d/./../b/c then you should return a/b/c.

I have the solution but it's not the most optimal or the best solution. I just wanted to see what others have.`public String canonicalPath(String path){ if(path == null || path.isEmpty()){ throw new RuntimeException("incorrect path provided"); } String[] chunks = path.split("/"); Stack<String> s = new Stack<String>(); List<String> arr = new ArrayList<String>(); for(String chunk: chunks){ if(chunk.isEmpty() || chunk == "."){ System.out.println("skipping"); }else{ if(!s.isEmpty() && s.peek().equals("..") && !chunk.equals("..")){ while (!s.isEmpty()) { if(s.peek().equals("..")){ s.pop(); }else{ s.pop(); break; } } s.push(chunk); }else{ s.push(chunk); } } } StringBuffer sb = new StringBuffer(); List<String> list = null; if(!s.isEmpty()){ list = new ArrayList<String>(s); } if(list != null){ for(String ss : list){ sb.append("/"+ss); } } return sb.toString(); }`

- 0of 0 votes
Given a list of integers, e.g.:

`{ 2, 6, 7, 9, 1, 0, 1, 2, 3, 6 }`

.

Write an time efficient algorithm to find the longest subset in which the difference between the minimum and maximum numbers is 0 or 1.

The subset can have a length of 0 and can hold any of the values in the original array (order not matters).

- 0of 0 votes
Given a 2 D array with m Entry points (which are on the edges) and n exit points which are on the edges give the total number of paths that are possible.

- 0of 0 votes
Link all the level order nodes to makes a linked list with the first node of each level acting as the root of that linklist.

10

/ \

6 17

/ / \

4 14 19

So the Linklist will be

10->null

6->17->null

4->14->19->null

- 0of 0 votes
You have three containers, small, medium and large. Passenger comes in, checkin the luggage. You have to store the baggage in the appropriate container and generate a unique token number. Then passenger should get back the bag using the same token number. Trick was if small container is full store in medium if available or large. Now if the large bag comes in and there is now a empty space in small, than move the small bag back to small & store the large bag. How to generate the unique token number and move the baagage internally without changing the token number?

Lookup should be in constant time complexity and insertion in minimum complexity.

- 0of 0 votes
Scenario : Multi Seller E-commerce Website

Given a list of products in a customer basket find the minimum number of seller required to deliver his order,so as to optimise shipping part.

Assuming you have already have below data

Customer orders products : P1,P2,P3,P4,P5,P6

Products and seller mapping

P1 = [1,2,3,4]

P2=[2,4,5,6]

where 1,2,3 etc denotes seller_ids.

p1

- 0of 0 votes
If I was a marketer for a large company, tell me how I can increase the number of likes I have on my Facebook business page to 5 million?

- 0of 0 votes
Your are given two strings str1 and str2, you have to generate another unique string str3, which can only generated by these two string str1 and str2, no other string can generate that string str3. Some later point you have to retrieve back those two string str1 and str2 form that unique string str3.

- 0of 0 votes
You are given an array, you have to replace each element of the array with product of the rest element. Example: {1,2,3}==> {6,3,2}

- 0of 0 votes
Suppose you have an array with infinite numbers, which is sorted and there may be duplicates. Find the occurrence of a number.

- 0of 0 votes
How will implement an auto complete feature? Eg: if you type clo it shows clothes etc

- 0of 0 votes
Suppose there are 2 streams, which has infinite value and write a method that returns a stream that would be a combination of both the streams in a sorted form

- 0of 0 votes
Write printf method.

- 1of 1 vote
Which is best Merge Sort or QuickSort?

Why and How?

- 0of 0 votes
Amazon wants to implement a new backup system, in which files are stored into data tapes. This new system must follow the following 2 rules:

1. Never place more than two files on the same tape.

2. Files cannot be split across multiple tapes.

It's guaranteed that all tapes have the same size and that they will always be able to store the largest file.

Every time this process is executed, we already know the size of each file, and the capacity of the tapes. Having that in mind, we want to design a system that is able to count how many tapes will be required to store the backup in the most efficient way.

The parameter of your function will be a structure that will contain the file sizes and the capacity of the tapes. You must return the minimum amount of tapes required to store the files.

Example:

Input: Tape Size = 100; Files: 70, 10, 20

Output: 2

- 0of 0 votes
Find the first word in a stream in which it is not repeated in the rest of the stream. Please note that you are being provided a stream as a source for the characters. The stream is guaranteed to eventually terminate (i.e. return false from a call to the hasNext() method), though it could be very long. You will access this stream through the provided interface methods. A call to hasNext() will return whether the stream contains any more characters to process. A call to getNext() will return the next character to be processed in the stream. It is not possible to restart the stream.

Example:

Input: The angry dog was red. And the cat was also angry.

Output: dog

In this example, the word ‘dog’ is the first word in the stream in which it is not repeated in the stream.

- 0of 0 votes
For a given matrix, find the maximum product of k elements. The elements can be formed from continuous 4 elements horizontally, vertically or diagonally. Eg: For k= 4, the maximum product is (6*4*7*9) from the last column,

1 2 0 -1 4

3 1 2 4 6

0 2 3 1 4

1 3 2 0 7

2 1 3 2 9

- 0of 0 votes
(Variant of Children-Sum Problem better than O(n^2))

Given a tree, implement a function which replaces a node’s value with the sum of all its childrens’ value, considering only those children whose value is less than than the main node’s value.

Eg: input = 60->50->80->40 , output = 90->40->40->0