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

Review: 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 (10 minutes)

  • Let's implement memoized factorial as we mentioned in the previous slide. This can make the O(n)O(n) algorithm faster in many cases by using what we have already done.

  • So if you already called 5!5! then you store that result.

  • Then when you call say 8!8! you compute 8∗7∗68 * 7 * 6 and multiply that by your old result of 5!5! and store that.

  • After this if you call 10!10! you compute 10∗9∗8!10*9*8! where 8!8! is your old result.

Starter code

public class F {
  public static long factorial(long n) {
    long f = 1L;
    for (long i = n; i > 0; i--) {
      f = f * i;
    }
    return f;
  }
}
System.out.println(F.factorial(5));  // 120
System.out.println(F.factorial(8));  // 40320
System.out.println(F.factorial(10)); // 3628800

Throwing exceptions

Exceptions

  • Exceptions are like errors except your code can handle it yourself to prevent the program from crashing.

  • You can use them to denote exceptional circumstances and how to deal with them.

  • Using these we can create fault tolerant programs that can keep running for years and even decades.

  • Imagine government web servers, spacecraft etc. You can't have these crashing.

Exception objects

  • There are lots of different types of objects that we use to denote exceptions.

  • They all inherit from the Exception class, if you don't know which one you want to use you can use just that, but it's usually more helpful to pick specific ones.

  • Adding a String message is often helpful, but optional.

  • IllegalArgumentException("Factorial input must be positive")

  • ArithmeticException("Factorial did not work for negative numbers")

  • IllegalStateException("This tictactoe board configuration is impossible");

Throwing exceptions

  • You use the throw keyword to say that it has occured. Unless some other code in the program 'catches' it, the program will exit.

  • Give it an exception object to throw.

  • throw new IllegalArgumentException("Factorial input must be positive")

  • throw new ArithmeticException()

  • throw new IllegalStateException("This tictactoe board configuration is impossible");

Problem (10 minutes)

  • Create a function splitEmail(String in) to split an email for the name and the domain. Take a string input and return it as a List of two strings.

  • challen@illinois.edu gives me a list with challen and illinois.edu.

  • If the input is null throw a NullPointerException

  • If the input does not contain a @ throw a IllegalArgumentException

  • No starter code :)

Catching exceptions and exception handling patterns

try and catch

We use try to put in the code that could have exceptions and catch(ExceptionType e) for each type of error

try {
  var l = splitEmail("abc@example.com");
  System.out.println(l.get(0));
} catch (NullPointerException e) {
  System.out.println("Give a proper email");
} catch (IllegalArgumentException e) {
  System.out.println(e.getMessage()); // print out the exception object's message
} catch (Exception e) {
  System.out.println("This covers all other generic exceptions");
}

the finally keyword

This code will always be executed no matter how the exception states go.

Used for cleanup code, you probably don't have to worry about it too much but it's sometimes there.

try {
  var l = splitEmail("abc@example.com");
  System.out.println(l.get(0));
} catch (NullPointerException e) {
  System.out.println("Give a proper email");
} finally {
  System.out.println("Thanks for using the program");
}

Rethrowing exceptions

try {
  throw new Exception("Had a problem");
} catch (NullPointerException e) {
  System.out.println("Had a problem: " + e);
  throw e;
} catch (Exception e) {
  System.out.println("Exceptionally: " + e);
  throw new IllegalStateException(e);
}

Sometimes we want to rethrow exceptions, sometimes you want to just log it or change the type.

Making your exceptions

And you can make your own exceptions as well really easily. Just extend Exception and you're done.

public class EMPNotEnoughException extends Exception { }

Problem (10 minutes)

  • Exception printer. Let's say we have a function getWebpage()

  • I want NullPointerException to be printed out on screen but rethrown.

  • I want IllegalStateException to be printed on screen but not rethrown (i.e. you handle it)

  • I want the remaining types of exceptions to not be printed, but rethown.

  • Make a finally block that prints Thank you for using our web browser

try {
  getWebPage("kotlin.cs.illinois.edu");
}

Solutions

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

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

1)

import java.util.HashMap;
public class F {
  private static HashMap<Long, Long> precomputedResults = new HashMap<>();
  public static long factorial(long n) {
    long f = 1L;
    for (long i = n; i > 0; i--) {
      if (precomputedResults.containsKey(i)) {
        f = f * precomputedResults.get(i);
        break;
      }
      f = f * i;
    }
    precomputedResults.put(n, f);
    return f;
  }
}
System.out.println(F.factorial(5));  // 120
System.out.println(F.factorial(8));  // 40320
System.out.println(F.factorial(10)); // 3628800

2)

import java.util.List;
import java.util.LinkedList;

List<String> splitEmail(String in) {
  if (in == null) {
    throw new NullPointerException();
  }
  
  if (!(in.contains("@"))) {
    throw new IllegalArgumentException();
  }
  
  var parts = in.split("@");
  var list = new LinkedList<String>();
  list.add(parts[0]);
  list.add(parts[1]);
  return list;
}
System.out.println(splitEmail("challen@illinois.edu"));

3

3)

public void getWebPage(String url) {
  return;
}
try {
  getWebPage("kotlin.cs.illinois.edu");
} catch (NullPointerException e) {
  System.out.println("null");
  throw e;
} catch (IllegalStateException e) {
  System.out.println("illegal");
} catch (Exception e) {
  throw e;
} finally {
  System.out.println("Thank you for using our web browser");
}