CS 199 EMP

Even More Practice

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 OO complexity of your solution.
  • hint: remember what % does?
  • hint: look up how to add an element to the start of a list
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

@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

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)O(n) as it has to multiply nn 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∗15! = 5 * 4 * 3 * 2 * 1, then 7!=7∗6∗5!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(n2)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)O(n) solution.
import java.util.HashMap;
public int[] twoSum(int[] nums, int target) {
        
}

Solutions

(no peeking, it's for your own good!)

(no seriously, attempt the problems with your groupmates first!)

1)

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)

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)

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