← IMC Interview InsightsSoftware Engineer

IMC·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

IMC software engineer interview with a data structures and complexity question. Pretty focused on fundamentals, the kind of thing you either know cold or you're fumbling through in real time.

Questions Asked (1)

Q1

What is the worst-case time complexity for each of these four operations: removing an element from a sorted array, checking if a key exists in a hash table, removing the minimum element from a min-heap, and finding the i-th element in a sorted array?

Algorithms & Data Structures
Author's notes

Four sub-questions packed into one, which felt a bit like a rapid-fire quiz.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each operation, identify the underlying data structure and the worst-case scenario that leads to the highest time complexity. State the complexity clearly and briefly justify why it is the worst case, mentioning any assumptions (e.g., array size, hash collisions).

Pro tip: Always clarify whether the operation includes finding the element first; for example, removing from a sorted array requires locating the element (O(log n) with binary search) plus shifting (O(n)), so the overall worst case is O(n).

1. Identify the data structure and operation

For each of the four operations, note the specific data structure (sorted array, hash table, min-heap) and the exact operation (remove, check existence, remove min, find i-th).

2. Determine the worst-case scenario

Think about the input or state that causes the maximum number of steps: e.g., removing the first element of an array, all keys hashing to the same bucket, removing the root of a heap, etc.

3. Derive the time complexity

Based on the worst-case scenario, count the dominant operations (comparisons, shifts, traversals) and express the complexity in Big-O notation.

4. State the complexity with justification

Clearly state the worst-case time complexity for each operation, providing a one-sentence justification for each.

5. Summarize and check for assumptions

Briefly recap all four complexities and mention any assumptions (e.g., hash table with chaining, array size n, heap size n).

Key Points to Mention

  • Removing from a sorted array: O(n) due to shifting elements after removal, even if the element is found in O(log n) via binary search.
  • Checking key existence in a hash table: O(n) worst-case when all keys collide, assuming chaining; with open addressing, it can also degrade to O(n).
  • Removing the minimum from a min-heap: O(log n) because you replace the root with the last element and bubble down.
  • Finding the i-th element in a sorted array: O(1) because arrays allow constant-time random access by index.
  • Mention that hash table worst-case assumes a poor hash function or adversarial input; average case is O(1).
  • Clarify that for sorted array removal, if the index is given, removal is still O(n) due to shifting.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.