CareerCup

Find LCA for list of nodes of a tree

Function defined as below -
TreeNode findLCA(TreeNode root, List<TreeNode> nodes)

Given a number n, make a set of m integers such that the integers lie between [1, n] 
and the sum of  two integers should produce an integer which is in the set.

Eg. **Input**
n=20, m=5
**Output**
[3, 6, 11, 14, 17]

Which test types we can use for drinks vending machine testing? Especially for check dimension, length, appearance of machine and cups?

A set of points in the 2D plane. Find the first k number of points with the shortest distance to the point (0, 0), where k is a positive integer.

e.g.
Input
{[-16, 5], [-1, 2], [4, 3], [10, -2], [0, 3], [-5, -9]}
k = 3

Output:
{[-1, 2], [0, 3], [4, 3]}
.

A matrix represents a sequence of travel points. One only can travel either left/right or up/down. Some of those points are dead points which one can't travel any further. There is a destination point in the matrix. Find the shortest path from the top left point (1, 1) to the destination.

e.g.
Input
[
[‘O’, ‘O’, ‘O’, ‘O’],
[‘D’, ‘O’, ‘D’, ‘O’],
[‘O’, ‘O’, ‘O’, ‘O’],
[‘X’, ‘D’, ‘D’, ‘O’],
]

Output
Route is (0, 0), (0, 1), (1, 1), (2, 1), (2, 0), (3, 0) The minimum route takes 5 steps.

I was asked to integrate linkedIn and dropbox. So linkedIn is not into file storage system, hence they want to use the services of dropbox. The goal is to create, update, delete the documents of a profile in linkedIn. But these documents will not be stored in linkedIn. They will be stored in dropbox.
Moreover, to get this integration, linkedIn does not want to scale up they system. This means, if they have 400 servers, they do not want to add any more servers to achieve the integration.
How can I design this?

Given a positive integer array and a positive integer. Find a pair of integers in the array so that the sum of the pair is the largest one among all pairs not larger than the given integer.

e.g.
Input
{90, 85, 75, 60, 120, 150, 125}
d: 250

Output:
{90, 125}

Design DB schema for maintaining e-commerce various category ,sub category ,sub-sub category and so on.

Write a program to find number of words in a file not using any standard tokenizing API's.

Given n, you will be getting stream of sets each set may contain like (1,3,4,5) which signifies that 1,3,4,5 are related. Similarly you may get like (6,7) , (1,8).
And you will be asked to find whether 1 & 4 are related => Yes (as they are from same set).
3 & 8 are related => yes as 8 & 3 are related through 1.
5 & 7 are related =>No

Card Game

Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.

Shopping Cart Programming test.
There are multiple types of customer(Regular, Premium) they have been given a discount based on their purchase amount. for e.x
Premium Customer
1) 0-$5000 0%
2) $5000-$10000 10%
3) 10000 - above 20%

Regular Customer
1) 0-$4000 10%
2) $4000 - $8000 15%
3) $8000 - $12000 20%
4) $12000 - above 25%

Read input from console:
Input:
Regular
$5000
Output:
$5000
Input:
Premium
$7000
Output
$8000

Implement a function which accepts a number and returns top 10 big numbers the function is called with so far;

If we call the function with 1.. to 100 , for the call function(100) the function will return 91 to 100 in reverse order since they are top 10 biggest number so far

Implement a fair mutex

An array is called a Good Array if the elements continually increasing or continually decreasing or continually decrease and then increase.
Question 1: He asked how will you tell whether a given array is a good array or not.
Question 2: Given an array, you are allowed to add any number of values to each of the element. Find the minimum sum of elements that can make the array a good array.

A software-based LRU Cache replacement algorithm has to be implemented for a Single Touch/Multi-Touch Cache. Single Touch can occupy at least 30% of the total cache space. A key accessed for the first time will appear in the Single Touch cache. When accessed multiple times, this will be part of the multi-touch cache. Also, multiple threads will access the cache. Following are the functions allowed for cache access.
1. get(key): returns the value against the key if present else return NULL
2. set(key, value): set the value against the key

