General programming

Short Circuit Evaluation

Short-circuit evaluation is a strategy most programming languages (including JavaScript) use to avoid unnecessary work. For example, say we had a conditional like this:

if (itIsFriday && itIsRaining) {
  console.log('board games at my place!');
}

Let’s say itIsFriday is false. Because JavaScript short-circuits evaluation, it wouldn’t bother checking the value of itIsRaining—it knows that either way the condition is false and we won’t print the invitation to board game night.

We can use this to our advantage. For example, say we have a check like this:

if (friends['Becky'].isFreeThisFriday()) {
  inviteToBoardGameNight(friends['Becky']);
}

What happens if ‘Becky’ isn’t in our friends object? Since friends[‘Becky’] is undefined, when we try to call isFreeThisFriday() we’ll get a TypeError.

Instead, we could first confirm that Becky and I are still on good terms:

if (friends.hasOwnProperty('Becky') && friends['Becky'].isFreeThisFriday()) {
  inviteToBoardGameNight(friends['Becky']);
}

This way, if ‘Becky’ isn’t in friends, JavaScript will ignore the rest of the conditional and avoid throwing the TypeError.

This is all hypothetical, of course. It’s not like things with Becky are weird or anything. We’re totally cool. She’s still in my friends object for sure and I hope I’m still in hers and Becky if you’re reading this I just want you to know you’re still in my friends object.

Garbage Collection

garbage collector automatically frees up memory that a program isn’t using anymore.

For example, say we did this in JavaScript:

function getMin(nums) {
  // NOTE: this is *not* the fastest way to get the min!
  const numsSorted = nums.slice().sort();
  return numsSorted[0];
}

const myNums = [5, 3, 1, 4, 6];
console.log(getMin(myNums));

JavaScript

Look at numsSorted in getMin(). We allocate that whole array inside our function, and once the function returns we don’t need the array anymore. In fact, once the function returns we don’t have any references to it anymore!

What happens to that array in memory? The JavaScript garbage collector will notice we don’t need it anymore and free up that space.

How does a garbage collector know when something can be freed?

One option is to start by figuring out what we can’t free. For example, we definitely can’t free local variables that we’re going to need later on. And, if we have an array, then we also shouldn’t free any of the array‘s elements.

This is the main intuition behind one garbage collector strategy:

  1. Carefully figure out what things in memory we might still be using or need later on.
  2. Free everything else.

This strategy is often called tracing garbage collection, since we usually implement the first step by tracing references from one object (say, the array) to the next (an element within the array).

A different option is to have each object keep track of the number of things that reference it—like a variable holding the location of an array or multiple edges pointing to the same node in a graph. We call this number an object’s reference count.

In this case, a garbage collector can free anything with a reference count of zero.

This strategy is called reference counting, since we are counting the number of times each object is referenced.

Some languages, like C, don’t have a garbage collector. So we need to manually free up any memory we’ve allocated once we’re done with it:

// make a string that can hold 15 characters
// including the terminating null byte ('\0')
str = malloc(15);

// ... do some stuff with it ...

// we're done. free that memory!
free(str);

C

We sometimes call this manual memory management.

Some languages, like C++, have both manual and automatic memory management.

Mutable vs Immutable Objects

mutable object can be changed after it’s created, and an immutable object can’t.

In Javascript, everything (except for strings) is mutable by default:

const array  = [4, 9];

array[0] = 1;
// array is now [1, 9]

JavaScript

Freezing an object makes it immutable, though:

const array  = [4, 9];

// Make it immutable
Object.freeze(array);

array[0] = 1;
// array is still [4, 9]

JavaScript

Strings can be mutable or immutable depending on the language.

Strings are immutable in Javascript:

const testString = 'mutable?';

testString[7] = '!';
// String is still 'mutable?'
// (but no error is raised!)

JavaScript

But in some other languages, like Swift, strings can be mutable:

var testString = "mutable?"

