during interview

• reiterate the question and clear out any confusions
• consider asking for 'edge cases ahead of time'.
  questions like "are there duplicate values on the input list?"
• write test cases thinking about edge cases as well. python testing#^bab8c4

• about modifying input array or returning a new arr:
  some people don't consider return array as auxiliary space

good knowledge

queue = [(i,j)]
curr_x, vurr_y = queue.pop(0)

this pop is actually O(n) bc python list is implemented this way.
to actually make this pop O(1) I have to implement a class called dequeue

slicing and concatenating values sequences create copies and require O(n) time, use start and end indices where possible.
corner cases: sequence that is empty, has 1 or 2 elements or has repeated elements.

deque

instead of memorizing the interfaces of a stak, queue and linked list I could learn to use deque. deque is built in python.
deque is a double ended queue that can add or remove elements from both ends in linear time.
if interviewer doesn't know what deque is I could explain and ask if I could use it.

deque vs list append and pop
deque is implemented as a double linked list.
deques have O(1) speed for appendleft() and popleft() while lists have O(n) for insert(0, value) and pop(0)
list append have to reallocate memory when growing in size, deques are consistent (since it is a linked list)
for append and pop to the right they are similar.

string builders instead of string concatenation

do not concatenate string within a loop.
strings are immutable. concatenating strings with '+' creates another object in memory, which is linear time O. instead use String Builder to build strings in constant time
or use "".join for the same effect
String builder is O(n), string concatenation is O(n^2)

dict del vs pop

I can use del(my_dic[my_key]) or my_dic.pop(my_key)

• del is faster bc doesn't have to return the key-val pair