Software Engineer

一些常规的操作， 参考这个视频。 基本位操作 把某一位变为1： def set_bit(x, position): mask = 1 << position return x | mask bin(set_bit(0b110, 0b101)) 输出0b100110. 因为x = 0b110 = 6, 翻转第五位，就用position = 0b101 = 5， 得到mask = 0b00100000, 用|把第五位变为1. 清除某一位（1变0)： def clear_bit(x, position): mask = 1 << position return x & ~mask 通过XOR^和1来翻转某一位： def flip_bit(x, position): mask = 1 << position return x ^ mask 通过&1可以作为取位操作, 来判断某一位是否是1: def is_bit_set(x, position): shifted = x >> position return shifted & 1 0b1100110 >> 0b101 = 0b11, 0b11 & 0b01 = 1...

在很多语言中，字符char类型是八位, 那么可能取值有256种(-128 ~ -1, 0 ~ 127). 但是用二进制表示为0000 0000 ~ 1111 1111, 无符号整数的全部位都表示数值，而有符号数的最高位是符号位（0表示正数，1表示负数），所以实际表达数值的只剩下n-1位。这样理论上char的取值应该是1111 1111 = -127到0111 1111 = 127. 而-128 = 1 1000 0000需要9位来表达, 所以char是如何仅仅通过八位表达-128? 首先, 因为计算机只能做加法, 所以减法操作要转化为加法, 尝试将符号位参与运算, 1-1就转化为1 + (-1), 用二进制表达为0000 0001 + 1000 0001 = -2, 很明显是错的. 如果用原码表示, 让符号位也参与计算, 显然对于减法来说, 结果是不正确的. 这也就是为何计算机内部不使用原码表示一个数. 为了避免这种错误, 引入反码(正数的反码是其本身, 负数的反码是符号位不变, 其余位取反), 用-1的原码1000 0001的反码1111 1110来表达-1, 这样1 + (-1) = [0000 0001]反 + [1111 1110]反 = [1111 1111]反, 转为原码1000 0000 = -0. 发现用反码计算减法, 结果的真值部分是正确的....

Memory Bit. 0 or 1. Byte. 8 bits. Megabyte (MB). 1 million or $2^{20}$ bytes. Gigabyte (GB). 1 billion or $2^{30}$ bytes. 64-bit machine. We assume a 64-bit machine with 8 byte pointers (References). ・Can address more memory. ・Pointers use more space (some JVMs “compress” ordinary object pointers to 4 bytes to avoid this cost). Typical memory usage for primitive types and arrays primitive types (bytes): boolean 1 byte 1 char 2 int 4 float 4 long 8 double 8...

假如有两种交税方式： 每天付 3 金币 每次付的金币呈指数级增长，但通知付款频率呈指数级下降 第1天：付 1 第2天：付 2 (累计 3) 第4天：付 4 (累积 7) 第8天：付 8 (累积 15) 哪种付的钱比较少？ 第二种比较划算，本质上等同于每天付 2，就是amortized constant。 A more rigorous examination of amortized analysis is done here, in three steps: Pick a cost model (like in regular runtime analysis) Compute the average cost of the i’th operation Show that this average (amortized) cost is bounded by a constant. 类似的应用在Array list 扩容中提到的 geometric resizing 方法(实际也是Python list 使用的方法)有体现, 所以使用一个因数来扩容数组, 可以让 ArrayList 的 add操作变为 amortized constant time....

Resource and Reference: CS61B Berkeley - Josh Hug Algorithms Princeton - ROBERT SEDGEWICK, KEVIN WAYNE 效率来源两个方面: 编程成本: 开发程序需要多长时间？代码是否容易阅读，修改和维护（大部分成本来自维护和可扩展性）？ 运行成本: 程序需要多长时间运行 (Time complexity)？ 需要多少内存 (Space complexity)？ Asymptotic Analysis Care about what happens for very large N (asymptotic behavior). We want to consider what types of algorithms would best handle scalability - Algorithms that scale well have better asymptotic runtime behavior. Simplification Summary Only consider the worst case. Pick a representative operation (aka: cost model) Ignore lower order terms Ignore multiplicative constants....

