Rambling Coding Interview (漫步编码面试)

After completed dozens of phone/onsite interviews with the FAANG and other big tech companies as an interviewee or interviewer over time, I believe there should be a way to extract and put together all these essential fundamentals and algorithms, be good enough for the coding interviews, so that you can brush up yourself just in 7-14 days with an intense and focused sprint. Now, let me walk you through this preparation and practice, help you suit up for the next job searching!

This is the first Java version guide, please download the code from github. You are more than welcome to contribute another version of C++, Python or other languages. Please feel free to create pull requests or leave your comments below for any feedback. Let’s refine this little guideline together to benefit all upcoming super star engineers! :star2:

Mindset & Strategy

First, I admire you! You are trying to get out of your comfort zone, motivate yourself against mediocrity and strive for continuous self-improvement. You have the will and determination to seek the harder path in life. Even though it might not end up with the most ideal job you want, but the learning process will make you a better programmer for sure.

I know job searching and coding interviews are challenging, struggling and stressful. But with an optimistic mindset been set and a pragmatic strategy to follow, we could change our attitude and perceptions, help us to get through it and succeed with a higher chance.

  • Don’t take too long. If you plan it for a year, or practice a bit of time every day through a few months, no good, you will be mostly in a standby mode, not fully activated your brain and won’t totally cool it down either, which makes you not able to relax and enjoy life for a long while, and even the whole family feels your tress. Plus, you will forget or get blur about what you already learned a while ago. Therefore, how about we try this way?! Make yourself a 1-2 weeks of concentration window, no work, no vacation, no entertainment, just practice your coding skill with this guide day in and day out. Then start scheduling interviews as a life routine, say 2 interviews each week, most interviews are not wasting your time, but forcing you to keep sharp and continuously improve yourself as you can always learn something new.

  • Do interviews to market yourself. Having a business mindset, you are not looking for a job, but a new client. It’s better to think of this company as a customer for your business of developing software. You are marketing and selling your service with your demo and products now. Viewing the relationship this way moves you from a position of powerlessness and dependency to one of autonomy and self-direction. You are taking advantage of these interviews to get valuable feedbacks, to feel the market trends & requirements, to know the gaps and your weak points, to keep fine-tuning your products (intro, resume, skillset, proficiency, and perfection). You are getting better and better to reach a peak condition. That’s why always plan your favorite company for the last, plus you might have a front offer to negotiate with them.

  • Interviews are somewhat unpredictable. You can’t know for sure what questions you’re going to be asked and might not be able to apply what learned recently at all. Don’t worry too much, ask for a minute to think it over, try to align it with what your learned here and grasp the essential and core concepts/algorithms that they are trying to probe/test. I always regret after the interview. “I could do it better!” Don’t get distracted and dwelling with that feeling, move forward and prepare for the next one. What it is done is done. You could still save yourself in the next one. In another word, finding a job/client is also a luck thing, you need to try enough times to accumulate your luck. the more interviews you conducted, the more chances you will be asked the right question by the right interviewer, and finally be blessed by the Goddess of Luck!

  • Don’t go too deep and complicated. Most of interview questions are on medium level, and many more new questions were created every day. It’s NOT a pragmatic approach, trying to familiarize yourself with most of the questions on LeetCode, HackerRank etc. You will find that most of your time and brain power were distracted, confused, or wasted on these tough or exotic questions. And even the interviewer will likely ask you to focus on a simple and decent solution first, don’t go too advanced/sophisticated. That’s why, I believe, these well-crafted abstract/typical/fundamental data structures and algorithms are still the keys, very important! Keep practicing them and build up your subconsciousness, so that you can quickly sense or realize that this brand-new question can be resolved by a similar solution with a little twist. Be alert when you think the question is too easy! Please ask more questions to double check with your initial ideas/thoughts/solutions.

  • Be vigilant during coding interviews. Mostly, it’s just a standard/polite procedure to introduce each other. Don’t talk too much about your background or working experience, just a few highlights and jump to the coding part, save more time for you to understand the question, think it over and code it out. Treat the interviewer well and be humble and polite, follow their hints/tips and show your expertise. Remember, you are a businessman now, how would you treat a potential client? If you want to succeed, you must learn how to swallow your pride and get out there. There could be, at the very last minute, you figured out what you have been struggling with, please try to express your new idea or solution as fast as possible before the time runs out. It’s fine to exceed the time a bit and skip the part “What questions do do want to ask?”, which they are already bored to repeat themselves. -:)

  • “Unfortunately…” That’s the scariest word, you don’t want to see in your mailbox or heard from a recruiter on the phone, during the job searching period. You might get rejected by a favorite company and feel heartbroken of thinking all the adventures you could have, all the things you could achieve and pursue, with this “only one” you want to be with… Please stop the emotional attachment, it’s not the end of the world. Again, treat them like a client, avoid too much into on a particular company. I’d have to say that if you take nothing else from this guide, take the following advice: get used to the rejection, learn to embrace failure, to expect it, to accept it, and to be ready to face it head-on. Be a Stoic, detach yourself from outcomes.

  • Practice is necessary. Make sure you practice the following snippets or algorithms a few times until you can write it out swiftly without peeking. Also reiterate to yourself what are the ideas, concepts, fundamentals, complexity, and score points behind them. Don’t just think in your head, you need to type it, run it, revise it, even debug it, even let your fingers to remember these list of syntax statements or coding patterns. With that been said, it’s time to let the hard working commence!

Complexity (Big O)

Big O time/space complexity is the language and metric we use to describe the efficiency of algorithms, it’s mostly a rough/amortized assessment of rate of increase, as summarized below. The time (runtime) complexity could have multiple variables, best/worst/expected case in an algorithm, e.g. \(O(n\log n+nL^2))\). The space complexity is about the amount of memory or space required by an algorithm. We will cover them with more examples/details through the guide.

Time Complexity

name complexity description example
constant \(1\) statement add two numbers
logarithmic \(\log n\) divide in half binary search
linear \(n\) loop find the max
linearithmic \(n\log n\) divide and conquer quick/merge sort
quadratic \(n^2\) double nested loop check all pairs
cubic \(n^3\) triple nested loop check all triples
exponential \(2^n\) exhaustive search check all subsets
factorial \(n!\) permutation and combination all subsets

Space Complexity

name complexity description example
constant \(1\) statement constant variables
linear \(n\) collections up to n size
linearithmic \(\log n\) divide and conquer recursive call
linear \(n\) recursion stack (depth) recursive call
depends? \(n?\) based on solution space-time tradeoff

Compare Runtimes

  // Calculate 2^n (n >= 0) in a recursive way
  public int f1(int n) {
    if (n <= 0) {
      return 1;
    }
    return f1(n - 1) + f1(n - 1);
  }

  // Calculate 2^n (n >= 0) in an iterative way
  public int f2(int n) {
    int r = 1;
    for (int i = 0; i < n; i++) {
      r += r;
    }
    return r;
  }
  • Image f1(n) calls as a stack tree, which has depth N and each node has two children.
  • f1(n) gives us time complexity: \(O(2^n)\) and space complexity: \(O(n)\).
  • f2(n) gives us time complexity: \(O(n)\) and space complexity: \((O(1))\).
  • f2(n) is much better than f1(n) in term of the Big O runtimes!

Bit Manipulation

Bit manipulation is used in a variety of problems. Sometimes, the question explicitly calls for bit manipulation, Other times, it’s simply a useful technique to optimize your code. You should be comfortable doing bit manipulation by hand, as well as with code.

Operators & Samples

Operator    Name         Example     Result  Description
a & b       and          3 & 5       1       1 if both bits are 1.
a | b       or           3 | 5       7       1 if either bit is 1.
a ^ b       xor          3 ^ 5       6       1 if both bits are different.
~a          not          ~3          -4      Inverts the bits.
n << p      left shift   3 << 2      12      Shifts the bits of n left p positions. Zero bits are shifted into the low-order positions.
n >> p      right shift  5 >> 2      1       Shifts the bits of n right p positions. If n is a 2's complement signed number, the sign bit is shifted into the high-order positions.
n >>> p     right shift  -4 >>> 28   15      Shifts the bits of n right p positions. Zeros are shifted into the high-order positions.
/* Optional, NOT have to understand all of them. */
0110 + 0110 = 1100
0100 * 0011 = 4 * 0011 = 0011 << 2 = 1100
1101 ^ (~1101) = 1101 ^ 0010 = 1111 // a ^ (~a) = all ones
16 & (16 - 1) = 0, 11 & (11 - 1) = 10, 20 & (20 - 1) = 16 // x & (x - 1) clear the lowest set bit in x.
16 & ~(16 - 1) = 16, 11 & ~(11 - 1) = 1, 20 & ~(20 - 1) = 4 // x & ~(x - 1) extracts the lowest set bit of x.
16 & -16 = 16, 11 & -11 = 1, 20 & -20 = 4 // or x & -x extracts the lowest set bit of x.
-75 (10110101) >> 1 = -38 (11011010) // arithmetic shift, fill in the new bits with the sign bit.
-75 (10110101) >>> 1 = 90 (01011010) // logical shift, fill in 0 in the most significant bit.

