What is structuredClone()?

• structuredClone() is a global function introduced in 2022 that enables deep cloning of JavaScript objects. Unlike traditional methods like JSON.stringify() and JSON.parse(), which struggle with complex structures and circular references, structuredClone() handles these challenges effortlessly.

Why is it a game-changer?

• It’s a robust tool for creating true deep clones, preserving the integrity of nested objects and circular references without the need for extra logic or workarounds. Plus, it’s available in modern environments, including Web Workers.

1. Simple Object Cloning: The Basics

• Using {...obj} (Shallow Copy)

const original = { name: "Alice", details: { age: 25 } };
  const shallowCopy = { ...original };

  shallowCopy.details.age = 30;

  console.log(original.details.age); // 30
  console.log(shallowCopy.details.age); // 30

The spread operator {...obj} only creates a shallow copy. The details object is not deeply cloned, so changes to shallowCopy.details affect the original details as well.

Using JSON.stringify() + JSON.parse() (Deep Copy)

const original = { name: "Alice", details: { age: 25 } };
  const deepCopy = JSON.parse(JSON.stringify(original));

  deepCopy.details.age = 30;

  console.log(original.details.age); // 25
  console.log(deepCopy.details.age); // 30

This method creates a deep copy, but it has limitations: it cannot handle functions, undefined, or circular references.

Using structuredClone() (Deep Copy)

const original = { name: "Alice", details: { age: 25 } };
  const clone = structuredClone(original);

  clone.details.age = 30;

  console.log(original.details.age); // 25
  console.log(clone.details.age); // 30

structuredClone() creates a deep clone, preserving the structure without any of the limitations of JSON.stringify() and handling complex data types like circular references and undefined.

2. Handling Circular References: A Challenge

• Circular Reference with {...obj}

const original = { name: "Alice" };
  original.self = original;

  // This will cause an error:
  const shallowCopy = { ...original }; // TypeError: Converting circular structure to JSON

{...obj} can’t handle circular references, resulting in an error.

• Circular Reference with JSON.stringify()

const original = { name: "Alice" };
  original.self = original;

  // This will cause an error:
  const jsonCopy = JSON.parse(JSON.stringify(original)); // TypeError: Converting circular structure to JSON

JSON.stringify() also fails with circular references, throwing an error.

• Circular Reference with structuredClone()

const original = { name: "Alice" };
  original.self = original;

  const clone = structuredClone(original);

  console.log(clone !== original); // true
  console.log(clone.self === clone); // true

structuredClone() seamlessly handles circular references, creating a proper deep clone without errors.

3. Cloning with Functions and undefined: Another Test

• Using {...obj}

const original = { name: "Alice", greet: () => "Hello!", value: undefined };
  const shallowCopy = { ...original };

  console.log(shallowCopy.greet()); // "Hello!"
  console.log(shallowCopy.value); // undefined

{...obj} copies functions and undefined as expected, but only shallowly.

• Using JSON.stringify()

const original = { name: "Alice", greet: () => "Hello!", value: undefined };
  const jsonCopy = JSON.parse(JSON.stringify(original));

  console.log(jsonCopy.greet); // undefined
  console.log(jsonCopy.value); // undefined

JSON.stringify() cannot serialize functions or undefined, resulting in their loss in the cloned object.

• Using structuredClone()

const original = { name: "Alice", greet: () => "Hello!", value: undefined };
  const clone = structuredClone(original);

  console.log(clone.greet); // undefined
  console.log(clone.value); // undefined

structuredClone() also does not clone functions but preserves undefined values, making it more reliable than JSON.stringify() for complex objects.

4. Speed and Efficiency: A Performance Note

• Efficiency with Large Data

const largeArray = new Array(1e6).fill({ key: "value" });

  console.time("structuredClone");
  const clone = structuredClone(largeArray);
  console.timeEnd("structuredClone");

  console.time("JSON.stringify + JSON.parse");
  const jsonCopy = JSON.parse(JSON.stringify(largeArray));
  console.timeEnd("JSON.stringify + JSON.parse");

structuredClone() is often faster than JSON.stringify() + JSON.parse() for large, complex data, and avoids the pitfalls of serializing and deserializing.

5. Conclusion: Why structuredClone() is the Future

• Reliability: Handles circular references, functions, and undefined values more predictably.
• Efficiency: Performs deep cloning faster for large datasets and doesn’t require workarounds.
• Simplicity: One method to rule them all — no more choosing between {...obj}, JSON.stringify(), or custom deep clone functions.

You want to build a word cloud, an infographic where the size of a word corresponds to how often it appears in the body of text.

To do this, you’ll need data. Write code that takes a long string and builds its word cloud data in a hash map, where the keys are words and the values are the number of times the words occurred.

Think about capitalized words. For example, look at these sentences:

"After beating the eggs, Dana read the next step:"
"Add milk and eggs, then add flour and sugar."

What do we want to do with “After”, “Dana”, and “add”? In this example, your final hash map should include one “Add” or “add” with a value of 22. Make reasonable (not necessarily perfect) decisions about cases like “After” and “Dana”.

Assume the input will only contain words and standard punctuation.

You could make a reasonable argument to use regex in your solution. We won’t, mainly because performance is difficult to measure and can get pretty bad.

Are you sure your code handles hyphenated words and standard punctuation?

Are you sure your code reasonably handles the same word with different capitalization?

Try these sentences:

"We came, we saw, we conquered...then we ate Bill's (Mille-Feuille) cake."
"The bill came to five dollars."

We can do this in O(n)O(n) runtime and space.

The final hash map we return should be the only data structure whose length is tied to nn.

We should only iterate through our input string once.

Breakdown

We’ll have to go through the entire input string, and we’re returning a hash map with every unique word. In the worst case every word is different, so our runtime and space cost will both be at least O(n)O(n).

This challenge has several parts. Let’s break them down.

1. Splitting the words from the input string
2. Populating the hash map with each word
3. Handling words that are both uppercase and lowercase in the input string

How would you start the first part?

We could use the built-in String.split() method to separate our words, but if we just split on spaces we’d have to iterate over all the words before or after splitting to clean up the punctuation. And consider em dashes or ellipses, which aren’t surrounded by spaces but nonetheless separate words. Instead, we’ll make our own splitWords() method, which will let us iterate over the input string only once.

We’ll check if each character is a letter with Character.isLetter().

Now how can we split each word? Let’s assume, for now, that our helper method will return a list of words.

We’ll iterate over all the characters in the input string. How can we identify when we’ve reached the end of a word?

Here’s a simple example. It doesn’t work perfectly yet — you’ll need to add code to handle the end of the input string, hyphenated words, punctuation, and edge cases.

public static List<String> splitWords(String inputString) {
List<String> words = new ArrayList<>();
    int currentWordStartIndex = 0;
    int currentWordLength = 0;
    for (int i = 0; i < inputString.length(); i++) {
        char c = inputString.charAt(i);
        if (Character.isLetter(c)) {
            if (currentWordLength == 0) {
                currentWordStartIndex = i;
            }
            currentWordLength++;
        } else {
            String currentWord = inputString.substring(currentWordStartIndex,
                currentWordStartIndex + currentWordLength);
            words.add(currentWord);
            currentWordLength = 0;
        }
    }
    return words;
}

Careful — if you thought of building up the word character by character (using +=), you’d be doing a lot more work than you probably think. Every time we append a character to a string, Java makes a whole new string. If our input is one long word, then creating all these copies is O(n2)O(n2) time.

Instead, we keep track of the index where our word starts and its current length. Once we hit a space, we can extract the substring with our word and append it to the list. That keeps our split method at O(n)O(n) time.

Another option would be to use a StringBuilder. Lots of different ways to work with strings.