if let range = testString.range(of: "?") {
    testString.replaceSubrange(range, with: "!")
    // testString is now "mutable!"
}

Swift

Mutable objects are nice because you can make changes in-place, without allocating a new object. But be careful—whenever you make an in-place change to an object, all references to that object will now reflect the change.

Practice
Question 1

A crack team of love scientists from OkEros (a hot new dating site) have devised a way to represent dating profiles as rectangles on a two-dimensional plane.

They need help writing an algorithm to find the intersection of two users’ love rectangles. They suspect finding that intersection is the key to a matching algorithm so powerful it will cause an immediate acquisition by Google or Facebook or Obama or something.

Write a function to find the rectangular intersection of two given love rectangles.

As with the example above, love rectangles are always “straight” and never “diagonal.” More rigorously: each side is parallel with either the x-axis or the y-axis.

They are defined as objects like this:

const myRectangle = {

  // Coordinates of bottom-left corner
  leftX: 1,
  bottomY: 1,

  // Width and height
  width: 6,
  height: 3,
};

Your output rectangle should use this format as well.
Do you have an answer? No?
Then here is a hint to help get you started:

Initial Breakdown

Let’s break this problem into subproblems. How can we divide this problem into smaller parts?

Think you have an answer now? Yes?

Then check your answer against these gotchas one at a time:

Gotchas

What if there is no intersection? Does your function do something reasonable in that case?

What if one rectangle is entirely contained in the other? Does your function do something reasonable in that case?

What if the rectangles don’t really intersect but share an edge? Does your function do something reasonable in that case?

Do some parts of your function seem very similar? Can they be refactored so you repeat yourself less?

Full Breakdown

Let’s break this problem into subproblems. How can we divide this problem into smaller parts?

We could look at the two rectangles’ “horizontal overlap” or “x overlap” separately from their “vertical overlap” or “y overlap.”

Lets start with a helper function findXOverlap().

Need help finding the x overlap?

Since we’re only working with the x dimension, we can treat the two rectangles’ widths as ranges on a 1-dimensional number line.

What are the possible cases for how these ranges might overlap or not overlap? Draw out some examples!

There are four relevant cases:

1) The ranges partially overlap:

Two horizontal parallel lines. The right half of the top line overlaps the left half of the bottom line.

2) One range is completely contained in the other:

Two horizontal parallel lines. The bottom line is longer than the top line and extends farther out to the left and right.

3) The ranges don’t overlap:

Two horizontal parallel lines. The right end of the bottom line is to the left of the left end of the top line.

4) The ranges “touch” at a single point:

Two horizontal parallel lines. The right end of the bottom line is directly below the left end of the top line.

Let’s start with the first 2 cases. How do we compute the overlapping range?

One of our ranges starts “further to the right” than the other. We don’t know ahead of time which one it is, but we can check the starting points of each range to see which one has the highestStartPointThat highestStartPoint is always the left-hand side of the overlap, if there is one.

Not convinced? Draw some examples!

Similarly, the right-hand side of our overlap is always the lowestEndPoint. That may or may not be the end point of the same input range that had the highestStartPoint—compare cases (1) and (2).

This gives us our x overlap! So we can handle cases (1) and (2). How do we know when there is no overlap?

If highestStartPoint > lowestEndPoint, the two rectangles do not overlap.

But be careful—is it just greater than or is it greater than or equal to?

It depends how we want to handle case (4) above.

If we use greater than, we treat case (4) as an overlap. This means we could end up returning a rectangle with zero width, which … may or may not be what we’re looking for. You could make an argument either way.

Let’s say a rectangle with zero width (or zero height) isn’t a rectangle at all, so we should treat that case as “no intersection.”

Can you finish findXOverlap()?

Here’s one way to do it:

