CareerCup

Find the label with max width of a tree.
// 0 A
// /|\
// 1 B C D
// /| | \
// 2 E F G H
Answer is 2 here.

Design entity(model) structure of a file systems. You don't have to write any interfaces, just various models and their properties.

You have to desing a system for a shop kepper to keep his/her inventory managed. He/she have furniture at the begining, but he may add more items to it. His/her furnitures are wood char, wood table, steel chair, etc.
Each furniture have one property, a boolean one, called isChildSafe.


Later, he said, what if the shopkeeper wants to add new type of items, such as phone or may be something else, and he/she might also wants to add two new properties, such as isFireSafe, isWaterSafe etc.

How would you design extend to these types.

You have to design a job scheduler. The job schedular should be able to accept all kind of jobs, small or long running. Multiple systems might be adding jobs to it and multiple systems should be able to execute jobs simultaneously.
Please list down the components and data flows between them, what kind of interfaces you will be having, what kind of retry logic you will be providing, storage and middle tier design was also asked.

You are given set of strings, You have return anagrams subsets from it. An anagram set is that one where every string is an anagram of another string. If the subset contains only one string, don't include that in the result.

You are given a NxN boolean matrix, where matrix(i,j) will be one if 'i' is a parent of 'j' in a tree, otherwise, it is zero.
Construct this tree.

Design/Implement an LRU cache so that Read/Write/Find operation only takes constant time.

Now, Let's say, we will be considering the frequency as well. It means to keep the most used processes and in a case of the tie, use lease recently used to remove an element.

Now, as this new algorithm can cause many hits, or no new process will come to the cache if the last process of the cache has two hits., What can you do to prevent this, and how would you implement that.

There is a cluster of servers. In this cluster some group of servers are running application A, some group are running B, etc. Each application server produces huge logs and the log file sizes run into GBs. Each minute there are millions of log entries.

You need to design a system that allows you to:
1. Specify the name of the application whose logs you want to search.
2. Search any text that the log message may contain.
3. Search within a time stamp range.
4. Search within the specified log level(s).

The system should be real-time.

What is the cost / complexity of a String.indexof() function call in java?

How to check the validity of a 4 digit credit card expiration date (mm/yy)
that still works 100 years from now.
public boolean isValid(String s){

}

what is the time complexity for java.util.Random.nextInt()

If you are given 20 test cases, and you are asked to execute only one test case, which test case will you execute which will cover the main functionality.

Write the test cases for below logic.
i/p: string, strong
o/p: strng

You are given 2 strings: string, strong. Find the common alphabets in two strings and print it.
i/p: string , strong
o/p: strng

It is presidential election time.Mr X is fighting for the president.The country has N number of cities.
The cities are divided into developed & developing city on basis of a developemt index A.
If A is 1, then the city is developed. If A is 0, then the city is developing.
A close source to Mr X told that all the people from developing cities will vote for him while people
from only k number of developed cities will vote for him.
Find out the no of maximum vote in favour & minimum vote in against Mr X will get.

Input
------
10 3
0 12
0 6
0 7
1 8
1 12
1 17
1 20
1 22
1 5
1 6
First 2 line gives no of cities N= 10 & number of developed cities vote for Mr X k= 3
Next 10 lines give the development index A & number of people in the city
For example in the first line A= 0, no of people= 12

Write a function that returns true if the binary representation of an integer is a palindrome.

9 = 1001 = palindrome
8 = 1000 = not palindrome

Password Suggestor: Replace s with $ and a with @ and produce all password suggestions.
For Example: Password : P@ssword, P@$$word,pas$word etc..

Constructing City
In a country the cities are connected through roads of 3 types 1, 2, 3.
All the roads are bi-directional. The roads of a city has some restriction.
Road of type 3: both men and women can walk
Road of type 2: only women can walk
Road of type 1: only men can walk
Now the govt. wants to remove extra roads.But the cities should be connected for both men & women.
Connected means one should able to reach from one city to other & vice-versa.
Find out the maximum no of roads can be removed so that the cities can be accessible to both men & women.
Input:
5 5
1 2 3
2 3 3
3 4 3
5 3 2
5 4 1
First line gives no of cities & no of roads. Next each 5 lines gives city source, city destination, type for a roads.
5: no of cities 5: no of roads
1: city-1 2: city-2 3: type 3 road
o/p: 2

how does java implement priority queue?
i answered min heap, the interviewer seemed it was not right

Amazon SDE 2 On-site (4 of 4 Rounds)

Assume that there is an e-book application. For every book the sharable part of the book content cannot exceed 10% of the whole book. Design a module to decide whether the current part of content is sharable.

The description given is vague. I had to push him with questions to give the details.
At first I thought the problem was about strStr. But then the interviewer said that even if there are two paragraphs of the book content with the exact same texts, as long as they are not in the same place, they would be considered different content.
I then realized it’s a question about merging segments - have a helper to find each pair of start and end point of the input content (given multiple separated paragraphs). Then merge the intervals and see if they combined exceed 10% of the entire book.
The interviewer approved my solution and ask me to code it.

Overall I feel like that the Amazon SDE II Interview doesn’t focus on just algorithm. It’s more about problem solving in practice and then implement the only core function on whiteboard.

Perform an efficient DeepCopy of a linked list whose node is like below:

public class Node
{
	public int Value {get;set;}
	public Node Next{get;set;}
	public Node Random{get;set;}
}

The Random field points to any random node in the list.

Write code for the following: given a text file containing this information (Date the customer is logged in, tab, customer id)
04/11/2017 /t 0003
04/12/2017 /t 0003
04/13/2017 /t 0004
04/13/2017 /t 0003
How to get the list of those customers that log in on three consecutive days.

OOPS: How to design Amazon locker? Provide code using OOP

How to merge two binary trees in place? (without creating a new node)

You are given a rotated sorted array of size N. You have to search a given number into it.
Example: [4,6,8,14,90,-9,-2,0,3], Search -2.

Write a program which takes input a sorted array and positive number and updates the array so that if x appears m times in array then it appears exactly min(2,m) times in array. the update should be performed in one pass with no additional memory

What design pattern is used to implement a SynchronizedHashMap?

You are given an unsorted binary array.
Ex [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]
and a number K, which represents the number of swap operations allowed on this binary array.
you need to find out the maximum length continuous subarray that can be generated using K many swaps.
Ex if K = 3 in above case
[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]
so the answer is 9.

You are given a binary matrix whose each row is sorted. that means each row will have zeros at front and ones at the back. You need to find out the row which contains a maximum number of ones.
Ex :

[0 0 0 0 0 0 0 1 1 1 1 1]
[0 0 0 0 1 1 1 1 1 1 1 1]
[0 0 0 0 0 0 1 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 1 1 1]
[0 0 0 0 0 0 0 1 1 1 1 1]
[0 0 0 0 1 1 1 1 1 1 1 1]

Ans : second row and sixth with 8 ones. you will print [2,8] and [6,8];

Update : Required complexity O(M+N) + O(1) only.

Design a system to monitor services (like when they were down/ CPU time) etc.