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

48 practiced

Given a list of strings in Python, implement a function that returns a dictionary mapping each unique string to its frequency count. The function should be memory- and time-efficient for moderate lists (millions of items). Show code and explain complexity. Example input: ['a','b','a','c','b','a'] -> {'a':3, 'b':2, 'c':1}.

Sample Answer

A simple, efficient way is to stream through the list once and increment counts in a dictionary (hash map). For moderate lists (millions of items) this is O(n) time and O(k) space where k is number of unique strings. Use collections.Counter for readability and C-level speed, or a plain dict if you need minimal dependencies.

python

from collections import Counter
from typing import Iterable, Dict

def freq_count(items: Iterable[str]) -> Dict[str, int]:
    """
    Return a dict mapping each unique string to its frequency.
    Accepts any iterable so it can stream from generators or files.
    """
    # Counter is implemented in C and is memory-efficient for this use-case
    return dict(Counter(items))

If you prefer manual implementation:

python

def freq_count_manual(items):
    counts = {}
    for s in items:
        counts[s] = counts.get(s, 0) + 1
    return counts

Key points:- Time: O(n) single pass over input.- Space: O(k) for unique keys.- Use an iterator/generator to avoid building large intermediate lists.- For extremely large scale (bigger than memory), use external counting (e.g., map-reduce, partition by hash, or Spark's reduceByKey).

MediumTechnical

85 practiced

Implement a Python function that returns sliding windows of size k over an iterable without materializing the entire sequence. Each window should be returned as a tuple. Example: iterable [1,2,3,4], k=3 -> (1,2,3), (2,3,4). The function should work for generators and large inputs.

Sample Answer

Approach: use a fixed-size deque as a rolling buffer; advance the iterator and yield a tuple whenever the deque reaches size k. This works lazily for any iterable or generator and uses O(k) memory.

python

from collections import deque
from typing import Iterable, Iterator, Tuple, TypeVar

T = TypeVar("T")

def sliding_windows(iterable: Iterable[T], k: int) -> Iterator[Tuple[T, ...]]:
    """
    Yield sliding windows of size k from iterable as tuples.
    Works lazily for generators and large inputs.
    """
    if k <= 0:
        raise ValueError("k must be > 0")
    it = iter(iterable)
    window = deque(maxlen=k)

    # Fill initial window
    for _ in range(k):
        try:
            window.append(next(it))
        except StopIteration:
            return  # not enough items -> no windows

    yield tuple(window)

    # Slide: for each new item, append to deque and yield
    for item in it:
        window.append(item)
        yield tuple(window)

Key points:- Memory: O(k). Time: O(n).- Works for generators and any iterable; does not materialize full sequence.- Edge cases: k <= 0 raises ValueError; if iterable shorter than k, yields nothing.- Alternative: use itertools.islice + collections.deque or recipes like itertools.tee (tee duplicates iterators and can be heavier). Deque approach is simple and efficient for data-engineering sized streams.

HardTechnical

47 practiced

Find the longest palindromic substring of a given string. First describe a dynamic programming (O(n^2)) approach using a 2D table, then implement a more practical expand-around-center approach (O(n^2) time, O(1) space). Optionally outline Manacher's O(n) algorithm at a high level.

Sample Answer

Dynamic programming approach (O(n^2) time, O(n^2) space)- Idea: dp[i][j] is True if s[i..j] is a palindrome.- Recurrence: dp[i][j] = (s[i]==s[j]) and (j-i<2 or dp[i+1][j-1]).- Fill table by increasing substring length; track longest palindrome seen.- Pros: clear and easy to reason about. Cons: O(n^2) memory which can be heavy for large strings.

Practical expand-around-center approach (O(n^2) time, O(1) space)- For each center (character or gap between chars), expand left/right while characters match. Track max length.- Simpler, no extra memory, fast in practice.

Python implementation:

python

def longest_palindrome(s: str) -> str:
    if not s or len(s) < 2:
        return s

    start = 0
    end = 0

    def expand(l: int, r: int) -> (int, int):
        # expand while within bounds and characters equal
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        # return indices of found palindrome (inclusive)
        return l + 1, r - 1

    for i in range(len(s)):
        # odd length
        l1, r1 = expand(i, i)
        # even length
        l2, r2 = expand(i, i + 1)

        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2

    return s[start:end + 1]

Key points:- Time: O(n^2) worst-case (e.g., all same chars). Space: O(1).- Edge cases: empty string, single char, all-equal characters.

Manacher's algorithm (high level, O(n)):- Transform string with separators to handle even/odd uniformly.- Use a center and right boundary to reuse previously computed palindromic radii, avoiding re-checks.- Maintain array of palindrome radii; update center when expansion goes beyond right boundary.- Complexity O(n) time, O(n) space; more complex but optimal for very large inputs.

MediumTechnical

62 practiced

Group anagrams: given a list of strings, return a list of groups where each group contains anagrams. Implement in Python and discuss different ways to build the grouping key (sorted string vs character count) and their trade-offs for very long strings.

Sample Answer

A common approach is to use a hashmap mapping a canonical key for each string to a list of anagrams. Two popular keys:- sorted string (''.join(sorted(s))) — simple and works for all alphabets- character count tuple (counts for 'a'..'z' or unicode buckets) — O(L) per string, better for very long strings when L >> alphabet

Approach and implementation:

python

from collections import defaultdict

def group_anagrams(strs):
    """
    Group anagrams. Uses character-count key assuming lowercase a-z.
    For general unicode, use sorted key or a dict-based count key.
    """
    groups = defaultdict(list)
    for s in strs:
        # build a 26-length count tuple in O(len(s))
        counts = [0]*26
        for ch in s:
            counts[ord(ch)-97] += 1
        key = tuple(counts)
        groups[key].append(s)
    return list(groups.values())

Key points:- Time complexity sorted-key: O(n * L log L) where n = number strings, L = average length.- Time complexity count-key: O(n * (L + A)) where A = alphabet size (e.g., 26); effectively O(n * L) when A is small.- Space: both need O(n * L) to store strings; keys add O(n * A) for counts or O(n * L) for sorted keys.

Trade-offs:- Sorted key is simpler and supports arbitrary characters without predefining alphabet, but costly when strings are very long.- Count key is linear in string length and faster for long strings with small fixed alphabets; for Unicode you must handle large alphabet or use a sparse map (hashable), increasing overhead.- For huge datasets use streaming / distributed grouping (e.g., Spark: map key → groupByKey) and avoid materializing all strings in driver memory; choose count-key if per-item CPU matters.

Edge cases: empty strings, mixed case (normalize), non-letter chars (adjust alphabet), very long single strings (watch memory/time for sorting).

EasyTechnical

47 practiced

Implement an in-place function in Python that reverses a list of integers without using built-in reverse() or creating a new list. Your function should run in O(n) time and use O(1) extra space. Provide example usage and handle empty lists. Example:

python

lst = [1, 2, 3, 4]
reverse_in_place(lst)
# lst -> [4, 3, 2, 1]

Sample Answer

To reverse a list in-place in O(n) time and O(1) extra space, use the two-pointer swap method: one pointer at the start, one at the end, swap elements and move pointers toward the center until they meet.

python

def reverse_in_place(lst):
    """
    Reverse list of integers in-place.
    Handles empty list. Runs O(n) time, O(1) extra space.
    """
    left, right = 0, len(lst) - 1
    while left < right:
        # swap elements at left and right
        lst[left], lst[right] = lst[right], lst[left]
        left += 1
        right -= 1

# Example usage
lst = [1, 2, 3, 4]
reverse_in_place(lst)
print(lst)  # -> [4, 3, 2, 1]

empty = []
reverse_in_place(empty)
print(empty)  # -> []

Key points:- In-place swapping avoids allocating a new list.- Time complexity: O(n) (single pass swapping each element at most once).- Space complexity: O(1) (only two index variables).Edge cases:- Empty list and single-element list are handled naturally (loop doesn't run).- Works with any mutable sequence supporting index assignment (e.g., lists).

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.