Now we’ve solved the first part of the challenge, splitting the words. The next part is populating our hash map with unique words. What do we do with each word?

If the word is in the hash map, we’ll increment its count. Otherwise, we’ll add it to the hash map with a count of 1.

private Map<String, Integer> wordsToCounts = new HashMap<>();
public void addWordToHashMap(String word) {
    if (wordsToCounts.containsKey(word)) {
        wordsToCounts.put(word, wordsToCounts.get(word) + 1);
    } else {
        wordsToCounts.put(word, 1);
    }
}

Alright, last part! How should we handle words that are uppercase and lowercase?

Consider these sentences:

"We came, we saw, we ate cake."
"Friends, Romans, countrymen! Let us eat cake."
"New tourists in New York often wait in long lines for cronuts."

Take some time to think of possible approaches. What are some other sentences you might run into. What are all your options?

When are words that should be lowercase not?
Why not?
What are the ideal cases we’d want in our hash map?

Here are a few options:

1. Only make a word uppercase in our hash map if it is always uppercase in the original string.
2. Make a word uppercase in our hash map if it is ever uppercase in the original string.
3. Make a word uppercase in our hash map if it is ever uppercase in the original string in a position that is not the first word of a sentence.
4. Use an API or other tool that identifies proper nouns.
5. Ignore case entirely and make every word lowercase.

What are the pros and cons for each one?

Pros and cons include:

1. Only make a word uppercase in our hash map if it is always uppercase in the original string: this will have reasonable accuracy in very long strings where words are more likely to be included multiple times, but words that only ever occur as the first word in a sentence will always be included as uppercase.
2. Make a word uppercase in our hash map if it is ever uppercase in the original string: this will ensure proper nouns are always uppercase, but any words that are ever at the start of sentences will always be uppercase too.
3. Make a word uppercase in our hash map if it is ever uppercase in the original string in a position that is not the first word of a sentence: this addresses the problem with option (2), but proper nouns that are only ever at the start of sentences will be made lowercase.
4. Use an API or other tool that identifies proper nouns: this has a lot of potential to give us a high level of accuracy, but we’ll give up control over decisions, we’ll be relying on code we didn’t write, and our practical runtime may be significantly increased.
5. Ignore case entirely and make every word lowercase: this will give us simplicity and consistency, but we’ll lose all accuracy for words that should be uppercase.

Any of these could be considered reasonable. Importantly, none of them are perfect. They all have tradeoffs, and it is very difficult to write a highly accurate algorithm. Consider “cliff” and “bill” in these sentences:

"Cliff finished his cake and paid the bill."
"Bill finished his cake at the edge of the cliff."

You can choose whichever of the options you’d like, or another option you thought of. For this breakdown, we’re going to choose option (1).

Now, how do we update our addWordToHashMap() method to avoid duplicate words?

Think about the different possibilities:

1. The word is uppercase or lowercase.
2. The word is already in the hash map or not.
3. A different case of the word is already in the hash map or not.

Moving forward, we can either:

1. Check for words that are in the hash map in both cases when we’re done populating the hash map. If we add “Vanilla” three times and “vanilla” eight times, we’ll combine them into one “vanilla” at the end with a value 1111.
2. Avoid ever having a word in our hash map that’s both uppercase and lowercase. As we add “Vanilla”s and “vanilla”s, we’d always only ever have one version in our hash map.

We’ll choose the second approach since it will save us a walk through our hash map. How should we start?

If the word we’re adding is already in the hash map in its current case, let’s increment its count. What if it’s not in the hash map?

There are three possibilities:

1. A lowercase version is in the hash map (in which case we know our input word is uppercase, because if it is lowercase and already in the hash map it would have passed our first check and we’d have just incremented its count)
2. An uppercase version is in the hash map (so we know our input word is lowercase)
3. The word is not in the hash map in any case

Let’s start with the first possibility. What do we want to do?

Because we only include a word as uppercase if it is always uppercase, we simply increment the lowercase version’s count.

// current hash map
// {blue=3}
// adding
// "Blue"
// code
int lowerCaseCount = wordsToCounts.get(word.toLowerCase());
wordsToCounts.put(word.toLowerCase(), lowerCaseCount + 1);
// updated hash map
// {blue=4}

What about the second possibility?

This is a little more complicated. We need to remove the uppercase version from our hash map if we encounter a lowercase version. But we still need the uppercase version’s count!

// current hash map
// {Yellow=6}
// adding
// "yellow"
// code (we will write our "capitalize()" method later)
int capitalizedCount = wordsToCounts.get(capitalize(word));
wordsToCounts.put(word, capitalizedCount + 1);
wordsToCounts.remove(capitalize(word));
// updated hash map
// {yellow=7}

Finally, what if the word is not in the hash map at all?

Easy — we add it and give it a count of 1.

// current hash map
// {purple=2}
// adding
// "indigo"
// code
wordsToCounts.put(word, 1);
// updated hash map
// {purple=2, indigo=1}

Now we have all our pieces! We can split words, add them to a hash map, and track the number of times each word occurs without having duplicate words of the same case. Can we improve our solution?

Let’s look at our runtime and space cost. We iterate through every character in the input string once and then every word in our list once. That’s a runtime of O(n)O(n), which is the best we can achieve for this challenge (we have to look at the entire input string). The space we’re using includes a list for each word and a hash map for every unique word. Our worst case is that every word is different, so our space cost is also O(n)O(n), which is also the best we can achieve for this challenge (we have to return a hash map of words).

But we can still make some optimizations!

How can we make our space cost even smaller?

We’re storing all our split words in a separate list. That at least doubles the memory we use! How can we eliminate the need for that list?

Right now, we store each word in our list as we split them. Instead, let’s just immediately populate each word in our hash map!

Solution

In our solution, we make three decisions:

• We use a class. This allows us to tie our methods together, calling them on instances of our class instead of passing references.
• To handle duplicate words with different cases, we choose to make a word uppercase in our hash map only if it is always uppercase in the original string. While this is a reasonable approach, it is imperfect (consider proper nouns that are also lowercase words, like “Bill” and “bill”).
• We build our own splitWords() method instead of using a built-in one. This allows us to pass each word to our addWordToHashMap() method as it was split, and to split words and eliminate punctuation in one iteration.

To split the words in the input string and populate a hash map of the unique words to the number of times they occurred, we:

1. Split words by spaces, em dashes, and ellipses — making sure to include hyphens surrounded by characters. We also include all apostrophes (which will handle contractions nicely but will break possessives into separate words).
2. Populate the words in our hash map as they are identified, checking if the word is already in our hash map in its current case or another case.

If the input word is uppercase and there’s a lowercase version in the hash map, we increment the lowercase version’s count. If the input word is lowercase and there’s an uppercase version in the hash map, we “demote” the uppercase version by adding the lowercase version and giving it the uppercase version’s count.

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class WordCloudData {
    private Map<String, Integer> wordsToCounts = new HashMap<>();
    public WordCloudData(String inputString) {
        populateWordsToCounts(inputString);
    }
    public Map<String, Integer> getWordsToCounts() {
        return wordsToCounts;
    }
    private void populateWordsToCounts(String inputString) {
        // iterates over each character in the input string, splitting
        // words and passing them to addWordToHashMap()
        int currentWordStartIndex = 0;
        int currentWordLength = 0;
        for (int i = 0; i < inputString.length(); i++) {
            char character = inputString.charAt(i);
            // if we reached the end of the string we check if the last
            // character is a letter and add the last word to our hash map
            if (i == inputString.length() - 1) {
                if (Character.isLetter(character)) {
                    currentWordLength++;
                }
                if (currentWordLength > 0) {
                    String currentWord = inputString.substring(currentWordStartIndex,
                        currentWordStartIndex + currentWordLength);
                    addWordToHashMap(currentWord);
                }
            // if we reach a space or emdash we know we're at the end of a word
            // so we add it to our hash map and reset our current word
            } else if (character == ' ' || character == '\u2014') {
                if (currentWordLength > 0) {
                    String currentWord = inputString.substring(currentWordStartIndex,
                        currentWordStartIndex + currentWordLength);
                    addWordToHashMap(currentWord);
                    currentWordLength = 0;
                }
            // we want to make sure we split on ellipses so if we get two periods in
            // a row we add the current word to our hash map and reset our current word
            } else if (character == '.') {
                if (i < inputString.length() - 1 && inputString.charAt(i + 1) == '.') {
                    if (currentWordLength > 0) {
                        String currentWord = inputString.substring(currentWordStartIndex,
                            currentWordStartIndex + currentWordLength);
                        addWordToHashMap(currentWord);
                        currentWordLength = 0;
                    }
                }
            // if the character is a letter or an apostrophe, we add it to our current word
            } else if (Character.isLetter(character) || character == '\'') {
                if (currentWordLength == 0) {
                    currentWordStartIndex = i;
                }
                currentWordLength++;
            // if the character is a hyphen, we want to check if it's surrounded by letters
            // if it is, we add it to our current word
            } else if (character == '-') {
                if (i > 0 && Character.isLetter(inputString.charAt(i - 1))
                        && Character.isLetter(inputString.charAt(i + 1))) {
                    currentWordLength++;
                } else {
                    if (currentWordLength > 0) {
                        String currentWord = inputString.substring(currentWordStartIndex,
                            currentWordStartIndex + currentWordLength);
                        addWordToHashMap(currentWord);
                        currentWordLength = 0;
                    }
                }
            }
        }
    }
    private void addWordToHashMap(String word) {
        // if the word is already in the hash map we increment its count
        if (wordsToCounts.containsKey(word)) {
            wordsToCounts.put(word, wordsToCounts.get(word) + 1);
        // if a lowercase version is in the hash map, we know our input word must be uppercase
        // but we only include uppercase words if they're always uppercase
        // so we just increment the lowercase version's count
        } else if (wordsToCounts.containsKey(word.toLowerCase())) {
            int newCount = wordsToCounts.get(word.toLowerCase()) + 1;
            wordsToCounts.put(word.toLowerCase(), newCount);
        // if an uppercase version is in the hash map, we know our input word must be lowercase.
        // since we only include uppercase words if they're always uppercase, we add the
        // lowercase version and give it the uppercase version's count
        } else if (wordsToCounts.containsKey(capitalize(word))) {
            int newCount = wordsToCounts.get(capitalize(word)) + 1;
            wordsToCounts.put(word, newCount);
            wordsToCounts.remove(capitalize(word));
        // otherwise, the word is not in the hash map at all, lowercase or uppercase
        // so we add it to the hash map
        } else {
            wordsToCounts.put(word, 1);
        }
    }
    private String capitalize(String word) {
        return word.substring(0, 1).toUpperCase() + word.substring(1);
    }
}

Complexity

Runtime and memory cost are both O(n)O(n). This is the best we can do because we have to look at every character in the input string and we have to return a hash map of every unique word. We optimized to only make one pass over our input and have only one O(n)O(n) data structure.

Bonus

1. We haven’t explicitly talked about how to handle more complicated character sets. How would you make your solution work with more unicode characters? What changes need to be made to handle silly sentences like these:
2. I’m singing ♬ on a ☔ day.
3. ☹ + ☕ = ☺.
4. We limited our input to letters, hyphenated words and punctuation. How would you expand your functionality to include numbers, email addresses, twitter handles, etc.?
5. How would you add functionality to identify phrases or words that belong together but aren’t hyphenated? (“Fire truck” or “Interview Cake”)
6. How could you improve your capitalization algorithm?
7. How would you avoid having duplicate words that are just plural or singular possessives?

What We Learned

To handle capitalized words, there were lots of heuristics and approaches we could have used, each with their own strengths and weaknesses. Open-ended questions like this can really separate good engineers from great engineers.

Good engineers will come up with a solution, but great engineers will come up with several solutions, weigh them carefully, and choose the best solution for the given context. So as you’re running practice questions, challenge yourself to keep thinking even after you have a first solution. See how many solutions you can come up with. This will grow your ability to quickly see multiple ways to solve a problem, so you can figure out the best solution. And use the hints and gotchas on each Interview Cake question — they’re designed to help you cultivate this skill.

Your team is scrambling to decipher a recent message, worried it’s a plot to break into a major European National Cake Vault. The message has been mostly deciphered, but all the words are backward! Your colleagues have handed off the last step to you.

Write a method reverseWords() that takes a message as an array of characters and reverses the order of the words in place.

Why an array of characters instead of a string?

The goal of this question is to practice manipulating strings in place. Since we’re modifying the message, we need a mutable ↴ type like an array, instead of Java’s immutable strings.

For example:

char[] message = { 'c', 'a', 'k', 'e', ' ',
                   'p', 'o', 'u', 'n', 'd', ' ',
                   's', 't', 'e', 'a', 'l' };
reverseWords(message);
System.out.println(message);
// prints: "steal pound cake"

When writing your method, assume the message contains only letters and spaces, and all words are separated by one space.

Gotchas

We can do this in O(1)O(1) space. Remember, in place.

We can do this in O(n)O(n) time.

If you’re swapping individual words one at a time, consider what happens when the words are different lengths. Isn’t each swap O(n)O(n) time in the worst case?

Breakdown

Let’s start with a simpler problem. What if we wanted to reverse all the characters in the message?

Well, we could swap the first character with the last character, then the second character with the second to last character, and so on, moving towards the middle. Can you implement this in code?

public static void reverseCharacters(char[] message) {
int leftIndex = 0;
    int rightIndex = message.length - 1;
    // walk towards the middle, from both sides
    while (leftIndex < rightIndex) {
        // swap the left char and right char
        char temp = message[leftIndex];
        message[leftIndex] = message[rightIndex];
        message[rightIndex] = temp;
        leftIndex++;
        rightIndex--;
    }
}

Ok, looks good. Does this help us?

Can we use the same concept but apply it to words instead of characters?

Probably. We’ll have to figure out a couple things:

1. How do we figure out where words begin and end?
2. Once we know the start and end indices of two words, how do we swap those two words?

We could attack either of those first, but I’m already seeing a potential problem in terms of runtime. Can you guess what it is?

What happens when you swap two words that aren’t the same length?

// the eagle has landed
{ 't', 'h', 'e', ' ', 'e', 'a', 'g', 'l', 'e', ' ',
  'h', 'a', 's', ' ', 'l', 'a', 'n', 'd', 'e', 'd' };

Supposing we already knew the start and end indices of ‘the’ and ‘landed’, how long would it take to swap them?

O(n)O(n) time, where nn is the total length of the message!

Why? Notice that in addition to moving ‘the’ to the back and moving ‘landed’ to the front, we have to “scoot over” everything in between, since ‘landed’ is longer than ‘the’.

So what’ll be the total time cost with this approach? Assume we’ll be able to learn the start and end indices of all of our words in just one pass (O(n)O(n) time).

O(n2)O(n2) total time. Why? In the worst case we have almost as many words as we have characters, and we’re always swapping words of different lengths. For example:

// a bb c dd e ff g hh
{ 'a', ' ', 'b', 'b', ' ', 'c', ' ', 'd', 'd', ' ',
  'e', ' ', 'f', 'f', ' ', 'g', ' ', 'h', 'h' };

