# Google Intern Interview

## Procedure

* Two technical interview, 45 mins each.
* Determine which team to work with. (pixel, ChromeOS, Nest...)

## Preparation

* Leetcode medium ~ hard ([Link](https://neetcode.io/practice))
* Chinese interview
* No IDE, use Google Doc

## Knowledge

Data Structures
- Arrays, Linked Lists
- Stacks, Queues
- Trees, Graphs
- Hash Maps

Algorithms/Techniques
- Searching, Sorting
- DFS, BFS
- Pointers
- Sliding Window
- Dynamic Programming
- Recursion
- Backtracking
- Greedy approaches

Knowledge
- Time and Space Complexity Analysis
- Control flow
- Basic Maths and Algebra and Probability/Statistics

## Tips

### DO NOT JUMP STRAIGHT INTO CODING

Ask clarifying questions to understand the question, narrow it down or gather additional information
This will help you consider the possible edge cases and even build tests around that
Talk through your code as you go along as your interviewer may not fully understand your implementation

### Discuss your solution with your interviewer
Briefly how you plan to approach the problem and go through your solution at a high level before you go into implementing it
Consider tradeoffs between multiple solutions (e.g. trading Space with Time Complexity)

### Think about ways to improve the solution you'll present
This may involve identifying bottlenecks, unnecessary or repeated work
e.g. if the data is arranged in a certain order, do we really need to iterate through ALL the elements? Are there any redundant steps?
e.g. recursive solutions often require multiple recalculations, can we cache the results somewhere using Memoization so the same calculations don’t need to be repeated?

## 1st Interview Question

### Original Question

There's an array *Numbers* and the elements in *Numbers* are in range [1, K]. Now given a lucky number *lucky*, please return the longest consecutive *lucky* in *Numbers*.

Input:

*Numbers*: [1, 2, 2, 3, 3, 3, 3, 2, 2, 2, 4, 1, 1]
*lucky*: 2

Output:

3 (the longest consecutive *lucky* has length 3)

Similar questions:

* https://leetcode.com/problems/max-consecutive-ones/

### 1st Follow Up

Now given a query *Q*, please find the longest consecutive sequence of each element in *Q* in *Numbers*.

Input:

*Numbers*: [1, 2, 2, 3, 3, 3, 3, 2, 2, 2, 4, 1, 1]
*Queries*: [1, 2, 3, 2]

Output:

[2, 3, 4, 3]

### 2nd Follow Up

Following the original questions. If you can modify at most *M* numbers in *Numbers*, what is the longest consecutive sequence of *lucky*?

Input:

*Numbers*: [3, 2, 2, 3, 3, 3, 3, 2, 2, 2, 4, 1, 1]
*lucky*: 3
*M*: 2

Output:

7 (modify index 1, 2)

Similar questions:

* https://leetcode.com/problems/max-consecutive-ones-iii/

### 3rd Follow Up

Now given *M* and queries *Q*, if we can modify at most *M* numbers in *Numbers* at each query.

## 2nd Interview Question

* English

### Original Description

Given a grid with obstacles. Please return *true* if a car can drive from it's initial position to a target position. The car can only move left, right, up, and down.

- '#': obstacles
- '-': roads
- 'a': initial position
- 'A': target position

Input:

\###
a-A

Output:

true

Input:

a#A
#-#

Output:

false

### Follow Up:

There are two cars and each of them has it's own initial position and target position. The cars move in turns. In each turn, a car can choose to move left, right, up, down, or don't move. Two cars can't stop at the same grid at the same time.

Input:

a-A
\###
b-B

Output:

true

Input:

a-B
-#-
b-A

Output:

true

Input:

###-
aBAb
###-

Output:

true

Input:

aBAB

Output:

false