Skip to content
BoKSA

Programming Foundations

Programming Foundations

Use this page to revise the computer-science fundamentals that sit underneath any language or framework: how a program is executed, and how to reason about its efficiency.

Compiler, interpreter, JIT

  • A compiler translates source code into machine code (or another lower-level form) before the program runs.
  • An interpreter reads and executes source code line by line, while the program runs.
  • A JIT (just-in-time) compiler is a hybrid: it starts interpreting, but compiles the "hot" parts of the code to machine code as it runs, to get speed closer to a compiled language.

Memory: stack vs. heap, and garbage collection

  • The stack holds short-lived, fixed-size data (like local variables and function call information) and is managed automatically as functions are called and return.
  • The heap holds data whose size or lifetime isn't known upfront, and needs explicit or automatic management.
  • A garbage collector automatically frees heap memory that's no longer reachable from the running program, so you don't have to manage it by hand — but understanding that it exists explains a whole category of "why did that get slow / why is memory growing" questions.

Modules

Recognising modules (or components, or layers) in an existing codebase — a "user module", an "order module", a "database layer" — is a reading skill: most codebases are organised into named, purpose-specific chunks, and being able to name them is the first step to understanding how a system fits together.

Big O notation

Big O notation describes how the time (or memory) a piece of code needs grows as its input grows:

  • O(1) — constant time, regardless of input size.
  • O(n) — time grows linearly with input size.
  • O(log n) — time grows very slowly as input grows (e.g. binary search).
  • O(n log n) — typical of efficient sorting algorithms.

Data structures and their typical operations

  • Arrays/lists — fast indexing (O(1)), but inserting/deleting in the middle is slower (O(n)).
  • Maps/dictionaries — fast lookup and insertion (close to O(1)) by key.
  • Trees — search and insert typically O(log n) if balanced.

Searching and sorting

Linear search checks every item one by one (O(n)); binary search repeatedly halves a sorted list to find an item much faster (O(log n)) — but only works if the data is sorted first. Simple sorts (bubble, selection, insertion) are easy to understand but slow for large inputs (roughly O(n²)); merge sort and quicksort are more efficient (O(n log n)) and used in practice for larger datasets.

Starting Points

Key Points

  • You can explain the difference between a compiler, an interpreter, and a JIT compiler.
  • You can distinguish stack and heap memory, and explain what a garbage collector does.
  • You can identify modules or layers in an existing codebase.
  • You can explain Big O notation (O(1), O(n), O(log n), O(n log n)) in plain language.
  • You can name the typical complexity of common operations on arrays, maps, and trees.
  • You can explain the difference between linear and binary search, and when each applies.
  • You can name at least one simple sort and one more efficient sort, and roughly why the efficient one scales better.