Bit Functions

public class BitFunctions {
  public boolean getBit(int num, int i) {
    return (num & (1 << i)) != 0;
  }

  public int setBit(int num, int i) {
    return num | (1 << i);
  }

  public int clearBit(int num, int i) {
    return num & ~(1 << i);
    // clear all bits from the most significant bit through i (inclusive)
    // return num & ((1 << i) - 1);
    // clear all bits from i through 0 (inclusive)
    // return num & ((-1 << i + 1)); // NOTE: a sequence of 1 is -1
  }

  public int updateBit(int num, int i, boolean bitIs1) {
    int value = bitIs1 ? 1 : 0;
    int mask = ~(1 << i); // to clear bit
    return (num & mask) | (value << i);
  }

  public long swapBits(long x, int i, int j) {
    // extract the i-th and j-th bits, and see if they differ.
    if (((x >>> i) & 1) != ((x >>> j) & 1)) {
      long mask = (1L << i) | (1L << j); // combine
      x ^= mask; // flip their values with XOR
    }
    return x;
  }

  public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
      result += n & 1;
      n >>>= 1; // must do unsigned shift
      if (i < 31) // for last digit, don't shift!
        result <<= 1;
    }
    return result;
  }

  public int countBits(long x) {
    int count = 0;
    while (x != 0) {
      x &= (x - 1); // clear the lowest set bit
      count++;
    }
    return count;
  }
}

Design BitVector

Bit Vector/Set is a compact way to store a list of boolean values. JDK has a built in BitSet class which implements a vector of bits that grows as needed. Here is a simple but good example to demonstrate the bit vector with common bit tasks: Sizing, Shifting, Getting and Setting.

An array of int can be used to deal with array of bits. Assuming size of int to be 4 bytes, when we talk about an int, we are dealing with 32 bits. Say we have int A[10], means we are working on 10 * 4 * 8 = 321 bits.

public class BitVector {
  private static final int INT_SIZE = 32; // 4 bytes = 4 * 8 bits
  private int length;
  private int[] vector;

  public BitVector(int length) {
    this.length = length;
    if (length % INT_SIZE == 0)
      vector = new int[length / INT_SIZE];
    else
      vector = new int[length / INT_SIZE + 1];
  }

  public int length() {
    return length;
  }

  public boolean get(int i) {
    if (i < 0 || i >= length)
      throw new ArrayIndexOutOfBoundsException(i);
    return (vector[i / INT_SIZE] & (1 << (i % INT_SIZE))) != 0;
  }

  public void set(int i, boolean flag) {
    if (i < 0 || i >= length)
      throw new ArrayIndexOutOfBoundsException(i);
    if (flag)
      vector[i / INT_SIZE] |= 1 << (i % INT_SIZE); // mask like: 1000
    else
      vector[i / INT_SIZE] &= ~(1 << (i % INT_SIZE)); // mask like: 0111
  }

  public void print() {
    for (int v : vector) {
      for (int i = 0; i < INT_SIZE; i++) {
        System.out.print((v >> i & 1) - 0);
      }
    }
    System.out.println();
  }
}

Combine Multiple IDs

In the case, to design a MySQL sharding approach. You might use a 64 bit ID which contains 16 bit shard ID, 10 bits type ID, and 36 bit local ID.

ID = (shard ID << 46) | (type ID << 36) | (local ID<<0)
Given a ID 241294492511762325
Shard ID = (241294492511762325 >> 46) & 0xFFFF = 3429
Type ID  = (241294492511762325 >> 36) & 0x3FF = 1
Local ID = (241294492511762325 >>  0) & 0xFFFFFFFFF = 7075733
public class CompositeId {
  /**
   * 16 + 10 + 36 = 62 bits in total!
   * 
   * @param shardId contains 16 bits
   * @param typeId  contains 10 bits
   * @param localId contains 36 bits
   * @return 64 bits ID
   */
  public long encodeId(long shardId, long typeId, long localId) {
    return shardId << (10 + 36) | typeId << 36 | localId;
  }

  /**
   * Use mask bits to clear, then set new value
   * 
   * @param id     encoded id
   * @param typeId new type id
   * @return updated id
   */
  public long updateTypeId(long id, long typeId) {
    long mask = (1 << 10) - 1; // All ones
    id &= ~(mask << 36); // Clear bits
    id |= typeId << 36; // Set bits
    return id;
  }

  /**
   * @param id
   * @return shardId, typeId, localId
   */
  public long[] decodeId(long id) {
    long[] result = new long[3];
    result[0] = (id >> 46) & 0xFFFF; // 1111,1111,1111,1111
    result[1] = (id >> 36) & 0x3FF; // 11,1111,1111
    result[2] = id & ((1 << 36) - 1); // 0xFFFFFFFFF exceeds int!
    return result;
  }

  public String printBits(long id) {
    StringBuilder b = new StringBuilder();
    for (int i = Long.SIZE - 1; i >= 0; i--) {
      b.append((id & (1L << i)) != 0 ? '1' : '0');
    }
    return b.toString();
  }
}

Arrays & Strings

The array questions and string questions are often interchangeable. Let’s just practice a couple of questions to get deeper understanding of them.

Shuffle An Array

  public int[] shuffleAnArray(int[] nums) {
    if (nums == null)
      return null;
    Random random = new Random();
    int[] result = nums.clone();
    for (int j = 0; j < result.length; j++) {
      int i = random.nextInt(j + 1);
      if (i != j) {
        int temp = result[i];
        result[i] = result[j];
        result[j] = temp;
      }
    }
    return result;
  }

Reverse Words

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space. For example, Given s = “the sky is blue”, return “blue is sky the”.

  public void reverseWords(char[] str) {
    reverse(str, 0, str.length - 1);
    int start = 0, end = 0;
    while (end < str.length) {
      if (str[end] == ' ') {
        reverse(str, start, end - 1);
        start = end + 1;
      }
      end++;
    }
    reverse(str, start, end - 1);
  }

  private void reverse(char[] str, int start, int end) {
    while (start < end) {
      char tmp = str[start];
      str[start] = str[end];
      str[end] = tmp;
      start++;
      end--;
    }
  }

Find Idle Machines

There are 100 machines (1..100), given a list of active machines, find the intervals of idle machines.

Example:

Input: [1, 5, 7, 8, 15, 66, 67, 90]
Output: 2, 3, 4, 6, 9-14, 16-65, 68-89, 91-100
  // Find interval ranges and print out
  public String findIdleMachines(int[] machines) {
    int maxNum = 100;
    StringBuilder sb = new StringBuilder();

    int start = 1; // starts with 1
    for (int i = 0; i < machines.length; i++) {
      int end = machines[i] - 1;
      printIdleRange(start, end, sb);
      start = machines[i] + 1;
    }

    printIdleRange(start, maxNum, sb);

    return sb.toString();
  }

  private void printIdleRange(int start, int end, StringBuilder sb) {
    int idles = end - start + 1;
    if (idles > 3) {
      if (sb.length() > 0)
        sb.append(", ");
      sb.append(start).append("-").append(end);
    } else if (idles > 0) {
      for (int j = start; j <= end; j++) {
        if (sb.length() > 0)
          sb.append(", ");
        sb.append(j);
      }
    }
  }

Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

Example:

Input: nums = [1,2,3], k = 3
Output: 2
  // Use map to count different's frequency
  public int subarraySumEqualsK(int[] nums, int k) {
    int count = 0, sum = 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1); // init a start point!
    for (int i = 0; i < nums.length; i++) {
      sum += nums[i];
      int diff = sum - k; // here diff could also be a remainder = sum % k
      if (map.containsKey(diff)) {
        count += map.get(diff);
      }
      map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
  }

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Solution: Use DP, dp[i] represents the length of the longest increasing subsequence that ends with the element at index i.

  public int longestIncreasingSubsequence(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    for (int i = 1; i < nums.length; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
    }
    int longest = 0;
    for (int c : dp) {
      longest = Math.max(longest, c);
    }
    return longest;
  }

