---
marp: true
title: 22 October 2020
---

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

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

---
### <!-- fit --> WELCOME BACK!

---
# Review from last week: Interfaces
* an **Interface** is a shared boundary across which two or more separate components of a computer system exchange information
* Interfaces have to be implemented by a specific class, they can't function on their own, using the keyword ```implements```.
* You also have to implement **all the methods the interface declares**.

---
# Algorithims

* **Algorithm analysis** the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.

* **Big-O notation** is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

* you're asked about this in basically every tech interview

---
# O(n)
involves itterating though an object of size n

```java
HauntedHouse(House[] houses) {

  for(House h : houses) {
    if(h.isHaunted() == true) {
      panik();
    }
  }

}

```

---
# O(n^2)
involves itterating though an object of size n, n times (n * n)

```java
HasCandy(House[][] neighborhood) {

  for(i = 0; i < neighborhood.length; ) {
    if(h.isHaunted() == true) {
      panik();
    }
  }

}
```

---
# ArrayList
* The ArrayList class we have been implementing so far this week, is a resisable array
* The ```Array``` is traditionally an immutable object, meaning once it's been created, we can't make changes to it
  * so far, we have been getting around this by creating a ``new`` array each time, and copying the values we would like to keep back in.
  * deep copy


---
# ArrayList: Add/Remove
General strategy: 

1) create list of size  input.length +- 1 (depending on add/remove)
2) Itterate through input array
  3) If we want to insert: place the new value in, then insert the rest
  4) If we want to delete: ```continue``` through the array without copying the value in
  5) otherwise, continue copying values over.

6) return your newly-created array


---
# Example 1: Two Sum
This is a common interview-type question you may get, ***solve it, and give the runtime for your algorithim***

* 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

```Java
public int[] twoSum(int[] nums, int target) {
        
}
```

---
# Example 2: Remove Duplicates
another common interview-type question you may get, ***solve it, and give the runtime for your algorithim***
* Given a sorted array nums, remove the duplicates
* Return the length of this new array
* BONUS: can you solve this in-place? (O(1) space complexity)

```Java
public int removeDuplicates(int[] nums) {
}
```

---
# Example 3: Social Distancing
* You are the owner of a haunted house, and want to make sure you can fit your actors properly according to cdc guidelines. 
* ```int[] house ``` represents the squares you can place them in where 1 represents an occupied square
* Keep the actors at least one square apart [0, 1, 0, 1, 0, 1]
* Return true if you can keep all the actors distanced **without** extending the array, false otherwise

```Java
public bool canSocialDistance(int[] house, int n) {
}
```

---
#  <!-- fit --> Solutions 
## <!-- fit --> (no peeking, it's for your own good!)
---
## <!-- fit --> (no seriously, attempt the problems with your groupmates first!)

---
# Example 1 Solution   
 source: https://leetcode.com/problems/two-sum/


---
# Example 2 Solution 
source:    

---
# Example 3 Solution
source: https://leetcode.com/problems/can-place-flowers/

---
# Additional Sources
* https://www.w3schools.com/java/java_interface.asp
* Retired EMP slides: https://docs.google.com/presentation/d/1D2xN_lJFHAuPlAkVzZJ4CR2Ypvyb-ZoAzeHHrdMvT-o/edit#slide=id.g43508f564e_0_437

---
# Want more coding challenges?
* Hackerrank (interview prep, multiple languages):
  *   https://www.hackerrank.com
* CodingBat (for beginers in Java, Python): 
  * https://codingbat.com/java
