---
marp: true
title: 5 November 2020
---

# <!-- fit --> CS 199 EMP

## <!-- fit --> Even More Practice

---

# <!-- fit --> Attendance Link:

https://forms.gle/8yto1LvJ4hntiKNu7

---

# 2 meetings every week Tuesday and Thursday

* Early CST - Early risers and Eastern timezones

* Evening CST - Western timezones (and really late Eastern folks)

* Calendar contains zoom links

* Attend 7 sessions for credit, attendence via google form.

---

# Format

* 3 practice problems every session

* focused on practical understanding of concepts covered recently in class

* slides and material available after both sessions

--- 

# How to follow along:

* Small breakout rooms of working together 

* Work for 10-15 minutes together, feel free to use paper, whiteboards, online share tools.

* Use the code playground on the 125 homepage for the interactive running

---
# Review: Maps
* Arguably the most helpful data structure to use in any technical interview! Get used to using them, your life will be better!
* If you've used python before, these are also known as dictionaries.
* Acess a value based on some other unique key value. Examples include:
  * Your friends, and what their favorite color is
  * Words in a book, and what their part of speech is
  * Store products, and how many of each is in stock
* each key maps to **exactly one** value

Documentation: https://docs.oracle.com/javase/7/docs/api/java/util/Map.html

---
# Problem 1: Number List (10 minutes)
Given an integer, represent it as a List object, for example:
* input: `12345`
* output: `{1, 2, 3, 4, 5}`
* What is the big $O$ complexity of your solution.
* hint: remember what `%` does?
* hint: look up how to add an element to the start of a list


```java
import java.util.List;
import java.util.LinkedList;
List<Integer> numberList(int num) {
  var list = new LinkedList<Integer>();
  return list;
}
System.out.println(numberList(53251));
```

---
# Hashing

```java
@Override public int hashCode() {
  return Objects.hash(x, y, z);
}
```

* (From Lecture) A hash function is any function that can be used to map data of arbitrary size to fixed-size values.
* Every input in a hash function should produce a unique hash, otherwise, we have a **hash collision**
  * Birthday Paradox
  * The larger the hash, the less likley we are to have hash collisions (exponential)
  * For refference, Git uses a 160 bit hash function

---
# Problem 2: More with Maps (10 minutes)
Given a map of your friends and their favorite colors, return a list of all the friends with the same favoite color

```java
import java.util.List;
List<String> sharedFavoriteColor(String color,  Map<String, String> friendsToColors) {
}
var m = new HashMap<String, String>();
m.put("Harsh", "Green");
m.put("Rima", "Green");
m.put("David", "Blue");
System.out.println(sharedFavoriteColor("Green", m)); // Harsh and Rima
```

---

# Memoization

* It's the practice of storing results of computation to speed up the overall task.

* For example calculating a factorial is $O(n)$ as it has to multiply $n$ times.

* However, if we have to calculate a lot, we can store our past results to speed up new ones.

* Like let's say we already did $5! = 5 * 4 * 3 * 2 * 1$, then $7! = 7 * 6 * 5!$, so if we stored that already it can save time.

* To do this we often use `Map` or `List`. If it's a map we use the key as the input and the output to store the result. Since Map/List lookups are fast this works very well in practice.


---
# Problem 3: Two Sum, but faster (15 minutes)
* A few weeks ago, we had the infamous two sum interview question
* The runtime of the algorithim you gave was $O(n^2)$. Let's try to make it faster with a hashmap.
  * Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
  * assume that the array has only one solution
  * You may not use the same element twice.
  * Order of the return indecies does not mattter
* Use memoization to give a $O(n)$ solution.

```Java
import java.util.HashMap;
public int[] twoSum(int[] nums, int target) {
        
}
```

---

#  <!-- fit --> Solutions 
## <!-- fit --> (no peeking, it's for your own good!)

---
## <!-- fit --> (no seriously, attempt the problems with your groupmates first!)

---
### 1)

```java
import java.util.List;
import java.util.LinkedList;
List<Integer> numberList(int num) {
  var list = new LinkedList<Integer>();
  for (int n = num; n > 0; n /= 10) {
    list.offerFirst(n % 10);
  }
  return list;
}
System.out.println(numberList(53251));
```

---
### 2)
```java
List<String> sharedFavoriteColor(String color,  Map<String, String> friendsToColors) {
  var names = new ArrayList<String>();
  for (var name: friendsToColors.keySet()) {
    System.out.println(name);
    if (friendsToColors.get(name).equals(color)) {
      names.add(name);
    }
  }
  return names;
}
```

---
### 3)
```java
import java.util.HashMap;
 
public int[] twoSum(int[] nums, int target) {
  var complimentMap  = new HashMap<Integer, Integer>();

  // loop through current + compliment = target
  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
         
    if (complimentMap.containsKey(complement)) {
      int[] pair = {i, complimentMap.get(complement)};
      return pair;
    }
    complimentMap.put(nums[i], i);
  }
  return null;
}
```
source: https://medium.com/@jhng2525/leetcode-two-sum-problem-solution-java-7ccb7a01fb3a
