This article is part 1 of me explaining my experiences with Google’s 2021 internship process. After writing it, I realized it was a lot longer than I thought so I figured it would be best to split it up. This was the first FANG internship I received, and the first internship that relied on a series of technical interviews.

At the time, I was a Junior interning at JPMC. At the time I never had a whiteboarding interview done, nor did I get many callbacks. To get my (then) internship, I had my interviews done at a hackathon. Being jealous…

https://leetcode.com/problems/last-stone-weight-ii/

This article (and problem) assumes you are familiar with the following concepts:

- Dynamic Programming
- 0–1 Knapsack

If not, here are some useful resources:

- https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
- https://youtu.be/xCbYmUPvc2Q
- https://www.thelearningpoint.net/computer-science/algorithms-dynamic-programming---the-integer-knapsack-problem

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose **any two rocks** and smash them together. Suppose the stones have weights `x`

and `y`

with `x <= y`

. The result of this smash is:

- If
`x == y`

, both stones are totally destroyed; - If
`x != y`

, the stone of weight`x`

is totally destroyed, and the stone of weight`y`

has new weight`y-x`

.

…

A question you may be asked when it comes to graph-theory related problems is if we can create two subgroups with each group-member having a relationship only with elements in the opposite group.

For example, we may be asked to create two teams such that each team-member likes their teammates and any rivals they have are on he other team.

When we are given such problems, it can be thought of as a bipartite graph problem.

A graph is bipartite if it can be split into two sets such that the following rule applies:

- For each pair of vertices, (
*u*…

To understand treaps, a basic understanding of a Binary Search Tree and Binary Heaps are necessary.

A tree is a data structure that has a root node that contains some value, as well as pointers to child nodes. A binary tree is a tree that is restricted to at most two children. A binary search tree builds upon this and has another property, the value of each parent node should always be greater than those in it’s left subtree, and less than those in the right subtree (equal values can go solely in the left or the right subtree).

A…

Any program can be represented as a function, f(n), where each term is some type of action. For example, f(n) = n² + 5n + 4 represents the following:

for (int i = 0; i < n; i++) { // O(n)

for (int j = 0; j < n; j++) { // O(n), makes this whole loop O(n^2)

}

}for (int i = 0; i < n; i++) { // O(n)

}int i = 1; // O(1)

i += 1; // O(1)

i += 1; // O(1)return i; // O(1)

By representing our program as a function…

Computer Science Major at the University of Central Florida.