Chapter 67 Apple

67.1 Compound Iterator

Suitable for: Everyone
Time: 10-20 minutes
Format: Phone-Screen
Skills: Coding in Java, Data structures, Java Collections, using an interface

To initialize a CoderPad for this problem, go to https://coderpad.io/questions and select iTunes: Compound Iterator and press the Create Pad With Question button.

67.1.1 The Problem

Write a CompoundIterator. CompoundIterator takes an array of Iterators in its constructor; CompoundIterator itself should implement the java.util.Iterator interface, such that it iterates over the elements of the passed-in Iterators as if they were a single Iterator. If any of the Iterators in the passed-in array is null or empty, it should simply be skipped (note that this is not the same thing as saying that if the Iterators themselves return null elements from next(), those elements should be skipped — they should not be). It is expected that CompoundIterator will exhaust the passed-in Iterators. You do not need to provide a working implementation of the remove() method.

Use the following stub to start:

import java.util.Iterator;

public class CompoundIterator
implements Iterator {
  public CompoundIterator(Iterator[] iterators) {
    // TODO: Implement me
  }

  public boolean hasNext() {
    // TODO: Implement me
    return false;  // stub
  }

  public Object next() {
    // TODO: Implement me
    return null;  // stub
  }

  public void remove()
  throws UnsupportedOperationException {
    throw new UnsupportedOperationException(
      getClass().getName() + " does not support the remove() operation.");
  }
}

67.1.2 For the Interviewer

For more experienced candidates, add this stipulation: Some of the passed-in Iterators may be iterating over data structures that, either individually or in aggregate, are too large to hold in memory at one time (e.g., large result sets from a database), and so it is not acceptable to collapse the elements of the Iterators into a single in-memory data structure.

Encourage the candidate to think aloud about data structure and design choices.

67.1.3 Hints

• How far do you have to look ahead to tell whether there is a next element?

67.1.4 Followup Questions

For less experienced candidates who choose to collapse the Iterators into a single data structure — which is arguably the simplest (and therefore best) solution in the absence of a requirement not to collapse them — you might ask, “Under what circumstances would it be inappropriate to collapse the Iterators into a single data structure?”

67.1.5 Solution

67.1.5.1 Solution #1

Here is a solution that collapses the Iterators into a single data structure:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class CompoundIterator
implements Iterator
{
  private Iterator myIterator = null;

  public CompoundIterator(Iterator[] iterators)
  {
    List myList = new ArrayList();

    for (int i = 0; i < iterators.length; i++)
    {
      Iterator iterator = iterators[i];
      if (iterator != null)
      {
        while (iterator.hasNext())
        {
          Object obj = iterator.next();
          myList.add(obj);
        }
      }
    }

    myIterator = myList.iterator();
  }

  public boolean hasNext()
  {
    return myIterator.hasNext();
  }

  public Object next()
  {
    return myIterator.next();
  }

  public void remove()
  throws UnsupportedOperationException
  {
    myIterator.remove();
  }
}

67.1.5.2 Solution #2

Here is one that does not collapse the Iterators into a single data structure:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class CompoundIterator
implements Iterator {

  private Iterator[] iterators = null;
  private int index = 0;

  public CompoundIterator(Iterator[] iterators) {
    this.iterators = iterators;
  }

  public boolean hasNext() {
    if (iterators == null) {
      return false;
    }
    for (; index < iterators.length; index++) {
      Iterator oneIterator = iterators[index];
      if (oneIterator != null && oneIterator.hasNext()) {
        return true;
      }
    }
    // Fell out of the loop; must not have any more Iterators
    return false;
  }

  public Object next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    return iterators[index].next();
  }

  public void remove()
  throws UnsupportedOperationException {
    throw new UnsupportedOperationException(
    getClass().getName() + " does not support the remove() operation.");
  }
}

67.1.6 Unit Test

67.1.7 Evaluation

Run the Unit Test and evaluate the candidate’s code.

67.2 Implement Natural Numbers

Suitable for: Mid-Senior Level.
Time: 15-25 minutes
Format: In-Person
Skills: Abstract thinking, OOP, Java, asking clarifying questions and coding to spec.

67.2.1 The Problem

In a nutshell the problem is to implement Natural (non-negative) numbers without using int or any other numbers in java.

Basically a candidate is given a subset of Java language that has:

• OOP concepts:

  • classes
  • interfaces
  • methods

• Basic language structures:

  • local variables
  • booleans
  • flow control statements (if/elseif/else)
  • while loops

We ask a candidate to define non-negative numbers: [0, +infinity] using a given interface:

/**
 * An interface that represents non-negative integer number
 */
interface Number {
    /**
     * @return true is number represents 0 (zero)
     */
    boolean isZero();
    /**
     * @return a number that represents `this - 1`
     * For example if called on a number that represents 2 - a number that represents 1 should be returned
     */
    Number previous();
    /**
     * @return a number that represents `this + 1`
     * For example if called on a number that represents 2 - a number that represents 3 should be returned
     */
    Number next();
}

n.previous()就是减一(n-1), n.next()就是加一(n+1)的意思.

67.2.1.1 Questions to ask

• Ask candidate to implement this interface according to specification. Note that it is important to understand that there is no fields allowed
  
• Ask candidate to implement following methods, ask about time complexity:

interface Operations {
    /**
     * @param n1
     * @param n2
     * @return a Number that represents a sum of n1 and n2
     * O(n1) or O(n2) depending on which number is decremented
     */
    static Number sum(@Nonnull Number n1, @Nonnull Number n2) {
        throw new UnsupportedOperationException();
    }
    /**
     * @param n1
     * @param n2
     * @return a Number that represents a result of integer division of n1 by n2  (5/3=1 2/1=2 0/1=0 3/0=?)
     * @throws IllegalArgumentException if n2 is zero
     * O(n2)
     */
    static Number div(@Nonnull Number n1, @Nonnull Number n2) {
        throw new UnsupportedOperationException();
    }
}

67.2.1.1.1 Optional

• Talk about infinity, how can we implement a number that represents infinity, how can we add a method that detects infinity? How do we need to change operations to support that.

Double.POSITIVE_INFINITY;
boolean b=Double.isInfinite(0);

• Talk about rational numbers (or complex numbers)

67.2.2 Solutions

67.2.2.1 Implement interface in abstract class

abstract class NumberImpl implements Number {
    @Override
    public boolean isZero() {
        return false;
    }
    @Override
    public abstract Number previous();
    @Override
    public Number next() {
        return new NumberImpl() {
            @Override
            public Number previous() {
                return NumberImpl.this; //  outer.this  is outer class reference
            }
        };
    }
    /**
     * @return a number that represents zero
     */
    public static Number zero() {
        return new NumberImpl() {
            @Override
            public boolean isZero() {
                return true;
            }
            @Override
            public Number previous() {
                return null;
            }
        };
    }
}

67.2.2.2 Implement functions in interface

interface Operations {
    /**
     * @param n1
     * @param n2
     * @return a Number that represents a sum of n1 and n2
     */
    static Number sum(@Nonnull Number n1, @Nonnull Number n2) {
        if (n2.isZero())
            return n1;
        return sum(n1.next(), n2.previous());
    }
    /**
     * @param n1
     * @param n2
     * @return a Number that represents a result of integer division of n1 by n2  (5/3=1 2/1=2 0/1=0 3/0=?)
     * @throws IllegalArgumentException if n2 is zero
     */
    static Number div(@Nonnull Number n1, @Nonnull Number n2) {
        if (n2.isZero())
            throw new IllegalArgumentException("Division by Zero");
        Number result = NumberImpl.zero();
        while (!n1.isZero()) {
            Number tmp = n2;
            while (!tmp.isZero() && !n1.isZero()) {
                n1 = n1.previous();
                tmp = tmp.previous();
            }

            if (tmp.isZero()) {
                result = result.next();
            }
        }
        return result;
    }
}

67.3 Implement Natural Numbers 2

Suitable for: Mid Level.
Time: 30 minutes
Format: In-Person or Phone-Screen
Skills: Abstract thinking, Brain teaser, Algorithms

67.3.1 The Problem

In a nutshell, the problem is to implement basic operators, i.e. >=, +, -, *, / for natural numbers without using int or any other numbers in java.

Given the following definition of a natural number:

/**
 * An interface that represents a natural number (non-negative integer)
 */
interface Number {
    /**
     * @return true is number represents 0 (zero)
     */
    boolean isZero();

    /**
     * @return a number that represents `this - 1`
     * For example if called on a number that represents 2 - a number that represents 1 should be returned
     */
    Number previous();

    /**
     * @return a number that represents `this + 1`
     * For example if called on a number that represents 2 - a number that represents 3 should be returned
     */
    Number next();
}

, finish the implementation:

class Math {
    private final Number zero;
    public NumberMath(@Nonnull Number zero) {
        this.zero = zero;
    }
    public boolean greaterOrEqualThan(@Nonnull Number n1, @Nonnull Number n2) {
    ...
    }
    public Number addition(@Nonnull Number n1, @Nonnull Number n2) {
    ...
    }
    public Number subtraction(@Nonnull Number n1, @Nonnull Number n2) {
    ...
    }
    public Number multiplication(@Nonnull Number n1, @Nonnull Number n2) {
    ...
    }
    public Number division(@Nonnull Number n1, @Nonnull Number n2) {
    ...
    }
}

67.3.1.1 Restrictions

• Numbers are not singletons, i.e. operators == or .equals() do not compare the value of numbers.
• An implementation of Number is not available to the candidate, .previous() called on zero returns null.

67.3.2 Solutions

67.3.2.1 Implement interface

class Math {
  private final Number zero;

  public Math(Number zero) {
      this.zero = zero;
  }

  public boolean greaterOrEqualThan(Number n1, Number n2) {
      if (n1.isZero() && n2.isZero()) return true;
      if (n1.isZero()) return false;
      if (n2.isZero()) return true;
      return greaterOrEqualThan(n1.previous(), n2.previous());
  }

  public Number addition(Number n1, Number n2) {
      if (n1.isZero()) return n2;
      return addition(n1.previous(), n2.next());
  }

  public Number subtraction(Number n1, Number n2) {
      if (!greaterOrEqualThan(n1, n2))
          throw new IllegalArgumentException("the first argument must be "
            + "greater of equal than the second argument");
      if (n2.isZero()) return n1;
      return subtraction(n1.previous(), n2.previous());
  }

  public Number multiplication(Number n1, Number n2) {
      return multiplication(n1, n2, zero);
  }

  private Number multiplication(Number n1, Number n2, Number accumulator) {
      if (n1.isZero()) return accumulator;
      return multiplication(n1.previous(), n2, addition(accumulator, n2));
  }

  public Number division(Number n1, Number n2) {
      if (n2.isZero()) throw new IllegalArgumentException("division by "
        + "zero is not allowed");
      return division(n1, n2, zero);
  }

  private Number division(Number n1, Number n2, Number accumulator) {
      if (!greaterOrEqualThan(n1, n2) || n2.isZero()) return accumulator;
      return division(subtraction(n1, n2), n2, accumulator.next());
  }
}

67.4 N-Way-List-Merge

Suitable for: Everyone
Time: 15-35 minutes
Format: Phone-Screen
Skills: Algorithms, Data structures, Java Collections

To initialize a CoderPad for this problem, go to https://coderpad.io/questions and select AMP: N-Way-List-Merge and press the Create Pad With Question button.

67.4.1 The Problem

• You are given a task to implement a function that merges several sorted arrays (lists).
• Candidate should be able to come up with an O(N * Log M) solution. Where N is a total number of elements and M is a number of lists given. There are two ways of doing this:
  • Using MinHeap (PriorityQueue) and extract one element at a time
  • Merge pairs of lists, then merged pairs and so on (more complicated way of doing that code-wise)

67.4.2 Solutions

These are the real interview answers that we’ve accepted and invited people on-site.

67.4.2.1 Using Heap

import java.util.*;

