33 Meta .NET Developer Interview Questions & Answers

1. Recurring CharacterCodingEasyMeta

Question Details

Return the first character that appears more than once and explain how you stop at the earliest repeat.

Short Interview Answer (30-60 seconds)

I would scan the string from left to right and keep a HashSet<char> called seen. For each character, I first check whether it is already in the set. If it is, I return that character immediately, so I stop at the earliest repeat. Otherwise, I add it to the set and continue. I process each character at most once. This gives O(n) expected time and O(min(n, Σ)) auxiliary space.

Detailed Explanation

See the Code while reading this explanation.

The input is a string, and the goal is to return the first character that appears for a second time while reading from left to right. For the example "abcdbea", the answer is 'b'. We first see 'b' at index 1 and see it again at index 4. We stop there, so the later characters are not processed. A set is a good fit because it remembers every character already seen and lets us quickly test whether the current character has appeared before.

Useful Questions to Ask the Interviewer

Should character comparison be case-sensitive?
If no character repeats, should I return '\0' as the sentinel value?

How to Explain It in an Interview

1. Understand the input and required output

The input is a string. We return a character, not an index. The required character is the one whose second appearance is reached first during a left-to-right scan. In "abcdbea", that character is 'b'. If no character repeats, the shown solution returns '\0'.

2. Choose the algorithm and data structure

Use a HashSet<char> named seen. The set stores characters from earlier positions that have already been processed. The key invariant is simple: before processing the current character, seen contains exactly the distinct characters from earlier processed positions. This lets us tell whether the current character is a repeat.

3. Initialize and scan from left to right

Start with an empty set. At index 0, the character is 'a'. It is not in seen, so add it. At index 1, 'b' is not in seen, so add it. At index 2, 'c' is not in seen, so add it. At index 3, 'd' is not in seen, so add it. The set is now {'a', 'b', 'c', 'd'}.

4. Stop at the earliest repeat

At index 4, the current character is 'b'. Before changing the set, check whether 'b' is already present. It is, because 'b' was added at index 1. Return 'b' immediately. The characters at indices 5 and 6 are not processed because the answer has already been found.

5. Explain why the result is correct

We scan strictly from left to right. Every earlier index has already been fully processed before we reach index 4. Therefore, when 'b' is the first character we find already in seen, its second occurrence is the earliest repeat in the string. Returning immediately preserves that requirement.

6. Explain the C# implementation and complexity

The C# method creates a HashSet<char>, loops through the string, checks Contains before Add, and returns immediately when a repeat is found. HashSet lookup and insertion are O(1) on average, so the whole scan takes O(n) expected time. The set stores at most one entry for each distinct character, so auxiliary space is O(min(n, Σ)).

Key Insight / Why This Solution Works

The key idea is to remember characters that were already processed. A HashSet<char> is used because it can test membership and insert a character in O(1) average time. Before processing each character, the set contains only distinct characters from earlier positions. If the current character is already in the set, this is the first repeat reached by the left-to-right scan, so we return it immediately. Otherwise, we add it and continue.

Code

using System;
using System.Collections.Generic;

public static class Program
{
    public static void Main()
    {
        // Use the same example shown in the diagram.
        string input = "abcdbea";

        // Find the earliest recurring character and print it.
        char result = FirstRecurringChar(input);
        Console.WriteLine(result);
    }

    public static char FirstRecurringChar(string s)
    {
        // Handle an empty or missing input with the diagram's sentinel value.
        if (string.IsNullOrEmpty(s))
        {
            return '\0';
        }

        // Store each distinct character that has already been processed.
        HashSet<char> seen = new HashSet<char>();

        // Process the input from left to right and stop when the answer is found.
        foreach (char c in s)
        {
            // Check before insertion so an existing character is detected as a repeat.
            if (seen.Contains(c))
            {
                // Return immediately because this is the earliest repeat reached by the scan.
                return c;
            }

            // This is the first occurrence of c, so remember it for later checks.
            seen.Add(c);
        }

        // The full input was processed and no recurring character was found.
        return '\0';
    }
}

Time & Space Complexity

Let n be the length of the string and Σ be the number of possible distinct character values. We process the input at most once. HashSet<char> lookup and insertion are O(1) on average, so the total expected time is O(n). The set holds at most one copy of each distinct character, so the auxiliary space is O(min(n, Σ)). The method can finish early when it finds a repeat.

Where it is used

This pattern is useful when processing ordered data and you need to detect the first value that has already appeared. Examples include finding the first duplicate token, event code, identifier, or character in a stream while preserving the original processing order.

Why Interviewers Ask This

This question tests whether you recognize a simple hash-set pattern and preserve left-to-right order. The interviewer can see whether you understand duplicate detection, maintain a clear invariant, stop correctly on the first valid result, and write clean C#. It also tests whether you can explain expected hash-table complexity accurately and handle relevant edge cases such as empty input, all-unique characters, repeated characters, and case-sensitive comparisons.

Common interview mistakes

A common mistake is adding the current character to the set before checking whether it was already present. Another mistake is continuing after a repeat is found, which can return a later repeat instead of the earliest one. Candidates may also return the index instead of the character, forget the no-repeat sentinel, or claim guaranteed O(n) time instead of expected O(n) time for hash-based operations.

Interview tip

Say the invariant before coding: the set contains only characters from earlier processed positions. Then make the check-before-add order explicit, because that is what lets you detect the earliest repeat correctly.

Interviewer may ask next

How would this work if the characters arrived as a stream instead of one complete string?

The same approach still works. Keep the HashSet<char> between incoming characters. For each new character, check the set first. If it is already present, return or emit it immediately. Otherwise, add it and wait for the next character. The invariant is unchanged because the set contains exactly the characters seen earlier. Processing n streamed characters takes O(n) expected time, and the auxiliary space is O(min(n, Σ)). The tradeoff is that the set must remain in memory while the stream is being processed.

What is the worst-case behavior of the HashSet<char> operations used here?

HashSet<char> lookup and insertion are O(1) on average, which gives O(n) expected total time. They are not guaranteed O(1) in the worst case. With severe hash collisions, one operation can degrade toward O(n), so a full sequence can degrade toward O(n^2) in the worst case. The left-to-right algorithm and early-return rule do not change, and auxiliary space remains O(min(n, Σ)).

2. Liked PagesCodingEasyMeta

Question Details

List the pages a user has liked and describe how you would keep the output stable when likes arrive out of order.

Short Interview Answer (30-60 seconds)

I would keep the earliest like timestamp for each page in a Dictionary keyed by pageId. For each event for the target user, I add the page if it is new, or replace its timestamp only when an older like arrives. After processing the events, I sort by earliest timestamp ascending and use pageId as the tie-breaker. This makes the result stable regardless of arrival order. The expected time is O(n + u log u), with O(u) auxiliary space.

Detailed Explanation

See the Code while reading this explanation.

The goal is to list every page the user has liked exactly once. Like events can arrive in a different order from when the likes actually happened. For each page, we therefore keep the earliest like time found in all of its events. If an older event arrives later, we update the stored time. After processing the events, we order the pages from earliest like time to latest. If two pages have the same time, pageId gives a deterministic order. This produces the same result for the same events regardless of arrival order.

Useful Questions to Ask the Interviewer

Should each page appear only once even if the user has several Like events for it?
Should the final order use the earliest like timestamp for each page?
If two pages have the same earliest timestamp, can I use pageId as the deterministic tie-breaker?

How to Explain It in an Interview

1. Understand the input and required output

The input is a target userId and a stream of Like events. Each event contains userId, pageId, and timestamp. Events for other users are ignored. The output is the pageIds liked by the target user. Each page appears once. Pages are ordered by their earliest like timestamp in ascending order. If two pages have the same earliest timestamp, pageId is used as the tie-breaker.

2. Choose the algorithm and data structure

Use a Dictionary<int, long>. The key is pageId. The value is the earliest timestamp seen for that page. The central invariant is that after every processed event, the dictionary stores the minimum timestamp seen so far for each page. This makes the final result independent of event arrival order.

3. Initialize and process the events

Start with an empty dictionary. Process each Like event. If event.UserId does not match the target userId, skip it. If the page has not been seen, store its timestamp. If the page is already present, compare the new timestamp with the stored earliest timestamp. Replace the stored value only when the new timestamp is smaller. An equal or newer duplicate does not change the dictionary.

4. Walk through the verified example

For userId 42, the events arrive in this order: page 30 at 1003, page 20 at 1001, page 30 at 999, page 10 at 1002, and page 20 at 1015.

After event 1, the dictionary is {30 -> 1003}. After event 2, it is {30 -> 1003, 20 -> 1001}. Event 3 is an older like for page 30. Since 999 is smaller than 1003, page 30 is updated. The dictionary becomes {30 -> 999, 20 -> 1001}. Event 4 adds page 10. The dictionary becomes {30 -> 999, 20 -> 1001, 10 -> 1002}. Event 5 is a newer duplicate for page 20. Since 1015 is later than 1001, it is ignored. The dictionary stays {30 -> 999, 20 -> 1001, 10 -> 1002}.

Now sort by earliest timestamp and then by pageId. The order is page 30 at 999, page 20 at 1001, and page 10 at 1002. The final output is [30, 20, 10].

5. Explain why the result is correct

For every page, the dictionary always contains the smallest timestamp seen for that page. Taking the minimum does not depend on the order in which events arrive. Therefore, after all events are processed, every page has the same earliest timestamp for the same set of events. Sorting those values by timestamp and then pageId produces a deterministic result.

6. Explain the C# implementation

The C# code uses Dictionary<int, long> to map pageId to earliest timestamp. TryGetValue checks whether a page already has a stored timestamp. The code inserts a new page or updates an existing page only when the incoming timestamp is smaller. Dictionary lookup and update are O(1) on average. After the loop, LINQ sorts dictionary entries by timestamp and then pageId. Select returns only the pageIds.

7. Explain complexity and edge cases

Let n be the number of input Like events examined and u be the number of unique pages retained for the target user. Processing the events takes O(n) expected time because Dictionary lookup and update are O(1) on average. Sorting u pages takes O(u log u), so the total expected time is O(n + u log u). Auxiliary space is O(u). No likes return an empty list. Events for other users are ignored. Duplicate page likes keep the earliest timestamp. Equal timestamps are ordered by pageId.

Key Insight / Why This Solution Works

The key idea is to reduce all Like events for the same page to one stable value: that page's earliest timestamp. Use a dictionary where each key is a pageId and each value is the minimum timestamp seen for that page. The invariant is that after every processed event, the dictionary contains the earliest timestamp seen so far for each stored page. If an older event arrives late, it replaces the newer stored value. If an equal or newer duplicate arrives, the value stays unchanged. After processing, sort by earliest timestamp ascending and then pageId ascending to produce a deterministic result.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public static class Program
{
    public sealed class LikeEvent
    {
        public int UserId { get; init; }
        public int PageId { get; init; }
        public long Timestamp { get; init; }
    }

    public static List<int> GetLikedPages(int userId, IEnumerable<LikeEvent> events)
    {
        // Map each pageId to the earliest like timestamp seen for that page.
        // Keeping the minimum timestamp makes the result independent of arrival order.
        Dictionary<int, long> earliestLike = new Dictionary<int, long>();

        foreach (LikeEvent likeEvent in events)
        {
            // Ignore Like events that do not belong to the requested user.
            if (likeEvent.UserId != userId)
            {
                continue;
            }

            // Read the earliest timestamp already stored for this page, if one exists.
            bool alreadySeen =
                earliestLike.TryGetValue(likeEvent.PageId, out long earliestTimestamp);

            // Add a new page, or lower its stored value when an older event arrives later.
            // Equal or newer duplicate events do not change the minimum timestamp.
            if (!alreadySeen || likeEvent.Timestamp < earliestTimestamp)
            {
                earliestLike[likeEvent.PageId] = likeEvent.Timestamp;
            }
        }

        // Sort by earliest like time first.
        // Use pageId as a deterministic tie-breaker when timestamps are equal.
        // Return only the ordered pageIds.
        return earliestLike.OrderBy(entry => entry.Value)
            .ThenBy(entry => entry.Key)
            .Select(entry => entry.Key)
            .ToList();
    }

    public static void Main()
    {
        // Use the exact event sequence shown in the approved diagram.
        List<LikeEvent> events =
            new List<LikeEvent> { new LikeEvent { UserId = 42, PageId = 30, Timestamp = 1003 },
                                  new LikeEvent { UserId = 42, PageId = 20, Timestamp = 1001 },
                                  new LikeEvent { UserId = 42, PageId = 30, Timestamp = 999 },
                                  new LikeEvent { UserId = 42, PageId = 10, Timestamp = 1002 },
                                  new LikeEvent { UserId = 42, PageId = 20, Timestamp = 1015 } };

        // After processing, the earliest timestamps are:
        // page 30 -> 999, page 20 -> 1001, page 10 -> 1002.
        List<int> result = GetLikedPages(42, events);

        // Expected output: [30, 20, 10]
        Console.WriteLine("[" + string.Join(", ", result) + "]");
    }
}