List & Linked List

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

In terms of Linked List, Insert and delete are local operations and have O(1) time complexity. Search requires traversing the entire list at worst case, the time complexity is O(n).

Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

/**
 * The loop runs n * k times. In every iteration of loop, we call heapify which takes O(Log(k))
 * time. Therefore, the time complexity is O(nkLog(k)).
 */
public ListNode mergeKSortedLists(ListNode[] lists) {
  if (lists == null || lists.length == 0)
    return null;

  Queue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));
  for (ListNode node : lists) {
    if (node != null)
      queue.offer(node);
  }

  ListNode dummy = new ListNode(0);
  ListNode tail = dummy;

  while (!queue.isEmpty()) {
    ListNode node = queue.poll();

    // remove duplicates if required
    while (node.next != null && node.val == node.next.val) {
      node = node.next;
    }

    // check duplicates if required
    if (tail.val != node.val) {
      tail.next = node;
      tail = node;
    }

    if (node.next != null)
      queue.offer(node.next);
  }

  return dummy.next;
}
// simply merge two sorted list
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null)
        return l2;
    if (l2 == null)
        return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l2.next, l1);
        return l2;
    }
}

Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7

Reverse the 2 lists or use 2 stacks.

public ListNode addTwoNumbersII(ListNode l1, ListNode l2) {
  Stack<Integer> stack1 = new Stack<>();
  Stack<Integer> stack2 = new Stack<>();

  while (l1 != null) {
    stack1.push(l1.val);
    l1 = l1.next;
  }

  while (l2 != null) {
    stack2.push(l2.val);
    l2 = l2.next;
  }

  int sum = 0;
  ListNode node = new ListNode(0);
  while (!stack1.isEmpty() || !stack2.isEmpty()) {
    if (!stack1.isEmpty())
      sum += stack1.pop();
    if (!stack2.isEmpty())
      sum += stack2.pop();
    node.val = sum % 10;
    ListNode head = new ListNode(sum /= 10);
    head.next = node;
    node = head;
  }

  return node.val == 0 ? node.next : node;
}

Sorted Circular Linked List

Given a Circular Linked List node, which is sorted in ascending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.

Example:

Input: head = [3,4,1], insertVal = 2
Output: [3,4,1,2]
  public class Node {
    public int val;
    public Node next;

    public Node(int val) {
      this.val = val;
      this.next = this; // circular to itself
    }

    // Solution inside the node, note the do...while
    public Node insert(int newVal) {
      Node prev = this, curr = this.next;

      do {
        if (prev.val <= newVal && newVal <= curr.val) {
          return insert(prev, curr, newVal);
        } else if (prev.val > curr.val && (newVal >= prev.val || newVal <= curr.val)) {
          return insert(prev, curr, newVal);
        }
        prev = curr;
        curr = curr.next;
      } while (prev != this);

      return insert(prev, curr, newVal);
    }

    private Node insert(Node prev, Node curr, int newVal) {
      prev.next = new Node(newVal);
      prev.next.next = curr;
      return prev.next; // return the new node
    }
  }

  // Solution outside the node, note the do...while
  public Node insert(Node head, int newVal) {
    if (head == null) {
      Node newNode = new Node(newVal);
      newNode.next = newNode;
      return newNode;
    }

    Node prev = head;
    Node curr = head.next;
    do {
      if (prev.val <= newVal && newVal <= curr.val) {
        insert(prev, curr, newVal);
        return head;
      } else if (prev.val > curr.val && (newVal >= prev.val || newVal <= curr.val)) {
        insert(prev, curr, newVal);
        return head;
      }
      prev = curr;
      curr = curr.next;
    } while (prev != head);

    insert(prev, curr, newVal);
    return head;
  }

  private Node insert(Node prev, Node curr, int insertVal) {
    prev.next = new Node(insertVal);
    prev.next.next = curr;
    return prev.next;
  }

  public void printList(Node node) {
    Node head = node;
    do {
      System.out.print(node.val + "\t");
      node = node.next;
    } while (head != node);
  }

When we think of searching algorithms, we generally think of binary search which is very useful and important, can be applied to variants of questions, especially when the array, list, tree or items are already sorted or mean to be sorted. Like the “Guess Who” game is actually a binary sort and search algorithm. Sometimes, we need to think beyond binary search, say use a hash table.

Split Array Largest Sum

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

Example:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.
  // Binary search to squeeze out the largest sum
  public int splitArrayLargestSum(int[] nums, int m) {
    int max = 0;
    long sum = 0;
    for (int num : nums) {
      max = Math.max(max, num);
      sum += num;
    }

    if (m == 1)
      return (int) sum;

    long lo = max, hi = sum;
    while (lo <= hi) {
      long mid = lo + (hi - lo) / 2;
      if (isValidToGroup(mid, nums, m))
        hi = mid - 1;
      else
        lo = mid + 1;
    }

    return (int) lo;
  }

  private boolean isValidToGroup(long target, int[] nums, int m) {
    int count = 1;
    int total = 0;
    for (int num : nums) {
      total += num;
      if (total > target) {
        total = num;
        count++;
        if (count > m)
          return false;
      }
    }
    return true;
  }

Time Based Key-Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

  • TimeMap() Initializes the object of the data structure.
  • void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
  • String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.

Example:

TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"
  /**
   * Use binary search to simulate TreeMap
   */
  class TimestampMap {
    class Data {
      String value;
      int timestamp;

      Data(String value, int timestamp) {
        this.value = value;
        this.timestamp = timestamp;
      }
    }

    private Map<String, List<Data>> map;

    public TimestampMap() {
      map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
      map.computeIfAbsent(key, k -> new ArrayList<>()).add(new Data(value, timestamp));
    }

    public String get(String key, int timestamp) {
      if (!map.containsKey(key))
        return "";
      return binarySearch(map.get(key), timestamp);
    }

    // Find floor entry!
    private String binarySearch(List<Data> list, int timestamp) {
      int low = 0, high = list.size() - 1;
      while (low < high) {
        int mid = (low + high) >> 1;
        Data data = list.get(mid);
        if (data.timestamp == timestamp)
          return data.value;
        if (data.timestamp < timestamp) {
          if (list.get(mid + 1).timestamp > timestamp)
            return data.value;
          low = mid + 1;
        } else
          high = mid - 1;
      }
      return list.get(low).timestamp <= timestamp ? list.get(low).value : "";
    }
  }

Binary Tree

  • Recursive algorithm are well-suited to problems on trees. Remember to include space implicitly allocated on the function call stack when doing space complexity analysis.
  • Let T be a binary tree of n nodes, with height h. Implemented recursively, these traversals have O(n) time complexity and O(h) additional space complexity. (The space complexity is dictated by the max depth of function call stack.) If each node has a parent field, the traversals can done with O(1) additional space complexity.
  • Binary Tree Traversals:
    • In-Order Traversal (left -> current -> right);
    • Pre-Order Traversal (current -> left -> right);
    • Post-Order Traversal (left -> right -> current);

Find Leaves of Binary Tree

Given a binary tree, collect a tree’s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]

          1
         / \
        2   3
       / \     
      4   5    
Output: [[4,5,3],[2],[1]]
public List<List<Integer>> findLeaves(TreeNode root) {
  List<List<Integer>> res = new ArrayList<>();
  height(root, res);
  return res;
}

private int height(TreeNode node, List<List<Integer>> res) {
  if (null == node)
    return -1;
  int level = 1 + Math.max(height(node.left, res), height(node.right, res));
  if (res.size() < level + 1)
    res.add(new ArrayList<>());
  res.get(level).add(node.val);
  return level;
}

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

public class BSTIterator {
  final Deque<TreeNode> path;

  public BSTIterator(TreeNode root) {
    path = new ArrayDeque<>();
    buildPathToLeftmostChild(root);
  }

  public boolean hasNext() {
    return !path.isEmpty();
  }

  public int next() {
    TreeNode node = path.pop();
    buildPathToLeftmostChild(node.right);
    return node.val;
  }

  private void buildPathToLeftmostChild(TreeNode node) {
    TreeNode cur = node;
    while (cur != null) {
      path.push(cur);
      cur = cur.left;
    }
  }
}

Find K Closest Values

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

