CareerCup

AWS phone interview
Find the left view of binary tree
1
/ \
2 3
/\ \
4 5 6
/ /
7 8
/
9
return [1, 2, 4, 7, 9]

Given as list of movies in a csv file, extract the movie name and genre and be able to return a query based on the years and the genre.

Basically, Parsing a CSV input file and build an indexed data storage to allow search the data in time manner.

Given a list of tasks each with memory requirements and time, only one machine has K memory.
Do not consider the context switch, page swap, virtual memory, (for example, the machine has only 20mb memory, a task that requires 25MB of the task can only wait until there is enough memory to run it.) The running task cannot be suspended.
Ask how long it takes to complete all these tasks. . .

1) You sell roses. Each rose cost 30 cents to buy and you can sell them for $10 a dozen.
a) How many you need to sale to break even if you bought 600 roses?
b) Tomorrow is holiday - there's 20% likelihood you will sale 600 roses, 50% likelihood of selling 900 roses and 30% likelihood of selling 1200 roses. How many would you buy to maximize profit?

Write a method that can take in an unordered list of airport pairs visited during a trip, and return the list in order:

Unordered: ("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")
Ordered: ("ANC", "SEA"), ("SEA", "PDX"), ("PDX", "ITO"), ("ITO", "KOA"), ("KOA", "LGA"), ("LGA", "CDG")

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

Find the largest duplicate subtree in a binary tree


For example,

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
The following are two duplicate subtrees:

      2
     /
    4
and

    4

but the former is the largest, thus return the root of the first subtree

Given a target string, an input request replaces the word after the given index a->b such as:
Target string: "Hello world!"
Input:{s:0, a:Hello b: Goodbye}
Output:"Goodbye world!".
The requirement is that input be given to several words that need to be changed at one time: {{s:0,a:Hello,b:Goodbye},{s:11,a:!,b:?},{s:6 a: World,b:friend}}
And each modified index is based on the original unmodified target string so the end result is
"Goodbye friend?"

given a n-ary tree, find the total distance from this node to any other nodes

class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}


public int findDistance(TreeNode root, TreeNode node) {

}

How many squares are inside a m*n rectangle where some grids in the rectangle were grey and the gray grid could not appear in the small squares.

Given an int array, check if all the numbers can be divided into 5 consecutive numbers.
Eg: [1,2,2,3,3,4,4,5,5,6] Yes: (1,2,3,4,5) (2,3,4,5,6)
Followup: ask if you know that all the numbers are between 1 and 13,
what's a good optimization.

You have two matrixs, how to move the first matrix
(move up, down, left, and right) so that the two matrix in the two matrixs match most.

eg:
matrix 1:                matrix 2:
0 0 1                    0 0 0  
0 1 1                    1 1 0  
0 0 0                    1 1 0

Then, after taking matrix1 (1 left shift + 1 down),
the number of 1 in the match with matrix2 is 3

how to check if two graphs are structurally identical

class UndirectedGraphNode {

List<UndirectedGraphNode> neighbors;
UndirectedGraphNode() {
neighbors = new ArrayList<>();
}
}

convert a Sorted array to complete BST

Give a connected graph, no cycle,
Find the node where the average distance from all other nodes is the smallest

Input: an int array without sorting, then do a binary search on it, and find the number of digits that cannot be found by binary search.

<key = "a"; val = "3"; depend_list = null;/>; <key = "b"; val = "a * a";
Depend_list = {a};/>; <key = "c"; val = "a * b"; depend_list = {a,b};/>;
Lets output a map<key, value>,a -> 3, b -> 9, c -> 27
Follow-up questions: Make a statistic for all keys and corresponding map entries with the same value.

Given an array, find an x such that all numbers less than x are equal to themselves. Numbers greater than it are equal to x, and all numbers add up to a target
For example, [1 3 5 7 9] target=24, answer is8. Because when x=8, the array has only 9>8, so 1+3+5+7+8=24 is the closest to the target.

Give an N-length array with only 0 and 1 inside
Requires to find the minimum number of conversions needed to convert the array to 0 before all 1.
The conversion is to change a 0 to 1 or a 1 to 0,
And the number of 0 and 1 in the converted array can be arbitrary.
Just find the minimum conversion step

Imagine a horizontal corridor bounded by y = y1 and y = y2 lines on a 2D-plane. There are N sensors with centers (x, y) each of which operates in a range (r) on the plane . So, they cover some circular areas on the plane. See the figure below.

o            |
_____o___o__|____________ y = y1
		o	|OOO
__________oo|_____O______ y = y2
	O		|  O
