In this post, I’m going to share a series of videos that will walk you through an interesting, real problem you’d get in a coding interview (e.g. an interview for any role that involves programming, like software engineer, software developer, data engineer, data scientist, machine learning engineer, etc.).
For this problem, we are given a “matrix” (it’s up to you to determine how that would be represented programmatically) containing only 0s and 1s. Each row is sorted. Your job is to write an algorithm that will find the row with the maximum number of ones.
The below video series discusses the problem in more detail, and goes through 3 different solutions, ranging from naive (and slow), to a bit better, to even better (i.e. fast).
These types of questions also typically involve “complexity analysis” (i.e. determining how long your algorithm takes as a function of the input size). The below videos will discuss that as well.
Check them out!
Approach #1:
Approach #1 in Python:
Approach #2:
Approach #2 in Python:
Approach #3:
Approach #3 in Python:
The notebook: