PAYTM SDE 2 Interview Experience

📌 Problem

Interview asked to design and implement an LRU Cache.

---

🎯 Expectations

The interviewer expected a complete, working solution—not just a high-level approach.

Requirements:

• Write fully functional code
• Run through test cases to verify correctness
• Handle all edge cases:
  • Capacity limits
  • Updating existing keys
  • Repeated access
• Ensure optimal time complexity:
  • O(1) for both get and put operations

---

🧠 Key Discussion Points

Edge Cases Coverage

• Cache capacity = 0
• Updating an existing key
• Accessing non-existent keys
• Continuous evictions when capacity is exceeded

---

🧵 Multi-threading Considerations

The discussion extended to how the LRU Cache behaves in a multi-threaded environment.

Potential Issues:

• Race conditions during concurrent get and put
• Inconsistent state of the linked list or cache map

Possible Solutions:

• Use a global lock (mutex) for simplicity
• Implement read-write locks to improve concurrency
• Apply fine-grained locking for better scalability
• Use thread-safe data structures where applicable

---

🏁 Takeaway

The problem tested not just implementation skills, but also:

• Attention to edge cases
• Ability to write production-ready code
• Understanding of concurrency and system design considerations