万柳杂文集

坎通纳演讲

As flies to wanton boys we are to the gods.
They will kill us for the sport.
Soon the science will not only be able to slow down the ageing of cells, soon the science will fix the cells to the state.
And so, we become eternal.
Only accidents, crimes, wars, will still kill us.
But unfortunately, crimes and wars will mutiply.
I love football.
Thank you.

–埃里克 坎通纳 于公元2019年8月30日

万柳杂文集

序

青春的花瓣
–曾艳芬

温柔的微风 嘈杂的午后 昏昏沉沉做了一个梦
梦到多年以后 我褪去青涩懵懂
忙碌的工作 强装的笑容 浮沉在那茫茫人海中
拥有许多脸孔 内心却依然空洞
在夜里独自一人的时候 仿佛即将要被黑暗吞没
那伸出的双手 回应只有沉默 失重坠落
樱花的绽放斑驳这孤单的三月
而你的出现也照亮了这无尽的黑夜
然而花瓣一片一片 终将都凋谢
原来一切 都有期限
樱花的绽放芬芳了整座沉闷的花园
而你的微笑也柔软了一片压抑的蓝天
感谢苍白的青春里能与你擦肩
即使不能 一起永远
也无悔无怨
在花季过后的樱花还残留一地碎片
在你离开后我的心也只剩一片的残缺
花会盛开也会凋谢 有苦也有甜
爱恨之间 不会永远
在时间逝去后再梦回那有你的瞬间
在梦醒的时分微笑着却早已泪流满面
睁开双眼才发现已经到暮年
窗外蓝天 樱花正艳
为青春祭奠

2019.04.30 00:06 抄写

The Technical Interview Cheat Sheet

Studying for a Tech Interview Sucks, so Here’s a Cheat Sheet to Help

This list is meant to be a both a quick guide and reference for further research into these topics. It’s basically a summary of that comp sci course you never took or forgot about, so there’s no way it can cover everything in depth. It also will be available as a gist on Github for everyone to edit and add to.

Data Structure Basics

Array

Definition:

  • Stores data elements based on an sequential, most commonly 0 based, index.
  • Based on tuples from set theory.
  • They are one of the oldest, most commonly used data structures.

What you need to know:

  • Optimal for indexing; bad at searching, inserting, and deleting (except at the end).
  • Linear arrays, or one dimensional arrays, are the most basic.
    • Are static in size, meaning that they are declared with a fixed size.
  • Dynamic arrays are like one dimensional arrays, but have reserved space for additional elements.
    • If a dynamic array is full, it copies it’s contents to a larger array.
  • Two dimensional arrays have x and y indices like a grid or nested arrays.

Big O efficiency:

  • Indexing: Linear array: O(1), Dynamic array: O(1)
  • Search: Linear array: O(n), Dynamic array: O(n)
  • Optimized Search: Linear array: O(log n), Dynamic array: O(log n)
  • Insertion: Linear array: n/a Dynamic array: O(n)

Linked List

Definition:

  • Stores data with nodes that point to other nodes.
    • Nodes, at its most basic it has one datum and one reference (another node).
    • A linked list chains nodes together by pointing one node’s reference towards another node.

What you need to know:

  • Designed to optimize insertion and deletion, slow at indexing and searching.
  • Doubly linked list has nodes that reference the previous node.
  • Circularly linked list is simple linked list whose tail, the last node, references the head, the first node.
  • Stack, commonly implemented with linked lists but can be made from arrays too.
    • Stacks are last in, first out (LIFO) data structures.
    • Made with a linked list by having the head be the only place for insertion and removal.
  • Queues, too can be implemented with a linked list or an array.
    • Queues are a first in, first out (FIFO) data structure.
    • Made with a doubly linked list that only removes from head and adds to tail.

Big O efficiency:

  • Indexing: Linked Lists: O(n)
  • Search: Linked Lists: O(n)
  • Optimized Search: Linked Lists: O(n)
  • Insertion: Linked Lists: O(1)

Hash Table or Hash Map

Definition:

  • Stores data with key value pairs.
  • Hash functions accept a key and return an output unique only to that specific key.
    • This is known as hashing, which is the concept that an input and an output have a one-to-one correspondence to map information.
    • Hash functions return a unique address in memory for that data.