We take O(n)O(n) time to swap the first and last words (we have to move all nn characters):

// input: a bb c dd e ff g hh
{ 'a', ' ', 'b', 'b', ' ', 'c', ' ', 'd', 'd', ' ',
  'e', ' ', 'f', 'f', ' ', 'g', ' ', 'h', 'h' };
// first swap: hh bb c dd e ff g a
{ 'h', 'h', ' ', 'b', 'b', ' ', 'c', ' ', 'd', 'd',
  ' ', 'e', ' ', 'f', 'f', ' ', 'g', ' ', 'a' };

Then for the second swap:

// input: a bb c dd e ff g hh
{ 'a', ' ', 'b', 'b', ' ', 'c', ' ', 'd', 'd', ' ',
  'e', ' ', 'f', 'f', ' ', 'g', ' ', 'h', 'h' };
// first swap: hh bb c dd e ff g a
{ 'h', 'h', ' ', 'b', 'b', ' ', 'c', ' ', 'd', 'd',
  ' ', 'e', ' ', 'f', 'f', ' ', 'g', ' ', 'a' };
// second swap: hh g c dd e ff bb a
{ 'h', 'h', ' ', 'g', ' ', 'c', ' ', 'd', 'd',
  ' ', 'e', ' ', 'f', 'f', ' ', 'b', 'b', ' ', 'a' };

We have to move all nn characters except the first and last words, and a couple spaces. So we move n−5n−5 characters in total.

For the third swap, we have another 55 characters we don’t have to move. So we move n−10n−10 in total. We’ll end up with a series like this:

n+(n−5)+(n−10)+(n−15)+…+6+1n+(n−5)+(n−10)+(n−15)+…+6+1

This is a subsection of the common triangular series. ↴ We’re just skipping 4 terms between each term!

So we have the sum of “every fifth number” from that triangular series. That means our sum will be about a fifth the sum of the original series! But in big O notation dividing by 5 is a constant, so we can throw it out. The original triangular series is O(n2)O(n2), and so is our series with every fifth element!

Okay, so O(n2)O(n2) time. That’s pretty bad. It’s possible that’s the best we can do…but maybe we can do better?

Let’s try manipulating a sample input by hand.

And remember what we did for our character-level reversal…

Look what happens when we do a character-level reversal:

// input: the eagle has landed
{ 't', 'h', 'e', ' ', 'e', 'a', 'g', 'l', 'e', ' ',
  'h', 'a', 's', ' ', 'l', 'a', 'n', 'd', 'e', 'd' };
// character-reversed: dednal sah elgae eht
{ 'd', 'e', 'd', 'n', 'a', 'l', ' ', 's', 'a', 'h', ' ',
  'e', 'l', 'g', 'a', 'e', ' ', 'e', 'h', 't' };

Notice anything?

What if we put it up against the desired output:

// input: the eagle has landed
{ 't', 'h', 'e', ' ', 'e', 'a', 'g', 'l', 'e', ' ',
  'h', 'a', 's', ' ', 'l', 'a', 'n', 'd', 'e', 'd' };
// character-reversed: dednal sah elgae eht
{ 'd', 'e', 'd', 'n', 'a', 'l', ' ', 's', 'a', 'h', ' ',
  'e', 'l', 'g', 'a', 'e', ' ', 'e', 'h', 't' };
// word-reversed (desired output): landed has eagle the
{ 'l', 'a', 'n', 'd', 'e', 'd', ' ', 'h', 'a', 's', ' ',
  'e', 'a', 'g', 'l', 'e', ' ', 't', 'h', 'e' };

The character reversal reverses the words! It’s a great first step. From there, we just have to “unscramble” each word.

More precisely, we just have to re-reverse each word!

Solution

We’ll write a helper method reverseCharacters() that reverses all the characters between a leftIndex and rightIndex. We use it to:

1. Reverse all the characters in the entire message, giving us the correct word order but with each word backward.
2. Reverse the characters in each individual word.

public static void reverseWords(char[] message) {
// first we reverse all the characters in the entire message array
    // this gives us the right word order
    // but with each word backward
    reverseCharacters(message, 0, message.length - 1);
    // now we'll make the words forward again
    // by reversing each word's characters
    // we hold the index of the *start* of the current word
    // as we look for the *end* of the current word
    int currentWordStartIndex = 0;
    for (int i = 0; i <= message.length; i++) {
        // found the end of the current word!
        if (i == message.length || message[i] == ' ') {
            // if we haven't exhausted the array, our
            // next word's start is one character ahead
            reverseCharacters(message, currentWordStartIndex, i - 1);
            currentWordStartIndex = i + 1;
        }
    }
}
private static void reverseCharacters(char[] message, int leftIndex, int rightIndex) {
    // walk towards the middle, from both sides
    while (leftIndex < rightIndex) {
        // swap the left char and right char
        char temp = message[leftIndex];
        message[leftIndex] = message[rightIndex];
        message[rightIndex] = temp;
        leftIndex++;
        rightIndex--;
    }

Complexity

O(n)O(n) time and O(1)O(1) space!

Hmm, the team used your method to finish deciphering the message. There definitely seems to be a heist brewing, but no specifics on where. Any ideas?

Bonus

How would you handle punctuation?

What We Learned

The naive solution of reversing the words one at a time had a worst-case O(n2)O(n2) runtime. That’s because swapping words with different lengths required “scooting over” all the other characters to make room.

To get around this “scooting over” issue, we reversed all the characters in the message first. This put all the words in the correct spots, but with the characters in each word backward. So to get the final answer, we reversed the characters in each word. This all takes two passes through the message, so O(n)O(n) time total.

This might seem like a blind insight, but we derived it by using a clear strategy:

Solve a simpler version of the problem (in this case, reversing the characters instead of the words), and see if that gets us closer to a solution for the original problem.

Say you’re a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?

Whenever picking which coin to use, you’d take the highest-value coin you could. A quarter, another quarter, then a dime, a nickel, and finally two pennies. That’s a greedy algorithm, because you’re always greedily choosing the coin that covers the biggest portion of the remaining amount.

Some other places where a greedy algorithm gets you the best solution:

• Trying to fit as many overlapping meetings as possible in a conference room? At each step, schedule the meeting that ends earliest.
• Looking for a minimum spanning tree in a graph? At each step, greedily pick the cheapest edge that reaches a new vertex.

Careful: sometimes a greedy algorithm doesn’t give you an optimal solution:

• When filling a duffel bag with cakes of different weights and values, choosing the cake with the highest value per pound doesn’t always produce the best haul.
• To find the cheapest route visiting a set of cities, choosing to visit the cheapest city you haven’t been to yet doesn’t produce the cheapest overall itinerary.

Validating that a greedy strategy always gets the best answer is tricky. Either prove that the answer produced by the greedy algorithm is as good as an optimal answer, or run through a rigorous set of test cases to convince your interviewer (and yourself) that it’s correct.

A brute force search would walk through the whole array, taking O(n)O(n) time in the worst case.

Let’s say we have a sorted array of numbers. To find a number with a binary search, we:

1. Start with the middle number: is it bigger or smaller than our target number? Since the array is sorted, this tells us if the target would be in the left half or the right half of our array.
2. We’ve effectively divided the problem in half. We can “rule out” the whole half of the array that we know doesn’t contain the target number.
3. Repeat the same approach (of starting in the middle) on the new half-size problem. Then do it again and again, until we either find the number or “rule out” the whole set.

We can do this recursively, or iteratively. Here’s an iterative version:

public static boolean binarySearch(int target, int[] nums) {
// we think of floorIndex and ceilingIndex as "walls" around
    // the possible positions of our target, so by -1 below we mean
    // to start our wall "to the left" of the 0th index
    // (we *don't* mean "the last index")
    int floorIndex = -1;
    int ceilingIndex = nums.length;
    // if there isn't at least 1 index between floor and ceiling,
    // we've run out of guesses and the number must not be present
    while (floorIndex + 1 < ceilingIndex) {
        // find the index ~halfway between the floor and ceiling
        // we use integer division, so we'll never get a "half index"
        int distance = ceilingIndex - floorIndex;
        int halfDistance = distance / 2;
        int guessIndex = floorIndex + halfDistance;
        int guessValue = nums[guessIndex];
        if (guessValue == target) {
            return true;
        }
        if (guessValue > target) {
            // target is to the left, so move ceiling to the left
            ceilingIndex = guessIndex;
        } else {
            // target is to the right, so move floor to the right
            floorIndex = guessIndex;
        }
    }
    return false;
}
    // see if target appears in nums

How did we know the time cost of binary search was O(lg(n))O(lg(n))? The only non-constant part of our time cost is the number of times our while loop runs. Each step of our while loop cuts the range (dictated by floorIndex and ceilingIndex) in half, until our range has just one element left.

So the question is, “how many times must we divide our original array size (nn) in half until we get down to 1?”

n∗12∗12∗12∗12∗…=1n∗21​∗21​∗21​∗21​∗…=1

How many 1221​’s are there? We don’t know yet, but we can call that number xx:

n∗(12)x=1n∗(21​)x=1

Now we solve for xx:

n∗1x2x=1n∗2x1x​=1n∗12x=1n∗2x1​=1n2x=12xn​=1n=2xn=2x

Now to get the xx out of the exponent. How do we do that? Logarithms.

Recall that log⁡10100log10​100 means, “what power must we raise 10 to, to get 100”? The answer is 2.

So in this case, if we take the log⁡2log2​ of both sides…

log⁡2n=log⁡22xlog2​n=log2​2x

The right hand side asks, “what power must we raise 22 to, to get 2x2x?” Well, that’s just xx.

log⁡2n=xlog2​n=x

So there it is. The number of times we must divide nn in half to get down to 1 is log2nlog2​n. So our total time cost is O(lg(n))O(lg(n))

Careful: we can only use binary search if the input array is already sorted.

Put simply, a bottom-up algorithm “starts from the beginning,” while a recursive algorithm often “starts from the end and works backwards.”

For example, if we wanted to multiply all the numbers in the range 1..n1..n, we could use this cute, top-down, recursive one-liner:

public static int product1ToN(int n) {
    // we assume n >= 1
    return (n > 1) ? (n * product1ToN(n-1)) : 1;
}

This approach has a problem: it builds up a call stack of size O(n)O(n), which makes our total memory cost O(n)O(n). This makes it vulnerable to a stack overflow error, where the call stack gets too big and runs out of space.

To avoid this, we can instead go bottom-up:

public static int product1ToN(int n) {
    // we assume n >= 1
int result = 1;
    for (int num = 1; num <= n; num++) {
        result *= num;
    }
    return result;
}

This approach uses O(1)O(1) space (O(n)O(n) time).

Some compilers and interpreters will do what’s called tail call optimization (TCO), where it can optimize some recursive methods to avoid building up a tall call stack. Python and Java decidedly do not use TCO. Some Ruby implementations do, but most don’t. Some C implementations do, and the JavaScript spec recently allowed TCO. Scheme is one of the few languages that guarantee TCO in all implementations. In general, best not to assume your compiler/interpreter will do this work for you.

Going bottom-up is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with multiplying the numbers 1..n1..n, above). The other common strategy for dynamic programming problems is memoization.