Time & Space Complexity

Let n be the number of input Like events examined and u be the number of unique pages kept for the target user. Processing the events takes O(n) expected time because C# Dictionary lookup and update are O(1) on average, with normal hashing and collision caveats. Sorting the u retained pages takes O(u log u). Therefore, the total expected time is O(n + u log u). The dictionary stores one timestamp for each unique page, so the auxiliary space is O(u).

Where it is used

This pattern is useful in event-processing systems where records can arrive late or out of order but results must follow event time. Examples include activity feeds, audit-log processing, synchronization jobs, and data pipelines that need the earliest record for each key followed by deterministic ordering.

Why Interviewers Ask This

This question tests whether you can separate event arrival order from event-time order. The interviewer is checking whether you choose a suitable dictionary state, handle duplicate page likes correctly, maintain a clear minimum-timestamp invariant, and make the final order deterministic. It also tests practical C# skills such as Dictionary lookup and LINQ sorting, plus whether you include the sorting cost and describe hash-based operations using average or expected-time language.

Common interview mistakes

A common mistake is keeping the first event that arrives for each page instead of the earliest timestamp. That fails when an older event arrives later. Another mistake is replacing the stored timestamp with every duplicate, which can incorrectly move a page to a newer time. Candidates may also forget to ignore events for other users or forget the pageId tie-breaker when timestamps are equal. Another mistake is claiming O(n) total time and forgetting the O(u log u) sorting cost.

Interview tip

State the invariant early: for every page, the dictionary always stores the smallest timestamp seen so far. Then use the page-30 event that changes 1003 to 999 to show exactly why the method works when an older event arrives late.

Interviewer may ask next

How would you handle this if the Like event stream were very large?

I would continue processing events one at a time and keep only one dictionary entry per unique page. The dictionary therefore uses O(u) auxiliary space instead of storing all n events. After the stream is complete, I still need to sort the u retained pages, so the total expected time is O(n + u log u) and the auxiliary space is O(u). The main tradeoff is that all unique page entries must fit in memory for the final sort.

What if two pages have exactly the same earliest like timestamp?

The algorithm already handles this by sorting first by earliest timestamp and then by pageId. pageId acts as the deterministic tie-breaker, so the same set of events always produces the same order. The correctness invariant does not change because each page still stores its minimum timestamp. The expected time remains O(n + u log u), and the auxiliary space remains O(u).

3. Last TransactionCodingEasyMeta

Question Details

Identify the most recent transaction for each user or partition and clarify how ties on timestamp are resolved.

Short Interview Answer (30-60 seconds)

I would keep one best transaction for each user in a Dictionary keyed by UserId. I process the transactions in input order. A newer timestamp replaces the stored transaction. If timestamps are equal, the larger Id wins. If both timestamp and Id are equal, I keep the first one already stored. This leaves the most recent transaction for every user. With average O(1) dictionary operations, the solution takes O(n) expected time and O(k) auxiliary space for k distinct users.

Detailed Explanation

See the Code while reading this explanation.

We are given several transactions, and each transaction belongs to a user. We need to return one transaction for every user. The chosen transaction must have the latest timestamp for that user. When two transactions have the same timestamp, the transaction with the larger Id wins. If both timestamp and Id are equal, the first stored transaction stays. A dictionary fits this problem because it keeps only the current best transaction for each user while we process the input in order.

Useful Questions to Ask the Interviewer

Should ties on timestamp always be resolved by the larger transaction Id?
If both timestamp and Id are equal, should we keep the first transaction we saw?
Can the input contain no transactions?

How to Explain It in an Interview

1. Understand the input and required output

The input is a sequence of transactions. Each transaction has Id, UserId, Timestamp, and Amount. The output is one transaction per user. It must be the latest transaction for that user. If timestamps are equal, the larger Id wins. If timestamp and Id are both equal, the existing first-seen transaction stays.

2. Choose the algorithm and data structure

Use a Dictionary<string, Transaction>. The key is UserId. The value is the best transaction seen so far for that user. The central invariant is: after every processed transaction, the dictionary contains the best transaction seen so far for each user already encountered.

3. Initialize the state

Start with an empty dictionary named last. Process the transactions in their given order. When a user appears for the first time, store that transaction because there is no previous candidate for that user.

4. Walk through the example

The input transactions are: 101, U1, 2024-05-01 10:00:00, 50.00 102, U2, 2024-05-01 09:00:00, 20.00 103, U1, 2024-05-02 11:00:00, 75.00 104, U2, 2024-05-02 11:00:00, 60.00 105, U1, 2024-05-02 11:00:00, 30.00 106, U3, 2024-05-01 08:30:00, 40.00 107, U2, 2024-05-02 11:00:00, 80.00

Step 1: Read transaction 101 for U1. The dictionary is empty for U1, so store 101. State after the step: U1 -> 101. Step 2: Read transaction 102 for U2. U2 has no stored transaction, so store 102. State: U1 -> 101, U2 -> 102. Step 3: Read transaction 103 for U1. Its timestamp is later than transaction 101, so replace 101 with 103. State: U1 -> 103, U2 -> 102. Step 4: Read transaction 104 for U2. Its timestamp is later than transaction 102, so replace 102 with 104. State: U1 -> 103, U2 -> 104. Step 5: Read transaction 105 for U1. It has the same timestamp as transaction 103. Id 105 is larger than Id 103, so replace 103 with 105. State: U1 -> 105, U2 -> 104. Step 6: Read transaction 106 for U3. U3 has no stored transaction, so store 106. State: U1 -> 105, U2 -> 104, U3 -> 106. Step 7: Read transaction 107 for U2. It has the same timestamp as transaction 104. Id 107 is larger than Id 104, so replace 104 with 107. Final state: U1 -> 105, U2 -> 107, U3 -> 106.

The final transactions are U1: Id 105 at 2024-05-02 11:00:00 with amount 30.00, U2: Id 107 at 2024-05-02 11:00:00 with amount 80.00, and U3: Id 106 at 2024-05-01 08:30:00 with amount 40.00.

5. Explain why the result is correct

For each user, the dictionary always stores the best transaction among the records processed so far. A later timestamp always wins. When timestamps tie, the larger Id wins. Therefore, after all transactions are processed, every dictionary value is the correct last transaction for its user according to the required rules.

6. Explain the C# implementation

The method creates a dictionary keyed by UserId. For each transaction, TryGetValue checks whether a current best transaction exists. If not, the transaction is stored immediately. Otherwise, the code compares timestamps. It replaces the stored transaction when the new timestamp is later, or when timestamps are equal and the new Id is larger. It then returns the final dictionary.

7. Explain complexity and edge cases

Let n be the number of transactions and k be the number of distinct users. Dictionary lookup and update are O(1) on average, so the total expected time is O(n). The dictionary stores at most one transaction per user, so auxiliary space is O(k). Empty input gives an empty result. One transaction becomes that user's result. When all timestamps for a user are equal, the highest Id wins. When timestamp and Id are both equal, the first stored transaction remains.

Key Insight / Why This Solution Works

Keep a dictionary that maps UserId to the best transaction seen so far. When a transaction arrives for a user that is not yet in the dictionary, store it. Otherwise, compare it with the stored transaction. A later timestamp wins. If timestamps are equal, the larger Id wins. If timestamp and Id are both equal, keep the existing value. The invariant is that after each step, every dictionary entry is the best transaction seen so far for that user according to these exact comparison rules.

Code

using System;
using System.Collections.Generic;

public sealed class Transaction
{
    public long Id { get; set; }
    public string UserId { get; set; } = string.Empty;
    public DateTime Timestamp { get; set; }
    public decimal Amount { get; set; }
}

public static class Program
{
    public static Dictionary<string, Transaction> GetLastTransactions(
        IEnumerable<Transaction> transactions)
    {
        // Keep exactly one current best transaction for each user.
        var last = new Dictionary<string, Transaction>();

        foreach (Transaction tx in transactions)
        {
            // If this user has not appeared before, the current transaction
            // becomes the first and therefore current best candidate.
            if (!last.TryGetValue(tx.UserId, out Transaction? current))
            {
                last[tx.UserId] = tx;
                continue;
            }

            // A later timestamp always wins.
            // If timestamps tie, the larger transaction Id wins.
            // If both timestamp and Id tie, do not replace the first-seen value.
            if (tx.Timestamp > current.Timestamp ||
                (tx.Timestamp == current.Timestamp && tx.Id > current.Id))
            {
                last[tx.UserId] = tx;
            }
        }

        // The dictionary now contains the final last transaction for every user.
        return last;
    }

    public static void Main()
    {
        // Build the exact input sequence used by the approved diagram.
        var transactions = new List<Transaction> {
            new() { Id = 101, UserId = "U1", Timestamp = new DateTime(2024, 5, 1, 10, 0, 0),
                    Amount = 50.00m },
            new() { Id = 102, UserId = "U2", Timestamp = new DateTime(2024, 5, 1, 9, 0, 0),
                    Amount = 20.00m },
            new() { Id = 103, UserId = "U1", Timestamp = new DateTime(2024, 5, 2, 11, 0, 0),
                    Amount = 75.00m },
            new() { Id = 104, UserId = "U2", Timestamp = new DateTime(2024, 5, 2, 11, 0, 0),
                    Amount = 60.00m },
            new() { Id = 105, UserId = "U1", Timestamp = new DateTime(2024, 5, 2, 11, 0, 0),
                    Amount = 30.00m },
            new() { Id = 106, UserId = "U3", Timestamp = new DateTime(2024, 5, 1, 8, 30, 0),
                    Amount = 40.00m },
            new() { Id = 107, UserId = "U2", Timestamp = new DateTime(2024, 5, 2, 11, 0, 0),
                    Amount = 80.00m }
        };

        // Run the same dictionary algorithm shown in the walkthrough.
        Dictionary<string, Transaction> result = GetLastTransactions(transactions);

        // Print the users in the same order as the diagram's expected result.
        foreach (string userId in new[] { "U1", "U2", "U3" })
        {
            Transaction tx = result[userId];
            Console.WriteLine(
                $"{tx.UserId}: Id={tx.Id}, Timestamp={tx.Timestamp:yyyy-MM-dd HH:mm:ss}, Amount={tx.Amount:F2}");
        }
    }
}

Time & Space Complexity

Let n be the number of transactions and k be the number of distinct users. We process each transaction once. A Dictionary lookup or update is O(1) on average, so the total expected time is O(n). The dictionary keeps at most one transaction for each user, so the auxiliary space is O(k). Because the solution depends on hash-table operations, O(n) is an expected-time bound rather than a guaranteed worst-case bound.

Where it is used

This pattern is useful when software needs the newest record for each key, such as the latest payment per customer, latest status per order, newest event per device, or most recent update per account. It is also suitable for streaming data because the program only needs to keep the current best transaction for each user.

Why Interviewers Ask This

This problem checks whether you recognize a per-key aggregation pattern and choose a suitable dictionary. It tests whether you can define a deterministic tie-break rule, maintain the correct best-so-far state, and update it in the right order. It also checks practical C# knowledge with Dictionary and TryGetValue, correct handling of repeated users and ties, and accurate complexity reasoning using expected O(n) time and O(k) auxiliary space.

Common interview mistakes

