CareerCup

Given a sorted array which has been rotated n number of times. Find the value of n.

Clone the binary tree.

Return the maximum length sequence containing consecutive numbers from a binary tree.
90
/ \
1 66
/ \
2 67
/ \ /
5 4 68
/ \
99 100
Consecutive sequence of maximum length: [66, 67, 68] of length 3.

Implement Tower of Hanoi without using recursion.

A stepping number is defined as a number in which the absolute difference between the consecutive digits is not greater than 1, A stepping number cannot be a single digit number. You have to find the number of stepping numbers between n1 and n2 where n2 > n1 and n2, n1 > 0.

Given a stack of integers of size n, you have to sort it using only push and pop operations in O(1) space.

Given a tree return the number of elements for the level with the maximum elements.

Given an array it can be of 4 types
(a) Ascending
(b) Descending
(c) Ascending Rotated
(d) Descending Rotated

Find out which kind of array it is

Design a conference room booking system for a company which can have offices in multiple cities, each city can have multiple buildings, each building can have multiple floors, each floor can have multiple rooms. Each room can have features like capacitiy, video conferencing available, etc.

Design a kind of kindle fire application where we can subscribe news channel and read the news from all publishers as a digital format.

You are given a String S of length N. Now, a good subsequence is one that can be represented in the form (a raised to the power i) (b raised to the power j) (c raised to the power k) where i≥1, j≥1 and k≥1. For example ,if i=2, j=1, k=3, it represents the string aabccc. In short, a good subsequence is a subsequence that first consist of
i ′a′ characters, followed by j ′b′ characters, followed by k′c′ characters, where i≥1, j≥1 and k≥1

Now, you need to find the number of good subsequences of String S. As the number of such subsequences could be rather large, print the answer Modulo
(10 raised to the power 9) + 7.

Note: Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.

Input : abcabc

Output : 7

Explanation

Valid sub sequences are(1-based indexing):

{1,2,3}

{1,2,6}

{1,5,6}

{4,5,6}

{1,2,5,6}

{1,4,5,6}

{1,2,3,6}

I need to create a database that have five columns each entry is such that there can be repeated tuples in each column(No primary key).There will be no two same entries
There are 5 Methods that needs to be implemented
1. Create() - create the database
2. Add(string a,b,c,d,e) - Add single entries with 5 tuples(all strings)
3. Update (culumntype1, columnvalue1,culumntype2, columnvalue2)
- each entry having culumntype1 = columnvalue1 will be updated by columntype2=columnvalue2 and return total such eantries.
4. Delete (culumntype1, columnvalue1)
- each entry having culumntype1 = columnvalue1 will be deleted.and return total such eantries.
5. Search(culumntype1, columnvalue1)
- Search each entry having culumntype1 = columnvalue1 and return total such eantries.

How to implement in best possible way such that there can be 50,000 such entries?

how to create an object on the stack.
and also make sure that only 5 objects are created for the class

Design Amazon Recommendations Feature. Focus on designing how would you store and make it accessible fast? What would be class design like for the class which would provide list of products which people bought similar to a given product? How would you test that class?

Give a large multi MB byte file in memory, a system handles delete requests for segments typically of the order of bytes. The system has a constraint that individual purge requests of byte segments are expensive, so that the no. of purges are a minimum.

Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)

Effective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)

The users of the system always go by the absolute byte ordering of the file. Eg. if byte 1 is deleted, the users of the system will reference the actual byte 2 as byte 2.

What data structure would you use to store these intervals such that the following operations are efficient 1. Looking up an interval 2. Inserting a new interval that has no overlap with existing ones 3. Inserting a new interval that has partial overlaps with existing intervals. This would involve collapsing the existing intervals with the new interval to form a single large interval. Eg. Interval cache: {(1, 100), (250, 550), (1000, 1200)} , new interval : (400, 700) -> Interval cache: {(1,100), (250, 700), (1000, 1200)}

Given an mXn Sorted matrix and a value X. Every row is sorted and first number of every row is greater than last number of previous row Find the value X in most efficient way.

Given a Binary tree and value X. Find X in the tree and return its parent

X:

10
4 3
5 7 9 8

If X = 7, return 4

Given a list of list of positive integers, find all pairs of list which are having more than 3 elements overlapping.
What is the complexity.

Design OO food delivery app catering to use cases -
1) User can search different restaurant
2) User can select a restaurant
3) User sees a menu
4) Restaurant can change the menu any time
5) User adds an item from menu
6) User orders the food
7) User can track the order in real time
8) User can cancel the order
9) User pays for the order

Design food delivery app (OO design). Cater to use cases like search for different restaurants, selecting a restaurant, select an item from menu, menu can be updated in real time by restaurant, order the food, customer keeps track of the order in real time, payment for the order, cancel the order etc.

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?