For example, a simple recursive method for computing the nnth Fibonacci number:

public static int fib(int n) {
if (n < 0) {
        throw new IllegalArgumentException(
            "Index was negative. No such thing as a negative index in a series.");
    }
    // base cases
    if (n == 0 || n == 1) {
        return n;
    }
    System.out.printf("computing fib(%d)\n", n);
    return fib(n - 1) + fib(n - 2);
}Will run on the same inputs multiple times:

// output for fib(5)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
5

We can imagine the recursive calls of this method as a tree, where the two children of a node are the two recursive calls it makes. We can see that the tree quickly branches out of control:

To avoid the duplicate work caused by the branching, we can wrap the method in a class that stores an instance variable, memo, that maps inputs to outputs. Then we simply

1. check memo to see if we can avoid computing the answer for any given input, and
2. save the results of any calculations to memo.

import java.util.Map;
import java.util.HashMap;
class Fibber {
    private Map<Integer, Integer> memo = new HashMap<>();
    public int fib(int n) {
        if (n < 0) {
            throw new IllegalArgumentException(
                "Index was negative. No such thing as a negative index in a series.");
        // base cases
        } else if (n == 0 || n == 1) {
            return n;
        }
        // see if we've already calculated this
        if (memo.containsKey(n)) {
            System.out.printf("grabbing memo[%d]\n", n);
            return memo.get(n);
        }
        System.out.printf("computing fib(%d)\n", n);
        int result = fib(n - 1) + fib(n - 2);
        // memoize
        memo.put(n, result);
        return result;
    }
}

We save a bunch of calls by checking the memo:

// output of new Fibber().fib(5)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
grabbing memo[2]
grabbing memo[3]
5

Now in our recurrence tree, no node appears more than twice:

Memoization is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with the Fibonacci problem, above). The other common strategy for dynamic programming problems is going bottom-up, which is usually cleaner and often more efficient.

As an example, let’s look at the Fibonacci sequence (the series where each number is the sum of the two previous ones — 0, 1, 1, 2, 3, 5, 8, …).

If we wanted to compute the nnth Fibonacci number, we could use this simple recursive algorithm:

public static int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

CC#C++JavaJavaScriptObjective-CPHPPython 2.7Python 3.6RubySwift

We’d call fib(n-1) and fib(n-2) subproblems of fib(n).

Now let’s look at what happens when we call fib(5):

Our method ends up recursively calling fib(2) three times. So the problem of finding the nnth Fibonacci number has overlapping subproblems.

While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.

Each type of cake has a weight and a value, stored in objects of a CakeType class:

public class CakeType {
final int weight;
    final int value;
    public CakeType(int weight, int value) {
        this.weight = weight;
        this.value  = value;
    }
}

For example:

// weighs 7 kilograms and has a value of 160 shillings
new CakeType(7, 160);
// weighs 3 kilograms and has a value of 90 shillings
new CakeType(3, 90);

You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.

Write a method maxDuffelBagValue() that takes an array of cake type objects and a weight capacity, and returns the maximum monetary value the duffel bag can hold.

For example:

CakeType[] cakeTypes = new CakeType[] {
    new CakeType(7, 160),
    new CakeType(3, 90),
    new CakeType(2, 15),
};
int capacity = 20;
maxDuffelBagValue(cakeTypes, capacity);
// returns 555 (6 of the middle type of cake and 1 of the last type of cake)

Weights and values may be any non-negative integer. Yes, it’s weird to think about cakes that weigh nothing or duffel bags that can’t hold anything. But we’re not just super mastermind criminals — we’re also meticulous about keeping our algorithms flexible and comprehensive.

Gotchas

Does your method work if the duffel bag’s weight capacity is 0 kg?

Does your method work if any of the cakes weigh 0 kg? Think about a cake whose weight and value are both 0.

We can do this in O(n∗k)O(n∗k) time and O(k)O(k) space, where nn is the number of types of cakes and kk is the duffel bag’s capacity!

Breakdown

The brute force approach is to try every combination of cakes, but that would take a really long time — you’d surely be captured.

What if we just look at the cake with the highest value?

