Here’s another hypothetical phone screen question that would be great if only boolean logic was a core part of my day job. I learned in school that one could build a computer from only NAND gates or NOR gates, but I never actually tried to build up logical operations from those primitives (maybe EE majors had to?). I tried it out and it wasn’t too difficult, making it perhaps a good question to ask as part of a larger interview if someone mentions facility with this sort of thing.

I started by defining a NAND gate and then built up NOT, AND, OR, and XOR operations.

def _nand(a, b):
  return not (a and b)

def _not(a):
  return _nand(a, a)

def _and(a, b):
  return _not(_nand(a, b))

def _or(a, b):
  return _nand(_not(a), _not(b))

def _xor(a, b):
  return _and(_or(a, b), _nand(a, b))

As an extension, I changed the NAND gate to a NOR gate and adapted my other operations accordingly. This turned out to require only small and regular tweaks, which I think makes for a good extension.

def _nor(a, b):
  return not (a or b)

def _not(a):
  return _nor(a, a)

def _or(a, b):
  return _not(_nor(a, b))

def _and(a, b):
  return _nor(_not(a), _not(b))

def _xor(a, b):
  return _and(_or(a, b), _not(_and(a, b)))

Finally, since we are dealing with boolean operations, everything can be exhaustively tested.

assert(_nand(True, True) is False)
assert(_nand(True, False) is True)
assert(_nand(False, True) is True)
assert(_nand(False, False) is True)

assert(_nor(True, True) is False)
assert(_nor(True, False) is False)
assert(_nor(False, True) is False)
assert(_nor(False, False) is True)

assert(_not(True) is False)
assert(_not(False) is True)

assert(_and(True, True) is True)
assert(_and(True, False) is False)
assert(_and(False, True) is False)
assert(_and(False, False) is False)

assert(_or(True, True) is True)
assert(_or(True, False) is True)
assert(_or(False, True) is True)
assert(_or(False, False) is False)

assert(_xor(True, False) is True)
assert(_xor(False, True) is True)
assert(_xor(True, True) is False)
assert(_xor(False, False) is False)