CareerCup

A startup website has a lot of real-time traffic . I want to see the real-time view (refreshed every 1 min) of top 20 users by hit count within last 10 mins. Full distributed system, I have to resolve all the concurrency issues.

I was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:

There's a list of (x,y) points and a method getCircle with the following signature:

/**
* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference
* or it returns null if no such circle is possible.
*/
Circle getCircle(point1, point2, point3);
getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.

The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?

There are cards and each card has an identity. e.g. HC1 has ID 1, this ID also represents the cost of the card. Your sister already have some cards and you want to gift her cards which she do not have already. Program is to return the max number of cards you can buy for her.

Constraint : You have amount d, and want to buy as many distinct card as you can.

e.g. Sister Cards = [2, 3, 5], D : 7 Card you buy : 1, 4

Output : 2

You have been given a special and normal status of alphabets.

e.g. “01111001111111111011111111” represents “abcdefghijklmnopqrstuvwxyz”. Here 0 represents normal character and 1 represents special character.

Given an Input String S and a number k, find the maximum continuous sub array with maximum k number of number elements. There is no constraint on special character.

e.g.

S = “giraffe”, K = 1, “011110011111111110111111”

Output : 3

How ?

normal characters : a, g, f

one of the possible solution : gir (as this has only one normal character)

Given a binary String which represents the target state. Minimum number of flips needed to convert a same size Binary String (with all 0’s) to target state. A flip also causes all the right bits to be flipped.

e.g.

Input : 00101 (Represents Target)

Output : 3

Explanation :

00000 -> 00111 -> 00100 -> 00101

N cows are standing at the origin on x-axis, each cow has some appetite, in other word hunger index. A cow can sleep of 1 unit of time or eat for one unit of time or move left or move right. There are some vessels placed on the x-axis, they are having infinite supply of fiod. Find minimum time in which all cows appetite would be filled.

Input:
cow Apetitte = {1,1}
Vessle locations = {-1,1}
Answer would be 2 since both cow can go in different direction they would eat for one seconds. One second for moving and one second for eating.

This problem looks to be similar to rotten eggs/tomatoes.

Design and implement rate limiter for limiting api calls for a service distributed multiple users.

Design data structures which support millions of products coming in streaming manner, we need to find at any moment what are top n products at any day

A dictionary is combination of characters from a-z. let's say a=1,b=2.. and so on z=26. you are given n and k. you have to find sum of length k from given combination.
for example n=51 and k=3 then your answer should be =axz
as there can be many combination for given sum so it is suggested to print those string which comes first in dictonary

beautiful numbers are those numbers which contains digit only 4 and 5 also they are palindrome.length of number can't be odd. for example
44,55,4554 are beautiful numbers where as 38, 444 are not.
your task is to find nth number in this series. let's say if n=4 then output should be 4554. for n=1 output will be 44 always.

There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to travel from Station i to Station j (1 ¥leq i, j ¥leq N)$. Note that di,j=dj,i may not hold.
You are now at Station 1. From here, you have to visit all the stations exactly once. We assume that you have already visited Station 1. However, due to your schedule, there are M restrictions that must be satisfied. The format of each restriction is as follows:
• Station si must be visited before Station ti. (1≤i≤M)
Find the minimum time required to visit all the stations. Note that the last station to visit can be any of the stations.
Constraints
• 1≤N≤14
• 0≤di,j≤108 (1≤i,j≤N)
• di,i=0 (1≤i≤N)
• 0≤M≤N(N−1)⁄2
• 1≤si,ti≤N (1≤i≤M)
• si≠ti (1≤i≤M)
• There exists a path visiting all the stations under the given restrictions.
Input
Input is given from Standard Input in the following format: N d1,1 … d1,N : dN,1 … dN,N M s1 t1 : sM tM
Output
Print the minimum time required to visit all the stations.
Sample Input 1
4
0 2 3 4
1 0 3 4
1 2 0 4
1 2 3 0
3
1 2
2 3
3 4
Sample Output 1
9
Due to the restrictions, we can only travel as follows: Station 1 → Station 2 → Station 3 → Station 4. Thus, the answer is 2+3+4=9 and we should print 9.
Sample Input 2
3
0 1 20
1 0 20
10 20 0
0
Sample Output 2
21

You are given an array of length N consisting of integers, a={a1,…,aN}, and an integer L.
Consider the following subproblem:
• You are given an integer S.
• Find the largest value in the interval [S,S+L−1] in the sequence a, that is, find max(aS,…,aS+L−1).
Solve this subproblem for every S=1,…,N−L+1.
Constraints
• 1≤N≤105
• 1≤L≤N
• −109≤ai≤109
Input
Input is given from Standard Input in the following format: N L a1 … aN
Output
Print the answers in N−L+1 lines. The i-th line should contain the answer to the subproblem where S=i.
Sample Input 1
5 3
3 4 2 1 5
Sample Output 1
4
4
5
• The subproblem where S=1 asks the largest value among a={a1,a2,a3}={3,4,2}, so the first line in the output should contain 4.
• The subproblem where S=2 asks the largest value among a={a2,a3,a4}={4,2,1}, so the second line in the output should contain 4.
• The subproblem where S=3 asks the largest value among a={a3,a4,a5}={2,1,5}, so the third line in the output should contain 5.
Sample Input 2
4 1
-1000000000 1000000000 -1000000000 1000000000
Sample Output 2
-1000000000
1000000000
-1000000000
1000000000

