This exercise implements an array-shaped API using numeric keys in an object. The point is to expose the bookkeeping behind get, push, pop, insert, and remove. It is a teaching representation: a native array implementation also manages storage capacity, whereas the object in this lesson delegates its storage to the language runtime.
Keep length and occupied indexes consistent
Maintain one invariant: valid entries occupy indexes from zero through length minus one. An empty instance has length zero. Pushing an item stores it at the old length, then increments length. Popping must save the final item, remove its property, and reduce length. Returning the item and returning the new length are different API decisions; follow each method's contract in the current code.
For an instance containing [4, 8, 12], pushing 16 writes index 3. Popping then returns 16 and restores the original state. Test repeated pushes and pops so an old property cannot survive beyond the reported length and reappear later.
Shift in the direction that preserves unread values
To insert 6 at index 1, first move 12 to index 3, then 8 to index 2, then write 6. Moving from the insertion index toward the end would overwrite values before copying them. Removal has the opposite dependency: shift later values left, then delete the obsolete final property.
The current Python insertion fixes the loop boundary for insertion at index zero. Include that case in a trace: the first existing value must move too. Also test insertion at length, removal of the only item, and removal at the front. Agree on behavior for invalid indexes before extending the exercise beyond its supplied contract.
Explain the cost of the teaching model
Under expected constant-time object-key operations, indexed access and tail changes take constant work. Inserting or removing near the beginning shifts up to every element and takes linear time. Length itself is stored, so reading it does not require counting properties.
Do not use this object-backed implementation to claim that native arrays never resize or that all hash operations have a worst-case constant bound. Review Arrays for the capacity model, then open the current implementation lesson and explain each mutation before running it.
Understand the backing store used here
This teaching DynamicArray stores numeric positions in a map or object and tracks a separate logical length. It exposes shifting and index bookkeeping without managing a contiguous memory allocation or a growth capacity. It therefore does not demonstrate the amortized resize proof of a production vector. The native array concept example is the better place to compare host-language collection operations.
Push 4, 8, and 12, then insert 6 at position 1. Length becomes four and the right-to-left shift preserves the old suffix. Shifting left-to-right would overwrite a value before copying it. Removing position 2 then shifts the suffix left and deletes the obsolete final entry.
State this API's boundaries
insert accepts an existing index only. It does not insert into an empty structure or append at length; use push for those operations. Removal returns the language's absent result for an invalid position. Retrieval policies vary: some versions return an optional/default value and others throw on a missing key; the language notes identify those differences. Rust uses unsigned indices, so a negative external index must be rejected before conversion.
Expected constant-time backing-map access gives expected O(1) get, push, and pop. Insert and remove take expected O(n) because of shifting. The store retains O(n) active entries. Check invalid indices, empty pop, first and last removal, and repeated drain/refill cycles. After removal, no old value should remain retrievable beyond the logical end. This last check catches stale backing entries even when the displayed length looks correct.
Rust example and implementation choices
HashMap<usize, i32> owns the active entries and Option distinguishes missing values. insert returns a borrowed map view tied to the mutable call, so the caller cannot freely mutate the array while retaining that borrow. Indices are unsigned; reject negative external values before conversion. The map representation demonstrates shifts and logical length, while Vec would model contiguous capacity management more directly.
Complete implementation
use std::collections::HashMap;
struct DynamicArray {
length: usize,
data: HashMap<usize, i32>,
}
impl DynamicArray {
fn new() -> Self {
DynamicArray {
length: 0,
data: HashMap::new(),
}
}
fn get(&self, index: usize) -> Option<i32> {
self.data.get(&index).copied()
}
fn push(&mut self, item: i32) -> usize {
self.data.insert(self.length, item);
self.length += 1;
self.length
}
fn pop(&mut self) -> Option<i32> {
if self.length == 0 {
return None;
}
let popped_item = self.data.remove(&(self.length - 1));
self.length -= 1;
popped_item
}
fn insert(&mut self, index: usize, item: i32) -> Option<&HashMap<usize, i32>> {
if index >= self.length {
return None;
}
self.length += 1;
for i in (index + 1..self.length).rev() {
self.data.insert(i, self.data[&(i - 1)]);
}
self.data.insert(index, item);
Some(&self.data)
}
fn remove(&mut self, index: usize) -> Option<i32> {
if self.length == 0 {
return None;
}
if index >= self.length {
return None;
}
let item_to_be_removed = self.data[&index];
for i in index..self.length - 1 {
self.data.insert(i, self.data[&(i + 1)]);
}
self.data.remove(&(self.length - 1));
self.length -= 1;
Some(item_to_be_removed)
}
}
Continue in Rust
Open Implement an Array for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Rust example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The Rust interview preparation guide connects these language choices with further practice and the cross-language operation reference.