Stanford CS106B Programming Abstractions 和 CS106A 的学习笔记. 课程作业(cs106b spring 2017)实现代码见 https://github.com/ShootingSpace/cs106b-programming-abstraction Topics: A: Intro (by Java) B: Recursion, algorithms analysis (sort/search/hash), dynamic data structures (lists, trees, heaps), data abstraction (stacks, queues, maps), implementation strategies/tradeoffs Purposes become acquainted with the C++ programming language learn more advanced programming techniques explore classic data structures and algorithms and apply these tools to solving complex problems Reference Text Book: Data Structures & Algorithm Analysis in C++, 4th ed, by Mark A....

主要介绍： Hashcode（哈希码）与 equals（判断相等）的关系 Hashcode 方法的底层实现原理 开发中需要掌握的原则和方法 HashSet, HashMap, HashTable HashSet底层是调用HashMap. HashMap 使用hashCode和equals来进行对象比较。 拿HashSet和add()举例(其余的数据结构,和 remove, contains等方法类似): 假设HashSet里面已经有了obj1, 那么当调用HashSet.add(obj2)时: if (obj1 == obj2), 那么没有必要调用 hashCode(), 已经有了这个对象, 没必要添加了 else, if hashCode 不同，那么可以直接添加了, 没必要进一步调用 obj1.equals(obj2) 来判断对象是否相等 else hashCode 相同，那么需要进一步调用obj1.equals(obj2) 下面这段代码虽然 HashSet 只存了 a 对象，但当检查是否包含 b 对象时，返回true。 HashSet<String> wordSet = new HashSet<String>(); String a = "hello"; String b = "hello"; wordSet.add(a); return wordSet.contains(b); // return true 根据Javadoc for Set. adds the specified element e to this set if the set contains no element e2 such that (e==null ?...

测试 如何知道自己的程序是否真的在工作？在现实世界中，程序员相信他们的代码，因为代码通过了他们自己编写的测试。常用的测试有 Ad Hoc Testing， Unit test 和 Integration Testing。 Ad Hoc Testing，是指没有计划和记录的软件测试，除非发现缺陷，不然一般只运行一次。 Unit test 程序可分解为单元（或程序中可测试的最小部分），Unit test 严格测试代码的每个单元，最终确保项目正确运行。 Unit test 好处： Unit test 保证良好的代码结构（每个 method “只打一份工”），帮助我们较好地解析任务， 允许我们考虑每个方法的所有边界情况，并单独测试它们。 让我们每次只专注于一个单元，进行测试，debug，对准确度有信心后，再进行下一个单元的开发。相比于一次性写完所有代码，再测试debug，Unit test 减少了 debugging 时间。 坏处： 测试也要花时间 测试本身也是有可能出错的，测试可能不全面，不规范，或者有bug 有些单元是依赖于其他单元的 Unit testing 无法保证各个模块的交互，无法保证整个系统作为一个整体是否正常工作。 JUnit JUnit是一个给Java做测试的框架，由Erich Gamma（Design Patterns）和Kent Beck（eXtreme Programming）编写。 JUnit使用Java的 reflection 功能（Java程序可以检查自己的代码）和注释。 JUnit允许我们： 定义并执行测试和测试套件 使用测试作为规范的有效手段 使用测试来支持重构 将修改的代码集成到构建中 JUnit可用于多个IDE，例如BlueJ，JBuilder和Eclipse在一定程度上具有JUnit集成。 import org.junit.Test; import static org.junit.Assert.*; @Test public void testMethod() { assertEquals(<expected>, <actual>); } assertEquals测试一个变量的实际值是否等于它的期望值。 JUnit test 各个测试方法，必须是非静态的（JUnit的设计人员设计规定的）。...

