Core Data Structures Questions

Fundamental built-in data structures used in everyday programming and coding interviews: arrays/lists, strings, and hash maps (dictionaries). For array-like sequences, cover indexing, slicing or sub-ranging, iteration, common mutation operations (appending, inserting, removing elements), common algorithms such as sorting and reversing, and the memory and performance implications of each. For strings, cover indexing, slicing or substring extraction, common operations such as splitting, joining, trimming, and replacing, and general approaches to string manipulation and pattern processing. For hash maps and dictionaries, cover key value semantics, insertion and lookup, iteration patterns, safe access idioms (defaults, existence checks), and using hash tables for counting and grouping. Candidates should know the time complexity of common operations in plain terms (constant time, linear time, quadratic time) and be able to choose the appropriate structure for a problem and reason about space and performance tradeoffs. Practice should include implementation level manipulation exercises and classic interview problems such as two sum and frequency counting, written clearly in whatever language the candidate is most comfortable with (a specific language may be used for concrete code examples without the underlying concept being tied to it).

EasyTechnical

49 practiced

Compare iterating over a list vs iterating over a dict in Python. For each pattern (for x in list, for k in dict, for k,v in dict.items()), state what is being yielded, typical use-cases, and the time complexity of iteration. Show short code examples illustrating safe removal of items during iteration and explain pitfalls.

Sample Answer

for x in my_list- Yields: each element of the list, one by one.- Use-cases: simple element processing, map/filter style loops, index-free traversal.- Complexity: O(n) to iterate n items (amortized O(1) per next).

Example and safe removal:

python

# Bad: removes while iterating -> skips items
for x in my_list:
    if condition(x):
        my_list.remove(x)

# Safe: iterate over a copy or build a new list
for x in my_list[:]:        # shallow copy
    if condition(x):
        my_list.remove(x)

# Or use comprehension (preferred)
my_list = [x for x in my_list if not condition(x)]

Pitfall: removing from list while iterating forward can skip elements because indices shift. Iterating reversed avoids some cases:

python

for i in range(len(my_list)-1, -1, -1):
    if condition(my_list[i]):
        del my_list[i]

for k in my_dict- Yields: keys (equivalent to iter(my_dict)).- Use-cases: lookup values by key, mutate values, collect keys.- Complexity: O(n) overall; each next is O(1) average.

for k, v in my_dict.items()- Yields: (key, value) pairs via a dynamic view (dict_items) — iterates live snapshot of pairs.- Use-cases: read both key and value, transform dict into something else.- Complexity: O(n) overall; retrieving value from the pair is O(1).

Safe removal from dict:

python

# Raises RuntimeError: dictionary changed size during iteration
for k in my_dict:
    if cond(k, my_dict[k]):
        del my_dict[k]

# Safe: iterate over list(my_dict) to freeze keys
for k in list(my_dict):
    if cond(k, my_dict[k]):
        del my_dict[k]

# Or build a new dict
my_dict = {k:v for k,v in my_dict.items() if not cond(k,v)}

Pitfalls: mutating dict size during iteration raises RuntimeError. Using .items() gives pairs but still disallows structural mutation during iteration; wrap keys in list(...) to snapshot.

MediumTechnical

49 practiced

Show examples of using dict comprehensions to transform data: e.g., given a list of (key, value) pairs, produce a dict mapping keys to lists of values (group by key). Provide code and explain time/space complexities and readability tradeoffs vs explicit loops.

Sample Answer

To group a list of (key, value) pairs into a dict mapping each key to a list of values, you can use a dict comprehension combined with a set of keys, but that's often less efficient than using explicit loops or collections. Below are idiomatic patterns, with code, explanation, and trade-offs.

Approach 1 — explicit loop (clear, efficient)

python

pairs = [("a", 1), ("b", 2), ("a", 3), ("c", 4)]

# explicit loop using defaultdict
from collections import defaultdict

grouped = defaultdict(list)
for k, v in pairs:
    grouped[k].append(v)

# if you want a plain dict
grouped = dict(grouped)
# grouped == {'a': [1, 3], 'b': [2], 'c': [4]}

Approach 2 — dict comprehension with set of keys (uses comprehension but scans data repeatedly)

python

keys = {k for k, _ in pairs}
grouped = {k: [v for kk, v in pairs if kk == k] for k in keys}

Key points:- Approach 1 (defaultdict loop): single pass over pairs → Time O(n), Space O(m + n) where m is number of unique keys and n number of pairs. Readable, minimal overhead, recommended for production.- Approach 2 (dict comprehension): for each unique key, it scans the whole pairs list to collect values → Time O(m * n) worst-case, Space O(m + n). Less efficient but concise in some situations where data is small and you prefer declarative style.- Alternative: itertools.groupby after sorting: O(n log n) due to sort, but useful when you need sorted keys.

Tradeoffs (readability vs performance):- Comprehensions look concise and "Pythonic", but can hide repeated passes; for grouping, explicit loops or defaultdict are both more performant and clearer about intent.- For large datasets (typical in AI pipelines), prefer single-pass methods to avoid O(m * n) blowups.

Edge cases:- Empty list -> empty dict.- Keys with no values (not applicable here).- If ordering matters, use OrderedDict or preserve insertion order (Python 3.7+ dict preserves insertion order).

MediumTechnical