We can perform a in-order traversal. Another variant is to find K largest values, we need perform an reverse in-order traversal.

  /**
   * In-order traversal with the help of linked list.
   * 
   * Time complexity: O(N)
   */
  public List<Integer> closestKValues(TreeNode root, double target, int k) {
    LinkedList<Integer> list = new LinkedList<Integer>();
    inorder(list, root, target, k);
    return list;
  }

  private boolean inorder(LinkedList<Integer> list, TreeNode node, double target, int k) {
    if (node == null)
      return false;

    if (inorder(list, node.left, target, k))
      return true;

    if (list.size() == k) {
      if (Math.abs(list.getFirst() - target) < Math.abs(node.val - target))
        return true;
      else
        list.removeFirst();
    }

    list.addLast(node.val);
    return inorder(list, node.right, target, k);
  }

  /**
   * The idea is to convert BST into an array, sort it by the distance to the target, and return the k
   * closest elements.
   * 
   * Time complexity: O(NlogN). O(N) to build inorder traversal and then O(NlogN) to sort it.
   */
  public List<Integer> closestKValues2(TreeNode root, double target, int k) {
    List<Integer> nums = new ArrayList<>();
    inorder(root, nums);

    java.util.Collections.sort(nums, new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return Math.abs(o1 - target) < Math.abs(o2 - target) ? -1 : 1;
      }
    });
    return nums.subList(0, k);
  }

  private void inorder(TreeNode node, List<Integer> nums) {
    if (node == null)
      return;
    inorder(node.left, nums);
    nums.add(node.val);
    inorder(node.right, nums);
  }

  /**
   * We could use the heap of capacity k, sorted by the distance to the target.
   * 
   * Time complexity: O(Nlogk).
   */
  public List<Integer> closestKValues3(TreeNode root, double target, int k) {
    List<Integer> nums = new ArrayList<>();

    Queue<Integer> heap = new PriorityQueue<>((o1, o2) -> Math.abs(o1 - target) > Math.abs(o2 - target) ? -1 : 1);
    inorder(root, nums, heap, k);
    return new ArrayList<>(heap);
  }

  private void inorder(TreeNode r, List<Integer> nums, Queue<Integer> heap, int k) {
    if (r == null)
      return;

    inorder(r.left, nums, heap, k);
    heap.add(r.val);
    if (heap.size() > k)
      heap.remove();
    inorder(r.right, nums, heap, k);
  }

  /**
   * The idea is to compare the predecessors and successors of the closest node to the target, we can
   * use two stacks to track the predecessors and successors, then like what we do in merge sort, we
   * compare and pick the closest one to the target and put it to the result list.
   * 
   * Time complexity: O(log(n) + k)
   */
  public List<Integer> closestKValues4(TreeNode root, double target, int k) {
    List<Integer> ans = new ArrayList<>();

    Stack<Integer> s1 = new Stack<>(); // predecessors
    Stack<Integer> s2 = new Stack<>(); // successors

    inorder(root, target, false, s1);
    inorder(root, target, true, s2);

    while (k-- > 0) {
      if (s1.isEmpty())
        ans.add(s2.pop());
      else if (s2.isEmpty())
        ans.add(s1.pop());
      else if (Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target))
        ans.add(s1.pop());
      else
        ans.add(s2.pop());
    }

    return ans;
  }

  private void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack) {
    if (root == null)
      return;

    inorder(reverse ? root.right : root.left, target, reverse, stack);

    if ((reverse && root.val <= target) || (!reverse && root.val > target))
      return; // Early terminate

    stack.push(root.val);

    inorder(reverse ? root.left : root.right, target, reverse, stack);
  }
  • The two most common ways to search a graph are depth-first search (DFS) and breadth-first search (BFS). DFS is often preferred if we want to visit every node in the graph. BFS is generally better if we want to find the shortest path (or just any path).
  • Bidirectional search is used to find the shortest path between a source and destination node. It operates by essentially running two simultaneous BFS, one from each node. When their searches collide, we have found a path. The complexity reduces from O(k^d) to O(k^(d/2)).
  • A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices.
  • A directed acyclic graph (or DAG) is a digraph with no directed cycles.
  • A minimum spanning tree (MST) of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree. Prim’s or Kruskal’s algorithm computes the MST of any connected edge-weighted graph.

Kill Process

Given n processes, each process has a unique PID (process id) and its PPID (parent process id).

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

Example 1:
Input:
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation:
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

HashMap + Breadth First Search or Depth First Search, Both O(n) complexity.

  public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
    List<Integer> list = new ArrayList<>();
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < ppid.size(); i++) {
      if (ppid.get(i) > 0) {
        graph.putIfAbsent(ppid.get(i), new ArrayList<>());
        graph.get(ppid.get(i)).add(pid.get(i));
      }
    }
    // killProcessDfs(graph, kill, list);
    killProcessBfs(graph, kill, list);
    return list;
  }

  private void killProcessDfs(Map<Integer, List<Integer>> graph, int kill, List<Integer> list) {
    list.add(kill);
    if (graph.containsKey(kill)) {
      for (int next : graph.get(kill)) {
        killProcessDfs(graph, next, list);
      }
    }
  }

  private void killProcessBfs(Map<Integer, List<Integer>> graph, int kill, List<Integer> list) {
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(kill);
    while (!queue.isEmpty()) {
      int id = queue.poll();
      list.add(id);
      if (graph.containsKey(id)) {
        for (int next : graph.get(kill)) {
          queue.offer(next);
        }
      }
    }
  }

Deadlock Detection

One deadlock detection algorithm makes use of a “wait-for” graph: Processes are represented as nodes, and an edge from process P to Q implies P is waiting for Q to release its lock on the resource. A cycle in this graph implies the possibility of a deadlock.

Write a program that takes as input a directed graph and checks if the graph contains a cycle.

We can check for the existence of a cycle in graph by running DFS with maintaining a set of status. As soon as we discover an edge from a visiting vertex to a visiting vertex, a cycle exists in graph and we can stop.

The time complexity of DFS is O(V+E): we iterate over all vertices, and spend a constant amount of time per edge. The space complexity is O(V), which is the maximum stack depth.

public static boolean isDeadlocked(List<Vertex> graph) {
  for (Vertex vertex : graph) {
    if (vertex.state == State.UNVISITED && hasCycle(vertex)) {
      return true;
    }
  }
  return false;
}

private static boolean hasCycle(Vertex current) {
  if (current.state == State.VISITING) {
    return true;
  }

  current.state = State.VISITING;
  for (Vertex next : current.edges) {
    if (next.state != State.VISITED && hasCycle(next)) {
      // edgeTo[next] = current; // if we need to track path
      return true;
    }
  }  
  current.state = State.VISITED;

  return false;
}

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal, We say our starting node is eventually safe.

// This is a classic "white-gray-black" DFS algorithm
public List<Integer> eventualSafeNodes(int[][] graph) {
  int N = graph.length;
  int[] color = new int[N];
  List<Integer> ans = new ArrayList<>();

  for (int i = 0; i < N; i++) {
    if (hasNoCycle(i, color, graph))
      ans.add(i);
  }

  return ans;
}

// colors: WHITE 0, GRAY 1, BLACK 2;
private boolean hasNoCycle(int node, int[] color, int[][] graph) {
  if (color[node] > 0)
    return color[node] == 2;

  color[node] = 1;
  for (int nei : graph[node]) {
    if (color[nei] == 2)
      continue;
    if (color[nei] == 1 || !hasNoCycle(nei, color, graph))
      return false;
  }

  color[node] = 2;
  return true;
}

Cheapest Flights with K Stops

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

  public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[][] graph = new int[n][n];
    for (int[] flight : flights) {
      graph[flight[0]][flight[1]] = flight[2];
    }

    // minimum costs array
    int[] costs = new int[n];
    // shortest steps array
    int[] stops = new int[n];
    Arrays.fill(costs, Integer.MAX_VALUE);
    Arrays.fill(stops, Integer.MAX_VALUE);
    costs[src] = 0;
    stops[src] = 0;

    // priority queue would contain (node, cost, stop)
    Queue<int[]> minHeap = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
    minHeap.offer(new int[] { src, 0, 0 });

    while (!minHeap.isEmpty()) {
      int[] top = minHeap.poll();
      int city = top[0];
      int cost = top[1];
      int stop = top[2];

      if (city == dst) {
        return cost;
      }

      // if there are no more steps left, continue
      if (stop == k + 1) {
        continue;
      }

      // relax all neighboring edges if possible
      for (int neighbor = 0; neighbor < n; neighbor++) {
        if (graph[city][neighbor] > 0) {
          int nextCost = cost + graph[city][neighbor];
          if (nextCost < costs[neighbor]) { // better cost?
            costs[neighbor] = nextCost;
            minHeap.offer(new int[] { neighbor, nextCost, stop + 1 });
            stops[neighbor] = stop; // does not have to be the shortest path
          } else if (stop < stops[neighbor]) { // better steps?
            minHeap.offer(new int[] { neighbor, nextCost, stop + 1 });
            stops[neighbor] = stop;
          }
        }
      }
    }

    return costs[dst] == Integer.MAX_VALUE ? -1 : costs[dst];
  }

