Job preparationOptimisation
Optimisation and complexity interview questions
Time and space complexity, Big O notation, caching, memory leaks and parallel processing.
"It runs" does not satisfy a senior board. They want to know how fast it runs and how much memory it takes.
Big O is the shared language for that conversation. Without it the rest of your answers sound weaker than they are, so start here.
The questions
What is optimisation and why does it matter?
What to coverOptimisation means improving how well, how fast and how efficiently a program runs. It matters because it lowers resource use and improves the performance of the system.
What are time complexity and space complexity?
What to coverTime complexity measures how quickly an algorithm runs; space complexity measures how much memory it uses.
What is Big O notation and why is it used?
What to coverBig O is a way of expressing the time and space complexity of an algorithm. It is used to compare how efficient different algorithms are.
How do you analyse the time complexity of an algorithm?
What to coverBy working out the time complexity of each step and adding them together to get the total.
How would you optimise a program?
What to coverAnalyse its time and space complexity, use better-suited data structures and algorithms, unroll loops where it helps, and improve how memory is used.
What is a memory leak and how do you prevent one?
What to coverA memory leak is memory a program has used but never properly released. It is prevented through careful manual memory management, or by garbage collection.
What is dynamic programming and how does it help with optimisation?
What to coverDynamic programming solves a problem by reusing the solutions to its sub-problems. It helps because it removes the repeated work that would otherwise be redone.
What are caching and memoisation, and how do they work?
What to coverBoth store results that have already been computed, so the same computation does not have to be repeated later.
What is parallel processing and how does it improve performance?
What to coverParallel processing runs different parts of a program at the same time across several processors. It improves performance because it cuts the total time the work takes.
Which algorithm would you choose for a particular problem, and why?
What to coverThis depends on your experience and on the nature of the problem — but say what you weigh: how well the algorithm performs, its time and space complexity, and what it lets you optimise.
What tools or techniques do you use for code optimisation?
What to coverGive the method before the names: measure first, then change. For measuring — cProfile in Python, JProfiler or VisualVM in Java, gprof, perf or valgrind in C++, the browser DevTools and Lighthouse on the web, and EXPLAIN on a database. For technique — choosing the right data structure, caching and memoisation, database indexes, removing unnecessary loops and queries (the N+1 problem especially), and deferring or batching work where you can.
Tips for this round
- When you give a complexity, separate the best, worst and average cases.
- On optimisation, always say: measure first, then change. Optimising on a guess is the wrong method.