class Solution {
    /**
     * Accepts an array of sorted lists and merges them into one sorted list
     * Example: 0 [1, 3, 5, 6]
     *          1 [3, 4, 7],
     *          2 [-1, 2]     =>[-1, 1, 2, 3, 3, 4, 5, 6, 7]
     */
    public static List<Integer> merge(List<List<Integer>> lists) {
        List<Integer> result = new ArrayList<>();
        if (lists == null || lists.size() == 0) {
            return result;
        }

        Comparator<Node> comparator = new Comparator<Node>() {
            public int compare(Node a, Node b) {
                return a.value - b.value;
            }
        };

        Queue<Node> pq = new PriorityQueue<Node>(lists.size(), comparator);
        for (int i = 0; i < lists.size(); i++) {
            List<Integer> current = lists.get(i);
            if (current.size() > 0) {
                pq.offer(new Node(current.get(0), i, 0));
            }
        }

        while (!pq.isEmpty()) {
            Node top = pq.poll();
            result.add(top.value);
            if (top.y < lists.get(top.x).size() - 1) {
                Node newNode = new Node(lists.get(top.x).get(top.y + 1), top.x, top.y + 1);
                pq.offer(newNode);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.print(merge(
                Arrays.asList(
                        Arrays.asList(1, 3, 5, 6),
                        Arrays.asList(3, 4, 7),
                        Arrays.asList(-1, 2)
                )));
    }
}

class Node {
    public int value;
    public int x;
    public int y;

    public Node(int value, int x, int y) {
        this.value = value;
        this.x = x;
        this.y = y;
    }
}

67.4.2.2 By-pair Merging

import java.util.*;

class Solution {
    /**
     * Accepts an array of sorted lists and merges them into one sorted list
     * Example: [1, 3, 5, 6],[3, 4, 7],[-1, 2]=>[-1, 1, 2, 3, 3, 4, 5, 6, 7]
     * [[], [], []] -> []
     * [] -> []
     */

    // M - # lists
    // N - # elements
    // O(...) = O(N*log(M))
    public static List<Integer> merge(List<List<Integer>> lists) {
        //l1, l2, l3, l4, l5, l6, l7, l8
        // 1) l1 & l2, l3 & l4, l5 & l6, l7 & l8 -> 4 lists l12,l34,l56,l78
        // 2) l12 & l34, l56 & l78 -> l1234, l5678
        // 3) l1234 & l5678 -> result
        // throw new UnsupportedOperationException("Please implement this method");

        // Base condition check
        if (lists.size() == 0) {
            return new ArrayList<Integer>();
        } else if (lists.size() == 1) {
            return lists.get(0);
        }

        // Clone the input
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (List<Integer> l : lists) {
            res.add(l);
        }

        int numLists = lists.size();
        int numProcessed = 0;
        int start;
        while (numLists > 1) {
            start = 0;
            if (numLists % 2 != 0) {
                numProcessed++;
                start = 1;
            }

            // Process all current lists
            for (int i = start; i < numLists; i += 2) {
                res.set(numProcessed, merge(res.get(i), res.get(i + 1)));
                numProcessed++;
            }

            numLists = numProcessed;
            numProcessed = 0;
        }

        return res.get(0);
    }

    private static List<Integer> merge(List<Integer> l1, List<Integer> l2) {
        int i = 0; // for l1
        int j = 0; // for l2
        List<Integer> result = new ArrayList<Integer>();
        while (i < l1.size() && j < l2.size()) {
            if (l1.get(i) < l2.get(j)) {
                result.add(l1.get(i));
                i++;
            } else if (l1.get(i) > l2.get(j)) {
                result.add(l2.get(j));
                j++;
            } else {
                result.add(l1.get(i));
                result.add(l2.get(j));
                i++;
                j++;
            }
        }
        // Figure out where are the remaining elements to process (if any)
        List<Integer> temp = new ArrayList<Integer>();
        int t = 0;
        if (i < l1.size()) {
            temp = l1;
            t = i;
        } else if (j < l2.size()) {
            temp = l2;
            t = j;
        }

        for (int k = t; k < temp.size(); k++) {
            result.add(temp.get(k));
        }

        return result;
    }

    public static void main(String[] args) {
        // [-1, 1, 2, 3, 3, 4, 5, 6, 7]
        System.out.println(merge(
                Arrays.asList(
                        Arrays.asList(1, 3, 5, 6),
                        Arrays.asList(3, 4, 7),
                        Arrays.asList(-1, 2)
                )));

        // [-1, 1, 1, 2, 3, 3, 4, 5, 6, 7]
        System.out.println(merge(
                Arrays.asList(
                        Arrays.asList(1, 3, 5, 6),
                        Arrays.asList(3, 4, 7),
                        Arrays.asList(-1, 2),
                        Arrays.asList(1)
                )));

        // [-1, 1]
        System.out.println(merge(
                Arrays.asList(
                        Arrays.asList(-1),
                        Arrays.asList(1)
                )));

        // [1, 3, 5, 6]
        System.out.println(merge(
                Arrays.asList(
                        Arrays.asList(1, 3, 5, 6)
                )));
    }
}

• C++

// This is the text editor interface. 
// Anything you type or change here will be seen by the other person in real time.
// (sorted)
// Input1 = [-1, 0, 4, 7]
// Input2 = [0, 2, 2, 9]
// Output = [-1, 0, 0, 2, 2, 4, 7, 9]

// T: O(M+N) S: O(M+N)
vector<int> f(vector<int>& v1, vector<int>& v2){
    vector<int> r;
    int L1=v1.size(), L2=v2.size();
    int i=0, j=0;
    while(i<L1 and j<L2){
        if(v1[i]<v2[j])
            r.push_back(v[i++]);
        else
            r.push_back(v[j++]);
    }
    while(i<L1) r.push_back(v1[i++]);
    while(j<L2) r.push_back(v2[j++]);
    return r;
    
}

//vector<vector<int>>
//ArrayList<ArrayList<Integer>> 
// k = number of lists
// n = average number of integers per list
//
//K-way merge
//1. heap - n*k* logk
//2. DC - merge2-  N*K* logK

vector<int> f2(vector<vector<int>>& vv){
    if(vv.empty() || vv[0].empty()) return {};
    if(vv.size()==1) return vv[0]; //base case
    vector<vector<int>> r;
    for(int i=0;i<vv.size();i+=2){
        if(i+1==vv.size()){
            r.push_back(vv[i]);
        }else{
            auto tmp =f(vv[i], vv[i+1]);
            r.push_back(tmp);
        }
    }
    return f2(r);
}

67.5 Optimal 2-way Split

Suitable for: Mid-Senior Level.
Time: 30 minutes
Format: Phone-Screen
Skills: Knowledge of algorithms, asking clarifying questions and coding to spec.

To initialize a CoderPad for this problem, go to https://coderpad.io/questions and select iTunes: Optimal Two-Way Split and press Create Pad With Question.

67.5.1 The Problem

Divide an input array of numbers into 2 groups such that the absolute difference between an arithmetic mean in each group is maximized. Every element from the input array must belong to either one of the two groups. Discuss time and memory complexity of your solution.

67.5.2 For the Interviewer

Candidate may ask clarifying questions.

1. Q: “What are the numbers in the input array?” A: “Positive and negative doubles.”
2. Q: “Should I assume any particular order or distribution of the data in the input array?” A: “No.”
3. Q: “Is approximate solution acceptable?” A: “No, only exact solution.”
4. Q: “Should I consider illegal input?” A: “Yes, you should signal an error if illegal arguments are provided to the algorithm.” (Illegal argument is any array that does not have 2 or more elements.
5. Q: “Should I return 2 arrays?” A: “You should use as little memory as you can.” (A candidate might not know at this point that an answer may be represented as a single scalar, i.e. a split point that discriminates inputs: all inputs less or equal than the split point belong to one group. All the other elements belong to the other group).
6. Q: “What if there’s more then one valid output?” A: “Return the first solution.”

Candidate may propose a couple of clarifying examples.

• e.g. [2, 3, 1] -> {1},{2,3} or {1,2},{3} are both valid splits, in both cases the difference is maximized and equal to 1.5

Candidate should be able to propose a brute-force solution to find every possible split of data and choose the one that maximizes an objective function.

67.5.3 Hints

• Candidate should figure out that all elements in one group will be <= all the elements in the other group. Ask them to verbally prove this.

• Once the candidate has explored the problem, ask them if they can create a solution with O(n) time and O(1) additional memory complexity.

67.5.4 Followup Questions

• Candidate must be able to calculate time and space complexity of solution. Brute force time complexity is \(O(2^N-2)\) and memory complexity \(O(1)\). A candidate must be able to prove what is the time complexity verbally, something like:

"Each element might either be in one or the other group, so I have 2^N possible
combinations, where N is a number of elements in input array, but I don't allow
all elements in the same group, because then I can't calculate the arithmetic
mean in one of them, so that's where -2 comes from. O(1) memory complexity comes
from the fact that the brute-force solution only requires nesting loops and no
memoization."

000…000 and 111…111 are not allowed, so need to -2.

67.5.5 Solution

First Sort it : https://stackoverflow.com/questions/16252269/how-to-sort-an-arraylist

Then a sample solution for this problem follows:

double findOptimalGroupingInSortedArray(double[] input) {
  if (input == null || input.length < 2)
    throw new IllegalArgumentException("Input must have 2 or more elements.");
  double leftSum = input[0];
  double rightSum = 0.0;
  for (int i = 1; i < input.length; i++) {
    rightSum += input[i];
  }
  int splitIndex = 0;
  double maxDifference = rightSum / (input.length - 1) - leftSum;
  for (int i = 1; i < input.length - 1; i++) {
    leftSum += input[i];
    rightSum -= input[i];
    double currentDifference =
      (rightSum / (input.length - 1 - i)) - (leftSum / (i + 1));
    if (currentDifference > maxDifference) {
      maxDifference = currentDifference;
      splitIndex = i;
    }
  }
  return input[splitIndex];
}

Should be \(O(NlogN)\) due to sorting!

67.5.6 Evaluation

Rate the candidate based on the following scale (from 1-4):

67.5.6.1 4.0

• Candidate proposes O(N) time, O(1) space complexity solution
• Able to explain the complexity of his/her solution.
• Correct code (passes all tests).
• Candidate has a clear understanding of “impractical” solutions (brute-force solution). Was able to prove this mathematically.

67.5.6.2 3.0

• Candidate proposes O(N) time solution but used more memory than needed.
• Able to explain the complexity of his/her solution?
• Correct code (passes all tests).
• Candidate has a clear understanding of “impractical” solutions (brute-force solution) but could not rigorously prove the complexity.

67.5.6.3 2.0

• Candidate proposes worse than O(N) time complexity solution. Usually this happens when a candidate re-calculates the average over and over.
• Candidate is able to explain the complexity of his/her solution?
• Correct code (passes all tests).
• Candidate has a clear understanding of “impractical” solutions (brute-force solution) but could not rigorously prove the complexity.

67.5.6.4 1.0

• None of the above.

67.5.7 Reference:

https://arxiv.org/pdf/cond-mat/0310317.pdf
https://en.wikipedia.org/wiki/Partition_problem

67.6 Palindrome Questions

Suitable for: Mid-Senior Level.
Time: 15-45 minutes
Format: Phone-Screen or In-Person
Skills: Knowledge of algorithms, asking clarifying questions and coding to spec.

The coderpad.io Questions for this problem are in two parts. Start at https://coderpad.io/questions and look for the two questions called iTunes: Palindrome Function and iTunes: Palindrome Substrings. Select the Palindrome Function question and press the Create Pad With Question button, then once the candidate has finished with that question, continue with Palindrome Substrings.

67.6.1 The Problem

A palindrome is a string that is the same when read from left to right and right to left. This task is to write a function that counts how many palindromes are in a given input string.

67.6.2 For the Interviewer

Encourage the candidate to think aloud about data structure and design choices. Tell the candidate:

1. Implement a function that takes a string and answers if it is a palindrome or not. There are two caveats:

• String has special characters, that are ALL non-alphabetic characters. These characters we should simply ignore. For example a?a?12312?a--a== is a palindrome, since if you strip off non-alpha chars it is aaaa
• Lowercase letters are equal to uppercase. e.g. aBbA is a palindrome.

2. Second question is to implement a function that counts how many palindromes a given input string contains.

To simplify, we assume that string has NO special characters and all the chars are lowercased.

For example, elephant = 8 + 1 = 9, aaa = 3 + 2 + 1 = 6.

67.6.3 Hints

• If the candidate starts down a path that requires an algorithm with some additional memory or scratch space, let them know that they can create a more efficient function that does not need additional memory.
• If they can’t come up with an algorithm - give a hint, that every palindrome has a center.
• If that doesn’t help - tell that if x|word|x is a palindrome, then word is a palindrome as well.

67.6.4 Followup Questions

67.6.4.1 For Part 1 (Palindrome Function)

• Ask the candidate to work out the complexity of their algorithm.

67.6.4.2 For Part 2 (Palindrome Substrings)

• Ask for a naive solution (generate all the substrings and run through isPalindrome function)
• Ask for complexity (expected answer is O(N^3)).
• Ask to find a O(N^2) solution.

67.6.5 Solution

Sample solutions for the Palindrome problems follow.

67.6.5.1 isPalindrome Function

private boolean isAlphabetic(char c) {
  // we allow candidates to assume this method exists
  return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z');
}

private boolean equalsIgnoreCase(char c1, char c2) {
  // some candidates do conversion to upper case - which is also ok.
  // implementing something like this is optional, provides additional credit
  return c1 - c2 == 0 || Math.abs(c1 - c2) == 'a' - 'A';
}

private boolean isPalindrome(final String input) {
  if (input == null)
      throw new IllegalArgumentException("input mustn't be null");
  int start = 0;
  int end = input.length() - 1;
  while (start < end) {
    if (!isAlphabetic(input.charAt(start))) {
      start++;
      continue; }
    if (!isAlphabetic(input.charAt(end))) {
      end--;
      continue; }
    if (!equalsIgnoreCase(input.charAt(start), input.charAt(end)))
      return false;
    start++;
    end--; }
  return true;
}

67.6.5.2 Count Palindromes

private int countToSides(String s, int leftIndex, int rightIndex) {
  int count = 0;
  while (leftIndex >= 0 && rightIndex < s.length() && s.charAt(leftIndex) ==
         s.charAt(rightIndex)) {
    count++;
    leftIndex--;
    rightIndex++;
  }
  return count;
}

private int countPalindromes(final String input) {
  if(input == null) throw new IllegalArgumentException("input mustn't be null");
  int total = 0;
  for (int i = 0; i < input.length(); i++) {
    total += countToSides(input, i, i);
    total += countToSides(input, i, i + 1);
  }
  return total;
}

67.6.6 Evaluation

• The minimum for a candidate is to at least come up with an iterative solution that doesn’t require additional memory.
• Can estimate the complexity of their isPalindrome function.
• Can estimate the complexity of the naive approach for the Palindrome Substrings problem (Part 2).
• Candidate comes up with a good, clean, well structured solution to both parts of the problem.
• Candidate spent time clarifying and asking questions and discussing their approach before jumping into the implementation.

67.6.7 Reference:

Palindrome topics

67.7 Primes Sieve

Suitable for: Everyone
Time: 30 minutes
Format: Phone-Screen
Skills: Java Coding, simple algorithms, coding to spec.

To initialize a CoderPad for this problem, go to https://coderpad.io/questions and select the iTunes: Primes Sieve question and press the Create Pad With Question button.

67.7.1 The Problem

Sieve of Eratosthenes

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’s method:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
5. When the algorithm terminates, all the numbers in the list that are not marked are prime.

67.7.2 For the Interviewer

Encourage the candidate to think aloud about data structure and design choices.

This is an exercise in following requirements more than anything and some candidates simply ignore the algorithm and write their own prime number generator.

67.7.3 Followup Questions

Ask about the running time of the candidate’s solution. The typical solution will run in O(N log(log(N))). There is an O(N) variation. See more details here: http://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/ (This is Wrong!)

67.7.4 Solution

Here is a simple solution.

/**
 * Returns a list of primes up to including the upper bound
 * example usage: List<Integer> primes = findPrimes(10);
 *   —> [2,3,5,7]
 */
public List<Integer> findPrimes(Integer n) throws IllegalArgumentException {
  // Create a boolean array "prime[0..n]" and initialize
  // all entries as true. A value in prime[i] will
  // finally be false if i is not a prime, else true.
  boolean[] prime = new boolean[n+1];
  for (int i = 0; i <= n; i++)
    prime[i] = true;
  ArrayList<Integer> ret = new ArrayList<Integer>();

  for (int p = 2; p*p <= n; p++) {
    // If prime[p] is not changed, then it is a prime
    if (prime[p] == true){
      // Update all multiples of p
      for (int i = p*2; i <= n; i += p)
        prime[i] = false;
    }
  }

  // Output all prime numbers
  for (int p = 2; p <= n; p++)
    if (prime[p])
      ret.add(p);    

  return ret;
}

Another solution that uses a HashMap instead of a boolean array:

/**
   * Returns a list of primes up to including the upper bound
   * example usage: List<Integer> primes = findPrimes(10);
   *   —> [2,3,5,7]
   */
  public List<Integer> findPrimes(Integer n) throws IllegalArgumentException {
    ArrayList<Integer> ret = new ArrayList<Integer>();
    HashMap<Integer, Boolean> notPrime = new HashMap<Integer, Boolean>();
    int nextPrime = 2;
    while (nextPrime <= n) { // O(N)
      ret.add(nextPrime);
      for (int j = nextPrime + nextPrime; j <= n; j += nextPrime) { // O(LogLogN)
        notPrime.put(j, false);
      }
      nextPrime++;
      while (notPrime.containsKey(nextPrime)) nextPrime++; // skip non-prime numbers
    }
    return ret;
  }

67.7.5 Complexity

O(N log(log(N)))

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity

https://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm

https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes

67.7.6 Evaluation

• Did the candidate’s solution work?
• Did they implement the algorithm as specified?
• Could candidate speak to the complexity of the algorithm?

67.7.7 204. Count Primes From Leetcode

Description:

Count the number of prime numbers less than a non-negative number, n.

https://leetcode.com/problems/count-primes/

T: \(O(Sqrt(N) * LogLogN + N)\)

class Solution {
public:
    int countPrimes(int n) {
        if(n<2) return 0;
        vector<bool> v(n, true);
        for(int i=2; i*i<n; ++i){ // why i*i?  O(sqrt(N))
            if(!v[i]) continue;
            int j=i+i;
            while(j<n)  // O(loglogN)
                v[j]=false, j+=i;
        }
        return count(v.begin()+2, v.end(), true);  //O(N)
    }
};

T: \(O(N * LogLogN)\)

class Solution {
public:
    int countPrimes(int n) {
        if(n<2) return 0;
        vector<bool> v(n, true);
        int c=0;
        for(int i=2;i<n;++i){ // O(N)
            if(!v[i]) continue;
            c++;
            if(i*i<n){
                int j=i+i;
                while(j<n) // Total: O(LoglogN)
                    v[j]=false, j+=i;
            }
        }
        return c;
    }
};

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://www.geeksforgeeks.org/sieve-of-eratosthenes/

• Why i*i?

Everyone else is explaining why for a monolithic sieve (i.e. non-segmented). You need to check all prime factors up to the square root of the limit (e.g. N=49, we must check 7, but do not need to check anything higher, since any number divisible by a larger number would also be divisible by a number less than the square root of N, hence we would already have found it). I’m pretty sure this isn’t your question, which is instead about segmented sieves.

https://www.quora.com/Why-do-we-first-find-the-prime-numbers-up-to-square-root-of-N-in-segmented-sieve

67.8 Resource Pool

Suitable for: Everyone
Time: 30 minutes
Format: In-Person (preferably with a laptop for coding and testing)
Skills: Coding in Java, data structures, basic OO design, multithreading

To initialize a CoderPad for this problem, go to https://coderpad.io/questions and select the iTunes: Resource Pool question and press the Create Pad With Question button.

67.8.1 The Problem

Your task is to write a thread-safe ResourcePool in Java; it should have a constructor, taking an int that should be interpreted as the size of the pool. Other than the constructor, it only needs two public instance methods: claimResource() and releaseResource(). You can assume, for the purposes of this problem, that clients will always release Resources that they claim, and they will do so once, and only once.

Also, you can assume that the class Resource has a default, no-argument constructor (this is, admittedly, artificial, but it keeps things simple, and it keeps us focused on the ResourcePool). The class Resource is provided so that your code will compile. You cannot edit Resource, though; for the purposes of this problem, Resource looks like this:

public final class Resource
{
}

Below is a skeleton of the class that you should fill in. We’ll compile the class and test it.

public class ResourcePool
{
  /**
   * Construct a ResourcePool containing the specified
   * number of Resources.
   *
   * @param size the number of Resources to be contained by the pool.
   */
  public ResourcePool(int size)
  {
  }

  /**
   * Claim a {@link Resource} from the pool.  A Resource returned from this
   * method will not be given to another caller until after it has
   * been released via a call to {@link #releaseResource(Resource)}.
   *
   * @return a {@link Resource} from the pool, for use only by the caller
   */
  public Resource claimResource()
  {
    // TODO: Implement me
    return null;
  }

  /**
   * Release a {@link Resource} back into the pool; after this method has
   * been called, the Resource is available to future callers of
   * {@link #claimResource}.
   *
   * @param r the {@link Resource} to be released.
   */
  public void releaseResource(Resource r)
  {
    // TODO: Implement me
  }
}

67.8.2 For The Interviewer

Tell the candidate the following:

You are working in a high-volume multi-threaded application, like a web application, and your threads need to work with a class, let’s call it Resource, whose instances are rather expensive to construct, and not thread-safe; i.e., a given instance of Resource should only be used by one thread at a time. Once a given thread is done with the Resource, it could be used by another thread. Lots of threads need to use Resources for short periods of time, but once they’re done with the Resource, they may not need one again for a while, if at all.

• Encourage the candidate to think out loud about data structure choices.
• Encourage candidate to ask questions about anything that is unclear

There is one aspect of the problem deliberately left unspecified, so that the candidate needs to ask questions to drive out the specifics:

• Candidate asks: What happens when someone calls claimResource() and they’re all claimed?
• Interviewer responds: “What do you think should happen when the pool is empty? What are your options?”

(For example: grow the pool, make the client wait until one is available, throw an exception, just return null.)

After discussing the options, tell the candidate that they should just return null if the pool is empty.

If there is time after the problem is solved, you can move on to a version that uses wait() and notify().

67.8.3 Hints

• Many candidates start out thinking they need to keep track of Resources that are already claimed; most experienced candidates realize pretty quickly that the requirements of the problem are such that you only need to keep track of Resources that are currently available to be claimed.

• If the candidate chooses to use a Hashtable or similar key-value data structure, and does not switch directions relatively soon, you might ask, “I see you’ve chosen to use a Hashtable. What will you use as the key for each entry? Why?”

• The wait() method throws InterruptedException, which can typically be caught and ignored.

67.8.4 Followup Questions

• Ask the candidate why they chose the data structure(s) they did. Ask them what others they might have chosen, and what advantages there might be to one or the other.
• You might wish to discuss thread synchronization. Make the candidate walk you through how a race condition could occur, and have them point to the specific location in the code where having control pass to another thread would cause trouble. Ask the candidate whether everything they’ve synchronized needs to be synchronized, or whether the solution would still work with one of the synchronized keywords removed. (Depending on the solution, releaseResource() might or might not need explicit synchronization.)
• You might wish to discuss the fact that the wait()/notify() solution is susceptible to starvation.
• You might wish to discuss how a real ResourcePool would differ from this one; how it would use an initial size, a maximum size, and a policy for how large to grow the pool at once, etc.
• You might wish to discuss what a client would have to do in order to make certain that claimed Resources are invariably released. (For example, using a finally block could help with this.)
• You might wish to discuss the special considerations that apply to database connection pools. See if the candidate has an understanding that: (a) database connections can go stale and may need to be re-established, (b) database connections are often limited in number by policy; the database may not let you create arbitrarily many connections.
• If there’s time, you can even discuss with the candidate how they would write a JUnit test to test their class.

67.8.5 Solution

67.8.5.1 Solution #1 fastfail

Here is one example of a solution where an empty pool returns null.

import java.util.List;
import java.util.LinkedList;
public class ResourcePool{
  private List pool = new LinkedList();
  public ResourcePool(int size){
    for (int i = 0; i < size; i++)
      pool.add(new Resource());
  }
  public synchronized Resource claimResource(){
    if (pool.isEmpty()) return null;
    return (Resource) pool.remove(0); // pool.poll() , pool.pollFirst()
  }
  public synchronized void releaseResource(Resource r){
    pool.add(r);
  }
}

67.8.5.2 Solution #2 blocking

Here is a solution that uses wait() and notify().

import java.util.List;
import java.util.LinkedList;
public class ResourcePool{
  private List pool = new LinkedList();
  public ResourcePool(int size)  {
    for (int i = 0; i < size; i++)
      pool.add(new Resource());
  }
  public synchronized Resource claimResource(){
    while (true){
      if (!pool.isEmpty()){
        return (Resource) pool.remove(0);
      }
      try{wait();}
      catch (InterruptedException e){
        // ignore
      }
    }
  }
  public synchronized void releaseResource(Resource r){ // BUG - if call twice witt the same parameter
    pool.add(r);
    notify();
  }
}

67.8.6 Unit Test

Here is a JUnit test test their solution. Note that the constant EMPTY_POOL_RETURNS_NULL can be set to true for the initial solution, and then flipped to false to test the wait()/notify() solution.

import java.util.*;
import org.junit.*;
import static org.junit.Assert.*;
public class ResourcePoolTest{
  private static final boolean VERBOSE = false;
  private static final boolean EMPTY_POOL_RETURNS_NULL = true;
  private static final int POOL_SIZE = 10;
  private static final int NUM_THREADS = 20;
  private static final int NUM_ITERATIONS_PER_THREAD = 400;
  private static final long MAX_SLEEP_MS = 50L;
  private static final long THREAD_GROUP_WAIT_TIMEOUT =
  NUM_THREADS * NUM_ITERATIONS_PER_THREAD * MAX_SLEEP_MS;
  private static Random sRandom = new Random(System.currentTimeMillis());
  private Set mClaimedResources = null;
  private ResourcePool mPool = null;
  private int mMaxClaimedResources = 0;
  @Before
  public void setUp() throws Exception{
    try{
      mPool = new ResourcePool(POOL_SIZE);
      System.out.println("Created resource pool of class:" + mPool.getClass().getName());
      mClaimedResources = Collections.synchronizedSet(new HashSet());
    }catch (Throwable e){
      System.err.println("Exception caught within setUp(): ");
      e.printStackTrace();
      throw new Exception(e);
    }
  }
  @Test
  public void testClaimResourceSingleThreaded() throws Throwable{
    try{
      // Drain and fill the pool twice
      // (second time ensures that items returned to the pool become available again)
      for (int i = 0; i < 2; i++){
        for (int j = 0; j < POOL_SIZE; j++){
          Resource resource = mPool.claimResource();
          if (VERBOSE){
            System.out.println("Claimed resource " + resource);
          }
          assertNotNull("Expected non-null Resource from ResourcePool", resource);
          assertFalse("Resource " + resource + " already claimed.", hasClaimedResource(resource));
          storeClaimedResource(resource);
        }
        if (EMPTY_POOL_RETURNS_NULL){
          assertNull("Expected empty pool to return null.", mPool.claimResource());
        }

        for (Iterator iterator = mClaimedResources.iterator(); iterator.hasNext();){
          Resource resource = (Resource) iterator.next();
          mPool.releaseResource(resource);
        }
        forgetAllClaimedResources();
      }
    }catch (Throwable e){
      System.err.println("Throwable caught within test");
      e.printStackTrace();
      throw e;
    }
  }
  private boolean hasClaimedResource(Resource resource){
    return mClaimedResources.contains(resource);
  }
  private void forgetClaimedResource(Resource resource){
    mClaimedResources.remove(resource);
  }
  private void forgetAllClaimedResources(){
    mClaimedResources.clear();
  }
  private void storeClaimedResource(Resource resource){
    mClaimedResources.add(resource);
    mMaxClaimedResources = Math.max(mMaxClaimedResources, mClaimedResources.size());
    assertTrue("Expected maximum number of claimed resources at once to be less"+
      " than or equal to pool size",
    mMaxClaimedResources <= POOL_SIZE);
  }
  @Test
  public void testClaimResourcesMultiThreaded() throws Throwable{
    try{
      List threads = new ArrayList();
      ThreadGroup group = new ThreadGroup("ResourcePoolTestThreadGroup");
      for (int i = 0; i < NUM_THREADS; i++){
        ResourceConsumerThread thread = new ResourceConsumerThread(group, "TestThread-" + i);
        thread.start();
        threads.add(thread);
      }
      waitForThreadGroup(group, THREAD_GROUP_WAIT_TIMEOUT);
      for (Iterator iterator = threads.iterator(); iterator.hasNext();){
        ResourceConsumerThread thread = (ResourceConsumerThread) iterator.next();
        assertTrue("Expected Thread " + thread.getName() + 
          " to complete (probably a bug in the test).",
        thread.isDone());
        Throwable t = thread.getThrowable();
        if (t != null){
          throw t;
        }
      }
    }catch (Throwable e){
      System.err.println("Throwable caught within test");
      e.printStackTrace();
      throw e;
    }
  }
  private void waitForThreadGroup(ThreadGroup group, long maxWait){
    System.out.println("Max wait time for all threads to finish: " 
      + THREAD_GROUP_WAIT_TIMEOUT/1000 + " seconds.");
    long start = System.currentTimeMillis();
    boolean allDone = false;
    WAITING:
    while ((System.currentTimeMillis() - start) < maxWait){
      if (group.activeCount() == 0){
        allDone = true;
        break WAITING;
      }
    }
    if (!allDone){
      throw new RuntimeException("Not all threads completed in time");
    }
  }
  @After
  public void tearDown() throws Exception{
    try{
      System.out.println("Maximum number of resources claimed at any one time was: "
        + mMaxClaimedResources);
      mMaxClaimedResources = 0;
      forgetAllClaimedResources();
    }catch (Throwable e){
      System.err.println("Exception caught within tearDown(): ");
      e.printStackTrace();
      throw new Exception(e);
    }
  }
  class ResourceConsumerThread extends Thread{
    private Throwable mThrowable = null;
    private boolean mDone = false;
    public ResourceConsumerThread(ThreadGroup group, String name){
      super(group, name);
    }
    public Throwable getThrowable(){
      return mThrowable;
    }
    public boolean isDone(){
      return mDone;
    }
    public void run(){
      Resource resource = null;
      try{
        for (int i = 0; i < NUM_ITERATIONS_PER_THREAD; i++){
          // Claim a resource
          resource = mPool.claimResource();
          if (!EMPTY_POOL_RETURNS_NULL){
            assertNotNull("Expected non-null Resource from claimResource()", resource);
          }
          if (resource != null){
            synchronized(mClaimedResources){
              assertFalse("Resource " + resource + " already claimed.", hasClaimedResource(resource));
              storeClaimedResource(resource);
            }
          }
          // Hold the resource
          long sleepTime = Math.abs(sRandom.nextLong()) % MAX_SLEEP_MS;
          if (VERBOSE){
            System.out.println("Thread " + getName() + " sleeping for " 
              + sleepTime + "ms.");
          }
          sleep(sleepTime);
          // Release the resource
          if (resource != null){
            forgetClaimedResource(resource);
            mPool.releaseResource(resource);
            resource = null;
          }
        }
      }catch (Throwable e){
        mThrowable = e;
      }finally{
        synchronized(mClaimedResources){
          if (resource != null){
            mPool.releaseResource(resource);
            forgetClaimedResource(resource);
            resource = null;
          }
        }
        mDone = true;
        if (VERBOSE){
          System.out.println("Thread " + getName() + " completed.");
        }
      }
    }
  }
}

67.8.7 Evaluation

• On the surface, this is a very simple coding problem. But it can reveal a great deal more than strictly coding skills.
• Note how quickly the candidate realizes that the problem is underspecified (i.e., it doesn’t state what to do if the pool is empty).
• Note how readily the candidate comes up with alternate solutions for handling an empty pool.
• The choice of data structures is important; a good candidate will instinctively steer clear of a solution that requires them to iterate through the pool in order to find a suitable Resource to return.
• Pay attention to the candidate’s attitude when they hear that you’re actually going to compile and test their code. Some candidates are put off by having to write real code in an interview; better candidates look forward to the challenge, and enjoy coding anyway.

67.9 Refactor Rock, Paper, Scissors

Suitable for: Mid-Senior Level.
Time: 15-45 minutes
Format: Phone-Screen
Skills: Debugging, refactoring, asking clarifying questions and coding to spec.

To initialize a CoderPad for this problem, go to https://coderpad.io/questions and select iTunes: Refactor Rock, Paper, Scissors and press Create Pad With Question.

67.9.1 The Problem

In a nutshell, the task is to refactor the code for the Rock, Paper, Scissors game.

The Game class runs the game loop.

• First, it instantiates 2 players and then for each iteration of the loop.
• Uses the Player class to randomly select one of the 3 possible options (Rock, Paper, Scissors) for each player
• Runs the evaluation set of if-then-else conditions to decide which player wins,
• Increments the number of wins for the winner.

The loop ends when one of the player reaches 3 wins.

Stress to the candidate that the goals are to have code that is maintainable and extensible.

67.9.2 For the Interviewer

Encourage the candidate to think aloud about what they are seeing is wrong with the code and how to improve it.

67.9.3 Hints

• Where is there redundancy?
• Where is the code hard to maintain?

67.9.4 Followup Questions

Once the candidate comes up with the first pass solution, you can ask:

• Can you add a 4th option to the game, e.g. “Chainsaw”, which will beat all of the other options when it’s randomly selected.
• And once the candidate implements the “Chainsaw” extension, ask them to introduce another option, e.g. “Fire”, which will beat the Paper and the Chainsaw but not the “Rock” and “Scissors” (i.e. chainsaw has some electric component and cables which will get destroyed by “Fire”).

67.9.5 Solution

Sample solution.

static class Game {  
    enum Choice {  
      ROCK, PAPER, SCISSORS, FIRE, CHAINSAW;  
      static Choice getRandom() {  
        return Choice.values()[(int)(Math.random() * Choice.values().length)];  
      }  
    }  
    // "Beats" relationship  
    private final Map<Choice, Set<Choice>> beats = new HashMap<>();  
    // config  
    private final int numTotalWins;  
    Game(int numTotalWins) {  
      this.numTotalWins = numTotalWins;  
      // setup game rules  
      beats.put(Choice.ROCK, new HashSet<>(Arrays.asList( Choice.SCISSORS, Choice.FIRE)));  
      beats.put(Choice.PAPER, new HashSet<>(Arrays.asList( Choice.ROCK)));  
      beats.put(Choice.SCISSORS, new HashSet<>(Arrays.asList( Choice.PAPER, Choice.FIRE)));  
      beats.put(Choice.FIRE, new HashSet<>(Arrays.asList( Choice.PAPER, Choice.CHAINSAW)));  
      beats.put(Choice.CHAINSAW, new HashSet<>(Arrays.asList( Choice.ROCK,
        Choice.PAPER, Choice.SCISSORS)));  
    }  
    void play() {  
      int roundsPlayed = 0;    // Number of rounds played  
      int numDraws = 0;   
      int p1Wins = 0;  
      int p2Wins = 0;  
      while(p1Wins<numTotalWins && p2Wins<numTotalWins) {  
        System.out.println("***** Round: " +  
                           roundsPlayed + " *********************\n");  
        System.out.println("Number of Draws: "+   
                           numDraws + "\n");  
        Choice p1Choice = Choice.getRandom();  
        Choice p2Choice = Choice.getRandom();  
        System.out.println("Player 1: " + p1Choice +   
                           "\t Player 1 Total Wins: " + p1Wins);  
        System.out.println("Player 2: " + p2Choice+   
                           "\t Player 2 Total Wins: " + p2Wins);  
        if( beats.get(p1Choice).contains(p2Choice) ) {  
          p1Wins++;              
        } else if( beats.get(p2Choice).contains(p1Choice) ) {  
          p2Wins++;  
        } else {  
          numDraws++;  
        }            
      }            
      System.out.println("GAME OVER");                  
    }        
  }  
  public static void main(String args[]) {        
    Game game = new Game(3);  
    game.play();        
  }
}

67.9.6 Evaluation

Rate the candidate based on the following scale (from 2-4):

67.9.6.1 2.0

At the minimum the candidate should realize that the if-then-else condition in the main loop is spaghetti code is difficult to extend/maintain.

• Will usually detect there is redundant state in the Player class (just 1 field is needed to keep the number of wins) and will fix it, but will not pay attention to the naming of the setWins method, which should actually be called something like incrementWins, since it’s not a “setter”.
• Will try to refactor the if-then-else condition using a partial ordering of the set of the options, and then comparing the options taken by player 1 and player 2.
• Then, may realize the partial ordering is actually not good, since the options form a ring in the “is beaten by” relationship. To continue may come up with coding a special case using an “if” statement to “close the ring” but then they’ll keep adding hacks
• When asked for the extensions, will keep adding “if” conditions.

67.9.6.2 3.0

Candidates can come up with a solution that works but:

• In addition to remove redundant state in Player class, may rename the setWins method so its semantics is better self-documented.
• Will use some kind of data-driven lookup structure to model the “is beaten by” relationship. It may not come up with a generic solution during the first pass, but should arrive to one that supports the extended questions, once asked. Once refactored, the code should have replaced all the if-then-else conditions by a check to evaluate the “draw” or a lookup against the “is beaten by” data structure to decide which player wins.
• Regarding the implementation of the “playerChoice” it may still leave it as is, having to maintain the switch statement and the strings for “rock”, “paper”, “scissors” in different places in the code, instead of in a single place.
• The candidate may not pay attention to other concerns, such as “does the playerChoice method really belongs in the Player class?”

67.9.6.3 4.0

Candidates come up with a solution that:

In addition to all 3.0 requirements, will

• The extensions will be implemented by populating new cases in the data structure, never by changing logic.
• Centralize the knowledge about the options of the game and their “is beaten by” relationship in a single place. e.g. they may use an enum to model the Choice, and then redefine “playerChoice” method to use the Enum::values() method to pick one randomly instead of a explicit switch statement. The lookup data structure will be populated with values from the enum and the “playerChoice” method will not have to be modified when new choices are added.
• May decide to move the playerChoice method to a different place, since the current implementation doesn’t really depend on the Player state. Potential place: static method on the Choice enum, although a static method in the Game class may make sense too, as far as the access to the set of Choices is public (e.g. Enum::values() will, in case a choice is modeled as an enum)
• May totally ditch the Player class, since it’s not adding any value for the current functionality (number of wins can be kept in a local variable in the main loop).

67.10 Rolling Window

Suitable for: Mid-Senior Level Backend Engineer
Time: 45 minutes
Format: In-Person
Skills: Data Structures and Problem Solving

67.10.1 The Problem

You have a infinite stream of data flowing through your system. Each data-point/event is defined as a message.

class Message {
    String key;
    int value;
}

You cannot possibly store and process all the data in the stream. So, you define a window on the stream which holds K milliseconds worth of messages. Implement this window interface with the following operations:

interface Window {
    // Add a message to the window.
    void addMessage(Message msg); 
    // Get message with given key. Return `null` if the key doesn't exist in the window.
    Message getMsg(String key);
    // Get the average of all values in the window.
    double getAverage(); 
}

Constraints: * addMsg should be fast. * getMsg and getAverage cannot be prohibitively slow.

67.10.2 For the Interviewer

• The size of the window is given at instantiation of the class (K milliseconds) and does not change.
• The constraints are purposely vague (fast, slow). Candidates should be able to ask clarifying questions and come up with equivalent values in terms of time complexity.
  • Fast -> O(1)
  • Not Slow -> Better than O(N), where N = number of messages. O(log N) or O(K) is acceptable.
    
• If the candidate proposes a naive hash-map solution, add that removal of old values from the system should also be fast.
  • Re-iterate that the system :
    Cannot store all the incoming messages
    Has enough capacity to store messages for a window and a bit more.

67.10.3 Hints

• Bucket the keys rather than storing them individually.
  
• The most common way to do this is by using a Hash table with a timestamp as key.
  
• A circular buffer approach will eliminate the need to do removal. However, some logic is needed to read the correct slots (check if timestamp is beyond the window) when reading.
  
• Each entry in the structure above contains another hash table with mapping keys -> messages for that timestamp. We also store the average individually for each timestamp.

67.10.4 Followup Questions

• If the candidate uses a map of maps approach, ask him whether the cleanup should be done by a background thread in one of the client requests.
• Ask about thread-safety of the solution

67.10.5 Solution

67.10.5.1 Solution 1 : Use a Map keyed by time

public class RollingWindow implements Window {
    static class MapElement {
        private long timestamp;
        private Map<String, Message> events = new HashMap<>();
        private long sum;
    }
    private final Map<Long, MapElement> elements;
    private final int windowSize;
    public RollingWindow(int kMilliseconds) {
        windowSize = kMilliseconds;
    }
    public void addMessage(Message msg) {
        long currentTime = System.currentTimeMillis();
        elements.putIfAbsent(currentTime, new MapElement());
        elements.get(currentTime).events.put(msg.getKey(), msg);
        elements.get(currentTime).incrementSum(msg.getValue());
    }
    public Message getMessage(String key) {
        long currentTime = System.currentTimeMillis();
        return elements.entrySet()
                .stream()
                .filter(entry -> (currentTime - entry.getKey()) <= windowSize)
                .map(entry -> entry.getValue().events)
                .map(events -> events.get(key))
                .filter(Objects::nonNull)
                .findAny()
                .orElse(null);
    }
    public double getAverage() {
        long total = 0;
        long numElements = 0;
        long currentTime = System.currentTimeMillis();
        for (Map.Entry<Long, MapElement> entry : elements.entrySet()) {
            if (currentTime - entry.getKey() <= windowSize) {
                final MapElement mapElement = entry.getValue();
                total += mapElement.sum;
                numElements += mapElement.events.size();
            }
        }
        if (numElements == 0) return 0;
        return ((double) total) / ((double) numElements);
    }    
}

67.10.5.2 Solution 2 : Use a Circular Buffer

public class RollingWindow implements Window {
    static class ArrayElement {
        private long timestamp = 0;
        private Map<String, Message> events = new HashMap<>();
        private long sum = 0;
        public ArrayElement(long currentTime) {
            this.timestamp = currentTime;
        }
        public void incrementSum(int value) {
            sum += value;
        }
    }

    private final ArrayElement[] elements;
    public RollingWindow(int kMilliseconds) {
        elements = new ArrayElement[kMilliseconds];
    }
    private int getArrayIndex(long currentTime) {
        return (int) (currentTime % elements.length);
    }
    public void addMessage(Message msg) {
        long currentTime = System.currentTimeMillis();
        int index = getArrayIndex(currentTime);

        if (elements[index].timestamp != currentTime) {
            elements[index] = new ArrayElement(currentTime);
        }
        elements[index].events.put(msg.getKey(), msg);
        elements[index].incrementSum(msg.getValue());
    }
    public Message getMessage(String key) {
        long currentTime = System.currentTimeMillis();
        return Arrays.stream(elements)
                .filter(element -> (currentTime - element.timestamp) <= elements.length)
                .map(element -> element.events)
                .map(events -> events.get(key))
                .filter(Objects::nonNull)
                .findAny()
                .orElse(null);
    }
    public double getAverage() {
        long total = 0;
        long numElements = 0;
        long currentTime = System.currentTimeMillis();
        for (ArrayElement element : elements) {
            if (currentTime - element.timestamp <= elements.length) {
                total += element.sum;
                numElements += element.events.size();
            }
        }
        if (numElements == 0) return 0;
        return ((double) total) / ((double) numElements);
    }
}

67.10.6 Unit Test

TODO: When appropriate, create a JUnit test or other way to automatically check the candidate’s solution.

67.10.7 Evaluation

• The minimum for a candidate is to recognize the issues with using a hash-map to solve the problem and be able to describe a better solution.
• Can come up with a time complexity definition for fast/slow.
• Candidate comes up with an optimal and correct data structure and implements it correctly.
• Candidate describes where/how any cleanup of old messages (if necessary) is performed.
• Candidate spent time clarifying and asking questions and discussing their approach before jumping into the implementation.

其他的设计思想:

TreeMap of (timestamp to KV):

AddMsg(LogN)
getMsg(O(N))
getAverage(O(1))
cleanUP(O(LogN)): tailMap(x).clear()

Heap of (timestamp and KV) + HashMap(k->v,time): ??

AddMsg(logN or KLogN) - K是过期node的个数
getMsg(1 or KLogN)
getAverage(N)
cleanUP(KLogN)

2017(7-9月) 码农类 硕士 全职@Indeed - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生 indeed 刚刚skype面试结束
是一道Expiring Map的题目,楼主之前虽然看过这个,不过思路不清晰,在skype的时候,楼主使用的是自定义数据结构,Node中包含key value以及一个expiretime,这样在put的时候,就可以new一个node同时获得整个node过期的时间,于是当get一个node的时候,我们就将其过期时间和当前时间比较,如果小于当期时间,就从map中删除该key,返回nul,否则就正常返回.最后面试官问,如果大量数据过期怎么办,使用一个PriorityQueue,比较器是根据过期时间来的,这样堆顶就是最早过期的元素,于是我们可以在get的时候或者put的时候,将过期的元素都删除.楼主忘了在put的时候也要加上过滤过期数据的代码了…刚想起来,在最后的时候让分析了put和set的时间复杂度. 然后就结束了.不知道哪位有较好的解法,跪求.

http://www.1point3acres.com/bbs/thread-197737-1-1.html

2017(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Passfresh grad应届毕业生 一面:
实现一个会过期的Map.有put(key, value, lastTime)和get(key)两个方法.每个k-v对放入Map时附带一个有效时间lastTime,持续到过期前都可以正常get,过期后再get则返回无效标记.
关于lastTime什么数据结构我当时询问了面试官,他表示他也不很用JAVA不是很知道里面用什么时间库,就让我assume一个long getCurrentTime()方法来做了,于是解题中是用long来表示时间.
follow ups: 1.如果你出unit test你会出什么case. 2.时间复杂度. 3.如果要实现一个cleanUp(timeStamp)函数,清除所有在timeStamp时间之前的记录,你会怎么修改你的设计.实现.时间复杂度是多少.
二面:
实现一个票数统计器.String getLeader(Collection votes, Long timeStamp) 方法.其中Vote类有两个方法(String getLeader() 和 Long getTimeStamp())表示某一票是投给谁的,什么时候投的. 你要做的method是统计timeStamp之前所有的有效投票,把票数最高的参选人名字返回. follow ups: 1.写一个 List getTopKLeaders(Collections votes, Long timeStamp, int k) 方法,返回某个时间点前统计出来的前k名最强领导人. 2.优化新函数时间复杂度.
面试感受:
1.google家面试都是45分钟,我面到的几场都是围绕单独一个题目环境进行,但有一大几小follow ups循序渐进
2.用的编辑界面是Google Doc.写代码不是很好写,但是你讲解的时候你可以选中文字来highlight,感觉对讨论挺有帮助记得多用用.
timeline
10.20 内推
11.20 收到OA (当天完成)
11.22 约一二面 (11.29收到安排时间)
12.5 一二面背靠背.
12.11 约加面 (12.13收到安排时间)
12.18 三轮加面
12.19 通知面试通过送hiring committee
http://www.1point3acres.com/bbs/thread-310930-1-1.html

• 如何测试?

https://google.github.io/guava/releases/19.0/api/docs/com/google/common/cache/CacheBuilder.html
https://github.com/google/guava/wiki/CachesExplained
https://github.com/google/guava/wiki/CachesExplained#when-does-cleanup-happen
https://github.com/google/guava/wiki/CachesExplained#timed-eviction

Testing Timed Eviction Testing timed eviction doesn’t have to be painful…and doesn’t actually have to take you two seconds to test a two-second expiration. Use the Ticker interface and the CacheBuilder.ticker(Ticker) method to specify a time source in your cache builder, rather than having to wait for the system clock. …
The primary intent of this method is to facilitate testing of caches with a fake or mock time source.

Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility - https://goo.gl/zRzSG8

Implementation-wise, this will be done using a hierarchical timer wheel (prototype). This allows add, remove, rescheduling, and expiring to be performed in O(1) time. Instead of using a O(lg n) priority queue, it uses a hierarchy of ring buffers, where each slot represents a time span (second, minute, hour). As the wheels rotate, the entries in the buckets are expired or rescheduled. This cascading effect amortizes the penalty and all operations are run during the cache’s maintenance operation.

2017(10-12月) 码农类 博士 全职@Uber - 网上海投 - Onsite |Other在职跳槽
Uber seattle site onsite..
第一轮: rateLimiter… 面试官讲故事太多了,刚开始被绕进去了,最后才知道实际上是rate Limter, MAP+Queue的实现…这轮目测要跪
第二轮: 小印哥们, 各种parenthesis 变种,LC基本括号相关题follow up了一遍
第三轮: 三哥, LC原题,deecopy Linkedlist with random pointer, 关键是follow up一堆多机器怎么实现copy…这个目测答得不好,地里有经验的可以说说.
第四轮,又是Rate limiter….这次没让面试官讲故事绕进去,但关键一堆follow up scalable , consistent hashing, 没啥把握
第五轮 : BAR RAISER
补充内容 (2017-10-13 00:13):
楼主已挂,distributed system经验不足..
http://www.1point3acres.com/bbs/thread-297178-1-1.html

2017(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Pass在职跳槽
第一轮:应用题,parse存在乱码的文件.根本什么算法也没有,没啥参考性
第二轮:Range query sum 2D mutable.上来BIT的方法解释了半天,面试官之前没听说过所以很难理解,最后提示让用O(n) prefixsum array的方法
第三轮:Path Sum I & II, 就是最简单的那个DP,剩了15分钟聊了下天
第四轮:面经题,robot 打扫房间
第五轮:1. design 一个数据结构,里面有key,value,expiration time, 实现get, put, clean（清空已经过时的key)
2. (facebook, 10), (fakebook, 20) -> 给你prefix 和suffix 求以prefix开头和suffix结尾的所有项目中,分数最高的,不用写代码 就是纯design
例如:(fa, ok) -> fakebook; (fac, ok) -> facebook
http://www.1point3acres.com/bbs/thread-297519-1-1.html

https://softwareengineering.stackexchange.com/questions/150811/what-is-the-algorithm-for-expiring-items-in-key-value-storage

It seems that many people believed for some reason that freeing expired entries can not be performed in O(1), or even that it requires Omega(N) operations. Using a heap, or other priority queue data structures can obviously give you O(log N), but the patch below aims at O(1). This is achieved by having one bucket for each second, and by putting each entry in a proper bucket by looking at the expiration time. Then at each second we just free elements from the next bucket. This is obviously O(1) amortized time, but it can happen that you have a lot of elements that expire at the very same moment, so the patch offers a fixed limit for number of operations that you are willing to perform per one request, to make the garbage collection run smoother.

• TreeMap removing all keys greater than a certain key

https://stackoverflow.com/questions/22976970/treemap-removing-all-keys-greater-than-a-certain-key
https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html#tailMap-K-

jshell> import java.util.*;
jshell> TreeMap<Integer, String> treemap = new TreeMap<>();
treemap ==> {}
jshell> treemap.put(2, "two"); treemap.put(1, "one"); treemap.put(3, "three");
$5 ==> null
jshell> treemap.put(6, "six"); treemap.put(5, "five");
$7 ==> null
jshell> treemap
treemap ==> {1=one, 2=two, 3=three, 5=five, 6=six}
jshell> treemap.tailMap(3)
$29 ==> {3=three, 5=five, 6=six}
jshell> treemap.headMap(3)
$30 ==> {1=one, 2=two}
jshell> treemap.tailMap(3, false)
$31 ==> {5=five, 6=six}
jshell> treemap.headMap(3)
$32 ==> {1=one, 2=two}
jshell> treemap.headMap(3, false)
$33 ==> {1=one, 2=two}
jshell> treemap.headMap(3, true)
$34 ==> {1=one, 2=two, 3=three}
jshell> treemap.tailMap(3).clear();
jshell> treemap
treemap ==> {1=one, 2=two}

The same treemap above:

jshell> treemap.subMap(2,5).clear()
jshell> treemap
treemap ==> {1=one, 5=five, 6=six}

so it is a half open interval removal.

https://stackoverflow.com/questions/14290751/time-complexity-of-treemap-operations-submap-headmap-tailmap
https://stackoverflow.com/questions/38868481/time-complexity-of-treemap-operations-get-and-submap

• C++ Map

http://en.cppreference.com/w/cpp/container/map/erase
http://en.cppreference.com/w/cpp/container/map/lower_bound
http://en.cppreference.com/w/cpp/container/map/upper_bound

• Thread Safe Set

1. ConcurrentHashMap backed ConcurrentHashSet

ConcurrentHashMap<String,String> chm=new ConcurrentHashMap<>();
Set<String> chs = chm.newKeySet();

2. SynchronizedSet

Set<String> ss=Collections.synchronizedSet(new HashSet<>());

67.11 Trending URLs

TopK Frequent Elements

Suitable for: Mid-Senior Level.
Time: 20-45 minutes
Format: Phone-Screen
Skills: System design, knowledge of algorithms, asking clarifying questions.

There is no code for this question, it is intended as a way to judge a candidate’s problem decomposition and design skills. With particular attention to the scalability of the proposed solution.

67.11.1 The Problem

Social networking sites allow users to share URLs with their network. E.g. If you like a news article on CNN, you can share that URL, say, “http://www.cnn.con/news-article” with your friends. Other people on the network would also be sharing this and/or other URLs. If an article is popular, many people may be sharing its URL. Design a system that will tell us which URLs are popular at any given time.

67.11.2 For the Interviewer

Once you have laid out the problem, stop talking and let the candidate drive the conversation. The problem is deliberately unspecified. Let them ask clarifying questions. Some possible questions:

1. “Over what duration do we calculate popularity? Is it over 1 hour? 1 day?” (Answer: Ask them about what they think are good choices for the duration.)
2. “What is the size of the cluster - is it a single server or are there multiple servers?” (Answer: multiple, a real world scenario.)
3. “Should this be a separate system or be plugged into an existing system?”. Answer: we want to plug this into an existing system, such that it has low overhead. (“Overhead in terms of what? throughput? latency?” Answer: “latency”.)
4. “How many requests per second does the existing system serve?” (Answer: something non-trivial, say, 1000 queries per second).
5. “How many unique URLs per second?” (This question usually suggests that the candidate “got” the problem.)
6. “Does the answer need to be exact or approximate?” (Answer: “Approximate” is fine since no one really “knows” the most popular URLs for sure!)
7. “How many URLs should the system respond with? Is it a query parameter? Or is it fixed/ limited?” (Answer: 1K; any reasonably large number should be fine.)

Once they have asked their questions, ask them to design the system for 3 different durations simultaneously - 5m, 1h and 1d, i.e. the system should be able to tell us the most popular URLs for the past 5m, 1h and 1d. The choice of these durations is such that each duration may have a design choice that works well for it, but not necessarily for the others. E.g. Hadoop works well for 1d, but is perhaps unreasonable for 5m.

67.11.3 Followup Questions

• One popular choice here is to aggregate share-counts into small time windows, like 1 minute. If they go that route, ask them for the algorithm to efficiently compute and update the 5m, 1h and 1d counts.

• Ask the candidate to draw an architecture/design diagram with REST interfaces and system internals to illustrate their design.

67.11.4 Solution

Here is a possible satisfactory answer.

Since knowledge of the URLs is distributed, that knowledge would need to be conveyed out and aggregated at some point.

1. Each machine in the cluster knows about the URLs it shared. It aggregates this data in memory, over say every 1 minute, as a hash map.
2. The hash map shouldn’t store the entire URL, just a hash, assuming the hash function is good. E.g. MD5. Each machine should therefore support an interface to reverse map the hash value to the URL.
3. It truncates this to the top 10K or something (large enough that truncation does not affect the top 1K URLs).
4. Since the system needs to be low overhead, a messaging system like Kafka works well to convey these numbers to an external aggregator. Kafka message body looks like [{url1, share-count1}, {url2, share-count2}, …].
5. An aggregation system subscribes to the above Kafka message and further aggregates the url -> share-count map. This gives it good visibility over a 1min time interval.
6. It maintains 1440 such time intervals, one for each minute of the day, in a circular buffer.
7. Every minute, it computes/updates the top 5m, 1h and 1d top URLs. There is a small algorithm question here for the candidate - how to update the 5m, 1h and 1d stats efficiently. (Answer to that: add the latest counts and remove the oldest counts. That way that part of the logic is O(1), not O(n).)
8. These URLs, in sorted order, can then be stored into an online, low-latency key-value data store like Memcache or Redis (bonus points if they mention Cassandra, since they perhaps did their homework on Apple technologies!).

67.11.5 Evaluation

Score this on a scale from 2-4:

67.11.5.1 2.0

• May try to aggregate URL share-counts in the critical path of sharing the URL. This is a no-no, since we want this system to be low overhead.
• May use wrong tools for the job - e.g. an oracle database for a lookup.

67.11.5.2 3.0

• A good candidate will answer questions to your satisfaction. However, all their questions may not be upfront or proactive.
• They use the right tool for the job - Kafka or suitable variant for messaging, key-value store for lookups, etc.
• Be able to solve the algorithmic question about computing the top 5m, 1h and 1d URLs every minute efficiently.

67.11.5.3 4.0

• A great candidate will ask clarifying questions that will crisply define the problem. These include system requirements like latency, throughput, environment, interactions with other systems, etc. Their questions are usually not reactive (e.g. they get stuck on something and then they ask a clarifying question.)

67.12 URL Shortener

Suitable for: Mid-Senior Level.
Time: 15-45 minutes
Format: Phone-Screen
Skills: System design, knowledge of algorithms, asking clarifying questions.

There is no code for this question, it is intended as a way to judge a candidate’s problem decomposition and design skills. With particular attention to the scalability of the proposed solution.

67.12.1 The Problem

First ask the candidate if they are familiar with URL shorteners.

If they say yes, ask them to describe what they do to confirm.

If not, describe the problem domain:

In essence, a web service that when given a URL like
"http://www.mysite.com/mypage.html", it will provide back another shortened URL
like, for example, "http://aa.pl/abcd". The domain is a predefined prefix and
the path is unique to the original URL. Now additionally, if the service is
provided the shortened URLs, it will return the original URL. Once they get
this, ask the candidate to go thru how they would design a system that does
this.

67.12.2 For the Interviewer

Once you have laid out the problem, stop talking and let the candidate drive the conversation.

In case they ask, some scenario answers:

• It should be a process that communicates via HTTP.
• Ignore all the redirect stuff that real shorteners do. Focus on the actual internal work involved.
• Assume some scale here - 10k shortens per sec. 100k expands per sec. Importantly, mention that a single process cannot handle this. We want a distributed solution.
• The system design should consider that nodes may fail.
• Two URLs should never map to the same shortened one and vice versa.
• URLs can stick around forever. There is no requirement to expire them - unless they prefer to do so.

What you want is for them to try and focus on the system design of the two basic functions - namely shorten and expand (or any similar names they come up with). Of the two, the shorten function is more complex and is more important to drill into. They should consider the shorten algorithm and how it persists data so expand can use it.

67.12.3 Followup Questions

Ask the candidate some of these questions to probe their solution and thinking:

• How do you guarantee that there are no collisions on your shorten function?
• How is load balancing accomplished among all the nodes?
• What kind of data store would you use as the backend database and why?

67.12.4 Solution

Here is a possible answer that satisfies the given constraints:

Start with the two functions, shorten and expand most of the focus will be on the shorten design:

67.12.4.1 Shorten

Partition all things. Decide on a number of partitions this system will have. This is your maximum scale factor (# of machines). 2048, 1024, 512, etc (N) can be reasonable numbers. Each partition contains a int range counter.

Then MAX_INT * N is your theoretical max number of shortened URLs supported.

On startup, a process is “assigned” partitions via some coordination system (Zookeeper). If there is only one process, it would get all N partitions. if the second one joins, it would be re-balanced to get N / 2, etc.

For each partition, the process would then recover the maximum count already used in that partition from a durable storage to jump to where it left off. Now it can receive traffic. This may be load-balanced in any convenient way. Any process can receive any request.

When a process gets a shorten request, it would then (via round-robin / hash / etc) choose a partition to use to serve that traffic. It then increments the count on that partition, puts the partition id + count together into some number: some bytes are the partition Id, some are the counter. Then it converts it into some base encoding that is reasonable like Base62.

It then stores the ID and URL in some database so it can be queried via this ID. It should be put in a way so that it is easy to query the max value already set. This can be easy in some DBs by using a different table per partition and finding the max ID. In a KV store, you’d need to store the max ID per partition somewhere in addition to the normal data (in a KV store, this additional write should still be low impact).

Once complete, send back the URL prefix + the generated URL ID.

67.12.4.2 Expand

Pull the URL ID from the URL, decode it back to a number. Use it to find the data.

67.12.5 Reference:

linkedin-2016-12.html#design-tinyurl

67.12.6 Evaluation

Score this on a scale from 1-4:

67.12.6.1 1.0

At the minimum the candidate should realize that there are two main things to consider - shortening URLs and expanding them. Their solution functionally works, but:

• Doesn’t really make sense
• Would have immediate scaling issues.
• URL shortening collisions may happen at a reasonable probability.
• They may run out of possible shortenings relatively quickly.
• Use an unfriendly output of the shortening - like a UUID. It should be short (4-10 characters max).

67.12.6.2 2.0

Candidates can come up with a solution that works but:

• Requires coordination on each shorten attempt or multiple reads/writes.
• Shortened URLs may collide at a very low probability.
• Chooses a specific datastore for the URLs that cannot scale linearly for this type of system.
• They cannot explain possible failure scenarios (app and/or datastores) and how the system would respond in a reasonable way.
• It is non-trivial to expand the cluster.

67.12.6.3 3.0

Candidates come up with a solution that: - Does not require coordination between nodes during shorten/expand. - Shortened URLs can never collide. - Shorten requires no reads. It is a single write. (depends on DB used. An additional write may be needed). - Expand is a single read.

67.12.6.4 4.0

Candidates have a 3.0 solution, but can also:

• Explain and show how the system can be available on node failures (database failures, node failures, etc), for example:
  • How do we guarantee that only one node owns a partition and receives traffic at a given time considering different network partitions / stuckness?
  • What do we do if the database is irresponsive during shorten? During expand?
• Explain how we can have the highest level of availability for the the expand stage? For the shorten stage?
• Explain and show how the system can be expanded easily (while running).
• Can elaborate on the specific database technology used and how they would use it in this particular problem.

67.12.7 734. Sentence Similarity

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, “great acting skills” and “fine drama talent” are similar, if the similar word pairs are pairs = [[“great”, “fine”], [“acting”,“drama”], [“skills”,“talent”]].

Note that the similarity relation is not transitive. For example, if “great” and “fine” are similar, and “fine” and “good” are similar, “great” and “good” are not necessarily similar.

However, similarity is symmetric. For example, “great” and “fine” being similar is the same as “fine” and “great” being similar.

Also, a word is always similar with itself. For example, the sentences words1 = [“great”], words2 = [“great”], pairs = are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = [“great”] can never be similar to words2 = [“doubleplus”,“good”].

Note: The length of words1 and words2 will not exceed 1000.
The length of pairs will not exceed 2000.
The length of each pairs[i] will be 2.
The length of each words[i] and pairs[i][j] will be in the range [1, 20].

https://leetcode.com/problems/sentence-similarity/description/

class Solution {
public:
    bool areSentencesSimilar(vector<string>& w1, vector<string>& w2, vector<pair<string, string>> ps) {
        if(w1.size()!=w2.size()) return false;
        map<string,set<string>> m;
        for(auto& pr: ps)
            m[pr.first].insert(pr.second), m[pr.second].insert(pr.first);
        for(int i=0;i<w1.size();++i){
            if(w1[i]==w2[i]) continue;
            if(m[w1[i]].count(w2[i])==0) return false;
        }
        return true;
    }
};

67.12.8 737. Sentence Similarity II

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, words1 = [“great”, “acting”, “skills”] and words2 = [“fine”, “drama”, “talent”] are similar, if the similar word pairs are pairs = [[“great”, “good”], [“fine”, “good”], [“acting”,“drama”], [“skills”,“talent”]].

Note that the similarity relation is transitive. For example, if “great” and “good” are similar, and “fine” and “good” are similar, then “great” and “fine” are similar.

Similarity is also symmetric. For example, “great” and “fine” being similar is the same as “fine” and “great” being similar.

Also, a word is always similar with itself. For example, the sentences words1 = [“great”], words2 = [“great”], pairs = are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = [“great”] can never be similar to words2 = [“doubleplus”,“good”].

https://leetcode.com/problems/sentence-similarity-ii/description/