Stack & Queue

Decode Nested String

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
public String decodeString(String s) {
  Deque<Integer> count = new LinkedList<>();
  Deque<String> result = new LinkedList<>();
  int i = 0;
  result.push("");
  while (i < s.length()) {
    char c = s.charAt(i);
    if (Character.isDigit(c)) {
      int start = i;
      while (Character.isDigit(s.charAt(i + 1)))
        i++;
      count.push(Integer.valueOf(s.substring(start, i + 1)));
    } else if (c == '[') {
      result.push("");
    } else if (c == ']') {
      String sub = result.pop();
      StringBuilder sb = new StringBuilder();
      int times = count.pop();
      for (int j = 0; j < times; j += 1) {
        sb.append(sub);
      }
      result.push(result.pop() + sb.toString());
    } else {
      result.push(result.pop() + c);
    }
    i++;
  }
  return result.pop();
}

Longest Absolute File Path

Suppose we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file file2.ext.

In text form, it looks like this (with ⟶ representing the tab character):

dir ⟶ subdir1 ⟶ ⟶ file1.ext ⟶ ⟶ subsubdir1 ⟶ subdir2 ⟶ ⟶ subsubdir2 ⟶ ⟶ ⟶ file2.ext

If we were to write this representation in code, it will look like this: “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”. Note that the ‘\n’ and ‘\t’ are the new-line and tab characters.

Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by ‘/’s. Using the above example, the absolute path to file2.ext is “dir/subdir2/subsubdir2/file2.ext”. Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces.

Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

  /** Use stack to track longest file path */
  public int longestAbsoluteFilePath(String input) {
    int maxLen = 0;

    Stack<Integer> stack = new Stack<>();
    for (String path : input.split("\n")) {
      int level = path.lastIndexOf("\t") + 1;
      while (level < stack.size()) {
        stack.pop(); // find parent
      }
      int length = stack.isEmpty() ? 0 : stack.peek();
      length += path.length() - level + 1; // remove /t, add /
      stack.push(length);
      if (path.contains(".")) {
        maxLen = Math.max(maxLen, length - 1);
      }
    }

    return maxLen;
  }

Sliding Window

A sliding window problem needs to have a concrete condition where we can increase or decrease the boundary. The basic template of a sliding window problem has 3 steps: 1. Have two pointers or an array/collection type to count specific array input and keep on increasing the window toward right using outer loop. 2. Have a checking logic or while loop inside to reduce the window size by sliding toward right based on constrains of problem. 3. Track and update the result of current window based on problem requirement.

Longest Continuous Increasing

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

For example, if A = [1,3,5,4,7], The longest continuous increasing subsequence is [1,3,5], its length is 3.

Solution:

For the continuous subarray issue, we can first consider using sliding window. As below, we can use an anchor to mark the start of a new increasing subsequence at nums[i].

  public int[] longestContinuousIncreasingSubarray(int[] nums) {
    int start = 0, end = 0;
    int max = 0, anchor = 0; // anchor is slow pointer
    for (int i = 0; i < nums.length; i++) {
      if (i > 0 && nums[i - 1] >= nums[i])
        anchor = i;
      if (max < i - anchor + 1) {
        max = i - anchor + 1;
        start = anchor;
        end = i;
      }
    }
    return new int[] { start, end };
  }

Find Longest Substring

Given a string, find the length of the longest substring without repeating characters.

Examples: Given “abcabcbb”, the answer is “abc”, which the length is 3.

  // Use a map to track position easily
  public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    int max = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
      char c = s.charAt(right);
      if (map.containsKey(c)) {
        left = Math.max(left, map.get(c) + 1);
      }
      map.put(c, right);
      max = Math.max(max, right - left + 1);
    }
    return max;
  }

  // Use array to achieve the most efficient
  public int lengthOfLongestSubstring3(String s) {
    boolean[] seen = new boolean[256];
    char[] arr = s.toCharArray();
    int max = 0, left = 0, right = 0;
    // outer loop to increase window
    while (right < arr.length) {
      char c = arr[right];
      if (!seen[c]) {
        seen[c] = true;
      } else {
        max = Math.max(right - left, max);
        // inner loop to decrease window
        while (arr[right] != arr[left]) {
          char c2 = arr[left];
          seen[c2] = false;
          left++;
        }
        left++;
      }
      right++;
    }
    max = Math.max(right - left, max);
    return max;
  }

Sliding Window Median

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

For examples, if arr = [2,3,4], the median is 3; if arr = [1,2,3,4], the median is (2 + 3) / 2 = 2.5. You are given an integer array nums and an integer k.

There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the median array for each window in the original array. Answers within 10-5 of the actual value will be accepted.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6
  • Solution: Use two heaps with lazy removal
  • Time complexity: \(O(2⋅n\log k)+O(n−k)≈O(n\log k)\).
  • Space complexity: \(O(k)+O(n)≈O(n)\) extra linear space.
public class SlidingWindowMedian {
  public double[] medianSlidingWindow(int[] nums, int k) {
    Queue<Integer> large = new PriorityQueue<>((a, b) -> nums[a] == nums[b] ? Integer.compare(a, b) : Integer.compare(nums[a], nums[b]));
    Queue<Integer> small = new PriorityQueue<>((a, b) -> nums[a] == nums[b] ? Integer.compare(a, b) : Integer.compare(nums[b], nums[a]));
    double[] ans = new double[nums.length - k + 1];
    int balance = 0;
    int i = 0;
    while (i < nums.length) {
      if (large.isEmpty() || nums[i] >= nums[large.peek()]) {
        large.offer(i);
        balance++;
      } else {
        small.offer(i);
        balance--;
      }
      i++;

      while (balance > 1 || (!large.isEmpty() && large.peek() < i - k)) {
        int min = large.poll();
        if (min >= i - k) {
          small.offer(min);
          balance -= 2;
        }
      }

      while (balance < 0 || (!small.isEmpty() && small.peek() < i - k)) {
        int max = small.poll();
        if (max >= i - k) {
          large.offer(max);
          balance += 2;
        }
      }

      if (i - k >= 0) {
        ans[i - k] = k % 2 == 0 ? ((double) nums[small.peek()] + (double) nums[large.peek()]) / 2 : (double) nums[large.peek()];
        
        // Lazy removal of an outgoing number
        if (!small.isEmpty() && i - k == small.peek()) {
          small.poll();
          balance++;
        } else if (i - k == large.peek()) {
          large.poll();
          balance--;
        } else if (nums[i - k] >= nums[large.peek()]) {
          balance--;
        } else {
          balance++;
        }
      }

    }

    return ans;
  }
}

Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Sliding Window with Counters: Keep track of request counts for each user using multiple fixed time windows. Here we have an 5 mins rate limit we can keep a count for each second and calculate the sum of all 5*60 counters when we receive a new request to calculate the throttling limit.

In an application, each user can have a hit counter to construct a caching map. The rate limiter can significantly benefit from the Write-back/through cache by updating all counters and timestamps in cache only. The write to the permanent storage can be done at fixed intervals. This way we can ensure minimum latency added to the user’s requests by the rate limiter. The reads can always hit the cache first; which will be extremely useful once the user has hit their maximum limit and the rate limiter will only be reading data without any updates.

// Use double linked list
public class HitCounter {
  private int total;
  private int window;
  private Deque<int[]> hits;

  public HitCounter() {
    total = 0;
    window = 5 * 60; // 5 mins window
    hits = new LinkedList<int[]>();
  }

  public void hit(int timestamp) {
    if (hits.isEmpty() || hits.getLast()[0] != timestamp) {
      hits.add(new int[] { timestamp, 1 });
    } else {
      hits.getLast()[1]++;
      // hits.add(new int[] { timestamp, hits.removeLast()[1] + 1 });
    }
    // Prevent from growing too much
    if (hits.size() > window) {
      purge(timestamp);
    }
    total++;
  }

