CS专科／在职多年／刷题+健身+学AI

71        Simplify Path 这道题没有很大的普遍意义，只是应用stack的操作还尚有练手目的。找到+标记开头的可能的斜杠，都跳过去+记录第一个非斜杠的字母；再跳过+标记尾部可能的斜杠；从而找到本轮的整个directory name；要去除冗余，即碰到“.”，什么都不需要干，直接开始寻找下一个element。
43        Multiply Strings 汗颜：我的思路太死板，简直就是把算数草稿翻译成c++！？网上选了个最清楚解法，notePro里有图示，乘数是外循环，被乘数是内循环。关键不同于我的解法是：用result【i+j】只记录2个0到9的数的乘积的个位数，进位暂不在result数组中的记录，只存在局部播变量 carry中，将由下一轮inner for循环在line#xx处理与之相加操作。
68       Text Justification：Hard题，没参考别人的答案，自力更生，一共40行！我是先用一个辅助int数组记录wordCounter所有words的长度（关键是我给每个word都在尾部人为地加一个空格），这样省掉很多之后的“xxx.size()”调用，而且最后一行无需额外处理，因为已经是left-justified。所以之后只要注意#1: 每当扫描到每行最右侧的end 位置上的判断时长度时，使用(L + 1)；#2：因为是用greedy思路，所以必须贪心循环到越界一步，循环退出后要恢复end 指针和 current_line_length - = wordCounter[ - - end ];

现在抓紧时间去做20个引体向上 + 20个吊环俯卧直臂慢起。明天 on bording ，已经1:30AM了...

Tsien 发表于 2017-8-28 11:23
引体向上20.。。。666

@Tsien 您之前的帖子quote "我之前在coursera上了两门课，machine learning foundation和Andrew的machine learning，我就得很有意义"

我正在蠢蠢欲动ML
今年stanford李菲菲的课怎么样？youtube里刚挂上去的 http://cs231n.stanford.edu
本人时间特紧，希望前辈给点意见，多谢！

lz标题党！我想看的健身+学AI部分呢。。

fentoyal 发表于 2017-8-29 01:43
lz标题党！我想看的健身+学AI部分呢。。

AI 没动力了！估计学了没人要。@Tsien 这种牛人要靠近AI都不易，那我呢？
健身我从没断过，想看细节吗，我将来私下发图给你
PS 根据您的“～从不放过hard～”建议，我每天争取干掉至少一道hard，觉得这个比学AI来说更tangible，priority更高；不就是120++ 道吗，至少有个模糊上限。

死磕一道hard， “Kth element in 2 sorted array”的变形。下午突然收到ebay的"we don't see a fit" email，不会呀？！！！第二面时那三哥明明同意我所有的解答，最后一问时，我的回答三哥都觉得exceed exceptions; 既然是HR在LinkedIn上主动找到我，那我就给HR回email抒发了一下感受... 靠，居然还自己耿耿于怀了一晚上，严重影响今天的刷题效果！
刚刚夜里起来完成计划，在马桶上看看youtube，看到华春莹的发言后，我恍然大悟：原来三哥们本周团结起来报复老中，洞朗撤军多丢三哥们的脸呀！没脸也要找点脸！！！不过，paypal夜里11点来email要求onsite。东方不亮西方亮！

LC 65  Valid Number：没明白为什么被分类成hard？！顶破天也就是medium吧！要是被我碰上，一定别忘了先跟interviewer讨论3分钟各种允许的valid formats 然后从左到右，按照讨论好的条件 sequentially 把各类用for／while 走通；关键的是整数和分数部分的判断存储boolean值，要在最终扫到源串尾部时同时用AND逻辑确定return 真伪。

LC 534 Design TinyURL：这周有2个onsite，先把这题翻了翻。没什么新鲜的，都基本是2个主要 server instance／layer，一个负责接收requests，另一个负责处理millions of concurrent inputs 形成的冲突，当然需要及时快速处理。
LC 72    Edit Distance 居然DP书本上的照抄？！LC有点糊弄事。
LC 161  One Edit Distance  不用DP 但我对串的各种操作天生厌烦。几个复习要点：先把冗余去掉，保证下面处理的是s长于t的情形，并且保证下面都是s和t作为原始参数2者长度相等或差为1的情形；关键操作=“在短的串上insert长串的对应char ／长串删掉短串的char”，然后判断这个关键操作到底在整个扫描过程中是否曾经发生过一次而且仅一次。

PS 还把“ Kth Largest／smallest Element in M Sorted Arrays ” 通了通，作为昨天 LC 4 的补充。LC 4 好久不见了，有点模糊，希望这次是really LAST time going over this shit!

昨天累的要死，又是drug screening 又是 onboarding， 下午还去一个onsite  http://www.1point3acres.com/bbs/thread-291030-1-1.html

LC 127 Word Ladder : 本来LC 里graph的题就少，这道算是稍稍有点意思的。典型的BFS，但graph的扩展和frontier 的生长必需根据给定的dictionary 和字母表对每一个frontier里的单个字母表《穷举比较》实现。注意：#1 从dictioinary删除word 即可标注visited nodes，虽然这样做很懒，但快速简洁；#2 尽量用c++中unordered_set 和queue API，否则写起来太费事，特别是queue《由于本题队列里priority只是node's age，而age对本题没用处，所以可以用普通array代替》。我本人对graph，shortest path的题有天生好感，嘻嘻！没明白为什么通过了低于20%？？？只分类成medium ？
LC 126 Word Ladder II ：搞了一半儿，争取今天做出个自己满意的解法。

没锻炼，下午回家就睡，睡到3am才醒。罪过呀！

LC 126 Word Ladder II： 终于把这只老虎搞定！https://youtu.be/rhTGAiVUBA8  
下午回头来这里编辑补写算法细节

轻度锻炼：引体向上 + 俯卧飞鸟

先来补昨天的账
LC 126 Word Ladder II： 算法细节
方法A：普通的BSF结构循环，只是当找到target word时就可以终止，因为是shortest path类似的要求，所以没有必要继续循环找下一层frontier （要留意在每次开始新的frontier 搜索前要把老一轮frontier 的words从字典里删去，避免cycles ）；使用类似adjency list的二维数组存储每层的搜索结果，但在输出path时必须向source word进阶性回溯，所以就陷入了我特别不喜欢的反向DFS！！！
方法B：还是上面的基本思路，但frontier不仅是最前沿的nodes，而是由所有能到达前沿nodes的“扇形”paths组成的集合；这样稍微复杂点的data structure就完全避免上一种方法的DFS回溯寻找源word的苦难之旅； 但我的代码还是比较臃肿，过几天要用fresh eyes重新调整一下思路，看看能否减少繁多的book keeping variables。

LC   79   Word Search：一碰到递归，老是尼玛多多少少要出点低级错误！这次居然把base condition 给写反了！阿弥陀佛！
LC  208   Implement Trie (Prefix Tree)：为Word Search II 做准备。重温一下后看看网上其他人的方案，居然还有人用非递归来做！是不是有点自虐呀？？？

靠，这个周末天气热的居然到达38度，还没空调，怎么锻炼，可不是我自己找理由！

补充内容 (2017-9-4 09:43):
忘了提醒自己：凡是递归解法，如果自己在面试是一时想不清楚，时间又紧，就把能作为参数的变量统统塞进recursion函数 paramater list，然后再一边做一边想。大不了，完成后再把多余的参数划去。