Given a tree, and there will be treasure in one of the nodes. We can query any node, it will return the node itself if it contains the treasure or it returns the branch which leads to the treasure. we need to find out the treasure in minimum number of queries.

Design a jenkins kind of system

Imagine someone maliciously duplicated every file on your computer, and completely randomized their names and locations on your hard drive. Discuss an efficient way to clean up your drive of all these duplicates.

Two very very large files F1, F2 containing key, value pairs. Write these key, values to a third file without any duplicates.

Design real time tail log search

Build a key-value data structure that allows the user to take a snapshot of the data. The user can read the key-value store from any snapshot.

Structure has the normal key/value like methods plus something like
snapshot = dataStructure.takeSnapshot()
value = dataStructure.get(key, snapshot)
void dataStructure.deleteSnapshot()

A table has some number of balls at various positions on a line segment. All are moving with same speed in one or the other direction. Wherever a collision occurs they change direction. A ball falls from the edges of the table. Find the time when all balls fall of the table given initial position of each ball and speeds

Find the maximum number of concurrent sessions in the following data with the first value representing start time and last value end time. The input is not necessarily sorted.
Input: (2,5), (3,6), (8,10),(10,12),(9,20)
Output: 3 (from 8 to 20)
Input: (2,5), (3,6), (8,10),(9,12),(12,20)
Output: 2 (from 8 to 12 or 2 to 6)

Given a list L of video names and their watch rates, write a function that will return the videos with the top 10 watch rates. Video names may appear more than once.

Example:

L = [(‘abc’, 10), (‘def’, 15), (‘ghi’, 10), (‘abc’, 12), …, (‘xyz’, 100)]

The function should return [‘xyz’, ‘abc’, …, ‘def’, ‘ghi’]

Write a function that takes a list L and returns a random sublist of size N of that list. Assume that the indexes must be in increasing order. That is, you cannot go backwards.

Example:

L = [1, 2, 3, 4, 5]
N = 3

The function should return one of these lists:

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

Consider an undirected tree with N nodes, numbered from 1 to N. Each node has a label associated with it, which is an integer value. Different nodes can have the same label. Write a function that, given a zero indexed array A of length N, where A[j] is the label value of the (j + 1)-th node in the tree and a zero-indexed array E of length K = (N – 1) * 2 in which the edges of the tree are described, returns the length of the longest path such that all the nodes on that path have the same label. The length is the number of edges in that path.

Example:

A = [1, 1, 1, 2, 2]
E = [1, 2, 1, 3, 2, 4, 2, 5]

This tree is shown below. A node follows the form label, value.

----------1, 1

-----1, 2 1, 3

2, 4 2, 5
The function should return 2, because the longest path is 2->1->3, and there are 2 edges in this path.

Assume that 1 <= N <= 1000 and each element of the array A is an integer in the range [1, 1000000000].

Given a string A consisting of n characters and a string B consisting of m characters, write a function that will return the number of times A must be stated such that B is a substring of the repeated A. If B can never be a substring, return -1.

Example:
A = ‘abcd’
B = ‘cdabcdab’
The function should return 3 because after stating A 3 times, getting ‘abcdabcdabcd’, B is now a substring of A.

You can assume that n and m are integers in the range [1, 1000].

Given 1-D list of co-ordinates determine if interval (a,b) is covered

Ex - [(2,5), (5,7),(1,4)] and interval = (1,6)
return true
Explanation - Points 1 to 6 lies in list of interval given 1 to 4. 2 to 5 and 5 to 7.

[(1,4),(6,7),(2,5)] and interval - (1,6)
return false
Explanation - Distance between 5 to 6 is not covered in the list given so return false

Compare two documents(string array) based on n grams.
e.g doc1 – Today is Sunday.
doc2 – Today is Saturday
if n = 2 then number of duplicates is 1 (Today is)
if n = 1 then number of duplicates is (Today, is)
if n = 3 duplicates is 0