  public int getHits(int timestamp) {
    purge(timestamp);
    return total;
  }

  private void purge(int timestamp) {
    while (!hits.isEmpty() && timestamp - hits.getFirst()[0] >= window) {
      total -= hits.removeFirst()[1];
    }
  }
}

// Use array rotation
public class HitCounter {
  private int total;
  private int window;
  private int[][] hits;

   public HitCounter() {
    total = 0;
    window = 5 * 60; // 5 mins window
    hits = new int[window][2];
  }

  public void hit(int timestamp) {
    int i = timestamp % hits.length;
    if (hits[i][0] != timestamp) {
      purge(i, timestamp);
    }
    hits[i][1]++;
    total++;
  }

  public int getHits(int timestamp) {
    for (int i = 0; i < hits.length; i++) {
      if (hits[i][0] != 0 && timestamp - hits[i][0] >= window) {
        purge(i, timestamp);
      }
    }
    return total;
  }

  private void purge(int i, int timestamp) {
    total -= hits[i][1];
    hits[i][0] = timestamp;
    hits[i][1] = 0;
  }
}

Union Find

Union Find Util

/**
 * The UnionFind class represents a union–find data type (also known as the disjoint-sets data
 * type). It supports the union and find operations, along with a connected operation for
 * determining whether two sites are in the same component and a count operation that returns the
 * total number of components.
 */
public class UnionFind {
  private int[] parent; // parent[i] = parent of i
  private byte[] rank; // rank[i] = rank of subtree rooted at i (never more than 31)
  private int count; // number of components

  public UnionFind(int n) {
    if (n < 0)
      throw new IllegalArgumentException();
    count = n;
    parent = new int[n];
    rank = new byte[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      rank[i] = 0;
    }
  }

  public int find(int p) {
    validate(p);
    while (p != parent[p]) {
      parent[p] = parent[parent[p]]; // path compression by halving
      p = parent[p];
    }
    return p;
  }

  public int count() {
    return count;
  }

  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }

  public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ)
      return;

    if (rank[rootP] < rank[rootQ])
      parent[rootP] = rootQ;
    else if (rank[rootP] > rank[rootQ])
      parent[rootQ] = rootP;
    else {
      parent[rootQ] = rootP;
      rank[rootP]++;
    }

    count--;
  }

  private void validate(int p) {
    if (p < 0 || p >= parent.length)
      throw new IllegalArgumentException();
  }
}

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”]].

Solution: Two words are similar if they are the same, or there is a path connecting them from edges represented by pairs.

We can check whether this path exists by performing a depth-first search from a word and seeing if we reach the other word. The search is performed on the underlying graph specified by the edges in pairs.

Time Complexity: O(NP), where N is the maximum length of words1 and words2, and P is the length of pairs. Each of N searches could search the entire graph. You can also use Union-Find search to achieve Time Complexity: O(NlogP+P).

  private Map<String, String> parents = new HashMap<>();

  // Use graph BFS
  public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
    if (words1.length != words2.length)
      return false;
    Map<String, List<String>> graph = new HashMap<>();
    for (String[] pair : pairs) {
      for (String word : pair) {
        if (!graph.containsKey(word))
          graph.put(word, new ArrayList<>());
      }
      graph.get(pair[0]).add(pair[1]);
      graph.get(pair[1]).add(pair[0]);
    }
    Queue<String> queue = new ArrayDeque<>();
    Set<String> visited = new HashSet<>();
    for (int i = 0; i < words1.length; i++) {
      queue.clear();
      visited.clear();
      queue.offer(words1[i]);
      visited.add(words1[i]);
      search: {
        while (!queue.isEmpty()) {
          String word = queue.poll();
          if (word.equals(words2[i]))
            break search;
          if (graph.containsKey(word)) {
            for (String nei : graph.get(word)) {
              if (!visited.contains(nei)) {
                queue.offer(nei);
                visited.add(nei);
              }
            }
          }
        }

        return false;
      }
    }
    return true;
  }
  
  // Use union find
  public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
    if (sentence1.length != sentence2.length) {
      return false;
    }
    for (List<String> list : similarPairs) {
      union(list.get(0), list.get(1), parents);
    }
    for (int i = 0; i < sentence1.length; i++) {
      if (!find(sentence1[i]).equals(find(sentence2[i]))) {
        return false;
      }
    }
    return true;
  }

  private void union(String s1, String s2, Map<String, String> roots) {
    String ps1 = find(s1);
    String ps2 = find(s2);
    if (!ps1.equals(ps2)) {
      roots.put(s2, ps1); // halve path
      roots.put(ps2, ps1);
    }
  }

  private String find(String s) {
    while (parents.containsKey(s)) {
      s = parents.get(s);
    }
    return s;
  }  

Accounts Merge

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example:

Input: accounts = [[“John”,”johnsmith@mail.com”,”john_newyork@mail.com”],[“John”,”johnsmith@mail.com”,”john00@mail.com”],[“Mary”,”mary@mail.com”],[“John”,”johnnybravo@mail.com”]]

Output: [[“John”,”john00@mail.com”,”john_newyork@mail.com”,”johnsmith@mail.com”],[“Mary”,”mary@mail.com”],[“John”,”johnnybravo@mail.com”]]

Explanation: The first and third John’s are the same person as they have the common email “johnsmith@mail.com”. The second John and Mary are different people as none of their email addresses are used by other accounts. We could return these lists in any order, for example the answer [[‘Mary’, ‘mary@mail.com’], [‘John’, ‘johnnybravo@mail.com’], [‘John’, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’]] would still be accepted.

Solution:

  • Disjoint Set Union (DSU) or Depth-First Search (DFS)
  • Time Complexity: O(AlogA),where A=∑ai and ai is the length of accounts[i]
  public List<List<String>> accountsMergeWithDSU(List<List<String>> accounts) {
    DSU dsu = new DSU();
    Map<String, String> emailToName = new HashMap<>();
    Map<String, Integer> emailToID = new HashMap<>();
    int id = 0;
    for (List<String> account : accounts) {
      String name = null;
      for (String email : account) {
        if (name == null) {
          name = email;
          continue;
        }
        emailToName.put(email, name);
        if (!emailToID.containsKey(email)) {
          emailToID.put(email, id++);
        }
        dsu.union(emailToID.get(account.get(1)), emailToID.get(email));
      }
    }

    // Add all union emails
    Map<Integer, List<String>> ans = new HashMap<>();
    emailToID.forEach((email, id2) ->
      {
        ans.computeIfAbsent(dsu.find(id2), x -> new ArrayList<>()).add(email);
      });

    // Add name to the first place
    for (List<String> component : ans.values()) {
      Collections.sort(component); // Sort emails first
      component.add(0, emailToName.get(component.get(0)));
    }
    return new ArrayList<>(ans.values());
  }

  class DSU {
    int[] parent;

    public DSU() {
      parent = new int[10001];
      for (int i = 0; i <= 10000; ++i)
        parent[i] = i;
    }

    public int find(int x) {
      if (parent[x] != x) {
        parent[x] = find(parent[x]);
      }
      return parent[x];
    }

    public int find2(int x) {
      while (x != parent[x]) {
        parent[x] = parent[parent[x]]; // path compression by halving
        x = parent[x];
      }
      return x;
    }

    public void union(int x, int y) {
      parent[find(y)] = find(x);
    }
  }

  public List<List<String>> accountsMergeWithDFS(List<List<String>> accounts) {
    Map<String, String> emailToName = new HashMap<>();
    Map<String, ArrayList<String>> graph = new HashMap<>();
    for (List<String> account : accounts) {
      String name = "";
      for (String email : account) {
        if (name == "") {
          name = email;
          continue;
        }
        graph.computeIfAbsent(email, x -> new ArrayList<String>()).add(account.get(1));
        graph.computeIfAbsent(account.get(1), x -> new ArrayList<String>()).add(email);
        emailToName.put(email, name);
      }
    }

    Set<String> seen = new HashSet<>();
    List<List<String>> ans = new ArrayList<>();
    for (String email : graph.keySet()) {
      if (!seen.contains(email)) {
        seen.add(email);
        Stack<String> stack = new Stack<>();
        stack.push(email);
        List<String> component = new ArrayList<>();
        while (!stack.empty()) {
          String node = stack.pop();
          component.add(node);
          for (String nei : graph.get(node)) {
            if (!seen.contains(nei)) {
              seen.add(nei);
              stack.push(nei);
            }
          }
        }
        Collections.sort(component);
        component.add(0, emailToName.get(email));
        ans.add(component);
      }
    }
    return ans;
  }

