Skip to content

Latest commit

 

History

History
159 lines (140 loc) · 6.65 KB

arts-0003.md

File metadata and controls

159 lines (140 loc) · 6.65 KB

1.Algorithm

[485]  Max Consecutive Ones

Easy    array

Given a binary array, find the maximum number of consecutive 1s in this array.

Example:

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
  The maximum number of consecutive 1s is 3.

Note:

The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000

解答 本题可以采用常规的一次遍历和基于 hashtab 的方式进行处理(题目描述中已经定义不存在重复的数据)

(1).常规解法, 一次遍历比较，时间复杂度O(n)，空间复杂度O(1)
func findMaxConsecutiveOnes2(nums []int) int {
  maxCount, currentCount := 0, 0

  for _, num := range nums {
    if num == 1 {
      currentCount++
    } else {
      currentCount = 0
    }

    if currentCount > maxCount {
      maxCount = currentCount
    }
  }

  return maxCount
}

2.Review

how to ace a systems design interview

  • focus on thought process
    • open-ended problems
    • care about is the thought process behind your design choices.
    • come up with the best solution to each.
    • understand the problem:asking questions, sketching diagrams on the board, and bouncing ideas
    • know the constraints?
    • what kind of inputs does your system need to handle
    • you have to get a sense for the scope of the problem.
  • topics
    • Concurrency: threads, deadlock, starvation, parallelize algorithms, consistency and coherence
    • Networking: IPC, TCP/IP, the difference between throughput and latency
    • Abstraction: know roughly how an OS, file and database work
    • Real-World Performance: speed of everything: the relative performance of RAM, disk, SSD and your network.
    • Estimation: back-of-the-envelope calculation
    • Availability and Reliability: cope with network failures, understand durability
  • how to prepare
    • Do mock design sessions: Grab an empty room and a fellow engineer, and ask them to give you a design problem, preferably related to something they’ve worked on.
    • Work on an actual system.
    • Do back-of-the-envelope calculations for something you’re building and then write micro-benchmarks to verify them.
    • Dig into the performance characteristics of an open source system. For example, take a look at LevelDB. It’s new and clean and small and well-documented. Read about the implementation to understand how it stores its data on disk and how it compacts the data into levels.
    • Learn how databases and operation systems work under the hood.

3.Tip

本周搜索system design primer时，其中采用Anki flashcards来对知识的记录整理，同时由Anki有带出了艾宾浩斯曲线的相关理论知识。目前暂时只是处理了解状态，后续看实际情况再继续深入尝试用下，看实际的效果怎么样。

4.Share

4.1 system design primer Facebook的一个员工维护的有关系统设计的github仓库，目前有各种语言的版本，包括英文，日文，简体中文等。作者当初开启的这个项目的主要两个目标：

  • Learn how to design large-scale systems.
  • Prep for the system design interview.

design image

4.2 My System Design Template

leetcode上一个有关系统设计的面试流程模板

  • FEATURE EXPECTATIONS [5 min]
    • Use cases
    • Scenarios that will not be covered
    • Who will use
    • How many will use
    • Usage patterns
  • ESTIMATIONS [5 min]
    • Throughput (QPS for read and write queries)
    • Latency expected from the system (for read and write queries)
    • Read/Write ratio
    • Traffic estimates
      • Write (QPS, Volume of data)
      • Read (QPS, Volume of data)
    • Storage estimates
    • Memory estimates
      • If we are using a cache, what is the kind of data we want to store in cache
      • How much RAM and how many machines do we need for us to achieve this ?
      • Amount of data you want to store in disk/ssd
  • DESIGN GOALS [5 min]
    • Latency and Throughput requirements
    • Consistency vs Availability [Weak/strong/eventual => consistency | Failover/replication => availability]
  • HIGH LEVEL DESIGN [5-10 min]
    • APIs for Read/Write scenarios for crucial components
    • Database schema
    • Basic algorithm
    • High level design for Read/Write scenario
  • DEEP DIVE [15-20 min]
    • Scaling the algorithm
    • Scaling individual components:
      • Availability, Consistency and Scale story for each component
      • Consistency and availability patterns
    • Think about the following components, how they would fit in and how it would help
      • a) DNS
      • b) CDN [Push vs Pull]
      • c) Load Balancers [Active-Passive, Active-Active, Layer 4, Layer 7]
      • d) Reverse Proxy
      • e) Application layer scaling [Microservices, Service Discovery]
      • f) DB [RDBMS, NoSQL]
        • RDBMS
          • Master-slave, Master-master, Federation, Sharding, Denormalization, SQL Tuning
        • NoSQL
          • Key-Value, Wide-Column, Graph, Document
          • Fast-lookups:
            • RAM [Bounded size] => Redis, Memcached
            • AP [Unbounded size] => Cassandra, RIAK, Voldemort
            • CP [Unbounded size] => HBase, MongoDB, Couchbase, DynamoDB
      • g) Caches
        • Client caching, CDN caching, Webserver caching, Database caching, Application caching, Cache @Query level, Cache @Object level
        • Eviction policies:
          • Cache aside
          • Write through
          • Write behind
          • Refresh ahead
      • h) Asynchronism
        • Message queues
        • Task queues
        • Back pressure
      • i) Communication
        • TCP
        • UDP
        • REST
        • RPC
  • JUSTIFY [5 min]
    • Throughput of each layer
    • Latency caused between each layer
    • Overall latency justification

4.3 苹果电脑换芯及苹果放弃英特尔芯片的影响

以下两篇文件可以对苹果电脑，手机采用的芯片历史有一个详细的了解，也可以了解各大公司的战略布局