A common mistake is comparing Id before timestamp. Timestamp must be the primary rule. Another mistake is replacing the stored transaction whenever timestamps are equal without checking which Id is larger. Candidates may also replace an exact timestamp-and-Id tie even though the diagram keeps the first stored value. Another error is keeping every transaction instead of only one best transaction per user. Finally, describing the hash-based solution as guaranteed O(n) is inaccurate because Dictionary operations are O(1) on average.

Interview tip

State the comparison rule before writing the loop: later timestamp wins, equal timestamp uses the larger Id, and an exact tie keeps the existing record. Then explain the invariant as 'one best transaction seen so far per user.' This makes both the code and the correctness argument easy to present.

Interviewer may ask next

How would this change if transactions arrive as a continuous stream?

The same algorithm can process the stream incrementally. Keep the dictionary alive as events arrive. For each new transaction, compare it with the stored transaction for that UserId and replace it only when its timestamp is later, or when timestamps tie and its Id is larger. The invariant stays unchanged. Processing m new events takes O(m) expected time, and auxiliary space remains O(k) for k users. The main tradeoff is that the per-user state must remain available while the stream continues.

What is the worst-case behavior of the Dictionary-based solution?

The solution depends on hash-table operations that are O(1) on average. In pathological collision cases, individual dictionary operations can become slower, so the overall O(n) bound is expected rather than a guaranteed worst-case bound. The comparison rule and correctness do not change. Auxiliary space remains O(k), where k is the number of distinct users. The tradeoff is that the fast expected performance depends on normal hash-table behavior.

4. Session DifferenceCodingEasyMeta

Question Details

Compute the gap between consecutive sessions and define what happens at a user’s first session.

Short Interview Answer (30-60 seconds)

I would group the sessions by user and sort each user’s sessions by time. For the first session, I record a gap of 0 because there is no previous session. For every later session, I subtract the previous session time from the current time and store the difference in minutes. This works because each session is compared only with its immediate predecessor. The overall time is O(n log n), and the auxiliary space is O(n).

Detailed Explanation

See the Code while reading this explanation.

We receive session records for different users. Each record has a user and a session time. The goal is to find how much time passed since that same user’s previous session. The sessions may not already be in time order, so we first separate them by user and put each user’s sessions from earliest to latest. The first session has no earlier session to compare with, so this solution gives it a gap of 0 minutes. Every later session gets the number of minutes since that user’s immediately previous session.

Useful Questions to Ask the Interviewer

Should the first session use 0 to represent that there is no previous session?
Should the returned gap be measured in whole minutes?
Can the input sessions arrive in any order, so I should sort them by user and time?

How to Explain It in an Interview

1. Understand the input and required output

The input is a collection of user sessions. Each session has a user ID and a session time. The output keeps each session and adds its gap to the previous session for the same user. The first session for every user gets a gap of 0 minutes.

The diagram uses this example: U1 at 2025-05-01 09:00:00 U1 at 2025-05-01 09:30:00 U1 at 2025-05-01 10:15:00 U2 at 2025-05-01 08:00:00 U2 at 2025-05-01 12:00:00

The output gaps are 0, 30, 45, 0, and 240 minutes in that order.

2. Group and sort the sessions

First, group the records by user. Then sort each user’s sessions by session time in ascending order. This is necessary because each gap must compare the current session with the immediately previous session for that same user.

The central rule is that while one user is being processed, the previous-session variable always holds the timestamp of the session immediately before the current session in chronological order.

3. Initialize the first session

For each user, start with no previous session. The first session therefore has nothing earlier to subtract. The diagram defines its gap as 0 minutes. After recording that result, save the first session time as the previous time for the next iteration.

For U1, the first session is 09:00. Its gap is 0, and the previous time becomes 09:00.

For U2, the first session is 08:00. Its gap is also 0.

4. Walk through the remaining sessions

For U1, the second session is 09:30. The previous time is 09:00. The calculation is 09:30 - 09:00 = 30 minutes. Record 30, then update the previous time to 09:30.

The third U1 session is 10:15. The previous time is now 09:30. The calculation is 10:15 - 09:30 = 45 minutes. Record 45, then update the previous time to 10:15.

For U2, the second session is 12:00. The previous time is 08:00. The calculation is 12:00 - 08:00 = 240 minutes. Record 240.

After every user’s sessions are processed, return the results ordered by user ID and session time.

5. Explain why the result is correct

Each user is processed independently. Inside one user’s group, the sessions are sorted from earliest to latest. Therefore, when the code subtracts the previous timestamp from the current timestamp, that previous timestamp is exactly the immediately preceding session for that user. The first session has no predecessor, so the defined gap is 0. This produces the correct consecutive-session difference for every record.

6. Explain the C# implementation

The code groups sessions with GroupBy and sorts each group with OrderBy. For each user, it keeps a nullable DateTime called previousSessionTime. A null value means no session has been processed yet for that user. In that case, the current session gets a gap of 0. Otherwise, the code subtracts previousSessionTime from the current SessionTime and reads the difference in whole minutes. It then records the result and updates previousSessionTime to the current timestamp. Finally, it orders the complete output by user ID and session time.

7. Explain complexity and edge cases

Let n be the total number of sessions. Grouping and traversing the records take O(n) work. Sorting the per-user groups and ordering the final result give O(n log n) time in the worst case. Auxiliary space is O(n) for grouping, sorted group data, and output records.

A user with one session gets a gap of 0. Different users are handled independently. Two consecutive sessions with the same timestamp produce a gap of 0. Empty input produces empty output.

Key Insight / Why This Solution Works

The key idea is to compare every session only with the immediately previous session for the same user. Grouping keeps different users independent. Sorting each user’s sessions by SessionTime makes the predecessor relationship correct. The invariant is that before processing any session after the first, previousSessionTime contains the timestamp of the immediately preceding session in that user’s sorted sequence. The first session is the one special case and receives the defined gap of 0 minutes.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public sealed record Session(string UserId, DateTime SessionTime);

public sealed record SessionGap(string UserId, DateTime SessionTime, long GapMinutes);

public static class Program
{
    public static List<SessionGap> ComputeSessionGaps(List<Session> sessions)
    {
        // Store every output session together with its calculated gap.
        List<SessionGap> result = new List<SessionGap>();

        // Group by user so a session is compared only with sessions from the same user.
        IEnumerable<IGrouping<string, Session>> groups =
            sessions.GroupBy(session => session.UserId);

        foreach (IGrouping<string, Session> group in groups)
        {
            // Sort this user's sessions from earliest to latest before calculating gaps.
            List<Session> orderedSessions = group.OrderBy(session => session.SessionTime).ToList();

            // Null means this user's first session has not been processed yet.
            DateTime? previousSessionTime = null;

            foreach (Session session in orderedSessions)
            {
                // The first session has no predecessor, so its defined gap is 0.
                // Every later session uses the immediately previous sorted timestamp.
                long gapMinutes =
                    previousSessionTime is null
                        ? 0
                        : (long)(session.SessionTime - previousSessionTime.Value).TotalMinutes;

                // Record the current session and its gap before moving to the next session.
                result.Add(new SessionGap(session.UserId, session.SessionTime, gapMinutes));

                // Update the state so this timestamp becomes the next session's predecessor.
                previousSessionTime = session.SessionTime;
            }
        }

        // Match the diagram's final output order: user first, then session time ascending.
        return result.OrderBy(item => item.UserId).ThenBy(item => item.SessionTime).ToList();
    }

    public static void Main()
    {
        // Run the exact example shown in the approved diagram.
        List<Session> sessions =
            new List<Session> { new Session("U1", new DateTime(2025, 5, 1, 9, 0, 0)),
                                new Session("U1", new DateTime(2025, 5, 1, 9, 30, 0)),
                                new Session("U1", new DateTime(2025, 5, 1, 10, 15, 0)),
                                new Session("U2", new DateTime(2025, 5, 1, 8, 0, 0)),
                                new Session("U2", new DateTime(2025, 5, 1, 12, 0, 0)) };

        // Compute the consecutive-session gaps for both users.
        List<SessionGap> gaps = ComputeSessionGaps(sessions);

        // Print each result so the example can be verified directly.
        foreach (SessionGap gap in gaps)
        {
            Console.WriteLine(
                $"{gap.UserId} | {gap.SessionTime:yyyy-MM-dd HH:mm:ss} | {gap.GapMinutes}");
        }
    }
}

Time & Space Complexity

Let n be the total number of sessions. Grouping and traversing the sessions take O(n) work. Sorting the sessions inside the user groups can take O(n log n) in the worst case. The final ordering of the output also fits within O(n log n), so the total time complexity is O(n log n). Auxiliary space is O(n) because the grouping, sorted group data, and returned result can all grow with the number of sessions.

Where it is used

This pattern is useful for login history, activity logs, analytics, monitoring, and event-processing systems. It can measure how much time passed between consecutive events belonging to the same user, device, account, or other grouping key.

Why Interviewers Ask This

This question checks whether you can group related records, order time-based data correctly, and maintain simple state while walking through a sequence. It also tests whether you handle the first item explicitly instead of subtracting a value that does not exist. In C#, the interviewer can evaluate your use of grouping, sorting, DateTime subtraction, nullable state, result construction, and accurate complexity analysis.

Common interview mistakes

A common mistake is calculating gaps before sorting each user’s sessions. That can compare the wrong timestamps. Another mistake is carrying the previous timestamp from one user into the next user instead of resetting it. Candidates may also forget the first-session rule and try to subtract a missing previous time. Another mistake is returning a different time unit instead of the diagram’s minutes. Finally, do not claim O(n) total time because sorting is part of this implementation.

Interview tip

State the invariant before coding: after sorting one user’s sessions, previousSessionTime always holds the immediately preceding timestamp. Then explain that the first session is the one special case and gets a gap of 0.

Interviewer may ask next

How would the solution change if sessions arrived continuously as a stream?

If each user’s sessions are guaranteed to arrive in chronological order, keep the latest timestamp for each user in a Dictionary<string, DateTime>. For each new session, look up that user’s previous timestamp. If none exists, return a gap of 0. Otherwise, subtract the previous timestamp from the current one. Then store the current timestamp as the new latest value. Each event takes O(1) expected time for dictionary lookup and update, and the extra space is O(u), where u is the number of users. If events can arrive out of order, they must be buffered or reordered before final consecutive gaps are known.

Can the batch solution reduce its extra working memory?

Yes, if the input collection may be reordered. Sort the input in place by UserId and SessionTime, then make one pass while keeping only the current user and previous timestamp. The traversal itself uses O(1) working state. The sorting time remains O(n log n). The returned output still needs O(n) space because there is one result record per session. The tradeoff is that sorting in place changes the original input order.

5. Comments HistogramCodingEasyMeta

Question Details

Bucket comments into counts per range and explain the range boundaries you apply to the histogram.

Short Interview Answer (30-60 seconds)

I would define ordered, non-overlapping inclusive ranges and keep one count for each range. For every comment count, I scan the ranges from left to right, find the first range whose lower and upper bounds contain the value, increment that bucket, and stop checking ranges for that value. With n comments and k ranges, this takes O(n * k) time. The counts array uses O(k) auxiliary space. The ranges cover all non-negative values without gaps or overlaps.

Detailed Explanation

See the Code while reading this explanation.

The input is a list of comment counts. The goal is to group each count into a numeric range and return how many values belong to each range. The diagram uses five inclusive ranges: [0, 9], [10, 49], [50, 99], [100, 499], and [500, infinity]. For each value, we check the ranges in order and increase exactly one bucket. This is simple and works because the ranges do not overlap and cover every non-negative integer.

Useful Questions to Ask the Interviewer

Should comment counts always be non-negative?
Are these histogram ranges fixed, or should the method receive the ranges as input?
If a value does not belong to any configured range, should we ignore it or put it in an extra out-of-range bucket?

How to Explain It in an Interview

1. Understand the input and required output

The input is the comment-count list [0, 5, 7, 12, 20, 45, 55, 70, 99, 100, 150, 250, 499, 500, 501, 1200]. The output is a histogram. Each histogram entry contains a range and the number of input values inside that range. The five ranges are [0, 9], [10, 49], [50, 99], [100, 499], and [500, infinity]. The expected counts are [3, 3, 3, 4, 3].

