Season 1: The Technical Interview Arc

Pretty accurate TLDR of my adventure.

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.

The Pre-Game:


Problem Link:

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

Prerequisites:

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

  • Dynamic Programming
  • 0–1 Knapsack

If not, here are some useful resources:

Problem Statement:

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.


Introduction:

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.

Definition and Examples:

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

  • For each pair of vertices, (u


Background Information:

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

Binary Search Trees:

A…


Why Use This?

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…

Jose Iciano

Computer Science Major at the University of Central Florida.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store