Hash maps and interviews
Linked Lists
Linked List Homework Review
Linked list implementation
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next_node = next_node
def get_data(self):
return self.data
def get_next(self):
return self.next_node
def set_next(self, new_next):
self.next_node = new_next
Exercise
Writing find max with Linked Lists
Click here!
Complexity of linked lists
WikipediaHash maps
Dictionaries/ Objects/ Hash Maps/ Maps
myObject = { key : value,
key : value,
key : value }
Associative array
- Unordered associative array is the abstract data type that describes map of keys to values
- Dictionaries, hash maps, maps, symbol tables, are all examples of implementations to this problem
-
Operations include
- adding a pair to the collection
- removing a pair
- modifying an existing pair
- looking up a value associated with a particular key
Question time!
We're going to determine the time complexity of some operations on hash maps.
- What is the input N?
- How long does each step take?
What is the time complexity of...
looking up a value based on a key
phone_book = {'wong': 4098, 'scott': 4139}
phone_book['wong']
O(1) - Constant
O(n) - Linear
O(logn) - Logarithmic
What is the time complexity of...
Adding or removing a pair
phone_book = {'wong': 4098, 'scott': 4139}
phone_book['cooper'] = 6802
O(1) - Constant
O(n) - Linear
O(n2) - Quadratic
What is the time complexity of...
Looping over the set
phone_book = {'wong': 4098, 'scott': 4139}
for name, num in phone_book.items()
print name
O(1) - Constant
O(n) - Linear
O(n2) - Quadratic
Exercise
Letter count
Click here!
Time and space complexity of letter count
Time - O(n)
Space - O(1)
Recursion
Recursion
A method to solving problems where the solution depends on smaller forms of the same problem.
Solve part of the problem, and then combine that with the solution to the rest of the problem.
Exercise
Adding up all items in a list
Click here!
Time and space complexity?
Technical interviews
What to expect (typically)
This varies a lot between organizations, interviewers and problems.
- Interviewer will present the problem
- Make sure you understand the problem - ask questions
- Discuss possible ways to solve the problem - maybe write some pseudo code
- Write code for the most efficient solution you know how to implement
- Check your work and discuss test cases
- Discuss complexity and how to optimize your solution
How to prepare
- Practice writing code while talking aloud
- Not all technical interviews involve coding
- Interviews are a specific skill that takes practice to learn.
Q&A
Mock interview
Let's pick a problem as a class and one of the TAs can mock interview me.