There are N rooms in a row. The i-th room (1≤i≤N) from the left is called Room i. You are given M closed intervals [ai,bi] (1≤i≤M). At time 0, all rooms j such that ai≤j≤bi for some i (1≤i≤M) are occupied, and the other rooms are vacant.
You are given Q queries. The i-th query (1≤i≤Q) represents an event happening at time i, as follows:
• In the i-th query (1≤i≤Q), a closed interval [ci,di] (1≤i≤Q) is given.
• This query asks: "Are all rooms j such that ci≤j≤ci" vacant?
• If all those rooms are vacant, the query should be responded by OK, then all rooms j such that ci≤j≤ci get occupied.
• Otherwise, the query should be responded by OK, then nothing happens.
Process these queries.
Constraints
• 1≤N≤109
• 0≤M≤1000
• 1≤ai≤bi≤N (1≤i≤M)
• There are no rooms k such that ai≤k≤bi and aj≤k≤bj at the same time (1≤i<j≤M).
• 1≤Q≤1000
• 1≤ci≤di≤N
Input
Input is given from Standard Input in the following format: N M a1 b1 : aM bM Q c1 d1 : cQ dQ
Output
Print the responses in Q lines. The i-th line should contain the response to the i-th query.
Sample Input 1
5 2
1 1
4 4
3
3 3
2 3
5 5
Sample Output 1
OK
NG
OK
At time 0, Room 1 and 4 are occupied.
• At time 1, a query asks: "is Room 3 occupied?" Since Room 3 is vacant, we should print OK, then Room 3 gets occupied.
• At time 2, a query asks: "are Room 2 and 3 occupied?" Since Room 3 is occupied, we should print NG.
• At time 3, a query asks: "is Room 5 occupied?" Since Room 5 is vacant, we should print OK, then Room 5 gets occupied.
Sample Input 2
1000000000 1
2 999999999
4
1 1000000000
500000000 500000000
1 1
1000000000 1000000000
Sample Output 2
NG
NG
OK
OK

You are given N records. The content of the i-th record is represented by a string Si. These records are managed in pages, as follows:
• The first page: contains the first, ..., K-th records.
• The second page: contains the (K+1)-th, ..., 2K-th records.
• The third page: contains the (2K+1)-th, ..., 3K-th records.
• :
• The ceil(N⁄K)-th page: contains the ((ceil(N⁄K)−1)K+1)-th, ..., N-th records.
Here, ceil(X) represents the smallest integer not less than X. Print the contents of the records contained in the M-th page, in the order given.
Constraints
• 1≤N≤100
• 1≤K≤N
• 1≤M≤ceil(N⁄K)
• 1≤|Si|≤100 (1≤i≤N), where |S| is the length of S.
• Si is a string consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N K M S1 S2 : SN
Output
Print the contents of the records contained in the M-th page, in the order given. Use L lines, where L is the number of records that should be printed. The i-th line (1≤i≤L) should contain the content of the i-th record contained in the M-th page.
Sample Input 1
5 2 2
aaa
bbb
ccc
ddd
eee
Sample Output 1
ccc
ddd
• The first page contains the first and second records, which are aaa and bbb.
• The second page contains the third and fourth records, which are ccc and ddd.
• The third page contains the fifth record, which is eee.
Since the second page is requested, we should print ccc in the first line and ddd in the second line.
Sample Input 2
7 4 2
this
is
not
displayed
this
is
displayed
Sample Output 2
this
is
displayed

Make a system that returns the average number of hits on the site per minute from the past 5 minutes

You're given an array of integers sorted ( [1,2,3,5,6,7,10]) you need to serialize and compress this array into a string (1-3, 5-7,10)

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).

Use synchronized, wait() and notify() to write a program such that below mentioned conditions are fulfilled while reading and writing data to a shared resource.

When a write is happening, no read or other write should be allowed(read and write threads should wait)

When a read is happening, no write should be allowed (write threads should wait) but. other read threads should be able to read.

Donot use any API classes e.g. ReadWriteLock, AtomicInteger etc..

Design election voting system. Election would be country wide. System should be scalable, available and consistent.

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.

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

Find LCA for list of nodes of a tree

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

Given two numbers m and n. Find all numbers between these two numbers such that difference between adjacent digit is 1
For ex m =0 n =22
O/p - 0,1,2,3,4,5,6,7,8,9,10,12,21

Code an algorithm for a game consisting of two players. The input is a positive integer x. Each round, a player deducts a perfect square from the number. The player can choose any perfect square as long as it is less than or equal to the current number and greater than 0. The current player wins if the number becomes 0 after his deduction.

P0, P1, ...., Pn players in tournament. In first level, P0 plays with P1, P2 plays with P3 and so on. In level 2, Winner of P0,P1 plays with winner of P2,P3. For i,j output level in which they will face each other assuming they win all games.

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's at depth 1, one 2 at depth 2.
Example 2:

Input: [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17.

Use the location data getting generated from multiple delivery boys moving on the ground to estimate time which a delivery boy will take to move from point A to point B in an area. Additionally, try to do this in real time so that it can be used in assigning delivery boys and minimising delivery time in real time.

In a binary tree if the neighbours are set on fire for every node , find the path to optimally set the entire tree on fire.

Given an input stream of Swiggy order timestamps and costs, at any instant find the costliest order in the last X mins