## Amazon Interview Questions

- 2of 2 votes
PLEASE NOTE: NlogN time complexity requirement.

A non-empty zero-indexed array A of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

A min abs slice is a slice whose absolute sum is minimal.

For example, array A such that:

A[0] = 2

A[1] = -4

A[2] = 6

A[3] = -3

A[4] = 9

contains the following slice, among others:

(0, 1), whose absolute sum = |2 + (−4)| = 2

(0, 2), whose absolute sum = |2 + (−4) + 6| = 4

Both slices (0, 3) and (1, 3) are min abs slices and their absolute sum equals 1.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty zero-indexed array A consisting of N integers, returns the absolute sum of min abs slice.

For example, given:

A[0] = 2

A[1] = -4

A[2] = 6

A[3] = -3

A[4] = 9

the function should return 1, as explained above.

Assume that:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [−10,000..10,000].

Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

- 0of 0 votes
Hardest bug you faced

- 0of 0 votes
Let's assume that there's an array that has nonzero natural numbers where all the numbers repeat an even number of times, except for one value that repeats an odd number of times. Can you write me a function that takes this array, and returns the value that occurs the odd number of times?

Ex : - [ 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 ]

- 0of 0 votes
There is a data structure called mySruct and it contains a, b , c all three of type int . Which means that any data structure takes up 12 bytes . Then in the main define an array of 3 myStructs (ie taking up 36 bytes .. ) . Then define char * and make him an assignment to array( with casting ) . Then do

16 = + c * . That is, come to b in second myStruct. Then do c = 10 , and ask what 's going on?

So the answer is that arr [0] -> b becomes 10

- 0of 0 votes
Find the longest running positive sequence in an array -

Eg - [1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6]

It should return 5, with start index : 8

- 0of 0 votes
class a{

public int x=7;

public int y=9;

void f1(){x=24;}

void static f2(){y=35;}

}

what problem in the code?

what is need to change in the code for compaling?

- 1of 1 vote
Find the second most repeating number in an array without using extra storage. (I had given solution using a hash table)

- 0of 0 votes
Implement a stack that supports push, pop and median (the one from statistics) operation in the most efficient way

- 1of 1 vote
Implement a stack that supports push, pop and mode(the one from statistics) operation in the most efficient way

- 0of 2 votes
Write a program to test whether a string and all strings that can be made using the characters of that string are palindrome or not.

Eg:

Input Output

mmo True

yakak True

travel False

Note : Please do not use any inbuilt functions.

- 0of 0 votes
Given an array of ints, return a string identifying the range of numbers

Example

Input arr - [0 1 2 7 21 22 1098 1099]

Output - "0-2,7,21-22,1098-1099"

- 3of 3 votes
Sparse number is an integer if there are no adjacent 1 in it's binary representation.

Like: 5 -> 101 (no adjacent 1)

9 -> 1001 (no adjacent 1)

while 6-> 110 is not sparse number.

Now you are given an integer find the NEXT BIGGER sparse number.Please mind 'it is next bigger'.

- 0of 0 votes
Graph problem:

Critical node: If a node reaches another node only through one node.

Eg: A-C-B and A-E-B are critical nodes. (A reach B through one node which is C or E)

If A reaches B through more than one node, then they are not critical nodes.

1) A-C-B

A-D-E-B (A reach B thro C which might lead to critical node but A has another path to B thro D and E, so they are not critical nodes).

2) X-Y-Z

X-A-Z (X and Z are critical nodes)

Now find all critical nodes.

- 0of 0 votes
Given two sorted LinkedLists, merge them into one sorted LinkedList

- 0of 0 votes
Hashmap(what is it, time complexity of insertion and deletion)

- 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.