function findXOverlap(x1, width1, x2, width2) {

  // Find the highest ("rightmost") start point and lowest ("leftmost") end point
  const highestStartPoint = Math.max(x1, x2);
  const lowestEndPoint = Math.min(x1 + width1, x2 + width2);

  // Return null overlap if there is no overlap
  if (highestStartPoint >= lowestEndPoint) {
    return { startPoint: null, width: null };
  }

  // Compute the overlap width
  const overlapWidth = lowestEndPoint - highestStartPoint;

  return { startPoint: highestStartPoint, width: overlapWidth };
}

How can we adapt this for the rectangles’ ys and heights?

Can we just make one findRangeOverlap() function that can handle x overlap and y overlap?

Yes! We simply use more general parameter names:

function findRangeOverlap(point1, length1, point2, length2) {

  // Find the highest start point and lowest end point.
  // The highest ("rightmost" or "upmost") start point is
  // the start point of the overlap.
  // The lowest end point is the end point of the overlap.
  const highestStartPoint = Math.max(point1, point2);
  const lowestEndPoint = Math.min(point1 + length1, point2 + length2);

  // Return null overlap if there is no overlap
  if (highestStartPoint >= lowestEndPoint) {
    return { startPoint: null, overlapLength: null };
  }

  // Compute the overlap length
  const overlapLength = lowestEndPoint - highestStartPoint;

  return { startPoint: highestStartPoint, overlapLength: overlapLength };
}

We’ve solved our subproblem of finding the x and y overlaps! Now we just need to put the results together.

Solution

We divide the problem into two halves:

  1. The intersection along the x-axis
  2. The intersection along the y-axis

Both problems are basically the same as finding the intersection of two “ranges” on a 1-dimensional number line.

So we write a helper function findRangeOverlap() that can be used to find both the x overlap and the y overlap, and we use it to build the rectangular overlap:

function findRangeOverlap(point1, length1, point2, length2) {

  // Find the highest start point and lowest end point.
  // The highest ("rightmost" or "upmost") start point is
  // the start point of the overlap.
  // The lowest end point is the end point of the overlap.
  const highestStartPoint = Math.max(point1, point2);
  const lowestEndPoint = Math.min(point1 + length1, point2 + length2);

  // Return null overlap if there is no overlap
  if (highestStartPoint >= lowestEndPoint) {
    return { startPoint: null, overlapLength: null };
  }

  // Compute the overlap length
  const overlapLength = lowestEndPoint - highestStartPoint;

  return { startPoint: highestStartPoint, overlapLength: overlapLength };
}

function findRectangularOverlap(rect1, rect2) {

  // Get the x and y overlap points and lengths
  const xOverlap = findRangeOverlap(rect1.leftX, rect1.width, rect2.leftX, rect2.width);
  const yOverlap = findRangeOverlap(rect1.bottomY, rect1.height, rect2.bottomY, rect2.height);

  // Return null rectangle if there is no overlap
  if (!xOverlap.overlapLength || !yOverlap.overlapLength) {
    return {
      leftX: null,
      bottomY: null,
      width: null,
      height: null,
    };
  }

  return {
    leftX: xOverlap.startPoint,
    bottomY: yOverlap.startPoint,
    width: xOverlap.overlapLength,
    height: yOverlap.overlapLength,
  };
}
Complexity

 time and  space.

Bonus

What if we had an array of rectangles and wanted to find all the rectangular overlaps between all possible pairs of two rectangles within the array? Note that we’d be returning an array of rectangles.

What if we had an array of rectangles and wanted to find the overlap between all of them, if there was one? Note that we’d be returning a single rectangle.

What We Learned

This is an interesting one because the hard part isn’t the time or space optimization—it’s getting something that works and is readable.

For problems like this, I often see candidates who can describe the strategy at a high level but trip over themselves when they get into the details.

Don’t let it happen to you. To keep your thoughts clear and avoid bugs, take time to:

  1. Think up and draw out all the possible cases. Like we did with the ways ranges can overlap.
  2. Use very specific and descriptive variable names.
Question 2