Topological Ordering

A topological ordering of a directed acyclic graph (DAG): every edge goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.

DAGs can be used to represent compilation operations, dataflow programming, events and their influence, family tree, version control, compact sequence data, binary decision diagram etc.

Topological Ordering

Course Schedule

Let us practice it with the Course Schedule problem:

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

Input: 2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

The problem turns out to find a topological sort order of the courses, which would be a DAG if it has a valid order. try BFS and DFS to resolve it! O(E+V)

public int[] findOrderInBFS(int numCourses, int[][] prerequisites) {
  // initialize directed graph
  int[] indegrees = new int[numCourses];
  List<List<Integer>> adjacents = new ArrayList<>(numCourses);
  for (int i = 0; i < numCourses; i++) {
    adjacents.add(new ArrayList<>());
  }
  for (int[] edge : prerequisites) {
    indegrees[edge[0]]++;
    adjacents.get(edge[1]).add(edge[0]);
  }
  // breadth first search
  int[] order = new int[numCourses];
  Queue<Integer> toVisit = new ArrayDeque<>();
  for (int i = 0; i < indegrees.length; i++) {
    if (indegrees[i] == 0)
      toVisit.offer(i);
  }
  int visited = 0;
  while (!toVisit.isEmpty()) {
    int from = toVisit.poll();
    order[visited++] = from;
    for (int to : adjacents.get(from)) {
      indegrees[to]--;
      if (indegrees[to] == 0)
        toVisit.offer(to);
    }
  }
  // should visited all courses
  return visited == indegrees.length ? order : new int[0];
}

// track cycle with three states
public int[] findOrderInDFS(int numCourses, int[][] prerequisites) {
  // initialize directed graph
  List<List<Integer>> adjacents = new ArrayList<>(numCourses);
  for (int i = 0; i < numCourses; i++) {
    adjacents.add(new ArrayList<>());
  }
  for (int[] edge : prerequisites) {
    adjacents.get(edge[1]).add(edge[0]);
  }
  int[] states = new int[numCourses]; // 0=unvisited, 1=visiting, 2=visited
  Stack<Integer> stack = new Stack<>();
  for (int from = 0; from < numCourses; from++) {
    if (!topologicalSort(adjacents, from, stack, states))
      return new int[0];
  }
  int i = 0;
  int[] order = new int[numCourses];
  while (!stack.isEmpty()) {
    order[i++] = stack.pop();
  }
  return order;
}

private boolean topologicalSort(List<List<Integer>> adjacents, int from, Stack<Integer> stack, int[] states) {
  if (states[from] == 1)
    return false;
  if (states[from] == 2)
    return true;
  states[from] = 1; // visiting
  for (Integer to : adjacents.get(from)) {
    if (!topologicalSort(adjacents, to, stack, states))
      return false;
  }
  states[from] = 2; // visited
  stack.push(from);
  return true;
}

Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example: Input: [ “wrt”, “wrf”, “er”, “ett”, “rftt”]; Output: “wertf”

public String alienOrder(String[] words) {
	Map<Character, Set<Character>> map = new HashMap<>();
	Map<Character, Integer> degree = new HashMap<>();
	StringBuilder result = new StringBuilder();

	for (String word : words) {
		for (char c : word.toCharArray()) {
			degree.put(c, 0);
		}
	}

	for (int i = 0; i < words.length - 1; i++) {
		String curr = words[i];
		String next = words[i + 1];
		for (int j = 0; j < Math.min(curr.length(), next.length()); j++) {
			char c1 = curr.charAt(j);
			char c2 = next.charAt(j);
			if (c1 != c2) {
				if (!map.containsKey(c1))
					map.put(c1, new HashSet<>());
				Set<Character> set = map.get(c1);
				if (!set.contains(c2)) {
					set.add(c2);
					degree.put(c2, degree.getOrDefault(c2, 0) + 1);
				}
				break;
			}
		}
	}

	Queue<Character> queue = new LinkedList<>();
	for (Map.Entry<Character, Integer> entry : degree.entrySet()) {
		if (entry.getValue() == 0)
			queue.add(entry.getKey());
	}
	while (!queue.isEmpty()) {
		char c = queue.remove();
		result.append(c);
		if (map.containsKey(c)) {
			for (char c2 : map.get(c)) {
				degree.put(c2, degree.get(c2) - 1);
				if (degree.get(c2) == 0)
					queue.add(c2);
			}
		}
	}
	if (result.length() != degree.size())
		result.setLength(0);

	return result.toString();
}

Dynamic Programming

Dynamic programming (DP) is mostly just a matter of taking a recursive algorithm and finding the overlapping subproblems (that is, the repeated calls). You then cache those results for future recursive calls.

All recursive algorithms can be implemented iteratively (still use cache), although sometimes the code to do so is much more complex. Each recursive call adds a new layer to the stack, which means that if your algorithm recurses to a depth of n, it uses at least O(n) memory.

When DP is implemented recursively the cache is typically a dynamic data structure such as a hash table or a BST; when it’s implemented iteratively the cache is usually a one- or multi-dimensional array.

To illustrate the idea underlying DP, let’s walk through the approaches to compute the nth Fibonacci number.

Fibonacci Numbers

Mathematically, the nth Fibonacci number is given by the equation: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21,…

Simple Recursive Implementation

We can start with a simple recursive implementation. This gives us a runtime of roughly O(2^n), an exponential runtime.

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

Top-Down Dynamic Programming

We still use top-down dynamic programming, but with memorization this time! The runtime is roughly O(n) since we are caching the result and use it later.

public static int fibonacciII(int i) {
  return fibonacciII(i, new int[i + 1]);
}

public static int fibonacciII(int n, int[] memo) {
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  if (memo[n] == 0) {
    memo[n] = fibonacciII(n - 1, memo) + fibonacciII(n - 2, memo);
  }
  return memo[n];
}

Bottom-Up Dynamic Programming

Let’s change it to bottom-up dynamic programming, with memorization too! This give us the same O(n) runtime.

public static int fibonacciIII(int n) {
  if (n == 0)
    return 0;
  int[] memo = new int[n + 1];
  memo[0] = 0;
  memo[1] = 1;
  for (int i = 2; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }
  return memo[n];
}

Achieve The Best Complexity

We can even get rid of the memo table, to achieve O(n) time and O(1) space.

public static int fibonacciVI(int n) {
  if (n == 0)
    return 0;
  int a = 0;
  int b = 1;
  for (int i = 2; i <= n; i++) {
    int c = a + b;
    a = b;
    b = c;
  }
  return b;
}

Unique Paths in Grid

You are given an m x n integer array grid. There is a robot initially located at the top-left corner. The robot tries to move to the bottom-right corner. The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Example:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
0 0 0
0 1 0
0 0 0
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
  public int findHowManyUniquePathsInGridWithObstacles(int[][] obstacleGrid) {
    int width = obstacleGrid[0].length;
    int[] dp = new int[width];
    dp[0] = 1;
    for (int[] row : obstacleGrid) {
      for (int j = 0; j < width; j++) {
        if (row[j] == 1)
          dp[j] = 0;
        else if (j > 0)
          dp[j] += dp[j - 1];
      }
    }
    return dp[width - 1];
  }

Consecutive One in Matrix

Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix.

The line could be horizontal, vertical, diagonal, or anti-diagonal.

Example:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
0 1 1 0
0 1 1 0
0 0 0 1
Output: 3
  public int longestLineOfConsecutiveOneInMatrix(int[][] mat) {
    int m = mat.length, n = mat[0].length, max = 0;
    int[][][] dp = new int[m][n][4]; // 4 directions
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (mat[i][j] == 0)
          continue;
        Arrays.fill(dp[i][j], 1); // init as 1
        if (j > 0)
          dp[i][j][0] += dp[i][j - 1][0]; // left vertical
        if (i > 0 && j > 0)
          dp[i][j][1] += dp[i - 1][j - 1][1]; // up-left diagonal
        if (i > 0)
          dp[i][j][2] += dp[i - 1][j][2]; // up horizontal
        if (i > 0 && j < n - 1)
          dp[i][j][3] += dp[i - 1][j + 1][3]; // up-right anti-diagonal
        for (int k = 0; k < 4; k++) {
          max = Math.max(max, dp[i][j][k]);
        }
      }
    }
    return max;
  }

