Software Engineer

Phỏng vấn Software Engineer tại Công ty G: Codility, LRU Cache và bài toán System Design không rõ scope

Experience này có một điểm khá thú vị: hai vòng technical kiểm tra hai loại năng lực rất khác nhau.

Round 1 là bài toán execution under time pressure — đọc đề, code nhanh và thích nghi với một coding environment không quen thuộc.

Round 2 lại là bài toán problem framing — trước khi design, candidate phải xác định được chính xác mình đang design cái gì.

Và trong System Design interview, đôi khi bước "đề bài là gì?" quan trọng không kém bước "solution là gì?".

---

1. HR Screening

HR liên hệ trong khoảng 30 phút.

Nội dung chủ yếu xoay quanh:

• Khả năng giao tiếp bằng tiếng Anh.
• Expected salary.

Sau bước này, candidate đi tiếp vào technical interview.

---

2. Round 1 — 2 bài coding trong 50 phút

15 phút đầu dành cho introduction và trao đổi về work experience.

50 phút còn lại là coding với 2 bài:

1. N-ary Tree.
2. LRU Cache.

Điểm đáng chú ý nhất không nằm ở hai bài toán, mà nằm ở coding environment.

Codility không giống LeetCode

Candidate đã quen với format của LeetCode nên gặp một chút friction khi chuyển sang Codility.

Trên LeetCode, thông thường candidate đã có:

• Function signature.
• Input/output abstraction.
• Test cases.
• Code execution environment.
• Một số constraint được trình bày khá rõ.
• Có thể chạy thử solution trực tiếp với các testcase.

Trong experience này, Codility chỉ cung cấp một file gần như trống với main function.

Điều đó có nghĩa candidate phải tự xử lý nhiều thứ hơn:

• Đọc input.
• Xác định cách tổ chức chương trình.
• Tạo data structure cần thiết.
• Tự nghĩ testcase.
• Tự kiểm tra output.
• Sau đó mới tập trung hoàn toàn vào algorithm.

Với một candidate đã quen LeetCode, đây có thể là một context-switch cost không nhỏ trong một bài interview bị giới hạn thời gian.

Candidate chia sẻ rằng đã mất khoảng 30 phút cho bài đầu tiên, một phần vì chưa quen với format.

Sau đó bài LRU Cache được implement nhưng tổng thời gian bị vượt khoảng 5 phút.

---

3. Bài 1 — N-ary Tree

Bài đầu tiên được nhớ lại là một bài tính tổng từ một node trên N-ary Tree.

Wording chính xác của đề không còn được candidate nhớ đầy đủ, vì vậy phần này không nên xem là transcript nguyên văn.

Về mặt algorithm, nếu requirement là tính tổng toàn bộ subtree bắt đầu từ một node, cách tiếp cận tự nhiên là traversal:

• DFS.
• Hoặc BFS.

Với DFS, ta có thể:

1. Bắt đầu từ node được chỉ định.
2. Cộng giá trị của node hiện tại.
3. Duyệt toàn bộ children.
4. Cộng tiếp kết quả từ từng subtree.

Nếu có N node trong subtree cần duyệt:

Time complexity: O(N)

Space complexity: O(H) với recursive DFS, trong đó H là chiều cao của tree; hoặc có thể lên tới O(N) nếu sử dụng explicit stack/queue trong trường hợp tree có shape đặc biệt.

Điểm quan trọng trong interview không nhất thiết nằm ở việc bài này khó.

Challenge thực tế của candidate lại là:

Thời gian bị tiêu tốn khi chuyển từ LeetCode-style environment sang một coding environment ít abstraction hơn.

Đây là một distinction khá quan trọng.

---

4. Bài 2 — LRU Cache

LRU Cache là một bài data structure kinh điển vì nó kiểm tra khả năng kết hợp nhiều cấu trúc dữ liệu để đạt complexity yêu cầu.

Một implementation kinh điển sử dụng:

• Hash Map.
• Doubly Linked List.

Hash Map dùng để tìm node theo key trong O(1) average.

Doubly Linked List duy trì thứ tự:

Most Recently Used → ... → Least Recently Used

Khi gọi get(key):

• Tìm node trong Hash Map.
• Nếu tồn tại, đưa node lên đầu list.
• Trả về value.

Khi gọi put(key, value):

• Nếu key đã tồn tại, update value và đưa node lên đầu.
• Nếu key mới, thêm node vào đầu.
• Nếu vượt capacity, remove node cuối cùng — chính là Least Recently Used.

Nhờ đó:

• get() → O(1) average.
• put() → O(1) average.

Đây là lý do LRU Cache xuất hiện rất nhiều trong technical interview.

Nó không chỉ kiểm tra khả năng code Hash Map.

Candidate phải hiểu data structure composition:

Hash Map giải quyết lookup.

Doubly Linked List giải quyết ordering và removal/insertion.

---

5. Follow-up: Race Condition trong LRU Cache

Follow-up đáng chú ý:

