Given an array of integers target. From a starting array, A consisting of all 1’s, you may perform the following procedure :

• let x be the sum of all elements currently in your array.
• choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
• You may repeat this procedure as many times as needed.

Return True if it is possible to construct the target array from A otherwise return False.

Example 1:

Input: target = [9,3,5]
Output: true
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done


Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].


Example 3:

Input: target = [8,5]
Output: true


Constraints:

• N == target.length
• 1 <= target.length <= 5 * 10^4
• 1 <= target[i] <= 10^9

Solution: Backwards Simulation

Start with the largest number in the array, since it should be the sum of all previous numbers.

[9,3,5] => [9 – (3+5), 3, 5] => [1, 3, 5] => [1, 3, 5 – (1+3)] => [1, 3, 1] => [1, 3 – (1+1), 1] => [1,1,1] done

Time complexity: O(n + log(n*t)*logn)
Space complexity: O(n)

C++

Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayiand ends at endDayi.

You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.


Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4


Example 3:

Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4


Example 4:

Input: events = [[1,100000]]
Output: 1


Example 5:

Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
Output: 7


Constraints:

• 1 <= events.length <= 10^5
• events[i].length == 2
• 1 <= events[i][0] <= events[i][1] <= 10^5

Solution: Greedy

Sort events by end time, for each event find the first available day to attend.

Time complexity: O(sum(endtime – starttime)) = O(10^10)
Space complexity: O(max(endtime – starttime) = O(10^5)

Python

We can use a TreeSet to maintain the open days and do a binary search to find the first available day.

Time complexity: O(nlogd)
Space complexity: O(d)

C++

Implement the class ProductOfNumbers that supports two methods:

1. add(int num)

• Adds the number num to the back of the current list of numbers.

2. getProduct(int k)

• Returns the product of the last k numbers in the current list.
• You can assume that always the current list has at least k numbers.

At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example:

Input
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output: [null,null,null,null,null,null,20,40,0,null,32]
Explanation:
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.getProduct(2); // return 20.
The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32


Constraints:

• There will be at most 40000 operations considering both add and getProduct.
• 0 <= num <= 100
• 1 <= k <= 40000

Solution: Prefix product

Use p[i] to store the prod of a1*a2*…ai
p[i] = ai*p[i-1]
If ai is 0, reset p = [1].
Compare k with the len(p), if k is greater than len(p) which means there is 0 recently, return 0.
otherwise return p[n] / p[n – k – 1]

Time complexity: Add: O(1), getProduct: O(1)
Space complexity: O(n)

C++

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.

Return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.


Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0


Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3


Example 4:

Input: grid = [[-1]]
Output: 1


Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

Solution 1: Brute Force

Time complexity: O(m*n)
Space complexity: O(1)

Solution 2: Find the frontier

Time complexity: O(m+n)
Space complexity: O(1)

C++

Part 1. 收入的组成

1. 基本工资（Base salary）：基本工资主要由级别决定，不同级别之间的差距不大。每级可能差10%左右。
2. 奖金（Bonus）：和基本工资挂钩，是基本工资的10%～25%，主要由公司业绩和个人绩效决定。
3. 股票（RSU）：一般来说股票每年都会refresh，每次奖励都要要分4年来发，有些公司每年25%，有些公司第一年只有5%。如果你提前离职，后面的股票就都没了。奖励时的金额和级别/个人表现有关，最后（卖出时）的收入则和公司股价直接成正比。比如奖励$10,000的RSU，近期公司股价$50，则为200股。4年后公司股价涨到$100，就变成了$20,000（这里有没有考虑税的问题）。对于高级别员工来说，股票是大头，可能比基本工资还要高。

1. 签字费（Sign-on Bonus）：$20,000 ~$100,000+ 不等，不同厂家之间区别很大。通常需要保证工作一年以上，不然需要退回。
2. 搬家费（Relocation Bonus）：$3,000 ~$10,000 不等。可用于搬场，汽车运输，租车等。
3. 临时居住（Corporate housing）：有些公司对外地/外国员工提供14-30天不等的临时居住，通常为酒店式公寓。名义价值$250+/天。也就是$3,500 ~ $7,500的价值。利用这个时间段去找公寓就不会显得手忙脚乱，同时也可以剩下一笔小钱。湾区一居室的公寓基本上都要$3,000/月，和别人合租的话可以降低到$1,500~$2,000/月。当然住私人、远一些或者条件比较差的（比如车库）可以再降低到$1,000/月。 福利 1. 401K 公司匹配（Employer match）401K是美国的退休计划（养老金），主要由个人出资（每年有上限），可以用来投资基金，实现财富增长，并提供一部分税收优惠。公司会匹配员工的投资，通常为30%～50%（50%是上限）。目前401K每年上限为$19,500，公司最多匹配$9,750。如果你不存放401K，这笔钱就没有了。 2. 免费午餐：天下哪有免费午餐？湾区软件公司就有。 不仅午餐免费，早餐，晚餐，饮料，水果，零食等统统免费。有些甚至连周末也有。每顿饭的名义价值大概在$15~$20左右。如果三餐都在公司吃：$17.5*20*3 = $1,050/月。如果你自己不喜欢做饭，也不想出去下馆子，在公司吃饭可以省下不少钱。 3. 医疗保险：之前视频中没有提到，美国医疗特别贵，所以保险也很贵，一年也要好几千块美元。 4. 交通补贴：免费的班车，公共交通补贴，打车补贴等。 Part 2. 大厂横向比较 选取了Facebook, Microsoft, Apple, Google 和 Amazon等传统大厂来比较，也有收入比它们高的。这里只比较了base + bonus + stock。所有数据全部来自于 levels.fyi 网站。 首先每家公司对级别的要求/定义不太相同，我们先看一张天梯图： Entry level: Apple ICT2/ICT3, Amazon: L4, Google L3, Facebook E3, Microsoft 59,60 Intermediate level: Apple ICT3, Amazon: L5, Google L4, Facebook E4, Microsoft 61,62 Senior level: Apple ICT4, Amazon L6, Google L5, Facebook E5, Microsoft 63,64 从这张图就可以明显的看到，绿色部分的base salary增加的不多，主要是蓝色的stock部分随着级别呈指数增长。同时我也给出了近5年该公司的股票走势。长期持有增长型公司的股票收入相当可观。 微软相对前面两家来说package就要低一些，主要是stock比较少。 亚麻和苹果作为两家完全不同类型的公司没想到在薪资方面倒是出奇的统一。 Part 3. 税务问题 最后我们来简单聊一下税务问题。首先是免费声明：花花无法为你提供任何税务方面的服务和建议，下面的所有内容仅供参考，不能作为你报税依据。 我们假设一年的总收入为$200,000，单身，位于加州。

1. 401K pre-tax, $20,000 2. Standard deduction$12,000

Mission News Theme by Compete Themes.