CareerCup

There is a set, there are some balls, different balls have different weights, for example: [red ball 4, yellow ball 1, green ball 2, blue ball 2]
Ask for the first k-weight combination in this case, if k is 5 then:.
[Red, yellow, green, blue] 9
[Red, green, blue] 8
[Red, yellow, green] 7
[Red, yellow, blue] 7
[Red, Blue] 6 (or [Red, Green])

Consider there is a streaming service, which outputs Log object to your service. The Log object has fields like {timeStamp, userId, hashtag(used in the tweet), @userAddressUsedInTweet} etc. Imagine this streaming service has very high QPS. Design your service in such a way that it can output top K userId's within a configurable time window(example: last 1 hour, last 24 hour etc). This service should be extendable to get any top K category (Example: TopK userId's, TopK hashtags etc). What would you use to design such a service. Top K is defined by its frequency, example: 1,2,3,4,1,2,1,2,1,1,5 are the userIDs then the top 2 users are userId 1 and 2.

@EdgeCase:
1. Take into consideration how to store data in that window to get the topK user's.
2. The service should be highly available and should return the results quickly
3. Design and implement this service

Question:
* Implement a program which receives tasks, which are basically objects with "run()" method and
* a long field, where long field indicates the time after which the task should start running
* by calling the run() method

EdgeCases:
* Imagine a case, where (A,10) task A is scheduled to run after 10 seconds
* and then when at 3rd second, another task B comes where (B,2) seconds
* then which one would be executed first ?

input: words [['google', 30], ['gogle', '20'], ...]
queries [['go, le'], ...]
output: [30, .....]
The query is suffix and prefix, giving the maximum match.

N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

C * R 2-D array, there are R, G, B, Y four types of elements, if no vertical and horizontal has three adjacent elements are the same type, then the 2-D array is valid
Let write a function to determine whether a 2-D array is valid.


follow-up how to generate such a valid 2-D array

There are W white beans in the jar, R red beans. Random touch a bean. Touch white beans to eat directly. Touch red beans, put back, touch a bean, whether it is red, eat. Ask the last bean is the probability of white beans.

Give an Node {
              Node getLeft ();
              Node getRight ();
              String toString ();
}
Give a root node Node root
           *
         /   \
        +     -
       /  \    /  \
      1   2   3   4
Return (1 + 2) * (3-4)

If (1 + 2) + (3 + 4) does not need to be bracketed
Only leaf nodes are numbers

 
followup
Give you * + 12-34 to return this tree

Given a function randBetween (double d1, double d2), return a random double between d1 and d2,
returns a random point in a rectangle.
Give a bunch of rectangles, using randBetween to print a random point in the rectangle
follow up: What to do if you call this func many times

The two arrays [1,2,3,4,5], [2,3,4,5,6] find the first subfix and the second prefix the same longest case, such as the example is [2, 3,4,5]
Length of 4.
Followup: how to do two-dimensional array, how to optimize.

Given Two string, ask whether they can become the same after just one swap of two chars in one string.
For example:
"abcd", "bacd" Yes, you can swap ab in the first string to make it the same as the second string
"abcd", "adbc" can not

Follow-up, given Two string, ask whether they can become the same after N swaps of two chars in one string g, assuming that the swap does not overlap.
(str [0] <-> str [2] str [2] and str [0] will not be swapped with other locations)

An art museum has the shape of a square and it contains N*N rooms. Some of the rooms are open and they contain art, other rooms are locked. There are guards in some of the open rooms. The museum's administration is afraid of a break in and they would like to evaluate how well the guards are positioned in the open rooms inside the museum. Precisely, they wish to know for each open room what is the distance to the colest guard. This distance is the min number of rooms a guard needs to pass through to reach that room. The guards can only move through the open rooms North, South, East and West and they can't leave the museum.

'.' is for open room 'G' is for open room where a guard is '#' is for a locked room Noboday can enter or pass through thesse rooms.

There is a ball on the nth stairs, and it wants to get to the ground(level 0). There are some sticky stairs, and once the ball lands on the sticky stair, it is stuck and can never move.
During odd turns, you can jump down 1, 2, or 4 stairs. During even turns, you can jump down 1, 3, 4 stairs.
Return the number of ways you can get to ground.

You are in the upper left corner, sitting in a boat, you want to reach to the lower right corner, but the matrix has a certain height at each location (i, j), and the boat can only go through the cell with water in it, looking for the earliest time that the boat can reach from the upper left corner coordinates (0,0) to the lower right coordinates (n-1, n-1). Each day, water goes up by one height unit

Choose a random point from one single rectangle.
Choose a random point from multiple rectangles, if there isno overlapping among them.
Choose a random point from multiple rectangles, if there isoverlapping among them.

Given a string of size n consisting of 0s and/or 1s.you have to perform k queries and there are two types of queries possible.

