bug?
map[key] gets item mapped to key if present, and inserts the key if not, O(N)
thos should be O(1) amortized.
checking existence is O(1)
insertring os O(1)
O(1) + O(1) = O(1)
ignoring collisions of course,
Mainly just asking opinions as it probably just depends on what language you are most comfortable with but…any reason(s) why you would not want to use C++ in your first coding interview? Like, instead of Python? I know you can code programs/exercises quicker in Python but any other reasons? I like both of those languages so much so figured I’d ask.
Agree. For worst case, all should be O(N).
However, if we ignore collision in most cases, get/set element should be O(1).
C++ does have a singly linked list, since C++11 it has had forward_list.
What is the reasoning for recommending deque as a queue rather than queue? It’s backed by a deque by default but only exposes a queue interface and not the full interface of deque which generally makes it a better choice to represent an abstract queue datatype when you don’t actually need to rely on the specific properties of a deque that go beyond the queue interface.
I would recommend using push() and pop() for C++ instead of
enqueue: push_back(item) inserts item at the end of the queue, O(1) dequeue: pop_front() removes and return item from the head of the queue, O(1)