How do you prevent race access when using LRU Cache?

Đây là lúc bài coding chuyển sang production thinking.

Một LRU Cache implementation đơn giản có thể đúng trong single-threaded environment nhưng không còn an toàn khi nhiều thread cùng truy cập.

Ví dụ:

Thread A:

get(A)

Thread B:

put(B)

Cả hai có thể đồng thời modify linked list.

Nếu không có synchronization phù hợp, có thể xảy ra:

• Lost update.
• Corrupted linked-list pointers.
• Hai thread cùng evict / modify một node.
• Inconsistent Hash Map và Linked List state.
• Race condition.

Một approach phổ biến: Mutex

Có thể bảo vệ các operation thay đổi shared state bằng mutex.

Ví dụ về mặt concept:

get() → lock → lookup + move node → unlock

put() → lock → update map + list → unlock

Như vậy, tại một thời điểm chỉ một thread được phép modify critical section.

Tuy nhiên, câu trả lời tốt không nên dừng ở:

"Dùng mutex."

Interviewer có thể hỏi tiếp:

• Lock toàn bộ cache có gây contention không?
• get() có thực sự cần exclusive lock không?
• Có thể dùng read/write lock không?
• Nếu cache có throughput rất cao thì sao?
• Có thể shard cache thành nhiều segments không?
• Thread-safe implementation có làm thay đổi performance profile không?

Đây chính là điểm mà một bài LRU Cache từ algorithm question trở thành engineering question.

---

6. Một nuance quan trọng: Thread-safe không đồng nghĩa với "càng nhiều lock càng tốt"

Nếu toàn bộ cache được bảo vệ bằng một global mutex, implementation đơn giản và dễ reason hơn.

Nhưng khi concurrent access tăng cao, global lock có thể trở thành bottleneck.

Một hướng khác là partition/sharding:

Cache → Shard 1 / Shard 2 / Shard 3 / ...

Mỗi shard có:

• Hash Map riêng.
• LRU list riêng.
• Lock riêng.

Khi key được phân phối tương đối đều, các operation trên những shard khác nhau có thể giảm contention.

Đương nhiên, đây không phải lúc nào cũng là solution tốt hơn.

Trade-off xuất hiện:

• Complexity tăng.
• Global LRU semantics trở nên khó hơn.
• Memory overhead tăng.
• Hot key vẫn có thể tạo contention tại một shard.

Vì vậy, trong interview, câu trả lời mạnh thường không chỉ là:

"Dùng sharding."

Mà là:

"Nếu workload thực sự bị contention ở global lock, tôi mới cân nhắc sharding; còn nếu cache nhỏ và throughput không cao, mutex đơn giản có thể là lựa chọn dễ maintain hơn."

---

7. Round 2 — System Design

Round 2 là phần mà candidate gặp khó khăn nhất.

Theo experience được chia sẻ, candidate không xác định được interviewer muốn design system nào.

Candidate đã chủ động hỏi thêm và cố gắng clarify requirement, nhưng cảm nhận rằng expectation giữa hai phía không khớp.

Kết quả cuối cùng là:

Fail Round 2.

Điểm này đáng chú ý vì System Design interview không chỉ kiểm tra kiến thức architecture.

Nó còn kiểm tra một kỹ năng rất quan trọng:

Problem framing.

---

8. System Design không bắt đầu bằng Architecture Diagram

Một lỗi dễ gặp khi bước vào System Design là lập tức nghĩ đến:

• Load Balancer.
• API Gateway.
• Kafka.
• Redis.
• Database.
• Kubernetes.
• Microservices.

Nhưng trước tất cả những thứ đó phải có một câu hỏi đơn giản:

Exactly what problem are we solving?

Nếu chưa xác định được requirement, architecture diagram rất dễ trở thành một collection của những technology quen thuộc.

Một cách tiếp cận có cấu trúc hơn là bắt đầu bằng:

Step 1 — Clarify the goal

"Could you clarify what exactly we are trying to build?"

Step 2 — Identify users / actors

• Who uses the system?
• Client là ai?
• Internal service hay external customer?

Step 3 — Identify core use cases

• User cần làm gì?
• API nào là critical?
• Read hay write heavy?

Step 4 — Quantify scale

• Requests per second?
• Number of users?
• Data volume?
• Traffic peak?
• Expected growth?

Step 5 — Define constraints

• Latency requirement?
• Availability?
• Consistency?
• Security?
• Cost?
• Data retention?

Step 6 — Confirm scope

Một câu rất hữu ích:

"Let me confirm the scope before I start designing."

Sau đó repeat lại problem bằng lời của mình.

Ví dụ:

"So, if I understand correctly, we're designing an order management system for X users, with Y QPS, where the main requirement is Z. Is that correct?"

Nếu interviewer xác nhận, lúc đó mới bắt đầu architecture.

---

9. Khi interviewer không đưa requirement rõ ràng

Đây là một situation khó vì candidate có thể rơi vào hai thái cực.

