ARTS 第三周

ARTS是什么？
Algorithm：每周至少做一个leetcode的算法题；
Review：阅读并点评至少一篇英文技术文章；
Tip/Techni：学习至少一个技术技巧；
Share：分享一篇有观点和思考的技术文章。

一、Algorithm

Question: 636 Exclusive Time of Functions (Medium)
给定N个运行在单CPU的函数的运行时间log，找到每个函数的实际运行时间。
每个函数都有唯一的ID，编号为0到n-1，函数可以被递归的调用。
log为字符串，格式如下：function_id:start_or_end:timestamp。比如“0：start：0” 表示函数0 从时间0开始运行。“0：end：2”表示函数0在时间2结束。

#input and output example 
input:
n = 2
logs = 
["0:start:0",
 "1:start:2",
 "1:end:5",
 "0:end:6"]
Output:[3, 4]

Solution：
函数的调用，本身就是用stack来实现的。如果用堆来实现，首先从list[0]一次进行入栈，栈中保存的是进程编号，如果动作是start，且栈中不为空，那么直接入栈，且推的最上面一个进程运行时间为之前现在的时间减去上一次的时间。如果动作是stop，那么直接栈中最上面一个进程的运行时间为现在的时间减去上一次时间+1，然后出栈。

比如上面的case：
0:start:0 ans = [0,0] stack.top=0,curTime=0
1:start:2 ans = [2-0,0] stack.top=1,curTime=2
1:end:5 ans= [2,4] stack.top=0,curTime=6
0:end:6 ans=[6-6+1+2,4] stack=None, curTime=7
Output=[3,4]

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        ans = [0]*n
        s = []
        curTime = 0
        
        for i in range(len(logs)):
            curLog = logs[i].split(":")
            curId = int(curLog[0])
            status = curLog[1]
            nextTime = int(curLog[2])
            
            if (status == "start"):
                if (s):
                    ans[s[-1]] += nextTime - curTime
                s.append(curId)
                curTime = nextTime
            else:
                ans[s[-1]] += nextTime - curTime + 1
                s.pop()
                curTime = nextTime + 1
            
        return ans

Runtime: 76 ms, faster than 23.33% of Python3 online submissions for Exclusive Time of Functions.
Memory Usage: 13.1 MB, less than 6.90% of Python3 online submissions for Exclusive Time of Functions.
这是最终的结果，内存和运行时间都不是很理想。理论运行时间为O(N)，空间为O(N)。但是看了提交的运行时间比较短的结果，代码差不多，很迷。

二、Review：
Genuinely useful career resources for self-taught developers

自学的开发者的有用的资源推荐

1. 社区

• learnprogramming subreddit 挂逼了
• Stackoverflow.com
• Hacker News
• Quora programming community
• Slashdot
• Sourceforge

2. 写代码并构建自己的作品

• GitHub
• Bitbucket

3. 咨询并参与到wiki建设中

• Learnprogramming Wiki
• Wikibooks
• Kaggle Wiki

4. 通过不同的途径找到工作机会

• LinkedIn
• Hacker News
• AngelList

三、Tips
在使用vim的过程中，因为有快捷键，所以vim能比其他大部分的编辑器都要高效。比如复制，粘贴，光标快速移动，行内移动等等。

而Shell也是一样有快捷键的。

• ctrl+r：之后再输入命令，能够快速匹配历史命令
• clear：清理屏幕
• 上箭头或者ctrl+p：上一条命令
• 下箭头或者ctrl+n：下一条命令
• !!：重复上一条命令，其他的命令诸如!$,!^,!N,!str，这类不常用的就列了。
• ctrl+h：向前删除一个字符，等同于delete
• ctrl+d：向后删除一个字符，等同mac fn+delete
• ctrl+w：删除光标前一个单词
• ctrl+u: 删除光标前面所有内容
• ctrl+k：删除光标后面所有内容
• ctrl+a: 移动光标到开始（a为第一个字母）
• ctrl+3: 移动光标到结束（end）
• ctrl+f: 光标前移一次
• ctrl+b：光标后移一次
• alt+f：光标前移一个单词
• alt+b：光标后移一个单词
• ctrl+xx：行首到当前光标替换

四、Share
我的抖音账号只是用手机号码登录的，没有用微信登录，也没有打开通讯录权限。但是在可能认识的人中，给不推荐了不少微信好友。一直很感兴趣抖音、多闪等是如何推荐微信好友给用户的，分别在keso和可能吧公众号都看到了抖音会主动抓取用户的关系链。以下是根据多少搜索的信息总结，微信关系链获取的方式：

假如A分享了一个链接到微信，分享的链接中带有A的标识；如果其他的人B授权微信登录并通过微信浏览器访问了，那么抖音会认为B和A是相关的，可能是群友，也可能是二度关系。如果A和B这类的交互比较多，大概率就是朋友了，如果能收集到足够多的数据，就能计算用户大多数的关系链了。