We could keep putting the cake with the highest value into our duffel bag until adding one more would go over our weight capacity. Then we could look at the cake with the second highest value, and so on until we find a cake that’s not too heavy to add.

Will this work?

Nope. Let’s say our capacity is 100 kg and these are our two cakes:

new CakeType(1, 30);
new CakeType(50, 200);

With our approach, we’ll put in two of the second type of cake for a total value of 400 shillings. But we could have put in a hundred of the first type of cake, for a total value of 3000 shillings!

Just looking at the cake’s values won’t work. Can we improve our approach?

Well, why didn’t it work?

We didn’t think about the weight! How can we factor that in?

What if instead of looking at the value of the cakes, we looked at their value/weight ratio? Here are our example cakes again:

new CakeType(1, 30);
new CakeType(50, 200);

The second cake has a higher value, but look at the value per kilogram.

The second type of cake is worth 4 shillings/kg (200/50200/50), but the first type of cake is worth 30 shillings/kg (30/130/1)!

Ok, can we just change our algorithm to use the highest value/weight ratio instead of the highest value? We know it would work in our example above, but try some more tests to be safe.

We might run into problems if the weight of the cake with the highest value/weight ratio doesn’t fit evenly into the capacity. Say we have these two cakes:

new CakeType(3, 40);
new CakeType(5, 70);

If our capacity is 8 kg, no problem. Our algorithm chooses one of each cake, giving us a haul worth 110 shillings, which is optimal.

But if the capacity is 9 kg, we’re in trouble. Our algorithm will again choose one of each cake, for a total value of 110 shillings. But the actual optimal value is 120 shillings — three of the first type of cake!

So even looking at the value/weight ratios doesn’t always give us the optimal answer!

Let’s step back. How can we ensure we get the optimal value we can carry?

Try thinking small. How can we calculate the maximum value for a duffel bag with a weight capacity of 1 kg? (Remember, all our weights and values are integers.)

If the capacity is 1 kg, we’ll only care about cakes that weigh 1 kg (for simplicity, let’s ignore zeroes for now). And we’d just want the one with the highest value.

We could go through every cake, using a greedy ↴ approach to keep track of the max value we’ve seen so far.

Here’s an example solution:

public static long maxDuffelBagValueWithCapacity1(CakeType[] cakeTypes) {
long maxValueAtCapacity1 = 0L;
    for (CakeType cakeType : cakeTypes) {
        if (cakeType.weight == 1) {
            maxValueAtCapacity1 = Math.max(maxValueAtCapacity1, cakeType.value);
        }
    }
    return maxValueAtCapacity1;
}

(We’re using long because we’re looking for a max value.)

Ok, now what if the capacity is 2 kg? We’ll need to be a bit more clever.

It’s pretty similar. Again we’ll track a max value, let’s say with a variable maxValueAtCapacity2. But now we care about cakes that weigh 1 or 2 kg. What do we do with each cake? And keep in mind, we can lean on the code we used to get the max value at weight capacity 1 kg.

1. If the cake weighs 2 kg, it would fill up our whole capacity if we just took one. So we just need to see if the cake’s value is higher than our current maxValueAtCapacity2.
2. If the cake weighs 1 kg, we could take one, and we’d still have 1 kg of capacity left. How do we know the best way to fill that extra capacity? We can use the max value at capacity 1. We’ll see if adding the cake’s value to the max value at capacity 1 is better than our current maxValueAtCapacity2.

Does this apply more generally? If we can use the max value at capacity 1 to get the max value at capacity 2, can we use the max values at capacity 1 and 2 to get the max value at capacity 3?

Looks like this problem might have overlapping subproblems! ↴

Let’s see if we can build up to the given weight capacity, one capacity at a time, using the max values from previous capacities. How can we do this?

Well, let’s try one more weight capacity by hand — 3 kg. So we already know the max values at capacities 1 and 2. And just like we did with maxValueAtCapacity1 and maxValueAtCapacity2, now we’ll track maxValueAtCapacity3 and loop through every cake:

long maxValueAtCapacity3 = 0L;
for (CakeType cakeType : cakeTypes) {
    // only care about cakes that weigh 3 kg or less
    ...
}

What do we do for each cake?

If the current cake weighs 3 kg, easy — we see if it’s more valuable than our current maxValueAtCapacity3.

What if the current cake weighs 2 kg?

Well, let’s see what our max value would be if we used the cake. How can we calculate that?

If we include the current cake, we can only carry 1 more kilogram. What would be the max value we can carry?

We already know the maxValueAtCapacity1! We can just add that to the current cake’s value!

Now we can see which is higher — our current maxValueAtCapacity3, or the new max value if we use the cake:

long maxValueUsingCake = maxValueAtCapacity1 + cakeType.value;
maxValueAtCapacity3 = Math.max(maxValueAtCapacity3, maxValueUsingCake);

Finally, what if the current cake weighs 1 kg?

Basically the same as if it weighs 2 kg:

long maxValueUsingCake = maxValueAtCapacity2 + cakeType.value;
maxValueAtCapacity3 = Math.max(maxValueAtCapacity3, maxValueUsingCake);

There’s gotta be a pattern here. We can keep building up to higher and higher capacities until we reach our input capacity. Because the max value we can carry at each capacity is calculated using the max values at previous capacities, we’ll need to solve the max value for every capacity from 0 up to our duffel bag’s actual weight capacity.

Can we write a method to handle all the capacities?

To start, we’ll need a way to store and update all the max monetary values for each capacity.

We could use a hash map, ↴ where the keys represent capacities and the values represent the max possible monetary values at those capacities. Hash maps are built on arrays, ↴ so we can save some overhead by just using an array.

public static long maxDuffelBagValue(CakeType[] cakeTypes, int weightCapacity) {
// array to hold the maximum possible value at every
    // integer capacity from 0 to weightCapacity
    // starting each index with value 0 long
    long[] maxValuesAtCapacities = new long[weightCapacity + 1];
}

What do we do next?

We’ll need to work with every capacity up to the input weight capacity. That’s an easy loop:

// every integer from 0 to the input weightCapacity
for (int currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) {
    ...
}

What will we do inside this loop? This is where it gets a little tricky.

We care about any cakes that weigh the current capacity or less. Let’s try putting each cake in the bag and seeing how valuable of a haul we could fit from there.

So we’ll write a loop through all the cakes (ignoring cakes that are too heavy to fit):

for (CakeType cakeType : cakeTypes) {
// if the cake weighs as much or less than the current capacity
    // see what our max value could be if we took it!
    if (cakeType.weight <= currentCapacity) {
        // find maxValueUsingCake
        ...
    }
}

And put it in our method body so far:

public static long maxDuffelBagValue(CakeType[] cakeTypes, int weightCapacity) {
// we make an array to hold the maximum possible value at every
    // duffel bag weight capacity from 0 to weightCapacity
    // starting each index with value 0
    long[] maxValuesAtCapacities = new long[weightCapacity + 1];
    for (int currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) {
        for (CakeType cakeType : cakeTypes) {
            // if the cake weighs as much or less than the current capacity
            // see what our max value could be if we took it!
            if (cakeType.weight <= currentCapacity) {
                // find maxValueUsingCake
                ...
            }
        }
    }
}

How do we compute maxValueUsingCake?

Remember when we were calculating the max value at capacity 3kg and we “hard-coded” the maxValueUsingCake for cakes that weigh 3 kg, 2kg, and 1kg?

// cake weighs 3 kg
long maxValueUsingCake = cakeType.value;
// cake weighs 2 kg
long maxValueUsingCake = maxValueAtCapacity1 + cakeType.value;
// cake weighs 1 kg
long maxValueUsingCake = maxValueAtCapacity2 + cakeType.value;

How can we generalize this? With our new method body, look at the variables we have in scope:

