CareerCup

You

Given multiple tuples in the form of (A,B) where A is the parent and B is the child in a binary tree, find if the input is valid or not. 4 error conditions were provided:
1. If a parent has more than 2 children,
2. If duplicate tuples entered,
3. If the tree has a cycle,
4. If more than one root possible.

For violation of multiple validity conditions, print the condition coming first in the above order.
If the input is valid, print the tree in a serial representation. For eg: If input is (A,B), (B,C), (A,D), (C,E) , output: (A(B(C(E)))(D))

How would you tell whether a graph has a node with n degree??
tell your approach

Given max. travel distance and forward and backward route list, return pair of ids of forward and backward routes that optimally utilized the max travel distance.:

eg: max travel distance is : 11000
forward route list : [1,3000],[2,5000],[3,4000],[4,10000]
backward route list : [1,2000],[2,3000],[3,4000]

Result : [2,3] ...2 is from forward and 3 is from backward...total distance is 9000...no other combination is there which is >9000 and <=11,000.......0(n^2) solution is straight forward, thinking that sorting both might help.

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Given a room with thief on left side of the room with finite number of sensors. He has to reach on right side missing the sensors. Each sensor is placed at any random point in the room and has its coverage in the radius r. Find out if the thief can reach to the right side without touching the range of any sensor.?

please discuss approach first & then code it..

Amazon delivery services find shortest path
Given x^2 + y^2 will give you the distance and coordinate can be nagative
int[,] allLocations=new int[,] { { 1, 3 },{1,2 },{3,4 } };
var x=Closestdestinations(3, allLocations, 1);

public static List<List<int>> Closestdestinations(int numDestinations,
int[,] allLocations,
int numDeliveries)

Design an email client where you can only send emails to people who are present in your contact list. Build for only the following functionaliy
1) Send/Receive Emails
2) Add/Remove Contacts
3) See Inbox
4) See Sent Mail

Design a distributed LRU Cache.

What would be the sample class design of notification system?

What would be the sample class design of tic tac toe game?

What would be the sample class design of Outlook like meeting scheduler?

There are 3 threads. 1 is producer thread. 2 consumer threads. There is 1 buffer. Producer writes to the buffer. Consumers consume from buffer. How to synchronise between them so that consumers consume from buffer one after another, that is, the number of tokens that consumer thread1 consumes is same as number of tokens consumer thread2 consumes. Answer in c,linux

What is the best way to generate first N primes? (not primes up to N but first N primes)

How do find out the top trendings products on a last hour/day/monthly basis?

Given that we have access to a real-time stream of sold product ids.

Design Amazon prime video

How is code review done?

How is design review done?

Given an alphabet where we do not know the order of the letters also do not know the number of letters.

We are give an input list of tuples where each entry in the list gives an ordering between the 2 letters

Determine the alphabet order.

Ex-
<A, B>
<C, D>
<C, E>
<D, E>
<A, C>
<B, C>
Order is A, B, C, D, E

Imagine a horizontal corridor bounded by y = y1 and y = y2 lines on a 2D-plane. There are N sensors with centers (x, y) each of which operates in a range (r) on the plane . So, they cover some circular areas on the plane. See the figure below.

o            |
_____o___o__|____________ y = y1
		o	|OOO
__________oo|_____O______ y = y2
	O		|  O
_ _ _ _ _ _ | _ _ _ _ _ _
			|
	o O		|		o O
		O	|
			|
O			|
			|

The question is whether a path exist from x=-inf to x=+inf via corridor without being detected any radar.

Constraints:
1. You are free to move any direction only if you stay in the corridor.
2. You are free to go through corridor borders.
3. N sensors are given as list of (x, y, r) like [(1, 3, 2), (-1, -3, 4)]. x and y are signed integers. r is a unsigned integer.
4. y1 and y2 are integers.

My solution:
1. Create an intersection graph of N sensors by comparing them each other via Euclidean distance

(x1 - x2)^2 + (y1 - y2)^2 <= (r1 + r2)^2

2. If there is a path between y=y1 and y=y2 through intersected sensors, there do not exist any path from x=-inf to x=+inf. Otherwise, there do exist a path. So, I used BFS to search such a path.

Worst Case Complexity:
1. O(n^2)
2. O(V + E) = O(n + intersection_count)

Total: O(n^2)

My Best Case Optimization for Intersection Graph:
1. For each sensor, create two events for start and end of circles vertically. y = (y1 - r) and y = (y1 + r)
2. For each sensor, register those two events into an array.
3. Use a line sweep algorithm over 2, which is O(nlogn + intersection_count) and intersection_count may be n^2 at worst case.

I wonder if I should have had a better solution with the worst case < O(n^2).

Longest increasing subsequence, Number of Island, Basic SQL questions like joins, select statement etc, Code for finding the Name in the document. Like based on the property of name (which cannot be written in small case). Find its frequency.

Design online movie ticket system. Hardware and software capabilities, improvements etc

A number of islands. All the rounds had basic DB questions

Basic DB questions like joins, aggregations, primary keys etc

Number of islands. Big(O).

In the doc file the "Name" without any dictionary. Like finding the property of the name as Starts with the capital letter. Then find the frequency of only names present in the doc. Whiteboard coding

Longest Increasing Subsequence

Online movie ticket booking system design

Design a system to forward 20% of your requests to cloud datacenter and rest to onprem data center. comsider you are fwd api.

Design S3 file storage system.