How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snapchat.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snapchat during technical interviews.

Implement a custom list with iterator and map

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to implement a simple generic list type **without using any built-in collection classes** (e.g., no `ArrayList`, `LinkedList`, `Vector`, etc.). You may use primitive arrays / custom nodes. ### Part 1 — Implement a List Design and implement `MyList<T>` with at least the following operations: - `void add(T value)` - `T get(int index)` - `void set(int index, T value)` (or return a new value) - `T remove(int index)` - `int size()` Requirements: - Handle invalid indices (define behavior: throw an exception or return a sentinel). - Aim for reasonable time complexity (state your choice of underlying structure: dynamic array or linked list). ### Part 2 — Implement an Iterator Extend `MyList<T>` so it is iterable. - Implement an iterator type with standard iterator methods (e.g., `hasNext()` and `next()`; optionally `remove()` if you support it). - The iterator should traverse the list from index `0` to `size()-1`. ### Part 3 — Implement a map function Add a `map`-style higher-order function: - `MyList<R> map(Function<T, R> f)` (or equivalent in your language) It should: - Apply `f` to each element in order - Return a **new** `MyList<R>` containing the mapped results - Not modify the original list ### Clarifications - Assume single-threaded use. - You may assume elements can be `null` unless you choose to forbid it (but document your choice).

Quick Answer: This question evaluates proficiency in data structures and generic collection implementation, specifically list operations, iterator semantics, and higher-order map functions.

Implement a simple generic list type **without using any built-in collection classes** (no `ArrayList`, `LinkedList`, `Vector`, dynamic `list`/`vector` growth helpers, etc.). You may use a primitive fixed-size array (which you resize yourself) or custom nodes. Because this console drives your implementation through a scripted sequence of operations, write a single function `solution(operations)` that builds and exercises one or more named lists and returns the results of all *query* operations in order. ## What to build internally Your `MyList` must support, with reasonable time complexity: - `add(value)` — append to the end (amortized O(1); resize the backing array yourself when full) - `get(index)` — return the element, or the sentinel `'ERR'` for an invalid index - `set(index, value)` — overwrite an element; return `None`, or `'ERR'` for an invalid index - `remove(index)` — remove and return the element (shifting later elements left), or `'ERR'` - `size()` — current element count - iteration — yield elements from index `0` to `size()-1` in order - `map(f)` — apply `f` to each element in order and return a **new** list, **without modifying the original** ## Operation protocol `operations` is a list of tuples; the first element is the op name and remaining elements are arguments. `list_id`/`src_id`/`dst_id` are string handles. | Operation | Meaning | Appends to results | |---|---|---| | `('new', list_id)` | create an empty list | (nothing) | | `('add', list_id, value)` | append value | (nothing) | | `('get', list_id, index)` | read | value or `'ERR'` | | `('set', list_id, index, value)` | overwrite | `None` or `'ERR'` | | `('remove', list_id, index)` | remove + shift | removed value or `'ERR'` | | `('size', list_id)` | count | int | | `('iterate', list_id)` | traverse 0..size-1 | a list of the elements | | `('map', src_id, dst_id, fname)` | store `src.map(fn)` into `dst_id` | `None` | Named map functions: `'inc'` (x+1), `'double'` (x*2), `'square'` (x*x), `'neg'` (-x), `'str'` (str(x)). Return the list of results from the query ops (`get`/`set`/`remove`/`size`/`iterate`/`map`), in the order they occur. `new` and `add` contribute nothing. ## Clarifications - Assume single-threaded use. - An invalid index is any index `< 0` or `>= size()`; respond with the `'ERR'` sentinel rather than raising. - `map` must not mutate the source list.

Constraints

Do not use built-in collection classes for the list's internal storage; resize a primitive/fixed array yourself.
Indices are valid only when 0 <= index < size(); otherwise return the 'ERR' sentinel instead of raising.
map(f) must return a NEW list and must not mutate the source.
Elements may be any value (ints in the test driver); assume single-threaded use.
Map function names: 'inc', 'double', 'square', 'neg', 'str'.

Examples

Input: ([('new','a'),('add','a',10),('add','a',20),('add','a',30),('size','a'),('get','a',1),('iterate','a')],)

Expected Output: [3, 20, [10, 20, 30]]

Explanation: Add three elements, then size()=3, get(1)=20, and iteration yields them in insertion order.

Input: ([('new','a'),('add','a',1),('add','a',2),('add','a',3),('set','a',1,99),('iterate','a'),('remove','a',0),('iterate','a'),('size','a')],)

Expected Output: [None, [1, 99, 3], 1, [99, 3], 2]

Explanation: set(1,99) returns None and overwrites index 1; remove(0) returns the removed 1 and shifts the rest left, leaving [99, 3] with size 2.

Input: ([('new','a'),('get','a',0),('remove','a',0),('set','a',0,5),('size','a'),('iterate','a')],)

Expected Output: ['ERR', 'ERR', 'ERR', 0, []]

Explanation: Edge case: every access on an empty list is out of range and returns the 'ERR' sentinel; size()=0 and iteration yields an empty list.

Input: ([('new','a'),('add','a',1),('add','a',2),('add','a',3),('add','a',4),('add','a',5),('add','a',6),('size','a'),('get','a',5),('iterate','a')],)

Expected Output: [6, 6, [1, 2, 3, 4, 5, 6]]

Explanation: Adding 6 elements past the initial capacity of 4 forces the backing array to grow; all elements survive in order and get(5)=6.

Input: ([('new','src'),('add','src',1),('add','src',2),('add','src',3),('map','src','dst','double'),('iterate','dst'),('iterate','src'),('map','src','sq','square'),('iterate','sq')],)

Expected Output: [None, [2, 4, 6], [1, 2, 3], None, [1, 4, 9]]

Explanation: map('double') produces a new list [2,4,6] while src is unchanged ([1,2,3]); a second map('square') on src yields [1,4,9], confirming map never mutates its source.

Input: ([('new','a'),('add','a',-5),('add','a',0),('add','a',7),('get','a',-1),('get','a',3),('remove','a',5),('iterate','a')],)

Expected Output: ['ERR', 'ERR', 'ERR', [-5, 0, 7]]

Explanation: Negative indices and indices >= size are both invalid and return 'ERR'; the list of [-5, 0, 7] is untouched.

Hints

Back MyList with a fixed-size array plus an integer size; when size == capacity, allocate a new array of double the capacity and copy the elements over (this is exactly what ArrayList does under the hood).
remove(index) must shift every element after index one slot to the left and then decrement size; clear the now-unused tail slot to avoid leaking references.
For iteration, keep a cursor starting at 0; hasNext() is cursor < size() and next() returns data[cursor++]. In Python this is naturally a generator over indices 0..size-1.
map should iterate the source in order, apply f, and add each result to a brand-new MyList — never write back into the source's array.

Quick Overview

This question evaluates proficiency in data structures and generic collection implementation, specifically list operations, iterator semantics, and higher-order map functions.