A Variation on Flipping Lightbulb Switches, pt. 1

by JT Cho

##Introduction Problem. Suppose you are in a room with $n$ lightbulbs and $k$ switches, where $1 \leq n$ and $1 \leq k$. Suppose that any particular switch turns a subset of light bulbs on. Find the minimum number of switches such that flipping them on turns on all of the . . .

Enumerating Binary Strings Without K-Runs of Ones

by JT Cho

Despite having studied mathematics and computer science for quite some time now, I am still amazed to this day at how the two fields can intersect in profound and unexpected ways. This post expounds upon one such case, examining how solving a seemingly simple enumeration problem algorithmically convolves interesting mathematical . . .

Longest Substring With Two Unique Characters

by JT Cho

In advance of the interview season coming in the latter half of the summer/early fall, I've begun my interview preparation. :) Here, I'll tackle the following: Problem. Given a string $S$, compute the length of the longest substring $S_{ij}$ that contains at most $2$ distinct characters. Example. "ab& . . .

Algorithms 4: Symmetry in Parentheses

by JT Cho

'Tis the season for interviews and career preparation. So without further ado, let's do a welcome back post! Problem. Given an input string $s$ of length $n$ containing only left and right parentheses, determine whether or not it is a valid parenthetical expression. By definition, a parenthetical expression is valid . . .

Algorithms 3 - Maximal Path Sum between Two Leaves

by JT Cho

For this week's algorithm post, we'll examine a recent exam problem I had for my algorithms class! I couldn't come up with a story for this one, though, sorry. :( n.b. I present here my refined solution from the exam. It got full credit, but alternative solutions do exist! Problem. . . .