CareerCup

Design Uber low level OO design. Cater to use cases like search for a ride, different category of rides, select a ride, registration for a user and driver, paying for ride etc.

Given a dictionary and an char array print all the valid words that are possible using char from the array.

Ex- char[] arr = {'e','o','b', 'a','m','g', 'l'}

Dict - {"go","bat","me","eat","goal", "boy", "run"}

Print - go, me, goal.

We can pre-compute as much we want but the query time must be optimal.

Given input which is vector of log entries of some online system each entry is something like (user_name, login_time, logout_time), come up with an algorithm with outputs number of users logged in the system at each time slot in the input, output should contain only the time slot which are in the input. For the example given below output should contain timeslots
[(1.2, 1), (3.1, 2), (4.5, 1), (6.7, 0), (8.9, 1), (10.3,0)]

/*
[
("Jane", 1.2, 4.5),
("Jin", 3.1, 6.7),
("June", 8.9, 10.3)
]

=>

[(1.2, 1), (3.1, 2), (4.5, 1), (6.7, 0), (8.9, 1), (10.3, 0)]

*/

How would you design Amazon Lockers?

Amazon Lockers - Customers can use these lockers to have their products delivered. These lockers are physically available to customers at the same or several nearby zip codes.

The amazon site was working just fine until yesterday. But in the past 24 hours processing the customer orders is taking a really long time.

How would you debug and fix the issue?

When I asked if anything had changed in the past 24 hours, I was told several new products had been added after which the performance issues were noticed.

Given the root of a Binary Tree along with two integer values. Assume that both integers are present in the tree.
Find the LCA (Least Common Ancestor) of the two nodes with values of the given integers.
2 pass solution is easy. You must solve this in a single pass.

You are given 2 lists -
List 1: List<Demand> is a list of Demand objects.
List 2: List<Supply> is a list of Supply objects.

Return a result fulfillment List<Demand,List<Supply>>.

This means each demand could be satisfied by more than one supplies.

class Demand
{
Date startDate;
Date expirationDate;
int quantity;
}

class Supply
{
Date startDate;
Date expirationDate;
int quantity;
}

The Demand and Supply refers to that of groceries. You must map supplies to a demand only if the supply still has at least 3 days remaining to its expiration before the demand can be fulfilled.
A demand is said to be fulfilled 24 hours after all demands have been mapped to correspondingly available supplies.

Given a string with only parenthesis. Check if the string is balanced.
ex -
1) "<({()})[]> is balanced
2) "<({([)})[]> is not balanced

Write code for the partition subroutine in Quicksort.

How would you Design a HashTable?
In what ways would you attempt to address collisions?

Given that an external service gives a list of credit cards that have become fraud, design a fraud management system for a shopping website for bookings with fraud credit cards

Given a list of shops each of which have a list of toys with their prices and max number of children who can play with it at a time. Output the a list of best possible toy option from each shop given the number of children who are shopping.

ToyShopping
{

getListOfBestToysFromEachShop(List<Shop> shops);

}

Shop
{
int id,
List<Toy> listOfToys;
}

Toy
{
int toyId;
int shopId;
int price;
int maxChildren; //max number of children who can play with this toy
}

Design the classes for a Battleship Game. Write the attack function.

Write a program to check whether it is a valid binary tree or not. Check all test cases (e.g. No left Node case).

Given (a,b) can you reach to (c,d) if a and b can move either (a+b,b) or (a,a+b). Example a =1, b=4,c=5,d=9 then (1,4) -> (5,4) -> (5,9)

Design a logging system. The system contains multiple application servers which are logging the information to file system. In this scenario, we want to check and alarm in case an exception is thrown in any of the servers. We want a system that checks for appearance of specific words, "Error", "Exception", "Disk Full" etc. in the logs of any of the servers. How would you design this system?
What if we want to scale the system in future?

We need a functionality to block an user who makes more than 10 requests in last 5 minutes. You need to implement the following function.
{{
boolean block_user(int user_id)
{
//TODO: return true in case u want to block user
}
}}

object oriented design for robot vacuum cleaner.
write use cases, draw class diagram and interfaces
between them.

Design a deck of cards that can be used for different card game applications.

Please code out what you would need for the deck class and a card class.

Implement a deal method.

Design a system for searching strings in files present on a fileserver under a directory. there won't be any sub-directories. There could be more than thousand/lakhs files. And the file size could be in GBs. The matching line should be written to a single file. user will execute grep "string"
The sub-questions are
1) Design where the application executes on single machine.
2) Design where the application can execute on multiple machine.
3) Where could be the potential bottleneck.
4) What component would be bottleneck if 50 cores and slow disk.
5) What component would be the bottleneck if we 4 cores and fast disks.

You have two very large numbers that cannot be stored in any available datatypes. How would you multiply them?
How would you multiply more than two numbers?

How will you implement a dictionary.

Design a monitoring system for hotel booking site. Proper oops design.

Given two strings, print all the inter-leavings of the Strings in which characters from two strings should be in same order as they were in original strings.

e.g.
for "abc", "de", print all of these:
adebc, abdec, adbce, deabc, dabce, etc, etc

Given a matrix of positive integers, you have to reach from the top left corner to the bottom right in minimum cost. You can only go one square right, down or diagonally right-down. Cost is the sum of squares you've covered. Return the minimum cost.
e.g.
4 5 6
1 2 3
0 1 2

Answer: 8 (4+1+0+1+2)

Find the length of maximum number of consecutive numbers jumbled up in an array.

e.g.: 1, 94, 93, 1000, 2, 92, 1001 should return 3 for 92, 93, 94

A program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35

This is a interview question which needs to be optimized for time.

Suppose you have a 2 dimensional Array and you have a String say "Amazon" inside the Array such that the individual characters can be present from Left to Right, Right to Left, Top to down and down to up.

I will explain with example :

char[][] a = {
{B,B,A,B,B,N},
{B,B,M,B,B,O},
{B,B,A,B,B,Z},
{N,O,Z,B,B,A},
{B,B,B,B,B,M},
{B,B,B,B,B,A}
};

The above Array has two Amazon Strings. You need to return the count of number of such strings present.

Find the height difference between two nodes in a binary tree.

1
	2		3
4	     5    6	     7
			8	  9
				10

For example: For a given tree above, what would be the height difference between node 4 and node 10?

Milly and Pranjul are playing a game in which Pranjul will give an index of a chocolate.
Then, Milly has to tell him the box number in which that chocolate is in. There are N
such boxes and Ci chocolates are there in ith the box. Description of index is given below
:
Suppose there are A1, A2 … AN chocolates in 1st, 2nd… Nth boxes respectively. So,
indexing of chocolates in 1st box will be from 1 to A1, similarly in 2nd box indexing will be
A1 + 1 to A2 … and indexing in Nth box will be from AN-1 + 1 to AN.
Milly is blind folded so she can’t see the boxes. You are required to help her.
Input
First line will contain N (No. of boxes). Next line will contain N space separated
integers denoting Ci, the number of chocolates in ith box.
Next line will contain Q (No. of times Pranjul will ask her). Then each next Q lines
will contain the asked index I.
Output
For every query, print in a new line : the box number in which that index of
chocolate is in.
Constraints
1 ≤ N, Q ≤ 105
1 ≤ Ci ≤ 10
1 ≤ Σ Ci ≤ 106
1 ≤ I ≤ Σ Ci