2. Define the ranges and initialize the counts

Each range stores a lower bound, an upper bound, and a display label. Both finite boundaries are inclusive. The last range starts at 500 and has no practical upper limit in the histogram definition. In the C# implementation, long.MaxValue represents that upper limit. We create an integer array with five positions and initialize every count to zero. Position 0 represents [0, 9], position 1 represents [10, 49], and so on.

3. Process each comment count

For each input value, scan the ranges from index 0 upward. A value belongs to a range when value >= Lower and value <= Upper. When that condition is true, increment the count for that range and break out of the inner loop. The break is important because one value should be counted only once.

4. Walk through the verified example

Value 0 matches [0, 9], so the counts become [1, 0, 0, 0, 0]. Value 5 also matches [0, 9], giving [2, 0, 0, 0, 0]. Value 7 gives [3, 0, 0, 0, 0]. Values 12, 20, and 45 match [10, 49], producing [3, 3, 0, 0, 0]. Values 55, 70, and 99 match [50, 99], producing [3, 3, 3, 0, 0]. Values 100, 150, 250, and 499 match [100, 499], producing [3, 3, 3, 4, 0]. Finally, 500, 501, and 1200 match [500, infinity], so the final counts are [3, 3, 3, 4, 3].

5. Explain why the result is correct

The key rule is that the configured ranges are ordered, non-overlapping, and cover all non-negative integers. After each input value is processed, each array position equals the number of processed values that belong to its range. Because the code stops after the first match, a value cannot be counted twice. Therefore the final array contains the correct histogram counts.

6. Explain the C# implementation

The code stores each range in a Range record. It creates the five ranges and a counts array with the same length. The outer loop visits each comment count. The inner loop checks each range in order. When Contains returns true, the matching count is incremented and the inner loop stops. Finally, the ranges and counts are combined into a list of tuples such as ("[0, 9]", 3).

7. Explain complexity and edge cases

If n is the number of comments and k is the number of ranges, the shown implementation takes O(n * k) time because each value may check all k ranges. The counts array uses O(k) auxiliary space. An empty input produces zero for every bucket. Values outside configured ranges are ignored by this implementation. Very large non-negative values supported by the input type fall into the last bucket. Negative values do not match these ranges, so they are ignored unless a separate negative range is added.

Key Insight / Why This Solution Works

The main idea is to represent the histogram as a small ordered list of inclusive numeric ranges. Each range has one matching count. For every comment value, scan the ranges until the value satisfies lower <= value <= upper. Increment that bucket and stop checking further ranges for that value. The central invariant is: after processing any prefix of the input, counts[i] equals the number of processed values that fall inside ranges[i]. Because the ranges do not overlap, the first matching range is also the only matching range. The final bucket begins at 500, and the C# code uses long.MaxValue as its upper bound.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public static class Program
{
    // A histogram range uses inclusive lower and upper boundaries.
    public sealed record Range(long Lower, long Upper, string Label)
    {
        // Check whether this value belongs to the current bucket.
        public bool Contains(long value)
        {
            return value >= Lower && value <= Upper;
        }
    }

    public static List<(string Range, int Count)> BuildHistogram(IEnumerable<int> comments)
    {
        // Define the exact ordered, non-overlapping buckets from the diagram.
        // long.MaxValue represents the diagram's open-ended 500-and-above bucket.
        List<Range> ranges =
            new List<Range> { new Range(0, 9, "[0, 9]"), new Range(10, 49, "[10, 49]"),
                              new Range(50, 99, "[50, 99]"), new Range(100, 499, "[100, 499]"),
                              new Range(500, long.MaxValue, "[500, ∞)") };

        // counts[i] stores how many processed values matched ranges[i].
        int[] counts = new int[ranges.Count];

        // Process every comment count in its original input order.
        foreach (int value in comments)
        {
            // Check buckets from left to right until this value finds a match.
            for (int i = 0; i < ranges.Count; i++)
            {
                if (ranges[i].Contains(value))
                {
                    // Increment exactly the bucket that contains the value.
                    counts[i]++;

                    // Stop because the configured ranges do not overlap.
                    break;
                }
            }

            // A negative value matches none of these non-negative ranges and is ignored.
        }

        // Pair every range label with its final count for the histogram output.
        return ranges.Select((range, index) => (Range: range.Label, Count: counts[index])).ToList();
    }

    public static void Main()
    {
        // Run the exact verified example shown in the diagram.
        int[] comments = { 0, 5, 7, 12, 20, 45, 55, 70, 99, 100, 150, 250, 499, 500, 501, 1200 };

        List<(string Range, int Count)> histogram = BuildHistogram(comments);
        int total = 0;

        // Print the same five ranges and counts shown in the diagram.
        foreach ((string range, int count) in histogram)
        {
            Console.WriteLine($"{range}: {count}");
            total += count;
        }

        // All 16 example values are non-negative, so every one is counted.
        Console.WriteLine($"Total: {total}");
    }
}

Time & Space Complexity

Let n be the number of comment values and k be the number of histogram ranges. The shown code checks up to k ranges for each of the n values, so its time complexity is O(n * k). With five fixed buckets, this behaves like linear work in the number of comments, but the general nested-loop implementation is O(n * k). The counts array stores one integer per range, so it uses O(k) auxiliary space. The range definitions also contain k entries.

Where it is used

This pattern is useful when software must group numeric measurements into reporting bands. Examples include comment-count analytics, request-latency ranges, order-value ranges, user-activity levels, score bands, and monitoring dashboards. The important part is defining ranges that do not overlap and deciding clearly whether each boundary is inclusive or exclusive.

Why Interviewers Ask This

This question checks whether you can turn a reporting requirement into precise numeric boundaries. The interviewer can see whether you avoid gaps and overlaps, handle boundary values correctly, maintain a simple counting invariant, and keep the code consistent with the explanation. It also tests whether you can distinguish the number of input values from the number of buckets and give the correct O(n * k) time and O(k) auxiliary-space analysis for the shown implementation.

Common interview mistakes

A common mistake is creating overlapping ranges, which can make one value belong to more than one bucket. Another mistake is leaving gaps between boundaries, such as ending one bucket at 9 and starting the next at 11. Candidates may also mix inclusive and exclusive boundary rules without explaining them. Forgetting to break after a match can count a value more than once if the configured ranges overlap. Another mistake is claiming O(n) for the general nested-loop implementation instead of O(n * k). Negative values also need an explicit decision because the shown ranges begin at zero.

Interview tip

State the boundary rule before writing the loop. Say that the finite bucket boundaries are inclusive, the ranges are ordered with no gaps or overlaps, and the first matching bucket is incremented once. Then walk through boundary values such as 9, 10, 49, 50, 499, and 500 because those values quickly show that the ranges are defined correctly.

Interviewer may ask next

How would you change the solution if there were hundreds or thousands of ordered ranges?

The current code scans up to k ranges for every value, giving O(n * k) time. If the ranges stay ordered and non-overlapping, I could binary-search their boundaries instead of checking every range. For each value, I would find the candidate range in O(log k), verify that the value belongs to it, and increment that bucket. This preserves correctness because the ranges are ordered and non-overlapping. The new time complexity is O(n log k), and the counting space remains O(k). The tradeoff is more complex boundary-search code.

How would you handle negative comment counts?

The shown histogram starts at zero, so negative values currently match no bucket and are ignored. If negative values are valid input, I would add a clearly defined negative bucket before [0, 9], for example [long.MinValue, -1]. The same loop and invariant still work because the ranges remain ordered and non-overlapping. The time complexity stays O(n * k), and auxiliary space stays O(k), with k increased by one. The tradeoff is that the output contract now contains an additional range.

6. Employee SalariesCodingEasyMeta

Question Details

Return the salary result requested by the prompt and state how department or ranking filters affect the output.

Short Interview Answer (30-60 seconds)

I would first filter the employees by the requested department and allowed ranks. In the diagram example, I keep only Engineering employees whose rank is Senior or Lead. That leaves Alice with 120000 and Frank with 150000. I then average those salaries, which gives 135000. The department and rank filters decide which rows contribute to the calculation. The solution takes O(n) time and O(1) auxiliary space because the LINQ pipeline processes the filtered values without building another collection.

Detailed Explanation

See the Code while reading this explanation.

The problem asks us to return a salary result after applying the requested employee filters. In the diagram, we need the average salary for the Engineering department and for employees whose rank is Senior or Lead. We first remove employees from other departments. Then we remove employees whose rank is not allowed. Only the remaining salaries are used in the average. Alice has 120000 and Frank has 150000, so the final result is 135000. If no rows remain after filtering, this implementation returns 0.

Useful Questions to Ask the Interviewer

Which salary operation is required, such as average, sum, minimum, maximum, or count?
Should the department comparison ignore letter case?
Which rank values should be treated as matching the requested ranking filter?
What should be returned when no employee matches the filters?

How to Explain It in an Interview

1. Understand the input and required output

The input is a sequence of Employee objects, a department string, and a HashSet<string> containing the allowed ranks. Each employee has an ID, name, department, rank, and nullable salary. The shown task asks for the average salary after the filters are applied. For the example, the department is Engineering and the allowed ranks are Senior and Lead. The expected output is 135000.

2. Apply the department and rank filters

We start with all six employees. The department filter keeps employee IDs 101, 102, 103, and 106 because they are in Engineering. The rank filter then keeps only IDs 101 and 106 because their ranks are Senior and Lead. The code also requires a non-empty department, a non-empty rank, and a non-null salary before that salary can contribute to the result.

3. Walk through the example

The original rows are Alice 120000 Senior, Bob 90000 Mid, Carol 60000 Junior, David 80000 Senior in HR, Eva 70000 Mid in HR, and Frank 150000 Lead. Filtering by Engineering removes David and Eva. Filtering by the allowed rank set removes Bob and Carol. The remaining salary values are 120000 and 150000. Their average is (120000 + 150000) / 2 = 135000.

4. Compute and return the salary result

After filtering, Select extracts each remaining non-null salary as a decimal value. Any checks whether at least one matching salary exists. When values exist, Average calculates their arithmetic mean. When no value remains, the method returns 0m. For the verified example, the returned decimal value is 135000.

5. Explain why the result is correct

The invariant is that every salary passed to Average belongs to an employee who satisfies every active filter. The department must match Engineering, the rank must be Senior or Lead, and the salary must have a value. Therefore only Alice and Frank contribute to the example result. Their salaries are 120000 and 150000, so 135000 is the correct average.

6. Explain the C# implementation

The C# method builds a lazy LINQ pipeline. Where applies the department, rank, and non-null salary checks. HashSet<string>.Contains tests whether the employee rank is allowed. Select extracts the decimal salary value. Any checks whether the filtered sequence contains a value. If it does, Average calculates the result. Otherwise the method returns 0m. Main creates the same six employees shown in the diagram and produces 135000.

7. Explain complexity and edge cases

The filtering and aggregation work is O(n), where n is the number of employees. HashSet membership is O(1) on average. The query is lazy and does not build a separate list, so the shown method uses O(1) auxiliary space, excluding the input sequence and supplied rank set. Relevant edge cases are no matching employees, null salaries, one matching employee, and an empty allowed-rank set.

Key Insight / Why This Solution Works

The key idea is to reduce the employee sequence to only the rows that are allowed to affect the requested salary calculation. The method uses LINQ filtering and a HashSet<string> containing the permitted ranks. The central invariant is that every salary reaching Average belongs to an employee whose department matches the requested department, whose rank belongs to the allowed-rank set, and whose salary is not null. This matches the diagram because the department and ranking filters directly control which salaries contribute to the final aggregate. HashSet membership is O(1) on average.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Employee
{
    public int EmpId { get; set; }
    public string Name { get; set; } = string.Empty;
    public string Department { get; set; } = string.Empty;
    public string Rank { get; set; } = string.Empty;
    public decimal? Salary { get; set; }
}

