BIn Google coding interviews, you are expected not only to produce a correct solution, but also to justify its efficiency. Interviewers want to know whether your approach will scale for large inputs in systems such as Google Cloud log processing or config validation pipelines.
Explain how you would analyze the time complexity and space complexity of a coding solution.
Your answer should address:
Give a practical interview-style explanation rather than a purely mathematical one. You should be able to walk through a small code example, derive its runtime step by step, and explain common mistakes such as adding complexities incorrectly or ignoring hidden memory costs.
Big-O describes how runtime or memory usage grows as input size increases. In interviews, the goal is usually to identify the dominant term and ignore constants and lower-order terms.
for i in range(n):
print(i) # O(n) time
When code blocks run one after another, their costs are added. When one loop runs inside another, their costs are multiplied because the inner work repeats for each outer iteration.
for i in range(n):
pass
for j in range(n):
pass # O(n) + O(n) = O(n)
for i in range(n):
for j in range(n):
pass # O(n^2)
Recursive analysis requires counting both the number of subproblems and the work done per call. Space complexity must also include the maximum recursion depth because each active call uses stack memory.
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
Space complexity usually refers to extra memory beyond the input itself. Temporary arrays, hash maps, queues, and recursion stacks all count as auxiliary space.
seen = set() # Extra memory grows with input size
Some operations are occasionally expensive but cheap on average over many operations. Dynamic arrays and hash tables often use amortized analysis, which is acceptable to mention in interviews when relevant.
arr.append(x) # Typically O(1) amortized
