Skip to content

Latest commit

 

History

History
320 lines (259 loc) · 15.1 KB

2018-08-31-ARTS.md

File metadata and controls

320 lines (259 loc) · 15.1 KB
Raw

Week 6 ARTS

[A] - LC: 290. Word Pattern

package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 290. Word Pattern
 *
 * Given a pattern and a string str, find if str follows the same pattern.
 *
 * Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
 *
 * Example 1:
 *
 * Input: pattern = "abba", str = "dog cat cat dog"
 * Output: true
 * Example 2:
 *
 * Input:pattern = "abba", str = "dog cat cat fish"
 * Output: false
 * Example 3:
 *
 * Input: pattern = "aaaa", str = "dog cat cat dog"
 * Output: false
 * Example 4:
 *
 * Input: pattern = "abba", str = "dog dog dog dog"
 * Output: false
 * Notes:
 * You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
 */
public class WordPattern290 {

  public boolean wordPattern(String pattern, String str) {
    // checking length
    String[] strs = str.split(" ");
    if (pattern.length() != strs.length) return false;
    // first map checking character in pattern matching string in str
    Map<Character, String> fMap = new HashMap<>();
    // second map checking from string in str matching character in pattern
    Map<String, Character> sMap = new HashMap<>();

    for (int i = 0; i < strs.length; i++) {
      char ch = pattern.charAt(i);
      if (!fMap.containsKey(ch)) {
        fMap.put(ch, strs[i]);
      }
      if (!fMap.get(ch).equals(strs[i])) return false;
      if (!sMap.containsKey(strs[i])) {
        sMap.put(strs[i], ch);
      }
      if (sMap.get(strs[i]) != ch) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    WordPattern290 test = new WordPattern290();
    System.out.println(test.wordPattern("abba", "dog cat cat dog"));
    System.out.println(test.wordPattern("abba", "dog cat cat fish"));
    System.out.println(test.wordPattern("aaaa", "dog cat cat dog"));
    System.out.println(test.wordPattern("abba", "dog dog dog dog"));
  }
}
package leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 291. Word Pattern II
 *
 * Given a pattern and a string str, find if str follows the same pattern.
 * Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
 *
 * Examples:
 * pattern = "abab", str = "redblueredblue" should return true.
 * pattern = "aaaa", str = "asdasdasdasd" should return true.
 * pattern = "aabb", str = "xyzabcxzyabc" should return false.
 *
 * Notes:
 * You may assume both pattern and str contains only lowercase letters.
 */
public class WordPatternII291 {
  /**
   * This is much harder than word pattern which gave you a space separated strings.
   * Now you will need to self define string.
   * In this case, we will need to split string one by one to match the character in pattern.
   * Using one map character to string, and a set to store the defined string,
   * Backtracking string to match all characters
   *
   * E.g: pattern: "abab", string: "redblueredblue"
   * 'a' -> "r", 'b' -> "e", 'a' -> "d" (not match, first one match "r"), now backtrack
   * let 'b' -> ed", 'a' -> "b" (still not match), backtracking~
   * continue~~ until the whole string not match.
   *
   * now let 'a' -> "re", 'b' -> "d" ~ continue the process, not matching, then backtracking
   * ...
   * ...
   * let 'a' -> "red", 'b' -> "blue", all match, then return true.
   *
   * Keep backtracking the character and string matching, not then backtracking, found then return true.
   * Using recursive backtracking solution.
   *
   * let pattern be n, string be m, here
   * big O: O(m ^ n)
   */

  public boolean wordPatternMatch(String pattern, String str) {
    if (str.length() < pattern.length()) return false;
    Map<Character, String> map = new HashMap<>();
    Set<String> set = new HashSet<>();

    return isMatching(pattern, 0, str, 0, map, set);
  }

