Can you measure 1ml of water using unmarked beakers of size 5ml and 7ml? Learn how to solve tech interview “measuring questions” using Bezout’s Lemma. Produced by TRM intern Shucheng Li.
We begin by filling and emptying the beakers until we arrive at a solution. By analysing what we have done, we are able to convert the problem into an algebraic equation known as a Linear Diophantine Equation. The solvability of Linear Diophantine Equations is then discussed by introducing the concept of “greatest common divisor” (GCD) and the definition of “co-prime”. A further application of Bezout’s Lemma to the Chinese Zodiac Calendar is explored by introducing the concepts of “leat common multiple” (LCM) and the ‘Chinese Remainder Theorem”.