[timmaxw]

In Python job interviews, I think the interviewer will only judge your code on asymptotic complexity, not absolute speed. I think Python engineers generally aren't expected to know how to micro-optimize their Python code.

Some general tips for algorithmic complexity in Python:

- Python's list is equivalent to C++ std::vector. If you need to push/pop at the head of the list, use Python's "collections.deque" to avoid the O(N) cost. Python's standard library doesn't have a linked list implementation.

- Python's dict is a fast unordered hashmap. However, if you need order-aware operations like C++'s std::map::lower_bound(), you're out of luck; Python's standard library doesn't have a tree implementation.

- Python has a "bisect" module for binary searching in a Python list, and a "heapq" module for using a Python list as a heap. However, neither one is nicely encapsulated in a data type.

If your Python program is seriously CPU-bound, the normal solution is to use a C/C++/Rust extension. For example, if you're doing large numeric calculations, use NumPy; it can store a vector of numbers as a single contiguous array, which is much faster than a list-of-Python-floats.

If you want to parallelize across CPU cores, it's important to understand the Python GIL (global interpreter lock). Often you need to use multiple Python processes. See e.g. https://superfastpython.com/multiprocessing-pool-gil/

Maybe also worth reading about __slots__ (https://wiki.python.org/moin/UsingSlots); it's a micro-optimization that helps when allocating a lot of tiny Python objects.

Hope some of that is helpful! Good luck with your job interviews.

[ZeroCool2u]

"- Python's dict is a fast unordered hashmap. However, if you need order-aware operations like C++'s std::map::lower_bound(), you're out of luck; Python's standard library doesn't have a tree implementation."

I'm fairly certain that in Python 3.7 and later standard library dictionaries are now ordered by default.

[alfons_foobar]

Ordered by insertion (see [Mailinglist](https://mail.python.org/pipermail/python-dev/2017-December/1...))

This might or might not be what you want/expect...

[johndough]

You are correct. Dicts are ordered by insertion. Also, I'd like to add that, maybe surprisingly, sets are not.

    >>> set([3, 2, 1])
    {1, 2, 3}

    >>> set([10, 100, 1000])
    {1000, 10, 100}

[timmaxw]

Yes, Python dicts remember insertion order. This is different from C++ std::map, which maintains the keys in sorted order. For example, std::map::lower_bound(X) finds "the smallest key in the map which is greater than or equal to X" in O(log(N)) time. I don't think Python has any data structure in the standard library that supports this operation while also supporting insertion in O(log(N)) time.

[az09mugen]

You're right, it's even python 3.6, and you have also the OrderedDict https://realpython.com/python-ordereddict/

[DangitBobby]

A little nitpick: they were always ordered by insertion, 3.7 just codified that behavior as a guarantee instead of an implementation detail.

[azundo]

I believe lower_bound is ordering by key comparison - python dicts are insertion ordered.