What you need to know:

  • Designed to optimize searching, insertion, and deletion.
  • Hash collisions are when a hash function returns the same output for two distinct outputs.
    • All hash functions have this problem.
    • This is often accommodated for by having the hash tables be very large.
  • Hashes are important for associative arrays and database indexing.

Big O efficiency:

  • Indexing: Hash Tables: O(1)
  • Search: Hash Tables: O(1)
  • Insertion: Hash Tables: O(1)

Binary Tree

Definition:

  • Is a tree like data structure where every node has at most two children.
    • There is one left and right child node.

What you need to know:

  • Designed to optimize searching and sorting.
  • A degenerate tree is an unbalanced tree, which if entirely one-sided is a essentially a linked list.
  • They are comparably simple to implement than other data structures.
  • Used to make binary search trees.
    • A binary tree that uses comparable keys to assign which direction a child is.
    • Left child has a key smaller than it’s parent node.
    • Right child has a key greater than it’s parent node.
    • There can be no duplicate node.
    • Because of the above it is more likely to be used as a data structure than a binary tree.

Big O efficiency:

  • Indexing: Binary Search Tree: O(log n)
  • Search: Binary Search Tree: O(log n)
  • Insertion: Binary Search Tree: O(log n)

Search Basics

Definition:

  • An algorithm that searches a tree (or graph) by searching levels of the tree first, starting at the root.
    • It finds every node on the same level, most often moving left to right.
    • While doing this it tracks the children nodes of the nodes on the current level.
    • When finished examining a level it moves to the left most node on the next level.
    • The bottom-right most node is evaluated last (the node that is deepest and is farthest right of it’s level).

What you need to know:

  • Optimal for searching a tree that is wider than it is deep.
  • Uses a queue to store information about the tree while it traverses a tree.
    • Because it uses a queue it is more memory intensive than depth first search.
    • The queue uses more memory because it needs to stores pointers

Big O efficiency:

  • Search: Breadth First Search: O(|E| + |V|)
  • E is number of edges
  • V is number of vertices

Definition:

  • An algorithm that searches a tree (or graph) by searching depth of the tree first, starting at the root.
    • It traverses left down a tree until it cannot go further.
    • Once it reaches the end of a branch it traverses back up trying the right child of nodes on that branch, and if possible left from the right children.
    • When finished examining a branch it moves to the node right of the root then tries to go left on all it’s children until it reaches the bottom.
    • The right most node is evaluated last (the node that is right of all it’s ancestors).

What you need to know:

  • Optimal for searching a tree that is deeper than it is wide.
  • Uses a stack to push nodes onto.
    • Because a stack is LIFO it does not need to keep track of the nodes pointers and is therefore less memory intensive than breadth first search.
    • Once it cannot go further left it begins evaluating the stack.

Big O efficiency:

  • Search: Depth First Search: O(|E| + |V|)
  • E is number of edges
  • V is number of vertices
  • The simple answer to this question is that it depends on the size and shape of the tree.
    • For wide, shallow trees use Breadth First Search
    • For deep, narrow trees use Depth First Search

Nuances:

  • Because BFS uses queues to store information about the nodes and its children, it could use more memory than is available on your computer. (But you probably won’t have to worry about this.)
  • If using a DFS on a tree that is very deep you might go unnecessarily deep in the search. See xkcd for more information.
  • Breadth First Search tends to be a looping algorithm.
  • Depth First Search tends to be a recursive algorithm.

Efficient Sorting Basics

Merge Sort

Definition:

  • A comparison based sorting algorithm
    • Divides entire dataset into groups of at most two.
    • Compares each number one at a time, moving the smallest number to left of the pair.
    • Once all pairs sorted it then compares left most elements of the two leftmost pairs creating a sorted group of four with the smallest numbers on the left and the largest ones on the right.
    • This process is repeated until there is only one set.

What you need to know:

  • This is one of the most basic sorting algorithms.
  • Know that it divides all the data into as small possible sets then compares them.

