Collections · interview question
Choose the typical (average) time complexity of each operation.
Matrix / gridMedium
Choose for each row.
| Item | O(1) | O(log n) | O(n) |
|---|---|---|---|
| `ArrayList.get(i)` | |||
| `LinkedList.get(i)` | |||
| `HashMap.get(key)` | |||
| `TreeMap.get(key)` | |||
| `ArrayList.add(e)` at the end (amortized) |
Answer and explanation
Correct answer
ArrayList.get(i): O(1)LinkedList.get(i): O(n)HashMap.get(key): O(1)TreeMap.get(key): O(log n)ArrayList.add(e)at the end (amortized): O(1)
Why
LinkedList rarely wins in practice. Even inserts in the middle need an O(n) walk to find the position, and arrays are cache-friendly.
References
Test yourself on Collections
A free test with instant, explained results. No account needed.
More Collections questions
- Which statement about nulls in maps is correct?
- Which interface should a class implement to define its natural ordering, so that Collections.sort(list) works without…
- If you need a collection that supports quick insertion and removal of elements at both ends, but also provides indexed…
- Why do teams use a HashSet over a List when storing items in production code?
- Which Java collection should you use if you need to store elements with fast random access and allow duplicates?
- Which collection does not allow duplicate elements?