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.