Big O efficiency:

  • Best Case Sort: Merge Sort: O(n)
  • Average Case Sort: Merge Sort: O(n log n)
  • Worst Case Sort: Merge Sort: O(n log n)

Quicksort

Definition:

  • A comparison based sorting algorithm
    • Divides entire dataset in half by selecting the average element and putting all smaller elements to the left of the average.
    • It repeats this process on the left side until it is comparing only two elements at which point the left side is sorted.
    • When the left side is finished sorting it performs the same operation on the right side.
  • Computer architecture favors the quicksort process.

What you need to know:

  • While it has the same Big O as (or worse in some cases) many other sorting algorithms it is often faster in practice than many other sorting algorithms, such as merge sort.
  • Know that it halves the data set by the average continuously until all the information is sorted.

Big O efficiency:

  • Best Case Sort: Merge Sort: O(n)
  • Average Case Sort: Merge Sort: O(n log n)
  • Worst Case Sort: Merge Sort: O(n^2)

Bubble Sort

Definition:

  • A comparison based sorting algorithm
    • It iterates left to right comparing every couplet, moving the smaller element to the left.
    • It repeats this process until it no longer moves and element to the left.

What you need to know:

  • While it is very simple to implement, it is the least efficient of these three sorting methods.
  • Know that it moves one space to the right comparing two elements at a time and moving the smaller on to left.

Big O efficiency:

  • Best Case Sort: Merge Sort: O(n)
  • Average Case Sort: Merge Sort: O(n^2)
  • Worst Case Sort: Merge Sort: O(n^2)

Merge Sort Vs. Quicksort

  • Quicksort is likely faster in practice.
  • Merge Sort divides the set into the smallest possible groups immediately then reconstructs the incrementally as it sorts the groupings.
  • Quicksort continually divides the set by the average, until the set is recursively sorted.

Basic Types of Algorithms

Recursive Algorithms

Definition:

  • An algorithm that calls itself in its definition.
    • Recursive case a conditional statement that is used to trigger the recursion.
    • Base case a conditional statement that is used to break the recursion.

What you need to know:

  • Stack level too deep and stack overflow.
    • If you’ve seen either of these from a recursive algorithm, you messed up.
    • It means that your base case was never triggered because it was faulty or the problem was so massive you ran out of RAM before reaching it.
    • Knowing whether or not you will reach a base case is integral to correctly using recursion.
    • Often used in Depth First Search

Iterative Algorithms

Definition:

  • An algorithm that is called repeatedly but for a finite number of times, each time being a single iteration.
    • Often used to move incrementally through a data set.

What you need to know:

  • Generally you will see iteration as loops, for, while, and until statements.
  • Think of iteration as moving one at a time through a set.
  • Often used to move through an array.

Recursion Vs. Iteration

  • The differences between recursion and iteration can be confusing to distinguish since both can be used to implement the other. But know that,
    • Recursion is, usually, more expressive and easier to implement.
    • Iteration uses less memory.
  • Functional languages tend to use recursion. (i.e. Haskell)
  • Imperative languages tend to use iteration. (i.e. Ruby)
  • Check out this Stack Overflow post for more info.

Pseudo Code of Moving Through an Array (this is why iteration is used for this)

1
2
3
4
5
6
7
8
Recursion                         | Iteration
----------------------------------|----------------------------------
recursive method (array, n)       | iterative method (array)
  if array[n] is not nil          |   for n from 0 to size of array
    print array[n]                |     print(array[n])
    recursive method(array, n+1)  |
  else                            |
    exit loop                     |

Greedy Algorithm

Definition:

  • An algorithm that, while executing, selects only the information that meets a certain criteria.
  • The general five components, taken from Wikipedia:
    • A candidate set, from which a solution is created.
    • A selection function, which chooses the best candidate to be added to the solution.
    • A feasibility function, that is used to determine if a candidate can be used to contribute to a solution.
    • An objective function, which assigns a value to a solution, or a partial solution.
    • A solution function, which will indicate when we have discovered a complete solution.

What you need to know:

  • Used to find the optimal solution for a given problem.
  • Generally used on sets of data where only a small proportion of the information evaluated meets the desired result.
  • Often a greedy algorithm can help reduce the Big O of an algorithm.

