Arrays & Lists

Question 1

What is the time complexity of accessing an element in an array by index?

Accepted Answer

O(1) — Array access by index is O(1) because arrays store elements in contiguous memory, allowing direct calculation of memory address.

Question 2

What is the worst-case time complexity of inserting an element at the beginning of an array?

Accepted Answer

O(n) — Inserting at the beginning requires shifting all existing elements one position to the right, resulting in O(n) time complexity.

Question 3

Which operation is NOT efficient for arrays?

Accepted Answer

Frequent middle inserts — Frequent insertions in the middle require shifting elements, making it inefficient. Arrays excel at random access and cache-friendly operations.

Question 4

Which formula computes the memory address of element a[i] in a zero-indexed array?

Accepted Answer

base + (i × element_size) — Address = base + (index × element_size). Because the index multiplies a fixed element size, the CPU computes any address in constant time — the source of O(1) random access.

Question 5

Why is iterating an array sequentially so much faster than chasing pointers in a linked list?

Accepted Answer

Contiguous layout prefetches next elements — Array elements sit in contiguous memory, so loading one element pulls a whole cache line containing its neighbors. Linked-list nodes are scattered, causing frequent cache misses.

Question 6

What is the AMORTIZED time complexity of appending to a dynamic array (e.g. ArrayList, std::vector, Python list)?

Accepted Answer

O(1) amortized — Most appends are O(1); occasional resizes are O(n) but rare. Spreading the resize cost over all appends gives O(1) amortized per append.

Question 7

When a dynamic array runs out of capacity, why is its growth factor typically 1.5×–2× rather than +1 element?

Accepted Answer

To keep total copying linear — Geometric growth makes the number of resizes logarithmic and total elements copied O(n) overall, yielding O(1) amortized append. Growing by a constant would make appends O(n) amortized.

Question 8

Compared to a linked list, the array’s key weakness for insertion/deletion in the middle is that it must…

Accepted Answer

Shift elements to stay contiguous — Contiguity is the array’s strength for access but its weakness for middle edits: inserting/removing forces shifting all later elements, which is O(n).

Question 9

For a 2D array stored in ROW-MAJOR order with C columns, the address of a[i][j] (element size s, base b) is:

Accepted Answer

b + (i × C + j) × s — Row-major lays out row 0, then row 1, etc. Element a[i][j] is at offset (i × C + j) elements. Column-major (Fortran/MATLAB) swaps the roles of i and j.

Question 10

What is the time complexity of deleting the LAST element of an array?

Accepted Answer

O(1) — Removing the final element requires no shifting — just decrement the logical size. Deleting at the front or middle is O(n) because everything after must shift.

Array: [6 elements]

Cheap or expensive?

Test your knowledge

What is the time complexity of accessing an element in an array by index?

Interview Questions

References & Further Reading

Love this visualization?