You decide to test if your oddly-mathematical heating company is fulfilling its All-Time Max, Min, Mean and Mode Temperature Guarantee™.

Write a class TempTracker with these methods:

  1. insert()—records a new temperature
  2. getMax()—returns the highest temp we’ve seen so far
  3. getMin()—returns the lowest temp we’ve seen so far
  4. getMean()—returns the mean  of all temps we’ve seen so far
  5. getMode()—returns a mode  of all temps we’ve seen so far

Optimize for space and time. Favor speeding up the getter methodgetMax()getMin()getMean(), and getMode() over speeding up the insert() method.

Temperatures will all be inserted as integers. We’ll record our temperatures in Fahrenheit, so we can assume they’ll all be in the range 0..110.

If there is more than one mode, return any of the modes.

Do you have an answer? No?

Here is a hint to get you started:

Initial Breakdown

The first thing we want to optimize is our getter methods (per the instructions).

Our first thought might be to throw our temperatures into an array or linked list as they come in. With this method, getting the maxTemp and minTemp would take O(n) time. It would also cost us  space. But we can do better.

Think you have an answer now? Yes?

Then check your answer against these gotchas one at a time:

Gotchas

We can get O(1) time for all methods.

We can get away with only using O(1) additional space. If you’re storing each temperature as it comes in, be careful! You might be taking up O(n) space, where  is the number of temperatures we insert!

Are you trying to be fancy about returning multiple modes if there’s a tie? Good idea, but read the problem statement carefully! Check out that last sentence!

Failing to carefully read or listen to the problem statement is a very common mistake, and it always looks bad. Don’t let it happen to you.

Full Breakdown

The first thing we want to optimize is our getter methods (per the instructions).

Our first thought might be to throw our temperatures into an array or linked list as they come in. With this method, getting the maxTemp and minTemp would take O(n) time. It would also cost us O(n) space. But we can do better.

What if we kept track of the maxTemp and minTemp as each new number was inserted?

That’s easy enough:

class TempTracker {
  constructor() {
    this.minTemp = null;
    this.maxTemp = null;
  }

  insert(temperature) {
    if (this.maxTemp === null || temperature > this.maxTemp) {
      this.maxTemp = temperature;
    }
    if (this.minTemp === null || temperature < this.minTemp) {
      this.minTemp = temperature;
    }
  }

  getMax() {
    return this.maxTemp;
  }

  getMin() {
    return this.minTemp;
  }
}
This wins us  time for getMax() and getMin(), while keeping O(1) time for insert() and removing the need to store all the values.

Can we do something similar for getMean()?

Unlike with minTemp and maxTemp, the new temp and the previous mean won’t give us enough information to calculate the new mean. What other information will we need to track?

To calculate a mean we need to know:

  • how many values there are
  • the sum of all the values

So we can augment our class to keep track of the numberOfReadings and totalSum. Then we can compute the mean as values are inserted:

class TempTracker {
  constructor() {

    // For mean
    this.numberOfReadings = 0;
    this.totalSum = 0;
    this.mean = null;

    // For min and max
    this.minTemp = null;
    this.maxTemp = null;
  }

  insert(temperature) {

    // For mean
    this.numberOfReadings++;
    this.totalSum += temperature;
    this.mean = this.totalSum / this.numberOfReadings;

    // For min and max
    if (this.maxTemp === null || temperature > this.maxTemp) {
      this.maxTemp = temperature;
    }
    if (this.minTemp === null || temperature < this.minTemp) {
      this.minTemp = temperature;
    }
  }

  getMax() {
    return this.maxTemp;
  }

  getMin() {
    return this.minTemp;
  }

  getMean() {
    return this.mean;
  }
}

Can we do something similar for the mode? What other information will we need to track to compute the mode?

To calculate the mode, we need to know how many times each value has been inserted.

How can we track this? What data structures should we use?

Solution

We maintain the maxTempminTempmean, and mode as temperatures are inserted, so that each getter method simply returns a property.

