CS 199 EMP

Even More Practice

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

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)

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
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)
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
public bool canSocialDistance(int[] house, int n) {
}

Solutions

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

(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

Want more coding challenges?