46 practiced

Write a function merge_sorted(a: List[int], b: List[int]) -> List[int] that merges two sorted lists into a single sorted list using two pointers. Provide in-place strategies when possible, explain time and space complexity, and discuss when you might prefer to allocate a new list vs merge in-place for memory constraints.

Sample Answer

To merge two sorted lists with two pointers, iterate from the start of each list, compare current elements, append the smaller to the output, and advance that pointer. This is stable, O(n+m) time. If you can’t allocate a new list, you can merge in-place only when one list has extra buffer space at the end (common when merging into a preallocated array) by filling from the back.

python

from typing import List

def merge_sorted(a: List[int], b: List[int]) -> List[int]:
    """
    Merge two sorted lists into a new sorted list using two pointers.
    Time: O(len(a)+len(b)), Space: O(len(a)+len(b))
    """
    i, j = 0, 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    # append remaining
    if i < len(a):
        out.extend(a[i:])
    if j < len(b):
        out.extend(b[j:])
    return out

# In-place strategy when `a` has enough trailing buffer (len(a) == m + n, last n slots empty/placeholder)
def merge_into_a(a: List[int], m: int, b: List[int], n: int) -> None:
    """
    Merge b into a in-place. a has length m+n, with first m valid elements.
    Fills from the back to avoid overwriting.
    Time: O(m+n), Space: O(1)
    """
    i, j, write = m - 1, n - 1, m + n - 1
    while j >= 0 and i >= 0:
        if a[i] > b[j]:
            a[write] = a[i]
            i -= 1
        else:
            a[write] = b[j]
            j -= 1
        write -= 1
    # copy remaining b elements if any
    while j >= 0:
        a[write] = b[j]
        j -= 1
        write -= 1

Key points:- Time complexity O(m+n). Merging into a new list uses O(m+n) extra space.- In-place (merge_into_a) uses O(1) extra space but requires the target array to have reserved space and knowing lengths.- Prefer allocating a new list when immutability, simplicity, or thread-safety matters, or when both inputs are tightly packed and no buffer exists.- Prefer in-place when memory is constrained or working with large arrays (e.g., huge tensors) and you can preallocate space; be careful with aliasing and side effects.Edge cases: empty arrays, duplicates, negative numbers — both implementations handle these.

MediumTechnical

52 practiced

Design and implement a simple LRU cache class in Python with get(key) and put(key, value) operations. Back it with a dictionary for O(1) lookup and a doubly-linked list for O(1) updates when items are accessed/evicted. Explain complexity and behavior under capacity pressure.

Sample Answer

To implement an LRU cache with O(1) get and put, use a dict for key→node lookup and a doubly-linked list to maintain recency order (head = most recent, tail = least recent). On get, move node to head. On put, if key exists update value and move to head; if new and capacity full, remove tail node and its dict entry, then insert new node at head.

python

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}  # key -> Node
        # dummy head/tail to simplify edge cases
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        # unlink node
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node):
        # insert right after head
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if not node:
            return -1
        # mark most recently used
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key, value):
        node = self.map.get(key)
        if node:
            node.val = value
            self._remove(node)
            self._add_to_head(node)
            return
        if len(self.map) >= self.cap:
            # evict least recently used (tail.prev)
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        new_node = Node(key, value)
        self.map[key] = new_node
        self._add_to_head(new_node)

Key points:- All operations are O(1): dict lookup + constant pointer updates in list.- Space is O(capacity) for dict + nodes.- Under capacity pressure, put evicts the tail (least recently used) before inserting; get does not change capacity but refreshes recency. Use dummy head/tail to avoid null checks.Edge cases:- capacity <= 0 (should be handled by raising or treating as zero-capacity)- frequent updates of same key (handled by move-to-head)- concurrent access requires locking (not included).

MediumTechnical

56 practiced

Implement a function longest_unique_substring(s: str) -> str that returns the longest substring without repeating characters. Use a sliding-window approach with a dictionary to track last-seen positions. Provide Python code and analyze time and space complexity.

Sample Answer

To solve this, use a sliding window with two pointers (left, right) and a dict mapping each character to its last seen index. Move right to expand; when a repeated character is found inside the window, advance left to last_seen[char] + 1. Track the maximum-length substring positions.

python

def longest_unique_substring(s: str) -> str:
    """
    Return the longest substring without repeating characters.
    Sliding-window with last-seen index dictionary.
    """
    last_seen = {}          # char -> last index
    left = 0
    best_start = 0
    best_len = 0

    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            # repeat inside current window: move left past previous occurrence
            left = last_seen[ch] + 1
        last_seen[ch] = right
        cur_len = right - left + 1
        if cur_len > best_len:
            best_len = cur_len
            best_start = left

    return s[best_start:best_start + best_len]

Key points:- Uses in-place indices (no substring copies while scanning).- Handles all Unicode characters since dict keys are chars.

Time complexity: O(n) — each character visited once; dictionary operations average O(1).Space complexity: O(min(n, m)) where m is alphabet size (distinct characters stored).Edge cases: empty string -> "", all-unique -> entire string, all-same -> single char.Alternatives: use an ordered dict or boolean array for small fixed alphabets.

Unlock Full Question Bank

Get access to hundreds of Core Data Structures interview questions and detailed answers.

Join thousands of developers preparing for their dream job.