public static class Program
{
    public static decimal GetDepartmentAverageSalaryByRank(IEnumerable<Employee> employees,
                                                           string department,
                                                           HashSet<string> allowedRanks)
    {
        // Keep only employees that satisfy both requested filters and have a salary.
        IEnumerable<decimal> filteredSalaries =
            employees
                .Where(employee => !string.IsNullOrEmpty(employee.Department) &&
                                   employee.Department.Equals(department,
                                                              StringComparison.OrdinalIgnoreCase) &&
                                   !string.IsNullOrEmpty(employee.Rank) &&
                                   allowedRanks.Contains(employee.Rank) && employee.Salary.HasValue)
                // Salary.Value is safe here because the Where condition checked HasValue.
                .Select(employee => employee.Salary.Value);

        // The diagram defines 0 as the result when no employee survives the filters.
        if (!filteredSalaries.Any())
        {
            return 0m;
        }

        // Average only the salaries that passed both the department and rank filters.
        return filteredSalaries.Average();
    }

    public static void Main()
    {
        // Build the exact six-row employee example shown in the diagram.
        Employee[] employees = {
            new Employee { EmpId = 101, Name = "Alice", Department = "Engineering", Rank = "Senior",
                           Salary = 120000m },
            new Employee { EmpId = 102, Name = "Bob", Department = "Engineering", Rank = "Mid",
                           Salary = 90000m },
            new Employee { EmpId = 103, Name = "Carol", Department = "Engineering", Rank = "Junior",
                           Salary = 60000m },
            new Employee { EmpId = 104, Name = "David", Department = "HR", Rank = "Senior",
                           Salary = 80000m },
            new Employee { EmpId = 105, Name = "Eva", Department = "HR", Rank = "Mid",
                           Salary = 70000m },
            new Employee { EmpId = 106, Name = "Frank", Department = "Engineering", Rank = "Lead",
                           Salary = 150000m }
        };

        // The ranking filter accepts exactly the Senior and Lead ranks in this example.
        HashSet<string> allowedRanks =
            new HashSet<string>(new[] { "Senior", "Lead" }, StringComparer.OrdinalIgnoreCase);

        // Apply the Engineering department filter and the allowed-rank filter.
        decimal result = GetDepartmentAverageSalaryByRank(employees, "Engineering", allowedRanks);

        // Alice and Frank remain: (120000 + 150000) / 2 = 135000.
        Console.WriteLine(result);
    }
}

Time & Space Complexity

Let n be the number of employees. The method runs in O(n) time because it examines the employee sequence while applying the filters and calculating the average. HashSet<string>.Contains is O(1) on average for each rank check. The LINQ pipeline is lazy, so it does not create another collection containing all matching employees or salaries. The method therefore uses O(1) auxiliary space, excluding the input employee sequence and the already supplied allowed-rank HashSet. Any and Average may enumerate the filtered sequence separately, but the total asymptotic running time is still O(n).

Where it is used

This filtering-and-aggregation pattern is common in payroll systems, reporting tools, dashboards, and business APIs. A program can first restrict records by fields such as department and job rank, then calculate an aggregate such as average salary. A HashSet is useful when a record should be accepted only when one of its values belongs to a known set of allowed values.

Why Interviewers Ask This

This problem checks whether a candidate can translate business filtering rules into correct C# collection operations. The interviewer can evaluate whether the candidate understands how department and rank conditions affect an aggregate, handles nullable salary values, uses a HashSet correctly for membership tests, defines empty-result behavior, and explains the O(n) time and O(1) auxiliary-space costs of the shown lazy LINQ solution accurately.

Common interview mistakes

A common mistake is applying only the department filter and accidentally including Bob and Carol in the average. Another mistake is treating the text "Senior or higher" as an automatic string comparison instead of using the allowed-rank set shown in the diagram. A candidate may also include HR employees, forget to exclude null salary values before taking Average, or forget that Average on an empty sequence would throw. Another mistake is claiming that the supplied HashSet makes the method use O(n) auxiliary space even though that set is already an input.

Interview tip

Explain the filters with the actual employee IDs. Engineering first leaves 101, 102, 103, and 106. The Senior and Lead rank filter then leaves 101 and 106. After that, show the calculation (120000 + 150000) / 2 = 135000. This makes the effect of both filters easy for the interviewer to verify.

Interviewer may ask next

What changes if the prompt asks for the average salary of all Engineering employees with no rank filter?

Remove the allowed-rank condition from the Where predicate. Keep the Engineering department check and the non-null salary check. Alice, Bob, Carol, and Frank would then contribute to the average. Correctness is preserved because every remaining salary still belongs to the requested department. The running time remains O(n), and the auxiliary space remains O(1) for the lazy LINQ pipeline.

What changes if the allowed rank set is empty?

With the shown implementation, allowedRanks.Contains(employee.Rank) is false for every employee, so no salary survives the filters. The method therefore returns 0m. No different algorithm is required. The running time remains O(n), HashSet membership remains O(1) on average, and the method still uses O(1) auxiliary space beyond its inputs.

7. Like TrackerCodingMediumMeta

Question Details

Track like activity over time and explain how you aggregate repeated likes by the same user.

Short Interview Answer (30-60 seconds)

I would group likes by post and time window, then keep a HashSet of user IDs for each group. For every like event, I compute its hour window, find or create the set for that post and hour, and add the user. HashSet.Add ignores a repeated user, so repeated likes in the same window do not increase the count. Each event is O(1) average time, so n events take O(n) expected time. Auxiliary space grows with the stored unique users.

Detailed Explanation

See the Code while reading this explanation.

The goal is to track how many different users liked each post during each time window. A user may like the same post more than once. Those repeated likes should count only once inside the same window. The diagram uses one-hour windows. For every pair of post ID and hour, we keep the set of users who liked that post during that hour. The size of the set is the aggregated like count. This directly implements the repeated-like rule in the diagram.

Useful Questions to Ask the Interviewer

What time window should we use, such as one minute, one hour, or one day?
Should the same user count again when they like the same post in a different time window?
How long should completed time windows be retained?

How to Explain It in an Interview

1. Understand the input and required output

Each like event contains a postId, userId, and UTC timestamp. We need the number of unique users who liked each post during each time window. In the diagram, the window is one hour. Repeated likes from the same user for the same post during the same hour count only once.

The example processes these events in arrival order:

p1, u1, 2025-05-01 10:05 UTC
p1, u1, 2025-05-01 10:07 UTC
p1, u2, 2025-05-01 10:15 UTC
p1, u3, 2025-05-01 10:20 UTC
p1, u2, 2025-05-01 10:50 UTC
p1, u1, 2025-05-01 11:05 UTC
p2, u1, 2025-05-01 10:10 UTC
p2, u1, 2025-05-01 10:20 UTC
p2, u2, 2025-05-01 10:25 UTC

The final aggregated values are p1 from 10:00 to 10:59 = 3 unique users {u1, u2, u3}, p1 from 11:00 to 11:59 = 1 unique user {u1}, and p2 from 10:00 to 10:59 = 2 unique users {u1, u2}.

2. Choose the data structure

The diagram uses a ConcurrentDictionary whose key is (postId, window) and whose value is a HashSet<string>. The dictionary key identifies one post and one hour. The HashSet stores the unique users already counted for that post and hour. ConcurrentDictionary safely handles concurrent access to the dictionary itself. Because HashSet is mutable and is not thread-safe, accesses to each set that can race with a writer are protected with a lock in the corrected implementation.

The central invariant is that each set contains each user at most once for its exact post and time window. Therefore, the size of that set is the unique-like count for the key.

3. Initialize and process each event

For each event, convert the UTC timestamp to Unix seconds and divide by the one-hour window size. This produces the hour bucket. Combine postId and the bucket into the dictionary key. GetOrAdd returns the existing HashSet or creates a new one. Lock that set and call Add(userId). HashSet.Add changes the set only when the user is not already present.

4. Walk through the example

Event 1 is p1, u1 at 10:05. The key for p1 and the 10:00 hour does not yet have a set, so a set is created and u1 is added. State after the event: {u1}. Count = 1.

Event 2 is p1, u1 at 10:07. The same key is found. u1 is already in its set, so HashSet.Add leaves the set unchanged. State after the event: {u1}. Count = 1.

Event 3 is p1, u2 at 10:15. u2 is new for that key, so it is added. State after the event: {u1, u2}. Count = 2.

Event 4 is p1, u3 at 10:20. u3 is new, so it is added. State after the event: {u1, u2, u3}. Count = 3.

Event 5 is p1, u2 at 10:50. u2 is already present. State stays {u1, u2, u3}. Count = 3.

Event 6 is p1, u1 at 11:05. This event belongs to a different hour, so a new key is used. Its set becomes {u1}. Count = 1.

Event 7 is p2, u1 at 10:10. This is a different post, so a different key is used. Its set becomes {u1}. Count = 1.

Event 8 is p2, u1 at 10:20. u1 is already present for p2 in that hour. The set remains {u1}. Count = 1.

Event 9 is p2, u2 at 10:25. u2 is new for that key, so the set becomes {u1, u2}. Count = 2.

5. Explain why the result is correct

Every post-and-window key has its own HashSet. A HashSet does not store the same user ID twice. Therefore, a repeated like by the same user for the same post in the same hour cannot increase that hour's count. A different post or different hour uses a different dictionary key, so the same user can correctly count again there.

6. Explain the C# implementation and complexity

LikeTracker stores a ConcurrentDictionary<(string postId, long window), HashSet<string>> and a one-hour TimeSpan. TrackLike computes the window, uses GetOrAdd to obtain the set, locks that set, and adds the user. GetLikeCount computes the same key and reads the set count while holding the same set lock. Dictionary and HashSet operations are O(1) on average, so one event takes O(1) average time and n events take O(n) expected time. Auxiliary memory grows with retained post-window keys and their unique-user memberships.

Key Insight / Why This Solution Works

The key insight is to make the aggregation key contain both the post and the time window. The structure is (postId, window) -> HashSet<userId>. The HashSet performs deduplication. If a user likes the same post several times in one hour, Add does not create another entry. A different hour or a different post produces another dictionary key, so that user can be counted there. The invariant is that each set contains exactly the unique users seen for its post and window. ConcurrentDictionary protects dictionary operations, and per-set locking protects the mutable HashSet when concurrent calls are possible.

Code

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;

public static class Program
{
    public static void Main()
    {
        LikeTracker tracker = new LikeTracker();

        // Process the exact nine like events from the diagram in arrival order.
        tracker.TrackLike("p1", "u1", Utc(2025, 5, 1, 10, 5));
        tracker.TrackLike("p1", "u1", Utc(2025, 5, 1, 10, 7));
        tracker.TrackLike("p1", "u2", Utc(2025, 5, 1, 10, 15));
        tracker.TrackLike("p1", "u3", Utc(2025, 5, 1, 10, 20));
        tracker.TrackLike("p1", "u2", Utc(2025, 5, 1, 10, 50));
        tracker.TrackLike("p1", "u1", Utc(2025, 5, 1, 11, 5));
        tracker.TrackLike("p2", "u1", Utc(2025, 5, 1, 10, 10));
        tracker.TrackLike("p2", "u1", Utc(2025, 5, 1, 10, 20));
        tracker.TrackLike("p2", "u2", Utc(2025, 5, 1, 10, 25));

        // Query the exact three post-and-hour combinations shown in the diagram.
        Console.WriteLine(
            $"p1 10:00-10:59 => {tracker.GetLikeCount("p1", Utc(2025, 5, 1, 10, 0))}");
        Console.WriteLine(
            $"p1 11:00-11:59 => {tracker.GetLikeCount("p1", Utc(2025, 5, 1, 11, 0))}");
        Console.WriteLine(
            $"p2 10:00-10:59 => {tracker.GetLikeCount("p2", Utc(2025, 5, 1, 10, 0))}");
    }

    private static DateTime Utc(int year, int month, int day, int hour, int minute)
    {
        // Build UTC timestamps so ingestion and queries use one consistent time basis.
        return new DateTime(year, month, day, hour, minute, 0, DateTimeKind.Utc);
    }
}

public sealed class LikeTracker
{
    // Each key identifies one post and one time window.
    // Each value stores the unique users already counted for that key.
    private readonly ConcurrentDictionary<(string PostId, long Window), HashSet<string>> _store =
        new();

    // The diagram uses a one-hour aggregation window.
    private readonly TimeSpan _windowSize = TimeSpan.FromHours(1);