Pseudo Code of a Greedy Algorithm to Find Largest Difference of any Two Numbers in an Array.

1
2
3
4
5
6
greedy algorithm (array)
  var largest difference = 0
  var new difference = find next difference (array[n], array[n+1])
  largest difference = new difference if new difference is > largest difference
  repeat above two steps until all differences have been found
  return largest difference

This algorithm never needed to compare all the differences to one another, saving it an entire iteration.

origins: https://gist.github.com/TSiege/cbb0507082bb18ff7e4b#file-the-technical-interview-cheat-sheet-md

Blog

赵老改应该买个怎样的笔记本电脑

你也不玩游戏，只是正常用，所以没有挑贵的，觉得还是以轻便为主，电池能用住为主。性价比不是特别高。用不了6000块钱。Dell吧，就是电池老化的快，我现在的笔记本电池只能用1个小时，其他的还是不错的。具体你还是到实体店看一下，看看外观什么的。

这个东西三好街的幌子很多，给你看了三款dell的二款华硕的一款acer的，按照推荐的顺序只给你列出四个，我比较喜欢第一个。另外这个东西会不会大陆和香港走的是两种型号也说不定，大陆有的香港不一定有，具体的还是去看看吧。每个型号下面我给你标出我认为够用的配置参数，你到时比对即可，不好说会不会完全一样。具体配置上大约就是以下给出的为基础，大同小异，别让他们忽悠了。价格上，我不知道香港的笔记本是什么行情，我认为只能便宜不能贵，第一个型号的4000人民币左右还是合算的。

1.戴尔Vostro 成就 14 5000（14-5480D-3528R）

显示屏：14英寸 1366*768

CPU：Intel 酷睿i5 5200U 主频2.2GHz 睿频：2.7GHz 双核心/四线程

内存：4GB DDR3（L）1600MHz

硬盘：500GB+8GB 机械与固态混合硬盘（HDD+闪存）

显卡： NVIDIA Geforce 830M 2GB

没有光驱
三好街报价4500人民币，还送一个4GB的内存，加起来就是8G了，买之前考虑一下别买贵了。

2.戴尔Inspiron 灵越 14 5000（INS14UD-1528R）

显示屏：14英寸 1366*768

CPU：Intel 酷睿i5 5200U 主频2.2GHz 睿频2.7GHz 双核心/四线程

内存：4GB DDR3（L）1600MHz

硬盘：500GB 机械 硬盘

显卡： NVIDIA Geforce 920M＋Intel GMA HD 5500（独立显卡+集成显卡）2GB

有光驱

三好街报价3980人民币，还送一个4GB的内存，加起来就是8G了，买之前考虑一下别买贵了。

3.华硕U303LN4210

显示屏：13.3英寸 1920*1080

CPU：Intel 酷睿i5 4210U 主频1.7GHz 睿频2.7GHz 双核心/四线程

内存：4GB DDR3（L）1600MHz

硬盘：500GB 机械硬盘

显卡： NVIDIA GeForce 840M＋Intel GMA HD 4400（独立显卡+集成显卡）2GB

没有光驱

忘了报价多少钱了，没记住，好奇问问吧。

4.还有一个华硕的X55LTV？，但是可能型号比较新或者是我记错了，网上并没有找到准确的配置参数，大概是：

显示屏：15英寸

CPU：Intel 酷睿i5 5200U 主频2.2GHz 睿频2.7GHz 双核心/四线程

内存：4GB DDR3（L）1600MHz

硬盘：1TB 机械硬盘

显卡： NVIDIA GeForce 930 2GB

没注意有没有光驱

三好街报价4200人民币，具体型号到实体店问问吧。

另：光驱这个东西我认为是没有用的，不知道你现在还有什么地方需要光驱吗，没有光驱的电脑会薄一些。

买的时候，可以问问能不能花钱延保，延保包不包括大陆地区，一般自带保修是1-2年，如果价钱合理花点钱延个2年也可

这些显卡在你打英雄联盟时，据说开不了所有的特效

如果都不喜欢就再看看

建议飞机票不当钱的土豪买 Macbook Pro