Java 提供了 ArrayList, ArrayDeque 和 LinkedList 几个API. 队列 queue, 通俗的含义, 就是不能插队, 只能在末尾插入. 双端队列 Double Ended Queue (Deque) 是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩 –http://www.cplusplus.com/reference/deque/deque/ CS61b的project 1a需要实现两种双端队列（array based 和 linkedklist based）. 不同的API, 在考虑什么时候应该用哪个时, 我们需要考虑它们的性能差异: 搜索/定位：与LinkedList相比，ArrayList搜索更快。 ArrayList的get(int index)性能是O(1)的，而LinkedList的性能是O(n)。因为ArrayList基于array数据结构，可以直接用 array index 定位元素。 删除/插入：LinkedList 操作性能是O(1)，而ArrayList的性能从O(n)（删除/插入第一个元素）到O(n)（最后一个元素）都有可能。因为LinkedList的每个元素都包含两个指向其相邻前后元素的指针（地址），因此仅需要改变，被删节点的prev和next指针位置。而在ArrayList中，需要移动剩余元素，来重新填充array空间。 内存开销：LinkedList的每个元素都有更多的内存开销(额外的指针), 而ArrayLists没有这个开销。但是，ArrayLists需要占用初始容量。一般ArrayList的默认初始容量非常小（Java 1.4 - 1.8使用10）。但是，往ArrayLists添加元素时， 它可能会适当地增大容量，所以如果添加了很多元素，则必须不断调整数组的大小，那样也可能会导致元素频繁挪动位置。 综上所述： 如果在应用中需要频繁插入和删除，那么选择LinkedList。 假如一开始，就知道后面要添加大量元素，那就使用较高的初始容量来构造ArrayList。 大部分用例中, 相比LinkedList, 人们更偏爱ArrayList以及ArrayDeque。如果你不确定应该选哪个, 那么就直接考虑ArrayList吧(参考 https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist).

双向链表 Doubly Linked List 前面介绍过的单向链表有几个缺点. 第一个就是它的addLast操作非常慢。单向链表只有一个变量保存列表头的地址, 以及每个节点对后面节点的单向引用(链接). 对于很长的列表，addLast方法必须遍历整个列表, 直到找到列表末尾才能执行插入操作. 最直观的优化方案就是加个’车尾’ 这样我们就可以直接通过last.next引用末尾位置. 不过另一个问题并没有解决, 就是删除列表最后一项removeLast这个操作还是很慢。因为在目前的结构设计下, 我们需要先找到倒数第二项，然后将其下一个指针设置为null。而要找到倒数第二节点, 我们就得先找到倒数第三个节点…… 以此类推。也就是说，对于删除末尾的操作，还是要几乎遍历整个列表。 反方向的链接 基于前面单向链表构建双向链表, 一个比较有效的方法是额外为每个节点添加一个指向前面节点的链接 - 指针. public class OneNode { public OneNode prev; //指向前 public int item; public OneNode next; //指向后 } 增加这些额外的指针会导致额外的代码复杂度, 以及额外的内存开销, 这就是追求时间效率的代价. Sentinel 与尾节点 双向链表的一个设计初衷，就是为了解决单向链表针对列表末尾位置的操作效率不高的问题，除了sentinel和反方向的链接还不够，我们还需要一个节点（指针）能够直接帮我们定位到列表末端。可以考虑添加一个的尾节点last 这样的列表就可以支持O(1)复杂度的addLast,getLast 和 removeLast操作了。 循环双端队列 Circular double ended queue 上面的尾节点设计虽然没什么错误，但有点瑕疵：最后一个尾节点指针有时指向前哨节点，有时指向一个真正的节点。更好的方法是使双向链表首尾相连, 构成一个循环，即前后节点共享唯一的一个前哨节点。 这样的设计相对更整洁，更美观(主观上的), sentinel的prev就指向列表最后一个节点, sentinel的next指向列表第一个节点. public class LinkedListDeque<GType> { private class OneNode { public OneNode prev; public GType item; public OneNode next; public OneNode(OneNode p, GType i, OneNode n) { prev = p; item = i; next = n; } } } Sentinel’s forward link always points to the last element....