Trade-off time vs space trong coding interview thường biểu hiện thế nào?

Quy luật quen thuộc: muốn nhanh hơn thì thường phải tốn thêm bộ nhớ, và ngược lại.

Ví dụ điển hình là HashMap — đổi O(n) space để biến lookup từ O(n) xuống O(1), giúp Two Sum từ O(n²) còn O(n).

• Hay precompute/prefix sum: tốn O(n) bộ nhớ lưu tổng tích lũy để mỗi truy vấn range sum chỉ còn O(1).
• Chiều ngược lại: bài cần O(1) space buộc bạn xử lý in-place hoặc dùng two pointers thay vì tạo cấu trúc phụ.
• Khi trình bày, hãy nói rõ bạn đang đánh đổi cái gì lấy cái gì và vì sao nó hợp với constraint của đề (ví dụ memory limit chặt thì ưu tiên space).