CareerCup

Given the following input:

Array: array of integer coordinates(x,y) of length N

return a integer M that represents the maximum number of points that falls within the same line.

Example:

Array: [ [0,0], [1,1], [3, 12] ]
Output: 2# [0,0] and [1,1] falls in the same line. [3,12] falls on a different line. Thus the maximum number of points that falls on the same line is 2

Given the following inputs:

Array: Array of positive non repetitive integers of length N.
K: Integers in range of [2,N)
Target: A Target integer

return any subset of Array with K elements that sums up to target.

Example:

Array: [1,2,3,4,5]
K: 2
T: 6
Output: [1,5]

Array: [1,2,3,4,5]
K: 3
T: 6
Output: [1,2,3]

Array: [1,2,3,4,5]
K: 4,
T: 11
Output: [1,2,3,5]

Implement multithreaded rm -r <folder>, i.e recursively delete files/folder under <folder> by walking through it and assume there can be billions of files under folder and you can only delete folder if all contents in it are first deleted

Given a matrix. Convert it into a linked list matrix such that each node is connected to its next right and down node.

Ex:
1 2 3
4 5 6
7 8 9

Output:
1->2->3->NULL
| | |
v v v
4->5->6->NULL
| | |
v v v
7->8->9->NULL
| | |
v v v
--NULL-

This is my code.

class Ideone
{
	public static void main(String args[]) throws Exception {
		int arr[][] = { { 1, 2, 3 }, 
				        { 4, 5, 6 } };
		LList op = convert2DArrintoList(arr, 0, 0);
		System.out.println(op);
	}
 
	public static LList convert2DArrintoList(int arr[][], int col, int row) {
		if (col >= arr[0].length || row >= arr.length)
			return null;
		return new LList(arr[row][col], convert2DArrintoList(arr, col, row + 1), convert2DArrintoList(arr, col + 1, row));
	}
 
	static class LList {
		LList(int data) {
			this.data = data;
		}
 
		LList(int data, LList down, LList next) {
			this.data = data;
			this.down = down;
			this.next = next;
		}
 
		LList() {
			this.data = Integer.MAX_VALUE;
		}
 
		@Override
		public String toString() {
			return " " + this.data + " ";
		}
 
		int data;
		LList next;
		LList prev;
		LList rand;
		LList down;
	}
}

Are there better ways of doing it?

Generate all possible matched parenthesis, given n left parenthesis and right parenthesis needs to be matched.

Create a data structure that stores integers, let then add, delete. It also should be be able to return the minimum diff value of the current integers.
That is,
min_diff = minimum ( | x_i - x_j | )
Example:

-1,3,4,10,11,11
min_diff = 0

-1,3,4,10,11,14
min_diff = 1

Solve the 24 Game

Round4
Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0

Round3
For N light bulbs, implement two methods
I. isOn(int i) - find if the ith bulb is on or off.
II. toggle(int start, int end)

Round1
Find if two people in a family tree are blood-related.

Round2
Given some nodes in a singly linked list, how many groups of consecutively connected nodes there is.
For linked list
0->1->2->3->4->5->6,
given nodes 1, 3, 5, 6
there are 3 groups [1], [3], and [5, 6].

Given a sorted array A, find how many subsets of A satisfies MIN(subset) + MAX(subset) < K.

count number of combinations which are not possible.
There are 'n' empty slots.
A slot can be filled with 'O', 'E', or 'X'
A combination is possible if
1. 'O' s are placed in odd slot , 'E' a are placed in even slots.
2. 'O' and 'E' alternate among them,
i.e (OXOE) not allowed because between O s there is no 'E'; but (OEXXO) is allowed.
some allowed combinations
OEXXX, XXOEO, OXXEX
For 3 slots, not allowed combinations are
OXX
XXO
XEX
XXX
OXO
Only those combinations are considered in which O s and E s are in their respective odd and even slots.
i.e EEXXX will never be considered because a 'E' is in odd slot
A combination isn't allowed if 'O' is not followed by 'E' or vice versa

Given a sorted distinct array of integers and a key K. C closest elements to K are in range [L,R] inclusive, L<=R. Return L as the left index of C closest elements to K.
For example:
A = [1, 2, 5, 8, 9, 13]. K = 8 and C = 4. The result L = 3 because 4 closest elements to 8 are [5, 8, 9, 13]

Given a tree print in level zig-zag order.

Example suppose we have the given tree structure:
     1
    2 3
  4 5 6

it should print: 1 3 2 4 5 6 

First level prints left to right.
Then next level prints right to left.
Alternating for each level.

Assume the following node structure:
Node { 
  data: Integer,
  left: Node,
  right: Node,
  parent: Node,
}

Round 5:
Given a set of synonyms such as (fast, quick), (fast, speedy), (learn, study), decides if two sentences were synonymous.
(The sentences were structurally the same and has the same number of words in them.
The synonymous relation [fast ~ quick] and [fast ~ speedy] does not necessarily mean [quick ~ speedy].)

Follow-up:
If the synonymous relation passes down so that [fast ~ quick] and [fast ~ speedy] implies [quick ~ speedy], decide if two sentences were synonymous.

Round 4:
Implement a class Employment with these 3 methods: assignManager(p1, p2): assign p1 as p2's manager. beColleague(p1, p2): make p1 and p2 peer colleagues. isManager((p1, p2): decide if p1 is the manager of p2.