"1"(without quotes): Print length of the longest substring with all '1'.
"2 X"(without quotes): where X is an Integer between 1 to n.In this query, you will change character at Xth position to '1' (it is possible that the character at ith position was already '1')
Input Format:

First Line of input contains n and k, where n is string length and k is the number of queries.
Next line contains a string of 0's and/or 1's of length n.
Each of next k lines contains query of any one type (i.e 1 or 2).
Output Format: For each query of type 1, print in new line the maximum size of subarray with all 1's.

Example Input:
5 7
00000
1
2 3
1
2 5
1
2 4
1
Example Output:
0
1
1
3

given a html file, compare if two html file show the same contents.
Eg.
<html> <body> <p> H <i> ello </ i> </ p> <body> </ html> is typed as "Hello \ n" without regard to <i> , "\ n" because of <p>

follow up: what if the string is very long

given a binary matrix of 01s, each time you click a point (i, j), the bit of the same row and column are all flipped.
check if a matrix can be all 0s after many of this operation.

design a sweeping robot, there are three functions:
move (), which returns boolean value
turn_left (k), which make robot turns left k times.
turn_right (k), which make robot turns right k times.
Design an algorithm to make robot clean up all room. Timecomplexity, linear in term of room space.

Given a graph, each node may have one or more children, updating the value of a child node is not less than the parent node.
follow-up each child node may have one or more parent nodes,

Given a function that returns 0 and 1 with a probability of fifty percent, use this function to generate a random number between a and b with uniform distribution

Judge if two arrays has the same pattern,
The definition is the relative relationship between each number and other numbers are the same, such as 132, 354, the first number is less than the second, the first less than the third, the second is greater than the third,
So is the same,
132,352 is not the same, because the first 132 is less than the third, the first 352 is greater than the second,
follow up, the array may concern duplicates

A city bus station information, example, bus No. 1 stops at abcd station, bus No. 2 stops at cefg station. Then a-d you only need to take No. 1, thus return 1, a-g is 2, because you need to transfer at station c,
ask for a minimum bus you need to take to reach to another station. You can design any data structures.

The topic is to design a data structure to store employee relationships.

For example, A is B's direct manager, there is an operation is "" set_manager "," A "," B ">.


For example, B is a colleague of C <"set_peer", "B", "C">

At this point, we do this with <query_manager "," A "," B "> and we get True, which means that A is B's manager (either direct or indirect).

This is true if we have <"query_manager", "A", "C">, because C is a coworker for B, so A is also C's manager. That is, there is a transitive relationship between colleagues.

Follow up, such as query <"query_manager", "A", "D"> (D this person has not been initialized), what to do. Conflict how to do
For example, A is a direct manager of B, E is a direct manager of C, which is set_peer (B, C), there will be conflicts, B and C direct manager should be the same person,
E and A are two people, there are contradictions here.

given a dictionary, output the longest List <String>. The result of a String is the previous String add a character at any position.
example: {i, in, ing, sing, sting, string}

Find a “local minimum” in a binary tree

a local min is a node whose value is smaller than that of any other nodes that are connected to it

1. merge intervals with value
PD: there are a series of continuous intervals, and each interval has a value. Initially, the ith
interval is (i - 1, i - 1), merge these intervals and return the result.
Merge Rule:
a. We can only merge the ith interval with i-1 th or i + 1 interval. The value of new interval is the
mean of these two original intervals.
b. Define cost as absolute difference of two neighboring intervals,
every time merge two intervals with the smallest cost.
c. If the smallest cost exceeds a threshold t, then stop.
d. There may be multiple valid result, just return one.
for example:
value: 3 7 6 5 1
intervals: (0,0) (1,1) (2,2) (3,3) (4,4)
threshold: t = 2
first iteration:
min cost = |7 - 6| = 1, notice that |6 - 5| is also okay.
after merging:
value: 3 6.5 5 1
intervals: (0,0) (1,2) (3,3) (4,4)
second iteration:
min cost = |6.5 - 5| = 0.5
after merging:
value: 3 5.75 1
intervals: (0,0) (1,3) (4,4)
second iteration:
min cost = |3 - 5.75| = 2.75 > t = 2, stop
return [(0,0), (1,3), (4,4)]

Give all n cities the distance between them, and then you have to follow all the cities in the order of small to large index of the city, which means you must visit the cities in ascending order, and now you can choose not to visit k cities (k < n), ask choose not to go to which k cities can make the path shortest? Return the shortest journey.
int findShortestPath(int[][] matrix, int k){
}

Generate a random MxN starting board. It cannot have 3 or more pieces in a
row (horizontally or vertically) of the same color. K colors.

Implement a rate limiter attribute/decoration/annotation on top of an API endpoint. caps to N requests per minute with a rolling window (implement from scratch / test / compiling + working code. Was made to write the code in front of a computer.