• maxValuesAtCapacities
• currentCapacity
• cakeType

Can we use these to get maxValueUsingCake for any cake?

Well, let’s figure out how much space would be left in the duffel bag after putting the cake in:

int remainingCapacityAfterTakingCake = currentCapacity - cakeType.weight;

CC#C++JavaJavaScriptObjective-CPHPPython 2.7Python 3.6RubySwift

So maxValueUsingCake is:

1. the current cake’s value, plus
2. the best value we can fill the remainingCapacityAfterTakingCake with

int remainingCapacityAfterTakingCake = currentCapacity - cakeType.weight;
long maxValueUsingCake = cakeType.value + maxValuesAtCapacities[remainingCapacityAfterTakingCake];

We can squish this into one line:

long maxValueUsingCake = cakeType.value + maxValuesAtCapacities[currentCapacity - cakeType.weight];

Since remainingCapacityAfterTakingCake is a lower capacity, we’ll have always already computed its max value and stored it in our maxValuesAtCapacities!

Now that we know the max value if we include the cake, should we include it? How do we know?

Let’s allocate a variable currentMaxValue that holds the highest value we can carry at the current capacity. We can start it at zero, and as we go through all the cakes, any time the value using a cake is higher than currentMaxValue, we’ll update currentMaxValue!

currentMaxValue = Math.max(maxValueUsingCake, currentMaxValue);

What do we do with each value for currentMaxValue? What do we need to do for each capacity when we finish looping through all the cakes?

We save each currentMaxValue in the maxValuesAtCapacities array. We’ll also need to make sure we set currentMaxValue to zero in the right place in our loops — we want it to reset every time we start a new capacity.

So here’s our method so far:

public static long maxDuffelBagValue(CakeType[] cakeTypes, int weightCapacity){
// we make an array to hold the maximum possible value at every
    // duffel bag weight capacity from 0 to weightCapacity
    // starting each index with value 0
    long[] maxValuesAtCapacities = new long[weightCapacity + 1];
    for (int currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) {
        // set a variable to hold the max monetary value so far for currentCapacity
        long currentMaxValue = 0;
        for (CakeType cakeType : cakeTypes) {
            // if the current cake weighs as much or less than the current weight capacity
            // it's possible taking the cake would get a better value
            if (cakeType.weight <= currentCapacity) {
                // so we check: should we use the cake or not?
                // if we use the cake, the most kilograms we can include in addition to the cake
                // we're adding is the current capacity minus the cake's weight. we find the max
                // value at that integer capacity in our array maxValuesAtCapacities
                long maxValueUsingCake = cakeType.value
                    + maxValuesAtCapacities[currentCapacity - cakeType.weight];
                // now we see if it's worth taking the cake. how does the
                // value with the cake compare to the currentMaxValue?
                currentMaxValue = Math.max(maxValueUsingCake, currentMaxValue);
            }
        }
        // add each capacity's max value to our array so we can use them
        // when calculating all the remaining capacities
        maxValuesAtCapacities[currentCapacity] = currentMaxValue;
    }
} 

Looking good! But what’s our final answer?

Our final answer is maxValuesAtCapacities[weightCapacity]!

Okay, this seems complete. What about edge cases?

Remember, weights and values can be any non-negative integer. What about zeroes? How can we handle duffel bags that can’t hold anything and cakes that weigh nothing?

Well, if our duffel bag can’t hold anything, we can just return 0. And if a cake weighs 0 kg, we return infinity. Right?

Not that simple!

What if our duffel bag holds 0 kg, and we have a cake that weighs 0 kg. What do we return?

And what if we have a cake that weighs 0 kg, but its value is also 0. If we have other cakes with positive weights and values, what do we return?

If a cake’s weight and value are both 0, it’s reasonable to not have that cake affect what we return at all.

If we have a cake that weighs 0 kg and has a positive value, it’s reasonable to return infinity, even if the capacity is 0.

For returning infinity, we have a couple choices. We could return:

• The highest possible Long. In Java, that’d be Long.MAX_VALUE.
• Raise an exception indicating the answer is infinity.

What are the advantages and disadvantages of each option?

For the first option the advantage is the highest possible Long will behave like infinity in a few ways. For example, it’ll be greater than any other integer. But it’s a still a specific number, which can be an advantage or disadvantage — we might want our result to always be the same type, but representing infinity as a specific number is “lossy” — it won’t be clear if we’re talking about an actual value or the special case of infinity.

The second option is a good choice if we decide infinity is usually an “unacceptable” answer. For example, we might decide an infinite answer means we’ve probably entered our inputs wrong. Then, if we really wanted to “accept” an infinite answer, we could always “catch” this exception when we call our method.

Either option could be reasonable. We’ll go with the second one here.

Solution

This is a classic computer science puzzle called “the unbounded knapsack problem.”

We use a bottom-up ↴ approach to find the max value at our duffel bag’s weightCapacity by finding the max value at every capacity from 0 to weightCapacity.

We allocate an array maxValuesAtCapacities where the indices are capacities and each value is the max value at that capacity.

For each capacity, we want to know the max monetary value we can carry. To figure that out, we go through each cake, checking to see if we should take that cake.

The best monetary value we can get if we take a given cake is simply:

1. that cake’s value, plus
2. the best monetary value we can carry in our remaining duffel bag capacity after taking the cake — which we’ll already have stored in maxValuesAtCapacities

To handle weights and values of zero, we throw an infinity error only if a cake weighs nothing and has a positive value.

public static class InfinityException extends RuntimeException {
    public InfinityException() {
        super("Max value is infinity!");
    }
}
public static long maxDuffelBagValue(CakeType[] cakeTypes, int weightCapacity) {
    // we make an array to hold the maximum possible value at every
    // duffel bag weight capacity from 0 to weightCapacity
    // starting each index with value 0
    long[] maxValuesAtCapacities = new long[weightCapacity + 1];
    for (int currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) {
        // set a variable to hold the max monetary value so far for currentCapacity
        long currentMaxValue = 0;
        for (CakeType cakeType : cakeTypes) {
            // if a cake weighs 0 and has a positive value the value of our duffel bag is infinite!
            if (cakeType.weight == 0 && cakeType.value != 0) {
                throw new InfinityException();
            }
            // if the current cake weighs as much or less than the current weight capacity
            // it's possible taking the cake would get a better value
            if (cakeType.weight <= currentCapacity) {
                // so we check: should we use the cake or not?
                // if we use the cake, the most kilograms we can include in addition to the cake
                // we're adding is the current capacity minus the cake's weight. we find the max
                // value at that integer capacity in our array maxValuesAtCapacities
                long maxValueUsingCake = cakeType.value
                    + maxValuesAtCapacities[currentCapacity - cakeType.weight];
                // now we see if it's worth taking the cake. how does the
                // value with the cake compare to the currentMaxValue?
                currentMaxValue = Math.max(maxValueUsingCake, currentMaxValue);
            }
        }
        // add each capacity's max value to our array so we can use them
        // when calculating all the remaining capacities
        maxValuesAtCapacities[currentCapacity] = currentMaxValue;
    }
    return maxValuesAtCapacities[weightCapacity];
}

Complexity

O(n∗k)O(n∗k) time, and O(k)O(k) space, where nn is number of types of cake and kk is the capacity of the duffel bag. We loop through each cake (nn cakes) for every capacity (kk capacities), so our runtime is O(n∗k)O(n∗k), and maintaining the array of k+1k+1 capacities gives us the O(k)O(k) space.

Congratulations! Because of dynamic programming, you have successfully stolen the Queen’s cakes and made it big.

