CareerCup

The grid is n by m. Each cell contains a unique number on it. Maga is at the left-top and wants to go to right-bottom. But there is a condition. Maga can go through only two way - right and down. And the path of your move is called the nodes you have passed through over them. The path is called the most beautiful if the following condition is satisfied: The sorted of the path has to be lexicographic smallest as possible as. Output the most beautiful path for given grid.
Input:
In the first line you are given two numbers: the dimensions of grid - n and m. The next n lines contains m numbers. Each number is unique.
Output:
Output the most beautiful path.

4 2
3 1

Return 1 2 4
There are 2 ways to reach at (2,2) cell. The pathes are 4, 3, 1 or 4, 2, 1 respectively. So The most beautiful of them is 4, 2, 1 because if looking the sorted of them it looks like these : 1, 3, 4 and 1, 2, 4 respectively. So 1, 2, 4 is lexicographic smaller than the other. So the ans is 1 2 4.

Two binary tree, to determine whether the two trees "similar", similar refers to the corresponding node in each tree in the left child and right child can be the same or in the opposite order, such as the following two trees, D, E where DE And DE can also be DE and ED, BC is the same, but the parent child relationship must be the same.
Followup is if left and right can be the same how to do,

A
   / \
  B C
/ \
D E

    A
  / \
C  B
     / \
     D E

given n player competition, a bool canbeat (int a, int b) can return a whether beat b. Asked to return a sequence, the sequence only requires two adjacent to the front beat behind. Example, 1 beat 2, 2 beat 3, 3 beat 4, 3 beat 1, 4 beat 1 You can return "1234", that is, although 3,4 can beat 1, but not adjacent does not matter

Give a two-dimensional array, which represents the value of the jump to the four directions, asked whether from the upper left corner to the lower right corner, follow up the shortest distance

To A and B two list, B is A shuffle obtained, find the mapping used shuffle,
To be able to handle duplicate elements.
Follow-up: Requirements space O (1),

list, push is pushed to the head, pop return each element with the same probability. If you push a sorted list into it, how to pop a sorted list out. Follow-up, asked if pop is from head, and push each element with the same probability in any position, how pop a sorted list out?

Determines whether two strings containing backspace keys are the same.

A car can receive two instructions A and R. A moves forward for a second and then doubles in speed. R stopped and then reversed. Given a String composed of AR, find where will the car stop.
Follow-up, given the location if the final stop, find the instruction string.

class EncodingChecker {
EncodingChecker (String pattern) {...} // constructor
boolean isEncoded (String s) {...} // for any string s, check whether s is encoded from pattern, see below
}

pattern = 'abcabc'
s = '123123' -> True
= 'cbzabc' -> False
= 'xyzxyz' -> True

Second question: If the pattern is not one but one million, how to write isEncoded?

Define a flight class, the flight has four attributes start, end, start time and arrival time,
There is also a list of strings, represents there is a crew member on that site.
given a list of flights, along with the list of strings mentioned above, asking if the flight crew availability is available for all flights.

example: flight 1 {A, B, 3, 10}, flight 2 {A, C, 1, 7}, flight 3 {C, D, 9, 11} crew member list {"A", "A"} Then return true because flight 3 can take off as flight 1 and flight 2 take off first, then flight 2 descends to bring flight crew A to C.
If flight 3 is {C, D, 6, 12} then return false because no flight crew member is in C at time 6.

You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start at root, but need to end at a leaf, and it must go downwards (traveling only from parent nodes to child nodes).
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
}
}

Give a bunch of rectangles, randomly return a point within the rectangle, the probability to be proportional to the size of the rectangle.
Follow up1: If you want to repeatedly call the function to generate random points how to do.
Follow up2: If the rectangles overlap how to do?

Given an extremely large file that contains parenthesis, how would you say that the parenthesis are balanced?

The file cannot fit in the memory. How would you process the file and how would you store the intermediate results.

Walk me through the entire algorithm.

Examples: 
{[()]}, {[](){}}, [] are some valid examples.

Given a matrix of each element is the height of the location, the side of the matrix has a river height h, water diffuse matrix results,
Follow up If there is a place where there is not drowning a person and a dog, people want to reach the dog's position without water, the river is highly uncertain,
Ask the maximum height h such that the number of steps taken by a person is less than or equal to a given k. Traverse the height h,

Question: Given a sorted integer array, return sum of array so that each element is unique by adding some numbers to duplicate elements so that sum of unique elements is minimum.

I.e., if all elements in the array are unique, return the sum. If some elements are duplicates, then increment them to make sure all elements are unique so that the sum of these unique elements is minimum.

Some examples:

input1[] = { 2, 3, 4, 5 } => return 19 = 2+3+4+5 (all elements are unique, so just add them up)
input2[] = { 1, 2, 2 } => return 6 = 1+2+3 (index 2 is duplicate, so increment it)
input3[] = { 2, 2, 4, 5 } => return 14 = 2+3+4+5 (index 1 is duplicate, so increment it)

given two strings a and b.
print out the minimum number of flips of the characters in a such
that a is an anagram of b.

JSON parsing is an essential toolkit in modern web development. Whether you are on the client side or server side, these methods need to be fast, efficient and dependable. But what if one day...
Suddenly, all of the JSON parser libraries went missing.
You have been called upon to save us all from impending doom.
Please re-implement the standard json parsing methods in your favorite language and restore the world to it's natural order.

Subproblem #1
Write a function, dictionaryToJson to convert a dictionary into a string.
For example, assuming you have dictionary like: dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)), the key field is always a string type, the value field could be a string type or a nested dictionary type. And the output would be "{a:apple,b:{b:blueberry,c:cranberry}}"

Subproblem #2
Write a reverse function, jsonToDictionary to convert a string into a dictionary.
Convert a string into the dictionary. e.g., given the input of “{a:apple,b:{b:blueberry,c:cranberry}}”, output dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)).
The names and values only contains letters. You can assume that there is no error in the input. You should not use regular expressions.

To a binary array, if you want to move 1 to the array side, 0 to the other side, Can only swap two adjacent elements each time, ask the least number of swap Why? For example, the number of min swaps for [0, 1, 1, 0, 0] is 2 (01100 -> 10100 -> 11000)

balanceSum, return to the array to meet the minimum sum equal to the minimum index. Title conditions are all positive numbers, the array length> = 3, there must be solution. If a = [1,2,1,3] returns 3 because a [1] + a [2] = a [4]

Give a string that outputs the largest alphabetical order of all consecutive substrings For example, "ab", substring has {"a", "ab", "b"}, output "b"

stream reading number, with timestamp, Design data structure to know the minimum value of the past year, the average,

sorting nested dictionaries
give a
{b: {cb: cranberry, bb: blueberry} a: apple, c: cherry}

{a: apple, b: {bb: blueberry, cb: cranberry}, c: cherry}

To sort the key output, if there is nested dictionaries, but also to sort

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.