CareerCup

Given two points on a directed acyclic graph determine their least common ancestor, give it's time complexity, and describe any improvements you could make (if possible).

Given a binary matrix of 0 and 1 where we can move in 4 directions left, right, top, down and we can only pass through 1's. Find the shortest path from given source coordinate (a,b) to destination (m,n) given we can flip any one of the zero to one.

Given a list of sentences and a list of phrases. The task is to find which sentence(s) contain all the words in a phrase and for every phrase print the sentences number that contains the given phrase.
Constraint: A word cannot be a part of more than 10 sentences.
Examples:

Input:
Sentences:
1. Strings are an array of characters.
2. Sentences are an array of words.
Phrases:
1. an array of
2. sentences are strings
Output:
Phrase1 is present in sentences: 1,2
Phrase2 is present in sentences: None
Since each word in phrase 1 exists in both the sentences,
but all the words in second phrase do not exist in either.

You are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge. Your task is to find the shortest path from a to b satisfying the above condition.

You are given a n x m grid consisting of values 0 and 1. A value of 1 means that you can enter that cell and 0 implies that entry to that cell is not allowed. You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) such that you can only move in the right or down direction from every cell. Your task is to calculate the total number of ways of reaching the target.
Constraints :-
1<=n, m<=10, 000

There is a meeting scheduled in an office that lasts for time t and starts at time 0. In between the meeting there are n presentations whose start and end times are given i.e. the ith presentation starts at s[i] and ends at e[i]-1. The presentations do not overlap with each other. You are given k, the maximum number of presentations that you can reschedule keeping the original order intact. Note that the duration of the presentation can't be changed. You can only change the start and end time. Your task is to maximize the longest time period in which there is no presentation scheduled during the meeting.
Constraints :-
1<=t<=1, 000, 000, 000
0<=k<=n
1<=n<=100, 000
e[i]<=s[i+1], 0<=i <n-1
s[i] < e[i] for 0<=i<=n-1

Print numbers that matches with the index in given non-duplicate unordered array.

Write a program to encode a string from --> ABABXBYZXXX --> X4B3A2Y1Z1 (what should be the storage requirements for optimal conversion of 10TB file)

Suppose there is a function given to you that:

def get_friends( person_id ) { /*  returns friends of person */ }

How you are now going to recommend friends to a person based on number of mutual friends? So, come up with the function:

def friend_reco( person_id, max_no_of_friends ){ }

Given billions of Identity cards of the form :

card : {
   my_id : "my id",
   "moms_id" : "mom id",
   "dad_id" : "dads id"  
}

If one gives you two Person's id, how can you tell if these 2 persons are blood related.
So, write a function that is:

def is_blood_related( person_id_1, person_id_2 ) // go on..

Given an array of integers find the maximum value of a[i] - a[j] + a[k]
with constraints i < j < k and a[i] < a[j] < a[k]

You're running a pool of servers where the servers are
numbered sequentially starting from 1. Over time, any
given server might explode, in which case its server
number is made available for reuse. When a new
server is launched, it should be given the lowest available number.

Write a function which, given the list of currently
allocated server numbers, returns the number of the next server to allocate.

For example, your function should behave something like the following:

>> next_server_number([5, 3, 1])
2
>> next_server_number([5, 4, 1, 2])
3
>> next_server_number([3, 2, 1])
4
>> next_server_number([2, 3])
1
>> next_server_number([])
1

Server names consist of an alphabetic host type (e.g. "apibox") concatenated with the server number,
with server numbers allocated as before (so "apibox1",
"apibox2", etc. are valid hostnames).

Write a name tracking class with two operations,
allocate(host_type) and deallocate(hostname).
The former should reserve and return the next
available hostname, while the latter should release
that hostname back into the pool.

# For example:
#
# >> tracker = Tracker.new()
# >> tracker.allocate("apibox")
# "apibox1"
# >> tracker.allocate("apibox")
# "apibox2"
# >> tracker.deallocate("apibox1")
# nil
# >> tracker.allocate("apibox")
# "apibox1"
# >> tracker.allocate("sitebox")
# "sitebox1"

Write a map implementation with a get function that lets you retrieve the value of a key at a particular time.
t:0 A =1
t:2 A = 2
get(A, t:1) -> 1
get(A, t:3) -> 2

Implement following method of ScheduledExecutorService interface in Java

schedule(Runnable command, long delay, TimeUnit unit)
Creates and executes a one-shot action that becomes enabled after the given delay.

scheduleAtFixedRate(Runnable command, long initialDelay, long period, TimeUnit unit)
Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given period; that is executions will commence after initialDelay then initialDelay+period, then initialDelay + 2 * period, and so on.

scheduleWithFixedDelay(Runnable command, long initialDelay, long delay, TimeUnit unit)
Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given delay between the termination of one execution and the commencement of the next.

Implement a thread-safe data structure which can keep track of number of incoming
requests grouped by IP Address over a time window. Add support for grouping by other
attributes such as BrowserAgent.

Given a string select two non-overlapping strings that are same and remove them. Perform this operation recursively till there are no desired strings.
Print the number of possible substring after completing above operation.
Ex - abcc
Duplicate non-overlapping substring - abc
After removing abc from we are left with 1 substring abc.

In a 2-D matrix of m*n select m-1 elements from each row such that that the resulting sum is minimum and each column is selected atleast once.

Ex -
2 3 5
3 2 5
4 4 7
Selecting (2,3) from 1st row, (2,5) from 2nd row and (4,4) from 3rd row would result in minimum sum of 20

Question: Can you break the given string into words, provided by a given hashmap of frequency of word as <word: n>

Example:
HashMap -> {"abc":3, "ab":2, "abca":1}
String: abcabcabcabca
output: Yes; [ abc, abc, abc , abca ]

Example:
HashMap -> {"abc":3, "ab":2}
String: abcabab
output: No

Example:
HashMap -> {"abc":3, "ab":2, "abca":1}
String: abcx
output: No

Find LCA for list of nodes of a tree

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

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

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

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.

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.

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

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’]