Keep in mind: in some cases, it might not be worth using our optimal dynamic programming solution. It’s a pretty slow algorithm — without any context (not knowing how many cake types we have, what our weight capacity is, or just how they compare) it’s easy to see O(n∗k)O(n∗k) growing out of control quickly if nn or kk is large.

If we cared about time, like if there was an alarm in the vault and we had to move quickly, it might be worth using a faster algorithm that gives us a good answer, even if it’s not always the optimal answer. Some of our first ideas in the breakdown were to look at cake values or value/weight ratios. Those algorithms would probably be faster, taking O(nlg⁡n)O(nlgn) time (we’d have to start by sorting the input).

Sometimes an efficient, good answer might be more practical than an inefficient, optimal answer.

Bonus

1. We know the max value we can carry, but which cakes should we take, and how many? Try adjusting your answer to return this information as well.
2. What if we check to see if all the cake weights have a common denominator? Can we improve our algorithm?
3. A cake that’s both heavier and worth less than another cake would never be in the optimal solution. This idea is called dominance relations. Can you apply this idea to save some time? Hint: dominance relations can apply to sets of cakes, not just individual cakes.
4. What if we had an object for every individual cake instead of types of cakes? So now there’s not an unlimited supply of a type of cake — there’s exactly one of each. This is a similar but harder problem, known as the 0/1 Knapsack problem.

What We Learned

This question is our spin on the famous “unbounded knapsack problem” — a classic dynamic programming question.

If you’re struggling with dynamic programming, we have reference pages for the two main dynamic programming strategies: memoization and going bottom-up.

Here’s a sample binary tree node class:

public class BinaryTreeNode {
public int value;
    public BinaryTreeNode left;
    public BinaryTreeNode right;
    public BinaryTreeNode(int value) {
        this.value = value;
    }
    public BinaryTreeNode insertLeft(int leftValue) {
        this.left = new BinaryTreeNode(leftValue);
        return this.left;
    }
    public BinaryTreeNode insertRight(int rightValue) {
        this.right = new BinaryTreeNode(rightValue);
        return this.right;
    }
}

Gotchas

Your first thought might be to write a recursive method, thinking, “the tree is balanced if the left subtree is balanced and the right subtree is balanced.” This kind of approach works well for some other tree problems.

But this isn’t quite true. Counterexample: suppose that from the root of our tree:

• The left subtree only has leaves at depths 10 and 11.
• The right subtree only has leaves at depths 11 and 12.

Both subtrees are balanced, but from the root we will have leaves at 3 different depths.

We could instead have our recursive method get the array of distinct leaf depths for each subtree. That could work fine. But let’s come up with an iterative solution instead. It’s usually better to use an iterative solution instead of a recursive one because it avoids stack overflow. ↴

We can do this in O(n)O(n) time and O(n)O(n) space.

What about a tree with only one leaf node? Does your method handle that case properly?

Breakdown

Sometimes it’s good to start by rephrasing or “simplifying” the problem.

The requirement of “the difference between the depths of any two leaf nodes is no greater than 1” implies that we’ll have to compare the depths of all possible pairs of leaves. That’d be expensive — if there are nn leaves, there are O(n2)O(n2) possible pairs of leaves.

But we can simplify this requirement to require less work. For example, we could equivalently say:

• “The difference between the min leaf depth and the max leaf depth is 1 or less”
• “There are at most two distinct leaf depths, and they are at most 1 apart”

If you’re having trouble with a recursive approach, try using an iterative one.

To get to our leaves and measure their depths, we’ll have to traverse the tree somehow. What methods do we know for traversing a tree?

Depth-first ↴ and breadth-first ↴ are common ways to traverse a tree. Which one should we use here?

The worst-case time and space costs of both are the same — you could make a case for either.

But one characteristic of our algorithm is that it could short-circuit and return false as soon as it finds two leaves with depths more than 1 apart. So maybe we should use a traversal that will hit leaves as quickly as possible…

Depth-first traversal will generally hit leaves before breadth-first, so let’s go with that. How could we write a depth-first walk that also keeps track of our depth?

Solution

We do a depth-first walk ↴ through our tree, keeping track of the depth as we go. When we find a leaf, we add its depth to a list of depths if we haven’t seen that depth already.

Each time we hit a leaf with a new depth, there are two ways that our tree might now be unbalanced:

1. There are more than 2 different leaf depths
2. There are exactly 2 leaf depths and they are more than 1 apart.

Why are we doing a depth-first walk and not a breadth-first ↴ one? You could make a case for either. We chose depth-first because it reaches leaves faster, which allows us to short-circuit earlier in some cases.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
private static class NodeDepthPair {
    BinaryTreeNode node;
    int depth;
    NodeDepthPair(BinaryTreeNode node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}
public static boolean isBalanced(BinaryTreeNode treeRoot) {
    // a tree with no nodes is superbalanced, since there are no leaves!
    if (treeRoot == null) {
        return true;
    }
    // we short-circuit as soon as we find more than 2
    List<Integer> depths = new ArrayList<>(3);
    Deque<NodeDepthPair> nodes = new ArrayDeque<>();
    nodes.push(new NodeDepthPair(treeRoot, 0));
    while (!nodes.isEmpty()) {
        // pop a node and its depth from the top of our stack
        NodeDepthPair nodeDepthPair = nodes.pop();
        BinaryTreeNode node = nodeDepthPair.node;
        int depth = nodeDepthPair.depth;
        // case: we found a leaf
        if (node.left == null && node.right == null) {
            // we only care if it's a new depth
            if (!depths.contains(depth)) {
                depths.add(depth);
                // two ways we might now have an unbalanced tree:
                //   1) more than 2 different leaf depths
                //   2) 2 leaf depths that are more than 1 apart
                if (depths.size() > 2 || (depths.size() == 2
                        && Math.abs(depths.get(0) - depths.get(1)) > 1)) {
                    return false;
                }
            }
        // case: this isn't a leaf - keep stepping down
        } else {
            if (node.left != null) {
                nodes.push(new NodeDepthPair(node.left, depth + 1));
            }
            if (node.right != null) {
                nodes.push(new NodeDepthPair(node.right, depth + 1));
            }
        }
    }
    return true;
}

Complexity

O(n)O(n) time and O(n)O(n) space.

For time, the worst case is the tree is balanced and we have to iterate over all nn nodes to make sure.

For the space cost, we have two data structures to watch: depths and nodes.

depths will never hold more than three elements, so we can write that off as O(1)O(1).

Because we’re doing a depth first search, nodes will hold at most dd nodes where dd is the depth of the tree (the number of levels in the tree from the root node down to the lowest node). So we could say our space cost is O(d)O(d).

But we can also relate dd to nn. In a balanced tree, dd is O(log⁡2(n))O(log2​(n)). And the more unbalanced the tree gets, the closer dd gets to nn.

In the worst case, the tree is a straight line of right children from the root where every node in that line also has a left child. The traversal will walk down the line of right children, adding a new left child to nodes at each step. When the traversal hits the rightmost node, nodes will hold half of the nn total nodes in the tree. Half is O(n)O(n), so our worst case space cost is O(n)O(n).

What We Learned

This is an intro to some tree basics. If this is new to you, don’t worry — it can take a few questions for this stuff to come together. We have a few more coming up.

Particular things to note:

Focus on depth-first ↴ vs breadth-first ↴ traversal. You should be very comfortable with the differences between the two and the strengths and weaknesses of each.

You should also be very comfortable coding each of them up.

One tip: Remember that breadth-first uses a queue and depth-first uses a stack (could be the call stack or an actual stack object). That’s not just a clue about implementation, it also helps with figuring out the differences in behavior. Those differences come from whether we visit nodes in the order we see them (first in, first out) or we visit the last-seen node first (last in, first out).