Word Break (3 Solutions)

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

NOTE: There could be multiple ways to break word, in industry, also need to consider the context, category, culture etc to pick up the most suitable one! You should even choose different dictionaries which might have ranking for each words. To support multiple languages, we need use unicode as well, to avoid excessive space cost associated with R-way tries, consider using TST (Ternary Search Tree).

// Recursion with memoization
public boolean wordBreak1(String s, List<String> wordDict) {
  return wordBreak1(s, new HashSet<String>(wordDict), 0, new Boolean[s.length()]);
}

public boolean wordBreak1(String s, Set<String> wordDict, int start, Boolean[] memo) {
  if (start == s.length())
    return true;
  if (memo[start] != null)
    return memo[start];
  for (int end = start + 1; end <= s.length(); end++) {
    if (wordDict.contains(s.substring(start, end)) && wordBreak1(s, wordDict, end, memo))
      return memo[start] = true;
  }
  return memo[start] = false;
}

// Use Breadth-First-Search
public boolean wordBreak2(String s, List<String> wordDict) {
  Set<String> wordDictSet = new HashSet<>(wordDict);
  Queue<Integer> queue = new LinkedList<>();
  int[] visited = new int[s.length()];
  queue.add(0);

  while (!queue.isEmpty()) {
    int start = queue.remove();
    if (visited[start] == 0) {
      for (int end = start + 1; end <= s.length(); end++) {
        if (wordDictSet.contains(s.substring(start, end))) {
          queue.add(end);
          if (end == s.length())
            return true;
        }
      }
      visited[start] = 1;
    }
  }

  return false;
}

// Dynamic programming
public boolean wordBreak3(String s, List<String> wordDict) {
  Set<String> wordDictSet = new HashSet<>(wordDict);
  boolean[] found = new boolean[s.length() + 1];
  found[0] = true;
  for (int i = 1; i <= s.length(); i++) {
    for (int j = 0; j < i; j++) {
      if (found[j] && wordDictSet.contains(s.substring(j, i))) {
        found[i] = true;
        break;
      }
    }
  }
  return found[s.length()];
}

// Also can apply Trie Tree (or TST) to break earlier (if there were many words to check)

// Can also resolve the question: Concatenated Words
// A word can only be formed by words shorter than it. So we can first sort the input
// by length of each word, and only try to form one word by using words in front of it.
public List<String> findAllConcatenateWords(String[] words) {
  List<String> result = new ArrayList<>();
  Set<String> preWords = new HashSet<>();
  Arrays.sort(words, (a, b) -> (a.length() - b.length()));
  for (String word : words) {
    if (canForm(word, preWords))
      result.add(word);
    preWords.add(word);
  }
  return result;
}
private static boolean canForm(String word, Set<String> dict) {
  if (dict.isEmpty())
    return false;
  boolean[] dp = new boolean[word.length() + 1];
  dp[0] = true;
  for (int i = 1; i <= word.length(); i++) {
    for (int j = 0; j < i; j++) {
      if (dp[i] && dict.contains(word.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[word.length()];
}

Recursion & Backtrack

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Solution: To implement this method, we’ll make use of a 2-d boolean array dp. In this array dp[i][j] implies if it is possible to obtain a substring of length (i+j+2) which is a prefix of s3 by some interleaving of prefixes of strings s1 and s2 having lengths (i+1) and (j+1) respectively.

  // DFS is the most efficient way!
  public boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length())
      return false;
    return dfs(s1, s2, s3, 0, 0, 0, new boolean[s1.length() + 1][s2.length() + 1]);
  }

  public boolean dfs(String s1, String s2, String s3, int i, int j, int k, boolean[][] invalid) {
    if (invalid[i][j])
      return false;
    if (k == s3.length())
      return true;
    boolean valid = (i < s1.length() && s1.charAt(i) == s3.charAt(k) && dfs(s1, s2, s3, i + 1, j, k + 1, invalid))
        || (j < s2.length() && s2.charAt(j) == s3.charAt(k) && dfs(s1, s2, s3, i, j + 1, k + 1, invalid));
    if (!valid)
      invalid[i][j] = true;
    return valid;
  }

  // DP has the stable complexity O(m*n)
  public boolean isInterleave2(String s1, String s2, String s3) {
    if (s3.length() != s1.length() + s2.length())
      return false;
    boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];

    dp[0][0] = true;
    for (int i = 1; i < dp.length; i++)
      dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
    for (int j = 1; j < dp[0].length; j++)
      dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);

    for (int i = 1; i <= s1.length(); i++) {
      for (int j = 1; j <= s2.length(); j++) {
        dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
      }
    }
    return dp[s1.length()][s2.length()];
  }

Minimum Cost For Tickets

  /**
   * 
   * Minimum Cost For Tickets
   * 
   * You have planned some train traveling one year in advance. The days of the year in which you will
   * travel are given as an integer array days. Each day is an integer from 1 to 365.
   * 
   * Train tickets are sold in three different ways:
   * 
   * a 1-day pass is sold for costs[0] dollars, a 7-day pass is sold for costs[1] dollars, and a
   * 30-day pass is sold for costs[2] dollars. The passes allow that many days of consecutive travel.
   * 
   * For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7,
   * and 8. Return the minimum number of dollars you need to travel every day in the given list of
   * days.
   * 
   * <pre>
   * Example 1:
   *
   * Input: days = [1,4,6,7,8,20], costs = [2,7,15]
   * Output: 11
   * Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
   * On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
   * On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
   * On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
   * In total, you spent $11 and covered all the days of your travel.
   * </pre>
   *
   */
  public int mincostTickets(int[] days, int[] costs) {
    int[] durations = { 1, 7, 30 }; // 3 different ways
    return recursiveDP(days, costs, durations, 0, new int[days.length]);
  }

  public int recursiveDP(int[] days, int[] costs, int[] durations, int i, int[] memo) {
    if (i >= days.length) {
      return 0;
    }

    if (memo[i] != 0) {
      return memo[i];
    }

    int ans = Integer.MAX_VALUE, j = i;
    for (int d = 0; d < durations.length; d++) {
      while (j < days.length && days[j] < days[i] + durations[d]) {
        j++;
      }
      ans = Math.min(ans, recursiveDP(days, costs, durations, j, memo) + costs[d]);
    }

    memo[i] = ans;
    return ans;
  }

Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Solution: DFS with Backtrack

  public boolean canPartitionKSubsets(int[] nums, int k) {
    int sum = 0;
    for (int n : nums)
      sum += n;
    if (sum % k != 0)
      return false;
    int target = sum / k;

    return partitionDFS(0, k, 0, target, nums, new boolean[nums.length]);
  }

  // DFS with Backtrack
  public boolean partitionDFS(int i, int k, int sum, int target, int[] nums, boolean[] visited) {
    if (k == 0)
      return true;
    if (target == sum)
      // start a new group
      return partitionDFS(0, k - 1, 0, target, nums, visited);
    if (i == nums.length || sum > target)
      return false;

    // move forward without using current value
    boolean result = partitionDFS(i + 1, k, sum, target, nums, visited);

    if (!result && !visited[i]) {
      // dfs with using current value
      visited[i] = true;
      result = partitionDFS(i + 1, k, sum + nums[i], target, nums, visited);
      visited[i] = false;
    }

    return result;
  }

Longest Increasing Path in a Matrix

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
9 9 4
6 6 8
2 1 1

Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Solution:

  • DFS + Memoization, cache the results for the recursion so that any subproblem will be calculated only once.
  • Time complexity: O(mn). Space complexity: O(mn). The cache dominates the space complexity.
  public int longestIncreasingPath(int[][] matrix) {
    if (matrix.length == 0)
      return 0;
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] memo = new int[m][n];
    int max = 1;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        max = Math.max(max, longestIncreasingPathDfs(matrix, i, j, m, n, memo));
      }
    }
    return max;
  }

  private int[][] dirs = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

  private int longestIncreasingPathDfs(int[][] matrix, int i, int j, int m, int n, int[][] memo) {
    if (memo[i][j] != 0)
      return memo[i][j];
    int max = 1;
    for (int[] dir : dirs) {
      int x = i + dir[0];
      int y = j + dir[1];
      if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
        max = Math.max(max, 1 + longestIncreasingPathDfs(matrix, x, y, m, n, memo));
      }
    }
    memo[i][j] = max;
    return max;
  }