KING

Chapter 12:

• undecidable decision problem不可解问题
  • 不是所有问题都能找到多项式级的算法
  • 有些问题甚至没有正确的算法

citadel onsite面试

• 结果是rejected

  面试流程

• 第一轮 hr发邮件通知说有一个技术面
  • 然后就会有一个技术人员打电话给你，然后面试一些技术方面的内容
  • 例如：
    • 如何找出两个只有一个field的数据库表的区别
    • 问了快排和归并的区别
    • 还有问mutex在什么时候用

Resize disk in OS X 10.10 Yosemite

• due to the update of OSX, we can not resize the disk after we split the disk in the first time.
• so we need to use some other command

what is pointer

• 形参
  • formal parameter
  • 定义时函数里面的变量
    • e.g int swao(int a, int b)
    • a和b就是形参
• 实参
  • actual parameter
  • 在主函数里面引用的
    • e.g swap(x,y)
    • x和y就是实参，实际的值

basic data structure and algorithm part2

图论

图的实现

• V为点的个数 E边的个数
• 邻接矩阵
  • 用一个n*n的矩阵
    • 第一列第二个为1的意思是
      • 第一个点和第二个点相连
      • 1为权值
  • O(V²)
  • 用一个二维数组实现
• 邻接表
  • 用一个n长度的数组
    • 然后每一个数组后面接的链表里面存着
      • 这个数组index对应的点和哪些点相连
        • 这些点存在链表里面
  • O(V+E)
  • stl实现
  • 用vector list
    • 然后Node就是每个点
      • 如果有别的点和这个Node相连，就list.push_back(别的点)

basic data structure and algorithm part2

树

• trie树
  • 特点
    • 根节点没有字符，除此之外，所有节点都只有一个字符
    • 从根节点到任意叶子节点，都是一个独立的单词
    • 每个节点的子节点包含的后续字符串都是不一样的
  • 但是hash表不能一边建立索引一边查数据
    • trie树可以
      • 因为只要之前建立过的，再次出现的时候，就不会再增加
    • 而hash表建立的时候，不知道之前这个单词出现过，所以还是要建完表
      • 再搜索