  private boolean isMatching(String pattern, int pIdx, String str, int sIdx,
                             Map<Character, String> map, Set<String> set) {
    // all matching, return true
    if (pIdx == pattern.length() && sIdx == str.length()) return true;
    // not matching, return false
    if (pIdx == pattern.length() || sIdx == str.length()) return false;

    char curr = pattern.charAt(pIdx);

    if (map.containsKey(curr)) {
      String existingStr = map.get(curr);

      if (!str.startsWith(existingStr, sIdx)) return false;

      return isMatching(pattern, pIdx + 1, str, sIdx + existingStr.length(), map, set);
    }

    for (int i = sIdx; i < str.length(); i++) {
      String currString = str.substring(sIdx, i + 1);
      if (!set.add(currString)) continue;
      map.put(curr, currString);

      if (isMatching(pattern, pIdx + 1, str, i + 1, map, set)) return true;

      // backtracking
      map.remove(curr);
      set.remove(currString);
    }

    return false;
  }

  public static void main(String[] args) {
    WordPatternII291 test = new WordPatternII291();
    System.out.println(test.wordPatternMatch("abab", "redblueredblue"));
    System.out.println(test.wordPatternMatch("aaaa", "asdasdasdasd"));
    System.out.println(test.wordPatternMatch("aabb", "xyzabcxzyabc"));
    System.out.println(test.wordPatternMatch("aabb", "xy"));
    System.out.println(test.wordPatternMatch("a", "xy"));
    System.out.println(test.wordPatternMatch("ab", "xyssgsd"));
    System.out.println(test.wordPatternMatch("ab", ""));
    System.out.println(test.wordPatternMatch("", ""));
    System.out.println(test.wordPatternMatch("s", ""));
  }
}

[R] - How to Design a Scalable Rate Limiter

Rate Limiting protects your APIs from overuse by limiting how often each user can call the API. This limiting is to control the large requests coming from one user to prevent usage of insufficient resources and system instability. Using Rate Limiting, the requests per second (QPS) can be limited to a fixed number, to prevent starve other consumers, and prevent the "spike" requests per user.

How we design a Rate Limiter, here we will focus on some algorithms to implement Rate Limiter:

  1. Maintain a Queue to record the time for every request. check previous requesting time when new request comes, if it is less than Rate, then reject. as below image, here we assume, we maintain a 1s queue, if the requests come within 1s, then we added into queue, otherwise, we reject.

alt text

2.Leaky Token Leaky token is an algorithm based on an analogy of how a bucket with a leak will overflow if either the average rate at which water is poured in exceeds the rate at which the bucket leaks or if more water than the capacity of the bucket is poured in all at once, and how the water leaks from the bucket at an (almost) constant rate.

You can think of a queue (FIFO) as a bucket holding the requests. If the queue is full, then additional requests will be discarded. alt text

Here has two variables:

  • one the bucket size, how much water can burst into bucket.
  • constant rate of dropping the water from bottom of the bucket.

Pros:

  • Easy to implement
  • It smooths out bursts of requests
  • Process requests at constant rate

Cons:

  • A burst of traffic can fill up the queue with old requests
  • Once filled with old requests, it will starve more recent requests from being processed.
  • No guarantee that requests get processed in a fixed amount of time
  • Need policy to coordinate and enforce the limit between load balance servers for fault tolerance or increased throughput.
  1. Token Bucket

Token Bucket is an algorithm (similar to Leaky token), but in opposite way.

  • A token (water) is added to the bucket every 1/QPS seconds.
  • The bucket can hold the most b tokens (capacity), the token is discarded if the bucket is full.
  • New request comes and get one token, if there is no token left in bucket, then the request will be blocked or rejected service.

alt text

Google Guava Rate Limiter has implemented Rate Limiter with Token Bucket algorithm.

References

  1. Leaky Bucket
  2. Token Bucket
  3. Java Implementaion Token Bucket
  4. Guava Rate limiter
  5. How to Design a Scalable Rate Limiting Algorithm

[T] - Interview Tips

I have been interviewer for a while now, most of time I interview a coding session or peer presentation session, when coding session, I usually ask a candidate a midium level algorithm questions, will have follow ups if the candidate finishs the question very quick.

For coding session, don't jump right into the solution, try to clearify problem with interviewer, and ask some questions (maybe some candidate have already seen the questions before, so you don't need to be hurry on it, ask some corner case questions, like whether the array is fixed array, or is it a stream data? or whether the array contains duplicate elements etc). When you stuck, don't stuck there, interviewer is willing to help, and assume that interviewer may not know the solution either, so you both will discuss the solutions, and improve the solution together (interviwer also want to know whether he/she is happy to work with you together as a potential co-worker within an hour).

  • Ask questions, Ask questions, Ask questions

