Hash Table Questions at MakeMyTrip: What to Expect

Hash Table questions appear in one-third of MakeMyTrip's technical interviews. For a company managing millions of hotel bookings, flight searches, and user sessions daily, efficient data retrieval is non-negotiable. Hash tables provide the O(1) average-time complexity for lookups, inserts, and deletes that powers their core systems—from caching frequent search results to deduplicating user data and matching inventory. Mastering them is not just about solving a problem; it's about demonstrating you can build the fast, scalable backend services their platform requires.

What to Expect — Types of Problems

MakeMyTrip's Hash Table problems typically focus on real-world data processing scenarios rather than abstract algorithm puzzles. You can expect two main categories:

1. Direct Key-Value Mapping: Problems where you use a hash table (dictionary, map, object) as the primary data structure to count frequencies, check for duplicates, or store mappings. Examples include finding the first non-repeating character in a stream of search queries or identifying two-sum pairs in pricing data.
2. Hash Table as a Supporting Tool: More complex problems where a hash table accelerates part of a solution for arrays, strings, or linked lists. This includes caching intermediate results (memoization) for dynamic programming or tracking node visits in graph-like structures.

The problems often involve strings (user IDs, location codes) and arrays (price lists, seat inventories). Expect follow-ups on optimization and handling edge cases, like collisions in theory or memory usage in practice.

How to Prepare — Study Tips with One Code Example

Focus on the core pattern: using a hash table to achieve O(1) lookups to avoid O(n) searches. The most frequent pattern is the "Frequency Counter." You iterate through a dataset, using elements as keys to store counts or indices. This transforms problems like "find duplicates" or "check anagrams" from O(n²) to O(n).

Practice this pattern by solving: "Given an array of customer IDs, find the first ID that repeats." The efficient solution uses a hash set to track seen IDs.

def first_repeating_id(ids):
    seen = set()
    for id in ids:
        if id in seen:
            return id
        seen.add(id)
    return None  # No repeat found

Recommended Practice Order

Build competence progressively:

1. Fundamentals: Two Sum, Valid Anagram, First Unique Character. Internalize the frequency counter pattern.
2. Aggregation: Group Anagrams, Top K Frequent Elements. Practice using hash tables to group or sort data.
3. Integration: LRU Cache, Subarray Sum Equals K. Solve problems where a hash table works with other structures (linked lists, prefix sums).
4. MakeMyTrip Specific: Practice the 8 tagged company questions last. They will combine these patterns in contexts similar to their domain.

Prioritize writing clean, correct code first. Then, discuss time and space complexity. Be prepared to explain why a hash table is the right choice and what the trade-offs are versus a sorted array or tree.

Practice Hash Table at MakeMyTrip