A loop that looks O(n) can secretly be O(n²), and the reason is almost always a membership check against the wrong container. Write if x in seen where seen is a Python list, and every check walks the whole list. Ten thousand items and you have a hundred million comparisons for something that should have been instant. Swap the list for a set and the same line drops to O(1) per check. Nobody wrote a nested loop, yet there one is.

Interviewers probe this because it separates people who memorized Big-O from people who know what their standard library actually does. You don’t get credit for reciting that hash lookups are constant time. You get credit for reaching for the hash structure without thinking, and for catching the moment clean-looking code hid a linear scan inside a loop.

Python: the list is a dynamic array, and it shows

CPython’s list is a contiguous array of pointers. Indexing and appending to the end are the fast paths: lst[i] and lst.append(x) are O(1), the append amortized because the array occasionally doubles and copies. The trap is the front. lst.pop(0) and lst.insert(0, x) both shift every remaining element by one slot, so they are O(n). People write a queue as a list, call pop(0) in a loop, and turn an O(n) traversal into O(n²) without noticing.

Reach for collections.deque when you need both ends. append, appendleft, pop, and popleft are all O(1). The cost is random access: dq[len(dq) // 2] is O(n) because a deque is a linked structure of blocks, not a flat array.

dict and set are hash tables. Lookup, insertion, and deletion average O(1). The worst case is O(n) if every key collides, but CPython’s hashing makes that a non-issue for ordinary keys, so quote O(1) and mention the worst case only if asked. Membership, x in d or x in s, is the same O(1). This is the single most useful fact for interview coding in Python: if you are checking membership repeatedly, the thing you check against should be a set or a dict, never a list.

For a priority queue, heapq runs a binary heap on top of an ordinary list. heappush and heappop are O(log n), and peeking at the smallest element is heap[0], which is O(1). Building a heap from an existing list with heapify is O(n), not O(n log n), which is worth knowing the moment someone asks for the k smallest elements.

One more that bites people: string building in a loop. s += piece creates a new string every time because Python strings are immutable, so a loop that grows a string one piece at a time is O(n²) in the total length. Collect the pieces in a list and call "".join(parts), which is O(n).

Java: ArrayList and LinkedList are not interchangeable

ArrayList is Java’s dynamic array. get(i) and set(i, x) are O(1), and add(x) at the end is amortized O(1). Inserting or removing in the middle is O(n) because of the shift, same as Python’s list. contains is a linear scan, O(n).

LinkedList tempts people who remember that linked lists have O(1) insertion. They do, but only if you already hold the node. get(i) on a LinkedList walks the chain from the nearest end, so it is O(n), and a loop that calls list.get(i) for each i is quietly O(n²). In practice ArrayList wins almost every time. Reach for LinkedList only when you insert and remove at the ends and never index by position, and even then ArrayDeque is usually the better call.

HashMap and HashSet give O(1) average for get, put, remove, and containsKey. The detail worth carrying into a Java interview: since Java 8, a single hash bucket that gets too crowded (eight or more entries, once the table has at least 64 slots) converts from a linked list into a red-black tree. That drops the worst case for that bucket from O(n) to O(log n). So the worst case for a current HashMap is O(log n), not O(n), a small point that signals you actually read how the class works.

When you need keys kept in sorted order, TreeMap and TreeSet are red-black trees with O(log n) insertion, lookup, and deletion, plus O(log n) navigation like floorKey and ceilingKey. That ordered navigation is the reason to accept the log factor over a HashMap. For a stack or a queue, skip the legacy Stack class and use ArrayDeque, which gives O(1) push and pop at both ends. PriorityQueue is a binary heap: O(log n) to offer and poll, O(1) to peek.

C++: know which map you reached for

The mistake that costs C++ candidates is treating std::map as a hash map. It is not. std::map and std::set are red-black trees, so find, insert, and erase are O(log n), and iteration comes out in sorted order. The hash versions are std::unordered_map and std::unordered_set, which give O(1) average for the same operations. Ask for a hash lookup and write std::map, and you have silently added a log factor to every access.

std::vector is the default sequence: operator[] is O(1), push_back is amortized O(1), and inserting or erasing anywhere but the end is O(n). If you know the size ahead of time, reserve avoids the repeated reallocations that make the amortized cost real. std::deque gives O(1) push and pop at both ends with O(1) indexing, which std::list cannot do. std::list is a doubly linked list with no operator[] at all; its selling point is O(1) splice and iterators that stay valid after inserts.

One worst-case detail matters more in C++ than elsewhere: unordered_map degrades to O(n) per operation under adversarial input, and competitive-programming judges have been known to feed inputs crafted to collide against the standard hash. On a normal interview problem you can quote O(1), but if the room is a low-latency or competitive shop, say that you would supply a custom hash for untrusted keys. std::priority_queue rounds out the set: a binary heap with O(log n) push and pop and O(1) top.

Equivalent containers across the three languages

Abstract structure	Python	Java	C++	Access or lookup	Insert	Remove
Dynamic array	list	ArrayList	std::vector	O(1) by index	O(1) amortized at end, O(n) in middle	O(1) at end, O(n) in middle
Hash map	dict	HashMap	std::unordered_map	O(1) average, O(n) worst	O(1) average	O(1) average
Ordered map (sorted keys)	no built-in; sortedcontainers or bisect	TreeMap	std::map	O(log n)	O(log n)	O(log n)
Hash set	set	HashSet	std::unordered_set	O(1) average	O(1) average	O(1) average
Double-ended queue	collections.deque	ArrayDeque	std::deque	O(1) at ends, O(n) in middle	O(1) at ends	O(1) at ends
Binary heap	heapq (on a list)	PriorityQueue	std::priority_queue	O(1) peek smallest	O(log n) push	O(log n) pop
Linked list	no idiomatic built-in	LinkedList	std::list	O(n) by index	O(1) at a held position	O(1) at a held position

Amortized, average, and worst case are three different claims

When you say append is O(1), you mean amortized O(1): most appends are constant, but the one that triggers a resize copies the whole array and is O(n). Averaged over many appends it comes out constant, which is the number that matters for a loop. Say “amortized” out loud when you mean it, because interviewers hear the precision.

Average versus worst case is a different axis. Hash structures are O(1) average and O(n) worst, with O(log n) worst for a current Java HashMap. For most interviews the average is the right answer, but the moment the problem mentions untrusted input, a latency guarantee, or an adversary, the worst case is what the interviewer is fishing for. Knowing which of the two they want is half the question.

You will not be asked to recite this grid. What earns the nod is the reflex to name the cost of the operation you just wrote, in the language you are writing, and to catch the one structure your language makes slow where you expect fast: the front of a Python list, random access on a Java LinkedList, a std::map you meant to be a hash. Build those three reflexes and the grid takes care of itself.