    public void TrackLike(string postId, string userId, DateTime timestampUtc)
    {
        // Convert the UTC event time into the same numeric hour bucket used for all events.
        long window =
            new DateTimeOffset(timestampUtc).ToUnixTimeSeconds() / (long)_windowSize.TotalSeconds;

        (string PostId, long Window) key = (postId, window);

        // Atomically get the set for this post and hour, or create it if this key is new.
        HashSet<string> users = _store.GetOrAdd(key,
                                                _ => new HashSet<string>());

        // HashSet is mutable and not thread-safe, so protect this set during an update.
        // Add returns false for a repeated user, leaving the unique-like count unchanged.
        lock (users)
        {
            users.Add(userId);
        }
    }

    public int GetLikeCount(string postId, DateTime windowStartUtc)
    {
        // Compute the query key with exactly the same window calculation used by TrackLike.
        long window =
            new DateTimeOffset(windowStartUtc).ToUnixTimeSeconds() / (long)_windowSize.TotalSeconds;

        (string PostId, long Window) key = (postId, window);

        // No stored set means no likes were recorded for this post and hour.
        if (!_store.TryGetValue(key, out HashSet<string>? users))
        {
            return 0;
        }

        // Read Count under the same per-set lock so the read cannot race with HashSet mutation.
        lock (users)
        {
            return users.Count;
        }
    }
}

Time & Space Complexity

For each like event, the ConcurrentDictionary lookup or insertion and the HashSet insertion are O(1) on average. Therefore, processing n events takes O(n) expected time. Hash-based operations do not guarantee O(1) in every possible worst case. Auxiliary space grows with the number of retained post-window groups and unique users inside them. Using the diagram's notation, the upper-bound description is O(P × W × U), where P is posts, W is retained windows, and U is unique users per post per window.

Where it is used

This pattern is useful for time-based analytics where duplicate user activity must not inflate a metric. Examples include unique likes per hour, unique reactions per day, unique viewers per time bucket, and similar event-stream counters that group activity by an entity and a time window.

Why Interviewers Ask This

This problem checks whether you can convert an event stream into a correct time-based aggregate. The interviewer can evaluate whether you choose a composite key, use a set to remove repeated user activity, keep different posts and windows separate, and explain hash-based complexity correctly. For C#, it also tests whether you understand that ConcurrentDictionary protects the dictionary but does not automatically make a mutable HashSet value safe for concurrent access.

Common interview mistakes

A common mistake is incrementing a counter for every event, which lets repeated likes inflate the result. Another mistake is deduplicating only by userId instead of by post and window, which would stop a user from being counted correctly for another post or another hour. It is also easy to calculate time buckets differently during writes and reads. Another mistake is treating ConcurrentDictionary as if it automatically made its mutable HashSet values thread-safe. Finally, candidates may incorrectly claim guaranteed O(1) hash operations instead of average O(1).

Interview tip

Before coding, say the mapping aloud: '(postId, hour) maps to the HashSet of users already counted.' Then walk through the second event, where u1 likes p1 again at 10:07, to show exactly why the count stays at 1.

Interviewer may ask next

How would this change if the time bucket were one minute or one day instead of one hour?

The data structure and invariant stay the same. I would change _windowSize so timestamps map to one-minute or one-day buckets. The dictionary would still map (postId, window) to a HashSet of unique users. Correctness is unchanged because each key still represents exactly one post and one window. Each event remains O(1) average time, so n events remain O(n) expected time. Space still grows with retained keys and unique-user memberships. Smaller buckets create more keys, while larger buckets may keep more users in each set.

How would you handle a very large stream where old windows cannot stay in memory forever?

I would keep the same aggregation rule but add a retention policy. When a window is complete and old enough, its unique-like count or snapshot can be persisted, then its in-memory HashSet can be removed. Active events still use the same (postId, window) key and HashSet invariant. Processing remains O(1) average per event and O(n) expected for n events. Memory becomes proportional to the retained active windows and their unique-user memberships. The tradeoff is that older queries may need persisted rollups instead of only memory.

8. Largest Salary by DepartmentCodingMediumMeta

Question Details

Return the top salary per department and clarify how ties among employees are handled.

Short Interview Answer (30-60 seconds)

I would keep one dictionary entry per department. Each entry stores the highest salary seen so far and the selected employee name. For every employee, I add a new department, replace the entry when the salary is higher, or keep the lexicographically smaller name when salaries tie. This works because each department entry always represents its best result so far. The aggregation is O(n) expected time with O(d) extra space, where d is the number of departments.

Detailed Explanation

See the Code while reading this explanation.

We receive employee records with a name, department, and salary. We need one result for each department. That result contains the highest salary and the selected employee name. When two employees in the same department share the highest salary, the diagram chooses the lexicographically smaller name. Alice is chosen over Bob in Engineering. Frank is chosen over Grace in Marketing. A dictionary works well because we only need to remember the best result seen so far for each department.

Useful Questions to Ask the Interviewer

When several employees share the highest salary, should I return all of them or use a deterministic rule such as the lexicographically smallest name?
Does the order of the returned departments matter?

How to Explain It in an Interview

1. Understand the input and required output

The input is a sequence of employee records. Each employee has an Id, Name, Department, and Salary. We return one record per department. Each result contains Department, EmployeeName, and the maximum Salary. When employees tie for that maximum salary, the lexicographically smallest employee name is selected.

The diagram uses these employees:

Alice, Engineering, 120000
Bob, Engineering, 120000
Charlie, Engineering, 110000
David, HR, 90000
Eva, HR, 95000
Frank, Marketing, 85000
Grace, Marketing, 85000
Hank, Marketing, 72000

The final result is Engineering -> Alice, 120000; HR -> Eva, 95000; Marketing -> Frank, 85000.

2. Choose the algorithm and data structure

Use a C# Dictionary. The key is the department name. The value stores two things: the maximum salary seen for that department and the selected employee name.

The invariant is: after every processed employee, each dictionary entry contains the highest salary seen so far for that department. If several processed employees share that salary, the stored name is the lexicographically smallest one.

3. Initialize and process the employees

Start with an empty dictionary.

Alice is the first Engineering employee, so store Engineering -> (120000, Alice).

Bob also has 120000. His salary ties the current maximum. Compare the names. Alice is lexicographically smaller than Bob, so Engineering stays (120000, Alice).

Charlie has 110000. That is below 120000, so Engineering does not change.

David is the first HR employee, so store HR -> (90000, David).

Eva has 95000. That is greater than 90000, so HR becomes (95000, Eva).

Frank is the first Marketing employee, so store Marketing -> (85000, Frank).

Grace also has 85000. This is a tie. Frank is lexicographically smaller than Grace, so Marketing stays (85000, Frank).

Hank has 72000. That is below 85000, so Marketing does not change.

4. Explain the tie rule

A tie matters only when the new salary equals the stored maximum salary. In that case, compare the current employee name with the stored name. If the current employee name is lexicographically smaller, replace the stored name. The maximum salary stays the same.

This rule selects Alice instead of Bob and Frank instead of Grace.

5. Explain why the result is correct

For each department, a higher salary always replaces the previous maximum. A lower salary cannot improve the answer. An equal salary can only change the selected employee when the new name is lexicographically smaller. Therefore, after all employees are processed, every dictionary entry contains the correct maximum salary and the correct employee under the tie rule.

6. Explain the C# implementation

The code creates a Dictionary<string, (decimal Salary, string Name)>. It processes every employee once. TryGetValue reads the current result for the employee's department. A new department creates a new entry. A higher salary replaces the entry. An equal salary uses StringComparison.Ordinal and keeps the lexicographically smaller name. Finally, the dictionary entries are converted to TopSalaryResult objects and ordered by department for deterministic output.

7. Explain complexity and edge cases

Let n be the number of employees and d be the number of departments. Dictionary lookup and update are O(1) on average, so building the dictionary takes O(n) expected time. The final OrderBy over d department results adds O(d log d), so the complete executable implementation takes O(n + d log d) expected time. The dictionary uses O(d) auxiliary space.

Relevant edge cases are an empty employee list, one employee in a department, several departments, all salaries being unique, multiple employees sharing the highest salary, and very large or very small salary values that still fit in decimal.

Key Insight / Why This Solution Works

The key idea is to keep only the current best result for each department. The dictionary key is the department. Its value stores the maximum salary and selected employee name. The invariant is that after every employee is processed, each stored department contains the highest salary seen so far and the lexicographically smallest employee name among employees tied at that salary. A higher salary replaces the stored tuple. An equal salary can replace only the name. A lower salary does nothing. This avoids rescanning previous employees for every department.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public sealed class Employee
{
    public int Id { get; set; }
    public string Name { get; set; } = string.Empty;
    public string Department { get; set; } = string.Empty;
    public decimal Salary { get; set; }
}

public sealed class TopSalaryResult
{
    public string Department { get; set; } = string.Empty;
    public string EmployeeName { get; set; } = string.Empty;
    public decimal Salary { get; set; }
}

public static class Program
{
    public static List<TopSalaryResult> GetTopSalaryByDepartment(IEnumerable<Employee> employees)
    {
        // Store one current winner for each department.
        // Each value contains the maximum salary seen and the selected employee name.
        Dictionary<string, (decimal Salary, string Name)> bestByDepartment = new();

        foreach (Employee employee in employees)
        {
            // A new department starts with the current employee as its best result.
            if (!bestByDepartment.TryGetValue(employee.Department,
                                              out(decimal Salary, string Name) current))
            {
                bestByDepartment[employee.Department] = (employee.Salary, employee.Name);
            }
            // A higher salary becomes the new maximum for this department.
            else if (employee.Salary > current.Salary)
            {
                bestByDepartment[employee.Department] = (employee.Salary, employee.Name);
            }
            // On a salary tie, keep the lexicographically smaller employee name.
            // Ordinal comparison gives a deterministic character-by-character rule.
            else if (employee.Salary == current.Salary &&
                     string.Compare(employee.Name, current.Name, StringComparison.Ordinal) < 0)
            {
                bestByDepartment[employee.Department] = (employee.Salary, employee.Name);
            }
            // A lower salary, or a tied salary with a larger name, needs no update.
        }

        // Convert the final dictionary state into output records.
        // Sort by department so the displayed result order is deterministic.
        return bestByDepartment
            .Select(entry => new TopSalaryResult { Department = entry.Key,
                                                   EmployeeName = entry.Value.Name,
                                                   Salary = entry.Value.Salary })
            .OrderBy(result => result.Department, StringComparer.Ordinal)
            .ToList();
    }

    public static void Main()
    {
        // Use the exact employee example shown in the diagram.
        List<Employee> employees = new() {
            new Employee { Id = 1, Name = "Alice", Department = "Engineering", Salary = 120000m },
            new Employee { Id = 2, Name = "Bob", Department = "Engineering", Salary = 120000m },
            new Employee { Id = 3, Name = "Charlie", Department = "Engineering", Salary = 110000m },
            new Employee { Id = 4, Name = "David", Department = "HR", Salary = 90000m },
            new Employee { Id = 5, Name = "Eva", Department = "HR", Salary = 95000m },
            new Employee { Id = 6, Name = "Frank", Department = "Marketing", Salary = 85000m },
            new Employee { Id = 7, Name = "Grace", Department = "Marketing", Salary = 85000m },
            new Employee { Id = 8, Name = "Hank", Department = "Marketing", Salary = 72000m }
        };

        // Run the aggregation and obtain one selected employee per department.
        List<TopSalaryResult> results = GetTopSalaryByDepartment(employees);

        // Print the final department, employee, and top salary values.
        foreach (TopSalaryResult result in results)
        {
            Console.WriteLine($"{result.Department}: {result.EmployeeName} - {result.Salary}");
        }
    }
}

Time & Space Complexity

Let n be the number of employees and d be the number of departments. The aggregation processes each employee once. Dictionary lookup and update are O(1) on average, so that part takes O(n) expected time. The executable code then sorts the d department results with OrderBy, which adds O(d log d). Therefore, the complete implementation takes O(n + d log d) expected time. The dictionary stores one entry per department, so auxiliary space is O(d).

Where it is used