_ _ _ _ _ _ | _ _ _ _ _ _
			|
	o O		|		o O
		O	|
			|
O			|
			|

The question is whether a path exist from x=-inf to x=+inf via corridor without being detected any radar.

Constraints:
1. You are free to move any direction only if you stay in the corridor.
2. You are free to go through corridor borders.
3. N sensors are given as list of (x, y, r) like [(1, 3, 2), (-1, -3, 4)]. x and y are signed integers. r is a unsigned integer.
4. y1 and y2 are integers.

My solution:
1. Create an intersection graph of N sensors by comparing them each other via Euclidean distance

(x1 - x2)^2 + (y1 - y2)^2 <= (r1 + r2)^2

2. If there is a path between y=y1 and y=y2 through intersected sensors, there do not exist any path from x=-inf to x=+inf. Otherwise, there do exist a path. So, I used BFS to search such a path.

Worst Case Complexity:
1. O(n^2)
2. O(V + E) = O(n + intersection_count)

Total: O(n^2)

My Best Case Optimization for Intersection Graph:
1. For each sensor, create two events for start and end of circles vertically. y = (y1 - r) and y = (y1 + r)
2. For each sensor, register those two events into an array.
3. Use a line sweep algorithm over 2, which is O(nlogn + intersection_count) and intersection_count may be n^2 at worst case.

I wonder if I should have had a better solution with the worst case < O(n^2).

Numbers with 4 are considered to be unlucky, floor numbers are skipped with numbers with 4; for a top level n, ask how many layers there are actually; for example n=20, that is 18 levels [Remove 4, 14]

I read this question here in careercup and saw no comments on it. So, I am answering it.
given a string find the sum of number of unique substring characters.
means if string is ACAX. the sub strings are A,C,A,X,AC,CA,AX,ACA,CAX,ACAX. in ACA, A occurs more than once so, its count is not considered, but C occurs once so its count is 1. Similarly in ACAX, A's count=0,C's count=1,X's count=1. In such a manner find sum of all counts for all substrings. The worst case time complexityis O(n). IF same substring occurs more than once then find its sum for that many times.

Input unsorted integer array represents a list of coins,
find the minimum amount of money that cannot be formed by these coins, each coin can only be used once
     E.g. {1,1} -> 3, {1,2,4} -> 8

Give me a list of int, find the length of the smallest cycle. For example, 1, 2, 1, 2, the length of the cycle is 2. Then 1, 2, 1, 2, 1 has a minimum length of 2. Then the length of 1, 2, 1, 2, 3 should be 5 because the entire list is not in repeat. Then the minimum length of 1, 2, 1, 2, 1, 1, 2 is 2.

Find the kth missing element in a sorted array. For example [2,3,5,7], k = 0: return 4, k = 1: return 6

expected time complexity logn

To an array and K, each element in the array can only move K positions to the left at most, no limit to the right, try to sort the array under the limit of K
a = [5, 2, 4, 3, 1], k = 2
Return [2, 3, 1, 4, 5]

Given a function rand32() (random number range 0-2**32-1) that randomly generates a 32-bit int, design a new random function:
Randn(n) generates a random distributed random number (0 - 2**n-1)
Rand3n(n) generates (0 - 3**n-1) the uniformly distributed random number

Topic: There is a set of coordinates. The original format of each coordinate is (1.3, 0.5). However, the comma and decimal point are gone. Only one string is left, allowing you to restore all possible combinations. For example, 123, possible (1, 23) (1, 2.3) (12, 3) (1.2, 3)

given period and threshold, Assume there is a endless streaming events, each event occurs at timestamp "x". The question want you to write an API that return true if number of the events are over the threshold within the period around timestamp "x"


Ex:
period = 3, threshold =2
getEvent(10) -> false
getEvent(12) -> false
getEvent(13) -> true [10,12,13]
getEvent(20) -> false


part one: event come in order
part two: event come without order

Given vector<int> nums, and pair<int, int> range. Find out how many continuous subsequences within this vector sum up the number within the range.

Input: [1, 2, 3], [3,6]
Output: (4)

because [1,2,3], [1,2], [2,3], [3]

Each have a (x,y) coordinate.
Write an API that group three Googler together for lunch if they are close enough. Otherwise, throw them in un-schedule pool.

Distance formula = sqrt((x1-x2) ^2 + (y1-y2) ^2)
Given an int range;

Range: 2
Input | Output of API Un-schedule pool
0,0 -> [] [[0,0]]
1,0 -> [] [[0,0], [1,0]]
3,0 -> [] [[0,0], [1,0], [3,0]]
1,1-> [[0,0], [1,0], [1,1]] [[3,0]]