You're getting ready for a leetcode-style interview in python. This post is an all-inclusive guide to the data structures you will need.
List
Starting out with the most basic data structure, lists will provide the needed functionality to solve a good portion of problems.
Lists are your friend when you need to use a Stack (Last-in, First-out), the .append() and .pop() (with no argument passed in) functionalities will manage that order for you.
# Declare a list
arr = []
# Append
item = 1
arr.append(item)
# Remove the last element
arr.pop()
# Remove an element at a given index
arr.pop(i)
Dictionary/Hash Map
You have two options for dictionaries, which come with a very simple tradeoff.
I go over the basic built-in dictionary functionality below, but I also leave a note afterwards about an alternative you can try if you encounter some issues.
dict = {}
#Add a key-value pair
dict['hello'] = 'goodbye'
dict['blog'] = 'post'
#dict = {'hello': 'goodbye', 'blog': 'post'}
#Remove a key
del dict["blog"]
#dict = {'hello': 'goodbye'}
#Check if a key is in a dictionary
if "blog" in dict:
Minor note:
Dictionaries can be a bit tricky because you'll occasionally run into an error if you try to access a key that doesn't exist in a dictionary. I don't want to overcomplicate this for you because these problems are somewhat rare and you should see whether your style of coding even encounters this issue.
If it does, feel free to look into DefaultDict. I used DefaultDict for the longest time but then felt that using the built-in dictionary was just a bit easier if you learn to bypass the error messages.
Heap(Priority Queue)
Priority queue's are definitely a bit ugly in python, but they are incredibly useful in many leetcode problems. You'll definitely need some practice using them in different scenarios before your interviews since they can get a bit complicated.
This also requires an import, but there's no built-in way to make a heap in python without such.
One more thing to note is that any heap you create using heapq will necessarily be a _min_heap, meaning 1, 2, 3 instead of 3, 2, 1. More on this below.
import heapq
h = [] # a normal array declared as always
heapq.heappush(h, 1)
heapq.heappush(h, 2)
heapq.heappop(h) # returns the value of the element (in this case 1)
You can also turn an existing list into a heap using heapq.heapify().
a = [1, 5, 3, 6, 2]
heapq.heapify(a)
# a is now [1, 2, 3, 5, 6]
Using tuples to sort non-numeric variables
Now, if you want to sort non-numeric variables and pass a weight in, you can do this with tuples.
h = []
heappush(h, (2, 'hello')
heappush(h, (6, 'goodbye'))
heappush(h, (4, 'this is'))
heappush(h, (1, 'my blog'))
heappop(h) # will return (1, 'my blog')
Converting a minheap to a maxheap
The last detail to know has to do with the fact that this is always a min-heap. What if you want the greatest value and not the least? What you can do in this case is multiply each value by -1 whenever you add to or remove from the heap.
The above example has been adapted to a max heap.
h = []
heappush(h, (-1 * 2, 'hello')
heappush(h, (-1 * 6, 'goodbye'))
heappush(h, (-1 * 4, 'this is'))
heappush(h, (-1 * 1, 'my blog'))
heappop(h) # will return (-6, 'goodbye')
If you wanted to then use that -6 (which really represents 6, you could simply multiply that by -1.
Queue
In my experience I think I always used other data structures during interviews, but if you like to approach problems with queues, you should know about a few ways to handle queues.
You could use a list to manage a queue and always pass in 0 as the argument to pop. (That is, strictly uses .append(i) and .pop(0). However, this isn't ideal for space and time complexity since every remaining element in the list will get copied over in memory.
There is an alternative, although it requires an import. You should probably check with your interviewer if this is okay, but at the very least you can demonstrate your understanding of data structures by discussing these tradeoffs.
Here's how to use the alternative:
from collections import deque
# Initialize a queue
queue = deque()
# Add an element
q.append(1)
# Remove an element
print(q.popleft())
Top comments (1)
What's your favorite data structure for coding interviews? Did I miss any?