This pattern is useful when software needs one best record for each group. Examples include the highest sale per store, the largest transaction per account, the best score per team, or the latest record per device. A dictionary lets the program update the current best value for one group without repeatedly scanning all earlier records.

Why Interviewers Ask This

This problem tests whether a candidate can group records while keeping only the information needed for each group. It checks Dictionary usage, state updates, and careful handling of equal maximum values. The tie rule tests attention to deterministic behavior. In C#, the interviewer can also evaluate tuple or result modeling, string comparison, expected hash-table complexity, output ordering, edge cases, and whether the explanation matches the implementation.

Common interview mistakes

A common mistake is replacing the stored employee on every salary tie instead of keeping the lexicographically smaller name. Another mistake is returning every tied employee, which does not match the diagram's tie rule. Candidates may also forget to replace the stored name when a higher salary becomes the new maximum. Using a different string comparison rule can make tie handling inconsistent. Another mistake is claiming guaranteed O(1) Dictionary operations. They are O(1) on average. Finally, if the returned results are sorted with OrderBy, that sorting cost must be included in the complete implementation's complexity.

Interview tip

State the dictionary invariant before writing code: for each department, the dictionary always stores the highest salary seen so far and the lexicographically smallest employee name among employees tied at that salary. Then make each code branch directly maintain that invariant.

Interviewer may ask next

What changes if every employee tied for the highest salary must be returned?

Store the maximum salary and a list of employee names for each department. A higher salary replaces the maximum and resets the list to the current employee. An equal salary appends the current employee. A lower salary does nothing. This preserves the invariant that the list contains exactly the employees tied at the current maximum. The scan remains O(n) expected time, plus output work. Space becomes O(d + t), where t is the number of stored tied employees. If the final department results are still sorted, add O(d log d) time.

How would the solution change if employees arrived as a stream?

The aggregation logic does not change. Keep the same dictionary in memory and update the matching department entry whenever a new employee arrives. The invariant remains true after every record. Each update is O(1) expected time, so processing n streamed employees is O(n) expected time. The dictionary still uses O(d) space. The main tradeoff is that the answer remains provisional until the stream ends, although the dictionary always represents the best results seen so far.

9. Threaded CommentsCodingMediumMeta

Question Details

Reconstruct threaded comment structure from parent-child links and explain how you order siblings.

Short Interview Answer (30-60 seconds)

I would rebuild the threads in two passes. First, I create one node for every comment and store it in a dictionary by Id. Then I attach each node either to its parent's Replies list or to the roots list. After linking, I sort every Replies list and the roots by CreatedAt ascending, then Id ascending. This works because every comment becomes one node and every non-root gets one parent link. The total expected time is O(n log n), dominated by sorting, and auxiliary space is O(n).

Detailed Explanation

See the Code while reading this explanation.

The input is a flat list of comments. Each comment has an Id, an optional ParentId, an author, text, and a creation time. The goal is to rebuild the reply structure. A comment with no ParentId is a top-level comment. A comment with a ParentId becomes a reply to that parent. The final result is a list of top-level comments. Each comment contains its ordered replies. Siblings are ordered by CreatedAt from earliest to latest, then by Id when creation times are equal.

Useful Questions to Ask the Interviewer

Can I assume every comment Id is unique?
Can I assume every non-null ParentId refers to a comment in the input?
Can the input comments arrive in any order?

How to Explain It in an Interview

1. Understand the input and required output

The input is one flat collection of comments. In the diagram, comment 1 is Alice at 10:00, comment 2 is Bob at 10:01 with ParentId 1, comment 3 is Carol at 10:02 with ParentId 1, comment 4 is Dave at 10:03 with ParentId 2, comment 5 is Eve at 10:04 with no parent, comment 6 is Frank at 10:05 with ParentId 2, and comment 7 is Grace at 10:06 with ParentId 5. The output is a list of root comments. Each root contains its replies, and those replies may contain more replies.

2. Choose the algorithm and data structure

I use a Dictionary<int, Comment>. The key is a comment Id. The value is the node created for that comment. This lets me find a parent by Id in O(1) average time. The central invariant is that after the first pass, every input Id maps to exactly one created node.

3. Build all nodes first

I first create a fresh node for every input comment and put it in the dictionary. At this point, every Replies list is empty. Building every node before linking is important because the input may be unordered, so a child can appear before its parent. After this pass, the dictionary contains nodes for Ids 1 through 7.

4. Attach each node to its parent or to roots

I then iterate over all created nodes. If ParentId is null, I add the node to roots. In the example, nodes 1 and 5 become roots. If ParentId has a value, I find that parent in the dictionary and append the node to the parent's Replies list. Nodes 2 and 3 go under node

Nodes 4 and 6 go under node
Node 7 goes under node 5.

5. Order siblings and roots

After all links exist, I sort each node's Replies list by CreatedAt ascending. If two comments have the same time, I compare Id ascending. I use the same comparison for the roots. For the example, root 1 at 10:00 comes before root 5 at 10:04. Under root 1, Bob at 10:01 comes before Carol at 10:02. Under Bob, Dave at 10:03 comes before Frank at 10:05.

6. Verify the final result

The final structure has root 1, Alice. Its replies are Bob and Carol. Bob's replies are Dave and Frank. The second root is 5, Eve. Eve's reply is Grace. This is correct because every comment appears once, every non-root is attached through its ParentId, and every sibling list follows the same CreatedAt-then-Id ordering rule.

7. Explain complexity and edge cases

Creating nodes and linking them uses Dictionary operations, which are O(1) on average per lookup or insertion. That part takes expected O(n) time. Sorting all child lists and the roots costs O(n log n) in the worst case for sorting, so the total expected time is O(n log n). Auxiliary space is O(n) for the dictionary, created nodes, roots, and reply references. Relevant cases shown in the diagram are empty input, all comments being roots, deep nesting without recursive sorting, equal timestamps using Id as the tie-breaker, and large inputs.

Key Insight / Why This Solution Works

The key insight is to separate node creation from parent linking. If I try to attach a child before every node exists, its parent may not have been created yet because the input can be unordered. The first pass therefore creates every node and stores Id -> node in a dictionary. The second pass links each non-root node to its parent and puts ParentId-null nodes in roots. The invariant is that each input Id maps to exactly one node. After linking, sorting each Replies list and roots by CreatedAt and then Id gives the deterministic hierarchy shown in the diagram.

Code

using System;
using System.Collections.Generic;

public sealed class Comment
{
    public int Id { get; set; }
    public int? ParentId { get; set; }
    public string Author { get; set; } = "";
    public string Text { get; set; } = "";
    public DateTime CreatedAt { get; set; }

    // Stores this comment's direct child comments.
    public List<Comment> Replies { get; } = new();
}

public static class Program
{
    public static List<Comment> BuildThreadedComments(IEnumerable<Comment> comments)
    {
        // First pass: create every node before linking parents and children.
        // This makes the algorithm independent of the input order.
        Dictionary<int, Comment> idToNode = new();

        foreach (Comment c in comments)
        {
            // Create a fresh node with an empty Replies list.
            idToNode[c.Id] = new Comment { Id = c.Id, ParentId = c.ParentId, Author = c.Author,
                                           Text = c.Text, CreatedAt = c.CreatedAt };
        }

        // ParentId == null means the node is a top-level comment.
        List<Comment> roots = new();

        // Second pass: attach every non-root node to its parent.
        foreach (Comment node in idToNode.Values)
        {
            if (node.ParentId is int parentId)
            {
                // The problem setup assumes a non-null ParentId refers to an existing node.
                idToNode[parentId].Replies.Add(node);
            }
            else
            {
                // Keep top-level comments in the roots list.
                roots.Add(node);
            }
        }

        // Order siblings by CreatedAt ascending, then Id ascending for equal times.
        static int Compare(Comment a, Comment b)
        {
            int byTime = a.CreatedAt.CompareTo(b.CreatedAt);
            return byTime != 0 ? byTime : a.Id.CompareTo(b.Id);
        }

        // Sort every node's direct Replies list using the same ordering rule.
        foreach (Comment node in idToNode.Values)
        {
            node.Replies.Sort(Compare);
        }

        // Sort the top-level comments with the same comparison.
        roots.Sort(Compare);
        return roots;
    }

    public static void Main()
    {
        // Exact example shown in the diagram.
        List<Comment> comments = new() { new Comment { Id = 1, ParentId = null, Author = "Alice",
                                                       Text = "Post", CreatedAt = At(10, 0) },
                                         new Comment { Id = 2, ParentId = 1, Author = "Bob",
                                                       Text = "Nice post!", CreatedAt = At(10, 1) },
                                         new Comment { Id = 3, ParentId = 1, Author = "Carol",
                                                       Text = "Thanks!", CreatedAt = At(10, 2) },
                                         new Comment { Id = 4, ParentId = 2, Author = "Dave",
                                                       Text = "I agree", CreatedAt = At(10, 3) },
                                         new Comment { Id = 5, ParentId = null, Author = "Eve",
                                                       Text = "Great read", CreatedAt = At(10, 4) },
                                         new Comment { Id = 6, ParentId = 2, Author = "Frank",
                                                       Text = "Me too", CreatedAt = At(10, 5) },
                                         new Comment { Id = 7, ParentId = 5, Author = "Grace",
                                                       Text = "Indeed", CreatedAt = At(10, 6) } };

        List<Comment> roots = BuildThreadedComments(comments);

        // Print the same hierarchy that the diagram returns.
        PrintTree(roots);
    }

    private static DateTime At(int hour, int minute)
    {
        // A fixed date is enough because only the ordering of the shown times matters.
        return new DateTime(2026, 1, 1, hour, minute, 0, DateTimeKind.Unspecified);
    }

    private static void PrintTree(List<Comment> roots)
    {
        // Use a stack only for displaying the already-built tree without recursion.
        Stack<(Comment Node, int Depth)> stack = new();

        // Push roots in reverse so the smallest sorted root is printed first.
        for (int i = roots.Count - 1; i >= 0; i--)
        {
            stack.Push((roots[i], 0));
        }

        while (stack.Count > 0)
        {
            (Comment node, int depth) = stack.Pop();

            // Display each node with the Id, author, and time from the diagram.
            Console.WriteLine(
                $"{new string(' ', depth * 2)}{node.Id} ({node.Author}) {node.CreatedAt:HH:mm}");

            // Push replies in reverse so they are printed in their sorted order.
            for (int i = node.Replies.Count - 1; i >= 0; i--)
            {
                stack.Push((node.Replies[i], depth + 1));
            }
        }
    }
}

Time & Space Complexity

Let n be the number of comments. Creating the nodes and linking parents uses Dictionary lookups and insertions, which are O(1) on average, so those phases take expected O(n) time. Sorting every Replies list plus the roots costs O(n log n) in the worst case for sorting. Therefore, the total expected time is O(n log n), with sorting as the dominant cost. Auxiliary space is O(n) for the dictionary, created nodes, reply references, and root list. The construction and sorting do not require recursion.

Where it is used

This pattern is useful when software stores hierarchical data as flat records with parent IDs. Examples include threaded comments, discussion replies, category trees, folder-like structures, and other parent-child views. The dictionary gives fast parent lookup, while the final sorting phase gives a predictable order for siblings.

Why Interviewers Ask This

This problem checks whether the candidate can convert flat parent-child records into a hierarchy without losing node relationships. It also tests choosing a dictionary for fast parent lookup, separating construction from ordering, using a deterministic sibling comparison, writing correct C#, and explaining complexity accurately. The interviewer can also see whether the candidate notices nullable ParentId, understands average Dictionary lookup cost, and includes the O(n log n) sorting cost instead of claiming the whole solution is O(n).

Common interview mistakes

Common mistakes are trying to link a child before all nodes have been created, forgetting to put ParentId-null comments in the roots list, sorting roots but forgetting to sort every Replies list, sorting only by CreatedAt and forgetting the Id tie-breaker, treating an unknown parent as a root even though that behavior is not part of the shown solution, and claiming O(n) total time while ignoring the sorting cost.

Interview tip

Explain the solution as three phases: create every node, link parents and children, then sort replies and roots. This makes it easy to show why unordered input is safe and why the final hierarchy has deterministic sibling ordering.

