CareerCup

If xi<xj,yi<yj, we say (xj,yj)dominates(xi,yi). Given a set of number pairs (xi,yi),
how many indomitable pairs are there?

Mark likes to listen to music while travelling. His iPod™ contains
N songs and he wants to listen to L (not necessarily different) songs during
a trip. So he creates a playlist such that:
• Every song is played at least once.
• A song can be played again only if at least K other songs have been played

Mark wants to know how many different playlists are possible. Can you help Mark determine this number?

As the number can be very large,
display number modulo 1,000,000,007.

You are given N, K and L.

Given the width, height, start point, end point of the grid, and a list of points, you have to go through these points, ask how many paths are there from the start point to the end point, you can only move from (i, j) down and right.

The design of two functions, cyclecount (num, mod), cycleHistogram (low, high, mod). Probably, cyclecount (num, mod) do digits square sum mod operation. For example mod (12), mod (5) -> square (1) + square (2) mod 5 = 0 -> square (0) mod 5 = 0. Stop return 2. Finished digits square sum after take mod, mod and before the formation of a repetitive cycle. Return form the size before the cycle. CycleHistogram (low, high, mod) will give a [low, high]. Then return a histogram which stores the number of [low, high] inside the cycle size 1,2,3,4,5.

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