To maintain the mean at each insert, we track the numberOfReadings and the totalSum of numbers inserted so far.

To maintain the mode at each insert, we track the total occurrences of each number, as well as the maxOccurrences we’ve seen so far.

class TempTracker {
  constructor() {

    // For mode
    this.occurrences = new Array(111).fill(0); // Array of 0s at indices 0..110
    this.maxOccurrences = 0;
    this.mode = null;

    // For mean
    this.numberOfReadings = 0;
    this.totalSum = 0;
    this.mean = null;

    // For min and max
    this.minTemp = null;
    this.maxTemp = null;
  }

  insert(temperature) {

    // For mode
    this.occurrences[temperature]++;
    if (this.occurrences[temperature] > this.maxOccurrences) {
      this.mode = temperature;
      this.maxOccurrences = this.occurrences[temperature];
    }

    // For mean
    this.numberOfReadings++;
    this.totalSum += temperature;
    this.mean = this.totalSum / this.numberOfReadings;

    // For min and max
    if (this.maxTemp === null || temperature > this.maxTemp) {
      this.maxTemp = temperature;
    }
    if (this.minTemp === null || temperature < this.minTemp) {
      this.minTemp = temperature;
    }
  }

  getMax() {
    return this.maxTemp;
  }

  getMin() {
    return this.minTemp;
  }

  getMean() {
    return this.mean;
  }

  getMode() {
    return this.mode;
  }
}

We don’t really need the getter methods since they all return properties. We could directly access the properties!

// Method
tempTracker.getMean();

// Property
tempTracker.mean;

JavaScript

We’ll leave the getter methods in our solution because the question specifically asked for them.

But otherwise, we probably would use properties instead of methods. In JavaScript we usually don’t make getters if we don’t have to, to avoid unnecessary layers of abstraction. But in Java we would use getters because they give us flexibility—if we wanted to change how we calculate values (for example, we might want to calculate a value just-in-time), it won’t change how other people interact with our class—they wouldn’t have to switch from using a property to using a getter method. Different languages, different conventions.

Complexity

O(1) time for each method, and O(1) space related to input! (Our occurrences array‘s size is bounded by our range of possible temps, in this case 0-110)

What We Learned

This question brings up a common design decision: whether to do work just-in-time or ahead-of-time.

Our first thought for this question might have been to use a just-in-time approach: have our insert() method simply put all of the temperatures in an array as they are recorded, and then have our getters compute e.g. the mode just-in-time, at the moment the getter is called.

Instead, we used an ahead-of-time approach: have our insert method compute and store our mean, mode, max, and min ahead of time (that is, before they’re asked for). So our getter just returns the precomputed value in O(1 time.

In this case, the ahead-of-time approach doesn’t just speed up our getters…it also reduces our space cost. If we stored all the temperatures as they came in and computed each metric just-in-time, we’d need O(n) space for n insert()s.

As an added bonus, the ahead-of-time approach didn’t increase our asymptotic time cost for inserts, even though we added more work. With some cleverness (channeling some greedy thinking to figure out what we needed to store in order to update the answer in O(1) time), we were able to keep it at O(1) time.

It doesn’t always happen this way. Sometimes there are trade-offs between just-in-time and ahead-of-time. Sometimes to save time in our getters, we have to spend more time in our insert.

In those cases, whether we should prefer a just-in-time approach or an ahead-of-time approach is a nuanced question. Ultimately it comes down to your usage patterns. Do you expect to get more inserts than gets? Do slow inserts have a stronger negative effect on users than slow gets?

We have some more questions dealing with this stuff coming up later.

Whenever you’re designing a data structure with inserts and getters, think about the advantages and disadvantages of a just-in-time approach vs an ahead-of-time approach.

Bonus

There’s at least one way to use a just-in-time approach, have O(1) time for each operation, and keep our space cost at O(1) for  inserts. How could we do that?