Round 3
Given a matrix of 0s and 1s where 0 is wall and 1 is pathway, print the shortest path from the first row to the last row.
Can walk to the left, top, right, bottom at any given spot.

Follow-up:
If every pathway takes a cost (positive integer) to get through, print the minimum cost path from the first row to the last row.

Google on-site June
Round 1
Leetcode 10

Round 2
Select a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).

Follow-up: Given multiple non-overlapped rectangles on the 2D grid, uniformly select a random point from the rectangles.

Check if any number is sum of any two numbers in array of length n
Example: [40,90,50] -> check -> true (90 = 40 + 50)
Example: [1,2,4] -> check -> false( A_x != A_y + A_z)

Compress String with character and its count.
Example: "aaabbba" -> compress -> "a3b3a1”

We have to merge a set of Intervals.How to decide if to sort them on start or end time? Which one is better to sort based on start or end time?

Phone Interview Amazon, Seattle
I. Get the sum of all prime numbers up to N. primeSum(N).
Follow-up: If primeSum(N) is frequently called, how to optimize it.

II. OODesign Parking Lot

Apple Map Team
1. Given an array A and some queries, query(i, j) returns the result of Ai*...*Aj, in other words the multiplication from Ai to Aj.
The numbers in A are non-negative.
Implement query(i, j).

2. Flatten nested linked list

3. POI search design

4. LC238 & LC279

Airbnb Interview

Min cost of flight from start to end if allowed at most k transfers.
Given all the flights in a string:
A->B,100,
B->C,100,
A->C,500,
If k = 1，from A to C the best route is A->B->C at the cost of 200.

You are given an old touch smartphone numbers having dial pad and calculator app.


Aim: The goal is to type a number on dialpad.

But as phone is old, some of the numbers and some operations can't be touched.
For eg. 2,3,5,9 keys are not responding , i.e you cannot use them
But you can always make a number using other numbers and operations in Calculator. There could be multiple ways of making a number

.Calculator have 1-9 and +,-,*,/,= as operations. Once you have made the number in Calculator you can copy the number and use it.

You have to find minimum number to touches required to obtain a number.


#Input:#
There will be multiple Test cases .Each test case will consist of 4 lines
1) First line will consist of N,M,O
N: no of keys working in Dialpad (out of 0,1,2,3,4,5,6,7,8,9)
M:types of operations supported (+,-,*,/)
O: Max no of touches allowed

2) second line of input contains the digits that are working e.g 0,2,3,4,6.
3) Third line contains the valued describing operations, 1(+),2(-),3(*),4(/)

4) fourth line contains the number that we want to make .

#Output:#
Output contains 1 line printing the number of touches required to make the number


#Sample Test Case:#
1 // No of test cases
5 3 5 // N ,M, O
1 2 4 6 0 // digits that are working (total number of digits = N),
1 2 3 // describing operations allowed (1--> '+', 2--> '-', 3--> '*' , 4--> '/' )(total number is equals to M)
5 // number we want to make


Answer 3
How 4? 1+4= , "=" is also counted as a touch



2nd Sample Case
3 // No of Test cases
6 4 5 // N ,M, O
1 2 4 6 9 8 // digits that are working (total number of digits = N),
1 2 3 4 // describing operations allowed (1--> +, 2--> -, 3--> , 4-->/)
91 // number we want to make
6 2 4 // 2nd test case
0 1 3 5 7 9
1 2 4 // +, -, / allowed here
28
5 2 10
1 2 6 7 8
2 3 // -, allowed
981

#Output:#
2 // 91 can be made by directly entering 91 as 1,9 digits are working, so only 2 operations
5// 35-7=, other ways are 1+3*7=
9//62*16-11=


Order for computation will be followed as symbols entered, if + comes, it will be computed first


One more example: lets say 1,4,6,7,8,9 works and +,-,* works.
2,3,5 and / doesn't work.
If you have to type 18-> 2 operations. (Each touch is considered an operation),br> If you have to type 5 -> '1+4=' that requires 4 operations. There could be other ways to make '5'.

Apple phone interview

Given an API to find all IPv4 addresses in a log file, find all IPs that occurred only once.

Follow-up: What if the log comes from a data stream.

Follow-up: If the machine has 4GB RAM, is there going to be a problem?

The memmove() function copies n bytes from memory area src to memory area dest. The memory areas may overlap: copying takes place as though the bytes in src are first copied into a temporary array that does not overlap src or dest, and the bytes are then copied from the temporary array to dest.

Suppose there are N number of clusters, B number of machines and number of tasks in clusters are stored in an array named a. The goal is to minimize the single most overloaded machine and every cluster must be given at least one machine. Output should be one integer representing the number of the tasks in the busiest machine (rounded up).

1<=N<=500000
N<=B<=2000000
1<=ai<=5000000

for example, N=2,B=7, a=[200,450], output should be 100.

Any ideas?

Thanks

4/5 Round at Uber
Coding: Given a 2D array of either '\' or '/', find out how many pieces this rectangle is divided into graphically.
For a 2X2 matrix with
/\
\/
The matrix split into 5 pieces - the diamond in middle and the four corners. Return 5 as the answer.


5/5 Round at Uber
Design Excel.

2/5 Round at Uber
Bar raiser - Behavioral questions. Coding: Find if a set of meetings overlap. Meeting has a starttime and an endtime with accuracy to minute. All meetings take place in the same day. Do this in O(n) time.

3/5 Round at Uber
Coding: Subset sum. Follow-up: Optimize the solution.