For system design session, usually the question will be vague, you must ask questions, and list data (if you are not sure, ask).

  • Understand / be clear about the requirements.
  • Do Analysis (list the functions/objects you will need for the question)
  • Using Data to support your architecture, the more detailed, the more convinced.
  • QPS (query per second), Peak data.

E.g Designing a Scalable Uber system

  • What business values we need to deliver? list the obejcts, Uber, has Rider (request a ride), Driver(receive a request), Payment(pay and go)
  • What is the maximum distance between a driver and a rider for a driver to be visible to a user?
  • Are we supporting pool?
  • What is the criterion to show a shared driver to a user?
  • How to divid the shared pool?
  • How many requests(QPS) should the system handle?
  • What happens when multiple users request the same driver?
  • Does this system require high consistency/high availability/persistency? ...

Play a role that you are working with the interviewers. Be nervous is normal, ask questions when you are not sure.

References

[1]System Design Primer [2]System Design Interview

[S] - Share some Podcasts I daily listen

Personal opinions:

  • Making use of your daily fragment time.
  • Listen to English podcasts can practice your listening.
  • Learn what is going on in your daily life / world.
  • Get some knowledge on history/tech/life experiences/business

Podcasts recommendation (some of personal favorites):

  • Accidental tech Podcast ATP is a podcast about Tech, Apple and related matters, that was created while trying trying to do a car show. hosted byMarco Arment, Casey Liss, and John Siracusa.

  • The Talk Show The Talk Show features discussion about technology, Apple, Mac, iPhone, iPad, movies, directors, and the Web. It’s America’s favorite podcast. Hosted by John Gruber, and Dan Benjamin

  • Google Cloud Platform Podcast Weekly talk about GCP, and other products by talking to googlers and other tech leaders Hosted by Mark Mandel and Melanie Warrick

  • 路书 由古村和瞿侠老师引领大家一起讨论艺术史和历史的一档播客

  • 选美 聊聊美国那些事

  • 天书广播 张湛博士说历史,奇闻逸事

  • 忽左忽右 程衍樑和杨一发起并制作的谈话类播客节目。我们将每期邀请一位在专业领域拥有足够发言权的嘉宾，尽我们所能，探索在某个单一问题上所能达到的讨论深度。

  • 硬影像 罗登主持，是一个关注影像之一切的播客。谈论影像背后的技术，历史和哲理。

  • Sinica Podcast - Weekly discussion of current affairs in China A weekly discussion of current affairs on China with journalists, writers, academics, policy makers, business people and anyone with something compelling to say about the country that's reshaping the world. Sinica is hosted by Kaiser Kuo and Jeremy Goldkorn.

  • 996 Podcast with GGV Capital “996” is the demanding work schedule many Chinese founders have organically adopted: 9am to 9pm, 6 days a week. To us, 996 captures the intensity, drive, and speed of Chinese internet companies, many of which are moving faster than their American counterparts.

  • Business Wars Business wars gives you the unauthorized, real story of what drives these companies and their leaders, inventors, investors and executives to new heights or to ruin. Hosted by David D. Brown

  • Acquired A podcast about technology acquisitions and IPOs. Acquired goes behind the scenes of the best (and worst) acquisitions and IPOs of all time. From the Instagram A+'s to the AOL-Time Warner fails, what can we learn from their journeys and apply to our own organizations and careers in business and in tech? Hosted by @gilbert and @djrosent.

  • Planet Money NPR The economy explained. Imagine you could call up a friend and say, "Meet me at the bar and tell me what's going on with the economy.

  • NPR politics podcast The NPR Politics Podcast is where NPR's political reporters talk to you like they talk to each other. With weekly roundups and quick takes on news of the day, you don't have to keep up with politics to know what's happening.

  • NPR How I Built this Guy Raz dives into the stories behind some of the world's best known companies. How I Built This weaves a narrative journey about innovators, entrepreneurs and idealists—and the movements they built

  • The American Life This American Life is a weekly public radio program and podcast. Each week we choose a theme and put together different kinds of stories on that theme.