Quá ít hỏi

Candidate tự assume toàn bộ requirement.

Sau 10 phút design, interviewer mới nói:

"That's not what I meant."

Hỏi quá lâu

Candidate liên tục hỏi clarification nhưng không đưa ra assumption hoặc direction nào.

Khi đó interview có thể mất nhiều thời gian mà chưa thể hiện được system design skill.

Một approach cân bằng hơn là:

Clarify → State assumptions → Start designing → Validate assumptions.

Ví dụ:

"I'll make a few assumptions so we can move forward. If any of them are incorrect, please correct me."

Đây là một kỹ thuật rất hữu ích trong System Design interview.

Nó biến ambiguity thành một phần của conversation thay vì chờ interviewer cung cấp một specification hoàn chỉnh.

---

10. System Design cũng là Communication

Experience này cho thấy một insight quan trọng:

Biết System Design và làm tốt System Design interview là hai chuyện có liên quan nhưng không hoàn toàn giống nhau.

Trong production, engineer thường nhận một requirement chưa hoàn hảo.

Engineer phải:

• Hỏi đúng câu hỏi.
• Xác định ambiguity.
• Đưa ra assumption.
• Ưu tiên requirement.
• Đề xuất solution.
• Giải thích trade-off.
• Điều chỉnh solution khi stakeholder thay đổi requirement.

System Design interview mô phỏng khá nhiều phần trong workflow đó.

Vì vậy, khi interviewer đưa một đề bài chưa rõ, việc candidate phản ứng với ambiguity cũng có thể trở thành một phần của assessment.

Tuy nhiên, trong experience này, candidate cảm nhận rằng expectation giữa hai phía không được align, nên không thể xác định chính xác nguyên nhân technical nào dẫn đến outcome ngoài việc candidate đã fail Round 2.

---

11. Điều đáng học từ experience này

Experience này có hai lesson rất khác nhau.

Lesson 1 — Đừng chỉ luyện LeetCode, hãy luyện coding environment

Nếu đã quen LeetCode, nên thử code trong environment gần với interview thực tế:

• File trống.
• Không có test case.
• Tự viết input.
• Tự viết output.
• Tự tạo test cases.
• Tự compile / run.
• Tự debug.

Bởi vì trong interview, vài phút đầu tiên để hiểu environment cũng là interview time.

Lesson 2 — System Design phải luyện cả problem framing

Một candidate có thể biết:

• Database.
• Cache.
• Kafka.
• Load Balancer.
• Microservices.

nhưng vẫn gặp khó nếu không biết bắt đầu từ requirement.

Một framework đơn giản có thể nhớ:

Requirements → Scale → API → Data Model → High-level Architecture → Deep Dive → Bottlenecks → Trade-offs

Và quan trọng nhất:

Đừng design solution cho đến khi bạn biết mình đang giải quyết problem nào.

---

12. Overall Interview Signal

Nhìn toàn bộ experience, interview đang kiểm tra ba lớp năng lực:

Coding execution

Candidate phải giải quyết 2 bài trong một khoảng thời gian khá giới hạn.

Production-oriented engineering

LRU Cache được follow-up bằng race condition, đưa câu hỏi từ data structure sang concurrency.

System Design & communication

Candidate phải làm rõ một problem chưa được xác định rõ, sau đó đưa ra architecture và communicate với interviewer.

Đây là một dạng interview mà technical knowledge chỉ là một phần của bài kiểm tra.

Khả năng thích nghi với environment, quản lý thời gian, clarify ambiguity và communicate technical reasoning cũng có thể ảnh hưởng trực tiếp đến outcome.

Câu hỏi bạn còn nhớ

HR Screening

• Khả năng giao tiếp tiếng Anh.
• Expected salary.

Round 1 — Coding

Question 1 — N-ary Tree

• Cho một node trong N-ary Tree, tính tổng các giá trị từ node đó.
• Candidate nhớ đây là bài đầu tiên trong phần coding, nhưng không còn nhớ chính xác toàn bộ wording của đề.

Question 2 — LRU Cache

• Implement một LRU Cache.
• Follow-up: nếu nhiều thread / concurrent access cùng sử dụng LRU Cache, làm thế nào để prevent race condition?

Round 2 — System Design

• System Design problem được interviewer đưa ra.
• Candidate cần clarify requirement và xác định system cần design.
• Candidate chủ động hỏi thêm để làm rõ scope nhưng hai phía không thống nhất được expectation.

Outcome: Fail Round 2.

Kết quả

• HR Screening: Passed / proceeded to interview.
• Round 1 — Coding: Candidate hoàn thành cả 2 bài nhưng vượt thời gian khoảng 5 phút.
• Round 2 — System Design: Fail.

Candidate chia sẻ rằng challenge lớn nhất ở Round 2 không nằm hoàn toàn ở việc thiếu kiến thức System Design, mà ở việc không xác định được interviewer đang kỳ vọng candidate design đúng problem nào.