Interviewer may ask next

What happens if two sibling comments have the same CreatedAt value?

The algorithm keeps the same structure and compares Id ascending as the tie-breaker. It first compares CreatedAt. Only when those values are equal does it compare Id. This gives a deterministic sibling order without changing any parent-child relationship. The total expected time remains O(n log n), and auxiliary space remains O(n).

How would the solution handle a very large input?

The same two-pass approach still works because each node is created once and linked once. The dictionary keeps parent lookup O(1) on average. The main memory cost remains O(n) because all nodes and the Id-to-node mapping must be available to handle arbitrary input order. Sorting remains O(n log n) in the worst case for sorting. The tradeoff is that this approach uses linear extra memory in exchange for simple and fast parent lookup.

10. Friendship TimelineCodingMediumMeta

Question Details

Build a chronological view of friendship events and describe how you treat accepts, removals, and duplicates.

Short Interview Answer (30-60 seconds)

I would first sort the friendship events by timestamp, keeping the original input order when timestamps are equal. For each event, I normalize the two users into one unordered pair, such as (min(u,v), max(u,v)). A dictionary stores whether that pair is currently Active or Removed. I record only state-changing accepts and removals, so duplicates are ignored. Sorting takes O(n log n), processing is O(n) expected, and auxiliary space is O(n).

Detailed Explanation

See the Code while reading this explanation.

We receive friendship events between two users. Each event contains a time, an event type, and two user IDs. The event is either ACCEPT or REMOVE. We need to return a chronological timeline containing only events that really change friendship state. An ACCEPT creates or recreates the friendship only when it is not already Active. A REMOVE is recorded only when the friendship is Active. Repeated events that leave the state unchanged are ignored. We sort by time and use one stored state for each unordered pair.

Useful Questions to Ask the Interviewer

If two events have the same timestamp, should their original input order be preserved?
Should (u, v) and (v, u) represent the same friendship?
Should repeated accepts and removals that do not change state be excluded from the returned timeline?

How to Explain It in an Interview

1. Understand the input and output

The input is a list of friendship events. Each event has a timestamp, a type, and two user IDs. The type is ACCEPT or REMOVE. The output is the chronological list of meaningful state changes only. The friendship itself is unordered, so pair (1,2) and pair (2,1) share one state.

2. Sort events and choose the state structure

First, sort events by timestamp in ascending order. When timestamps are equal, keep the original input order. Use a dictionary keyed by the normalized pair (min(u,v), max(u,v)). The value is the current friendship state, either Active or Removed. The important invariant is that, before each event is processed, the dictionary represents the state produced by all earlier sorted events.

3. Apply the ACCEPT and REMOVE rules

For an ACCEPT, check the current pair state. If it is not Active, record the event and set the state to Active. If it is already Active, the event changes nothing, so ignore it. For a REMOVE, record the event only when the pair is currently Active. Then set the state to Removed. If the pair is already Removed or has never been Active, ignore that REMOVE.

4. Walk through the verified example

The unsorted events are (5, ACCEPT, 1, 2), (3, ACCEPT, 1, 2), (8, REMOVE, 1, 2), (10, REMOVE, 1, 2), (6, ACCEPT, 1, 2), and (7, ACCEPT, 2, 3).

After sorting, the timestamps are 3, 5, 6, 7, 8, and 10.

At time 3, pair (1,2) has no Active state. Record ACCEPT and set (1,2) to Active.

At time 5, pair (1,2) is already Active. Ignore this duplicate ACCEPT. The state stays Active.

At time 6, pair (1,2) is still Active. Ignore this duplicate ACCEPT. The state stays Active.

At time 7, pair (2,3) is not Active. Record ACCEPT and set (2,3) to Active.

At time 8, pair (1,2) is Active. Record REMOVE and set (1,2) to Removed.

At time 10, pair (1,2) is already Removed. Ignore this duplicate REMOVE. The state stays Removed.

The returned timeline is [(3, ACCEPT, 1, 2), (7, ACCEPT, 2, 3), (8, REMOVE, 1, 2)].

5. Explain why the result is correct

The dictionary always represents the state after all earlier sorted events. We append an event only when it changes that state. Therefore repeated accepts and repeated removals cannot create duplicate timeline entries. Because we process events in chronological order, the events that are appended are already in chronological order.

6. Explain the C# implementation

The code attaches every event to its original position. OrderBy sorts by timestamp, and ThenBy uses that original position as the tie-breaker. Math.Min and Math.Max normalize the dictionary key. TryGetValue reads the previous state. The ACCEPT branch records the event only when the state is not Active. The REMOVE branch records it only when the state is Active. The output event keeps the original U and V values from that input event, while normalization is used only for state lookup.

7. Explain complexity and edge cases

Sorting costs O(n log n). The processing pass is O(n) expected because Dictionary lookup and update are O(1) on average. Auxiliary space is O(n). Relevant cases are repeated ACCEPT events, repeated REMOVE events, accepting again after a removal, reversed user order such as (2,1), and equal timestamps. The diagram also notes that self-friendship can be ignored or disallowed by the input contract. The shown code does not add a separate self-friendship check.

Key Insight / Why This Solution Works

The key idea is to convert the raw event list into real friendship state transitions. Sort by timestamp first and preserve original input order for equal timestamps. Normalize each friendship to the dictionary key (min(u,v), max(u,v)), so reversing the two users still refers to the same friendship. The dictionary stores the pair's current state. The central invariant is: before processing an event, the dictionary exactly represents the state after every earlier sorted event. Append an ACCEPT only when the pair is not Active. Append a REMOVE only when it is Active. Any event that leaves the state unchanged is a duplicate and is ignored.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public static class Program
{
    public sealed class Event
    {
        public int Time { get; set; }
        public string Type { get; set; } = string.Empty;
        public int U { get; set; }
        public int V { get; set; }
    }

    public static List<Event> BuildFriendshipTimeline(List<Event> events)
    {
        // Keep each event's original index so equal timestamps preserve input order.
        IEnumerable<Event> sortedEvents =
            events.Select((eventItem, index) => new { Event = eventItem, Index = index })
                .OrderBy(item => item.Event.Time)
                .ThenBy(item => item.Index)
                .Select(item => item.Event);

        // Store only events that really change friendship state.
        List<Event> timeline = new List<Event>();

        // Key: normalized unordered pair. Value: current state, Active or Removed.
        Dictionary<(int, int), string> status = new Dictionary<(int, int), string>();

        foreach (Event currentEvent in sortedEvents)
        {
            // Normalize the pair so (1,2) and (2,1) share the same state entry.
            int firstUser = Math.Min(currentEvent.U, currentEvent.V);
            int secondUser = Math.Max(currentEvent.U, currentEvent.V);
            (int, int)key = (firstUser, secondUser);

            // Missing means this pair is not currently Active.
            status.TryGetValue(key, out string? currentState);

            if (currentEvent.Type == "ACCEPT")
            {
                // Record ACCEPT only when it changes the pair to Active.
                if (currentState != "Active")
                {
                    status[key] = "Active";

                    // Keep the original event orientation in the returned timeline.
                    timeline.Add(new Event { Time = currentEvent.Time, Type = "ACCEPT",
                                             U = currentEvent.U, V = currentEvent.V });
                }
                // Duplicate ACCEPT while already Active is ignored.
            }
            else if (currentEvent.Type == "REMOVE")
            {
                // Record REMOVE only when an Active friendship exists.
                if (currentState == "Active")
                {
                    status[key] = "Removed";

                    // Keep the original event orientation in the returned timeline.
                    timeline.Add(new Event { Time = currentEvent.Time, Type = "REMOVE",
                                             U = currentEvent.U, V = currentEvent.V });
                }
                // REMOVE while not Active is a duplicate or no-op and is ignored.
            }
        }

        // The recorded events are already chronological because processing was sorted.
        return timeline;
    }

    public static void Main()
    {
        // Exact unsorted example shown in the approved diagram.
        List<Event> events =
            new List<Event> { new Event { Time = 5, Type = "ACCEPT", U = 1, V = 2 },
                              new Event { Time = 3, Type = "ACCEPT", U = 1, V = 2 },
                              new Event { Time = 8, Type = "REMOVE", U = 1, V = 2 },
                              new Event { Time = 10, Type = "REMOVE", U = 1, V = 2 },
                              new Event { Time = 6, Type = "ACCEPT", U = 1, V = 2 },
                              new Event { Time = 7, Type = "ACCEPT", U = 2, V = 3 } };

        List<Event> timeline = BuildFriendshipTimeline(events);

        // Expected returned timeline:
        // (3, ACCEPT, 1, 2)
        // (7, ACCEPT, 2, 3)
        // (8, REMOVE, 1, 2)
        Console.WriteLine("Returned timeline:");

        foreach (Event eventItem in timeline)
        {
            Console.WriteLine(
                $"({eventItem.Time}, {eventItem.Type}, {eventItem.U}, {eventItem.V})");
        }
    }
}

Time & Space Complexity

Let n be the number of events. Sorting takes O(n log n) time. After sorting, we examine each event once. Dictionary lookup and update are O(1) on average, so the processing pass is O(n) expected. The sorting step dominates, giving O(n log n) overall expected time. Auxiliary space is O(n). The dictionary can grow to O(n) distinct friendship pairs, and the sorting operation also stores data proportional to the input.

Where it is used

This pattern is useful when software receives events that describe state changes and needs a clean history containing only meaningful transitions. Examples include friendship histories, membership activation and cancellation, subscription status changes, access-control changes, and other event logs where repeated no-op events should not appear in the final timeline.

Why Interviewers Ask This

This question tests whether you can turn an event stream into a correct state history. The interviewer can see whether you recognize that a friendship pair is unordered, choose an appropriate dictionary key, maintain a clear state invariant, handle duplicate accepts and removals, preserve ordering rules, and write C# that matches the explanation. It also tests whether you include the sorting cost and describe Dictionary operations with average-case complexity rather than claiming guaranteed constant time.

Common interview mistakes

One common mistake is treating (u,v) and (v,u) as different friendships instead of normalizing the dictionary key. Another is adding every input event to the timeline instead of adding only state changes. Candidates may incorrectly record an ACCEPT while the pair is already Active, or record a REMOVE while it is not Active. Another mistake is forgetting the original input order when timestamps tie. It is also incorrect to claim O(n) total time because this solution first sorts the events in O(n log n). Finally, normalization should affect state lookup, not silently rewrite the U and V values returned for the event.

Interview tip

State the invariant before walking through the example: the dictionary contains the current friendship state after all earlier sorted events. Then process times 3, 5, 6, 7, 8, and 10 and say whether each event changes that state.

Interviewer may ask next

How would the solution change if the friendship events arrived continuously and were already ordered by time?

The sorting step could be removed. I would keep the same normalized-pair dictionary and apply the same ACCEPT and REMOVE rules to each incoming event. The invariant stays the same because every new event arrives after the events already processed. Processing n events would take O(n) expected time because each dictionary lookup or update is O(1) on average. Auxiliary state would be O(m), where m is the number of distinct friendship pairs. The tradeoff is that this requires the stream to be correctly ordered.

What changes if we need only the final friendship state and do not need the chronological timeline?

The state transition rules do not change, but I would not store accepted events in the timeline list. After all sorted events are processed, the dictionary itself contains the final state of each pair. Sorting still costs O(n log n), and the processing pass is O(n) expected. The dictionary needs O(m) auxiliary space for m distinct pairs. This reduces memory used for recorded history, but we lose the timestamps and sequence of meaningful changes.

33 Meta .NET Developer Interview Questions & Answers

Questions with Detailed ExplanationsWith Detailed Explanations

1. Recurring CharacterCodingEasyMeta

2. Liked PagesCodingEasyMeta

3. Last TransactionCodingEasyMeta

4. Session DifferenceCodingEasyMeta

5. Comments HistogramCodingEasyMeta

6. Employee SalariesCodingEasyMeta

7. Like TrackerCodingMediumMeta

8. Largest Salary by DepartmentCodingMediumMeta

9. Threaded CommentsCodingMediumMeta

10. Friendship TimelineCodingMediumMeta

.NET Developer Resume Examples