CMU课程15-721数据库系统设计(第三周)

CMU课程15-721最新一期开课啦!

课程安排

索引技术课程(三节)介绍的技术实际跟并发控制结合很紧密,接下来讨论查询相关技术(穿插了日志技术内容)

Query Execution & Scheduling

重点介绍查询执行与调度,特别是多用户DB中查询如何并行执行

处理进程模型:

  • 进程-woker 依赖OS调度,使用共享内存,例:DB2、Postgres、Oracle;还是因为当时没有linux设计
  • 进程池 CPU缓存支持不好
  • 线程-worker DB管控调度,新DB都用这个模型规避共享内存

利用多核并发加速执行:

  • Intra-Operator 在子集上独立运行相同函数(mapreduce)
  • Inter-Operator 运行类似流水线,做一部分工作(stream)

个人补充:MySQL仍然是一个线程完成一个work

补充一点内存访问架构(实际是体系结构中重要部分,由硬件设计决定)

  • UMA:多cpu与多内存都必须走中心bus
  • NUMA:几个cpu之间组成bus,cpu与内存一一对应(目前常用架构!)

数据分配策略:

  • 内存分配与cpu绑定,参考linux的move_pages
  • 使用malloc

将查询语句变为可调度的执行计划,OLTP简单,OLAP比较难。Hyper就是一个NUMA架构下多核横向分布动态调度架构:

Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age

每个核分配一个worker(并行),pull接收分配的任务,数据分布采用RR算法

Join Alogrithms I — Hashing

原先不懂为何hash join算法作为第一个项目作业,而不是在介绍这个之后再布置。后来发现实际上这里讲解的是最新研究的多核版本算法

Join Alogrithms II — Sort-Merge

Logging & Recovery I — Physical Logging

传统DB磁盘日志基于ARIES算法,使用fuzzy cp规则,管理Active Transan Table与Dirty Page Table,赋予LSN并在易失与非易失中都要维护,过程为:analysis,redo,undo。最慢的过程发生在其他事务等待log刷到磁盘。

mem DB就不需要维护Dirty Page Table,因为所有数据都在内存。undo记录也没必要存储。

实例是Silo系统,其将log,cp,恢复操作都并行化优化,论文将这些设计考虑与最终选择都讲解的非常清晰。

该系统假设每个CPU socket对应有一个存储设备。每个设备分配一个日志线程,CPU socket对应一组工作线程。日志线程每10个epoch创建一个文件,将旧日志文件重命名并记录最大epoch。日志维护两个队列:Free Buffers与Flushing Buffers。会有一个特殊日志线程跟踪最新已经持久化的epoch(即各个日志线程中持久化的epoch最大值),小于此epoch的事务信息才可以丢弃。

每个disk对应一个cp线程,该线程有可能因为分区而写多个文件(voltDB甚至直接使用MVCC的version来做cp),cp的频率。恢复也可以并行进行。使用YCSB和TPC-C测试,吞吐率损失10%,lantency没有统计。

Logging & Recovery II — Alternative Methods

讨论一下逻辑日志,内存checkpoint以及Facebook的快速恢复方法(共享内存恢复)。

OLTP中节点失效很少见(数据不大,通常<10个节点),因此比较适合使用逻辑日志,记录格式通常包括(存储方法名,输入参数,额外安全检测信息),注意逻辑日志协议设计要满足可确定性,因此需要:

  • 事务执行前顺序已经固定
  • 事务逻辑是确定的

voltDB设计日志协议:在事务运行前日志就已经记录命令,且此时顺序已经分配完毕(个人理解类似MySQL),cp操作由特殊事务进行并将系统切换为COW模式,另一个特殊线程负责扫描表并制作快照,无视cp发起后的所有变化操作;DBMS同步不需要2PC协议

CMU课程15-721数据库系统设计(第二个项目)

CMU课程15-721最新一期开课啦!

课程安排

Project #2 - Concurrent Index

实现一个支持无锁并发的BW树作为索引底层数据结构

  • PID到指针的映射表
  • 改动链
  • split/merge
  • 动态垃圾回收

论文中几个奇怪概念:

  • install CAS 即使用CAS操作来替换映射表中的项目
  • epoch机制 即使用版本号保证没有其他操作正在进行(可以执行物理删除)

实现要求:

  • 支持重复key且可以配置,如果配置为不允许则InsertEntry插入重复key的索引条目时返回false,且DeleteEntry只删除完全匹配的索引条目
  • 支持consolidation,需要考虑阈值
  • 支持split与merge,特别是并发插入与删除的情况
  • 应该有工具函数帮助测试结构完整性并可以修复,类似fsck
  • 支持动态垃圾回收,调用Cleanup函数进行物理释放,会使用GetMemoryFootprint统计内存情况
  • 支持reverse iterators并保证concurrent mutators正常工作

Profile方法

profile工具使用valgrind或perf

  1. valgrind

使用memcheck或callgrind动态检查:valgrind --tool=callgrind --trace-children=yes ./build/src/peloton -D data &> /dev/null&

  1. perf

通过收集linux的cpu周期计数实现,也支持收集其他事件
perf record -e cycles:u -c 2000

CMU课程15-721数据库系统设计(第一个项目)

CMU课程15-721最新一期开课啦!

课程安排

Project #1 - Hash Join Operator

做这个项目前必须了解几个join算法,问题是这些算法在本次课程里都没有讲解过。

1.嵌套循环连接(Nested Loops)

适用范围两个表, 一个叫外部表, 一个叫内部表。如果外部输入非常小,而内部输入非常大并且已预先建立索引,那么嵌套循环联接将特别有效率。循环嵌套连接查找内部循环表的次数等于外部循环的行数,当外部循环没有更多的行时,循环嵌套结束。

2.合并联接(Merge)

指两个表在on的过滤条件上都有索引, 都是有序的, 这样join时, sql server就会使用性能更好的Merge join算法。如果一个有索引,一个没索引,则会选择Nested Loops join算法。首先从两个输入集合中各取第一行,如果匹配,则返回匹配行。假如两行不匹配,则有较小值的输入集合+1。

3.哈希联接(Hash)

如果两个表在on的过滤条件上都没有索引, 则就会使用Hash join算法。也就是说, 使用Hash join算法是由于缺少现成的索引。

哈希匹配分为两个阶段,分别为生成和探测阶段:首先是生成阶段,将输入源中的每一个条目经过散列函数的计算都放到不同的Hash Bucket中;接下来是探测阶段,对于另一个输入集合,同样针对每一行进行散列函数,确定其所应在的Hash Bucket,在针对这行和对应Hash Bucket中的每一行进行匹配,如果匹配则返回对应的行。

同时做这个项目需要了解Peloton tile-based架构几个关键数据结构:

logical_tile设计 [backend/executor/logical_tile]

其中

  • position_lists_vector<vector<oid_t>> 用来描述tiles/colums, 例(1,2,3),(1,1,1)
  • schema_vector<LogicalTile::ColumnInfo> 用来描述logical tile的表字段组合, 会存在position_list_idx与position list对应, 例(Tile A-1 ATTR1, Tile A-1 ATTR2), (Tile A-1 ATTR3, Tile A-2 ATTR1)
  • visible_rows_vector<bool>用来描述position lists中每一行的可见性

ColumnInfo设计 [backend/executor/logical_tile]

在logical tile中用来描述一组表字段信息, 例如(Tile A-1 ATTR1, Tile A-1 ATTR2), 其中

  • position_list_idx 指回Position Lists中对应编号
  • base_tileshared_ptr<storage::Tile>指向存储Tile,直接使用指针而不是oid
  • origin_column_id 存储Tile中选择的表字段编号

ContainerTuple设计 [backend/expression/container_tuple]

用于包装logical tile中元组, 传入LogicalTile指针与元组行id(logical_tile, row_idx)

HashMapType 设计 [backend/executor/hash_executor]

用于定义hash表结构unordered_map<expression::ContainerTuple<LogicalTile>, unordered_set<pair<size_t, oid_t>, boost::hash<pair<size_t, oid_t>>>, expression::ContainerTupleHasher<LogicalTile>, expression::ContainerTupleComparator<LogicalTile>>
其中pair 表示

使用类型为vector<unique_ptr<executor::LogicalTile>>left_result_tiles_right_result_tiles_缓存
最终hash操作返回结果为vector<LogicalTile *> result使用BuildOutputLogicalTile方法(主要调用BuildSchema方法得到表字段组合)返回得到unique_ptr<LogicalTile>

CMU课程15-721数据库系统设计(第二周)

CMU课程15-721最新一期开课啦!

课程安排

并发控制课程(一共三节)已经结束,但具体细节需要结合索引技术(仍然是三节)进行讲解

Indexes I — Locking & Latching

本节就是对应用在传统B树索引上的各种锁和latch技术进行讲解

技术总结信息来自这篇文章:A Survey of B-Tree Locking Techniques

在讲解锁相关技术前,需要把B树家族的各个数据结构先总结说明一下。

B树(键值都在) -> B+树(值都在叶子节点) 其中B+树设计选择有:

  • Non-Unique索引 实现方法有1.允许键重复 2.值list
  • 变长键 实现方法有1.指针 2.节点长度可变 3.key map(即slot pages)

其他变形:

  • T-tree, 基于AVL树(不存key直接存指针),用于内存DB
  • Skip List, MemSQL完全使用以替代B+结构,实现上为一组多层list,最低层为排序单链key,每层key减半,插入时几率插入每一层;优势是省空间,无需额外平衡操作,易并发;缺点是反向查找复杂
  • Radix Tree 基树
  • MassTree
  • Fractal Tree

对索引加锁需要注意索引结构可能变化

  • lock: 事务粒度上保护索引逻辑,txn duration,可以回滚,(ex,sh,up,i)
  • latch: 线程粒度上保护索引内部实现,op duration,不需要回滚,(r,w)

因此lock-free index可以为no lock(MVCC)或no latch(cow,shadow page)

索引锁类型

  • predicate lock 在where条件上加锁,不好实现
  • key-value lock 在B树key上加锁
  • gap lock 在B树key后面gap上加锁
  • key-range lock 在B树key及后面gap上加锁
  • hierachical lock 一组key-range lock纵向上组合(IX, EX)

Indexes II — OLTP

本节先关注latch实现方法:

  • Compare&Swap CAS操作,使用__sync_bool_compare_and_swap(&M, 20, 30) 是其他实现的基础
  • Os Mutex 使用pthread_mutex_t (,about 25ns invocation)
  • Test&Set spinlock 使用std::atomic_flag(non-scalable, cpu缓存不友好)
  • Queue spinlock 使用std::atomic_flag(比mutex性能好,cpu缓存友好) lock chain
  • rw locks 可以使用spin lock实现

其中non-scalable指锁阻塞后性能不能线性增长
详细解释

个人补充:工程实践中共享对象的读写一致性方案(读写锁,COW与引用计数),引用计数并发可以使用HazardPointer解决
个人补充:spinlock vs mutex

重点讲解几个典型mem DB中OLTP索引设计:

  1. BW树(Hekaton)
  • latch free B+树
  • deltas 没有直接修改(使用额外record或info,物理page上挂链表),建少cpu缓存失效,使用epoch方便垃圾回收
  • mapping table 树所有都使用pid,需要维护pid到page物理位置的指针表,CAS使用在该指针上

该技术来自微软Hekaton的这篇文章:The Bw-Tree: A B-tree for New Hardware

  1. Concurrent skip list(MemSQL), latch free
    仅使用CAS操作实现insert与update无锁化

该技术来自这篇文章:Concurrent Maintenance of Skip Lists

  1. Adaptive基树(Hyper)

Indexes III — OLAP

OLAP的不同在于可以drill down、roll up、slice、pivot等维度变化操作,本节主要讲解OLAP中列索引设计

个人补充:很多需要数据库行转列操作

Star Schema vs Snowflake Schema (分层级关系表) 使用B+树结构因为数据重复会导致大量的空间浪费,OLAP更适合采用列数据库模式(方便压缩)

SQL Server的列索引设计(如何在行存储上实现列索引):最初设计表必须是只读的, 实现结构为segment directory即blob storage with dictionary/delta encode & compress 针对不同数据类型采用不同编码方法;新版支持insert/update/delete, 采用delta store支持插入更新,bitmap实现删除

bitmap索引技术:每个attr使用一个bitmap表示每个tuple的值(估算10million tuple, 43000个zip codes则需要额外53.75GB,原因是zip作为attr数量太大),需要考虑压缩方法

Storage Models & Data Layout

主要mem DB的数据存储模型,注意C++使用reinterpret_cast在编译期强制转换类型,需要注意缓存对齐中的按字对齐(e.g. 64-bit word)

Null处理:定义特殊值, Bitmap表示, Null Flag

存储模型分为:

  • N-ary Storage Model(NSM) 适合OLTP,insert-heavy,物理上使用堆组织或索引组织元组(比如使用聚族索引)
  • Decomposition Storage Model(DSM) 行存储又叫纵向扩展,适合OLAP,元组物理上使用固定长度或嵌入元组id
  • Hybrid Model 可以切换或同时适配

可以观察到刚插入的数据一般都比较活跃,时间推移后期一般变成只读数据,OLTP通过ETL过程进入OLAP数据仓库

CMU课程15-721数据库系统设计(第一周)

CMU课程15-721最新一期开课啦!

真是要强烈推荐这门课程:有在线视频,有教案,有作业,甚至还有自动评分工具,除了没老师与TA之外真的分享了几乎所有的课程资源,完全可以让我们这种墙内的后进生们自学。

课程安排

Course Introduction and History of Database Systems

以回顾数据库历史的方式串讲了数据库系统设计中的难点,也就是以后的课程内容目录:

  1. 并发控制
  2. 索引
  3. 存储模型,压缩
  4. join算法
  5. 日志与恢复
  6. 查询优化
  7. 新存储器件

未来所有作业与项目都是用C++11写的(牛逼!),准备好调试多线程
推荐每次上课前写一篇本次课阅读paper的心得,包括:主题思想(两句话)、系统使用与修改情况(一句话)、负载测试情况(一句话)

In-Memory Databases

因为新型存储器件的飞速发展导致内存数据库(其实还有内存文件系统)需求越来越强烈,原始基于硬盘为主存储结构的数据库设计因此会有哪些变化呢?

总结下传统硬盘数据库设计特点为:

  1. 使用内存做缓存池(涉及内存与磁盘上以“页”为单位的数据同步)
  2. 页为单位的索引数据组织(页号、slot号、header、tuple、blob等概念设计)
  3. 所有请求都会先经过缓存池(worker线程需要pin住该页防止被swap到磁盘)
  4. 并发控制保证事务可以等待磁盘数据读取时间,同时锁(lock)要保存到其他数据结构(非页结构)中防止被swap
  5. 使用WAL处理日志与恢复问题
  6. CPU时间统计:30%缓存池、30%锁、28%日志、12%真正操作

设计内存数据库,首先不要考虑使用mmap,缺点:内存操作无法非阻塞了、内存结构与磁盘必须相同、数据库系统不知道哪些页实际在内存中(说白了就是操作系统通用设计不可能比数据库架构师专业设计更好!)

内存数据库IO问题退居二线(DRAM 60ns, SSD 25000~30000ns),需要考虑其他性能问题:

  1. lock/latch
  2. cache-line miss
  3. pointer chasing
  4. predicate evaluations
  5. data move
  6. network

总结下设计特点为:

  1. 不需要缓存池和页结构(直接用指针取代id索引?定长或变长数据?但是一定得使用checksum保证数据正确)
  2. 获得锁时间跟获得数据时间一样!导致可能允许牺牲一点并发度(coarse-grained locking因为数据IO足够快)并且可以将锁信息与数据信息一起保存(增加CPU cache locality,mutex相对太慢,一定改用CAS)
  3. 索引设计问题凸显(需要多考虑一下CPU cache)
  4. 查询处理方式巨大改变(不需要顺序扫描,传统一次处理一个tuple方式相对太慢),考虑vector-at-a-time
  5. 仍然需要WAL,可能可以简化;仍然需要checkpoint操作

内容基本出自92年的文章: High-Performance Concurrency Control Mechanisms for Main-Memory Databases

发布第一次项目作业,等本人做完了另找时间写文章说明。

Concurrency Control I

介绍各种事务模型:nested trx、saga trx(其实在《事务处理》一书里面都已经见识过)

介绍各种并发控制方式:
Two-Phase Locking 和死锁避免方法

  • DL_DETECT
  • NO_WAIT
  • WAIT_DIE

Timestamp Ordering及优化方法

  • Basic T/O
  • MVCC
  • OCC
  • H-STORE

测试结果出自14年的文章: Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores

个人补充:MC涉及多线程访问内存值,CC解决多CPU副本一致性

Memory Consistency和Cache Coherence

Concurrency Control II — Multi-versioning

详细介绍隔离级别:比可串行化级别低一些的级别,包括REPEATABLE_READS, READ_COMMITTED

  • Dirty Read 脏读(提前读到后面修改的内容)
  • Unrepeatable Read 不可重复读(事务里两次读操作,后一次读的不同)
  • Phantom Read 幻读(读到其他事务插入或删除的数据)

产品方面voltDB完美支持可串行化,oracle11g最高支持SNAPSHOT_ISOLATION级别,新增两种级别:

  • CURSOR_STABILITY 内部cursor持有锁,有时防止Lost Update(写操作覆盖顺序不对)

  • SNAPSHOT_ISOLATION 保证事务所见snapshot相同(不能强化到可串行化级别 2009新paper有可串行化snapshot方案),防止Write Skew(部分写更新)

下面介绍多版本MVCC现代实现方法(timestamp-ordered好处在于不需要lock!)

mvcc设计考虑:

  • version chains(oldest-to-newest[w],newest-to-oldest[r])
  • version storage(全量或delta存[回滚段])
  • garbage collection(额外线程或合作,GC在重写负载造成15%额外负载])

Hekaton(SQL Server)

事务开始结束都赋予时间戳, 为每个tuple维护版本链(BEGING, END, POINTER),维护全局事务状态图(ACTIVE, VALIDATING[precommited,2PL不需要这个状态,因为锁即可保证]),事务维护元数据(Read set,Write set,Scan set[避免幻读],Commit dependency),乐观事务在多核表现下明显好于悲观事务

实现方面仅使用lock-free数据结构(没有latch或spin lock,使用bw-tree和skiplist,CAS)

该系统设计11年论文:High-Performance Concurrency Control Mechanisms for Main-Memory Databases

Concurrency Control III — Optimistic

首先讨论存储过程,产生于解决使用交互API问题(可以减少网络通信次数与等待)

  • ODBC/JDBC
  • DBMS wire protocols

存储过程的问题:不好版本控制与调试,不好移植

Optimistic方法 其中validation步骤:(可以并发进行)

  • backword 与已经提交的事务判断
  • forword 与还未提交事务判断

本课未学完待补充

Cracking the coding interview Q19-20

19.1 Write a function to swap a number in place without temporary variables

x=x^y y=x^y x=x^y
**19.2 Design an algorithm to figure out if someone has won in a game of tic-tac-toe** We could use 1 for player1 and 2 for player2 and sum caculation to judge if any player wins or we can simply go though all directions to judge after any player make a move. **19.3 Write an algorithm which computes the number of trailing zeros in n factorial** Just caculate how many 5 are there in factors as 2 is usualy enough and be careful that 25 has two 5 rather than one.
int NumZeros(int n){
    if(n < 0) return -1;
    int num = 0;
    while((n /= 5) > 0){ //deal with factor like 25
        num += n;
    }
    return num;
}

19.4 Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator. EXAMPLE Input: 5, 10 Output: 10

int mmax(int a, int b){
    int c = a - b;
    int k = (c>>31) & 0x01; //sign bit
    return a - k*c; //marvelous
}

19.5 The Game of Master Mind is played as follows:
The computer has four slots containing balls that are red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB (e.g., Slot #1 is red, Slots #2 and #3 are green, Slot #4 is blue)
You, the user, are trying to guess the solution. You might, for example, guess YRGB When you guess the correct color for the correct slot, you get a “hit”. If you guess a color that exists but is in the wrong slot, you get a “pseudo-hit”. For example, the guess YRGB has 2 hits and one pseudo hit. For each guess, you are told the number of hits and pseudo-hits Write a method that, given a guess and a solution, returns the number of hits and pseudo hits.

The key is to figure out if any color could be judge multiple times. If not, which is a harder problem, go though the guess and the solution in the same time and judge hit first then increase corresponding color in solution’s count if not hit and reduce color in guess’s count, remember if count is ever bigger or equal to zero then that leads to a pseudo hit count.

19.6 Given an integer between 0 and 999,999, print an English phrase that describes the integer (eg, “One Thousand, Two Hundred and Thirty Four”)

Firstly check zero and then check thousand using length and be careful with eleven to nineteen.

19.7 You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum EXAMPLE Input: {2, -8, 3, -2, 4, -10} Output: 5 (i.e. , {3, -2, 4} )

It’s a classic dp problem and dp[i] = max{dp[i-1]+k[i], k[i]}

19.8 Design a method to find the frequency of occurrences of any given word in a book

Using tire tree (or hash) and count every word.

19.9 Since XML is very verbose, you are given a way of encoding it where each tag gets mapped to a pre-defined integer value. The language/grammar is as follows:
Element –> Element Attr* END Element END [aka, encode the element tag, then its attributes, then tack on an END character, then encode its children, then another end tag]
Attr –> Tag Value [assume all values are strings]
END –> 01
Tag –> some predefined mapping to int
Value –> string value END
Write code to print the encoded version of an xml element (passed in as string)
FOLLOW UP
Is there anything else you could do to (in many cases) compress this even further?

19.10 Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5(i.e., implement rand7() using rand5()). FOLLOW use randAB() to generate randCD()

def rand7():
         ret = rand5()+rand5()
         if ret > 7:
            return rand7()
         return ret
     # A is bigger than B
     def randB():
         ret = randA()
         if(ret > B*(A/B))
            return randB()
         return ret%B+1

19.11 Design an algorithm to find all pairs of integers within an array which sum to a specified value.

Firstly sort and then go though the array from the lowest and highest to judge if their sum equals to a specified value.

20.1 Write a function that adds two numbers. You should not use + or any arithmetic operators.

int add(int a, int b){
    while(b != 0){
        int sum = a^b; // (0,1)->1 (1,1)->0 (0,0)->0
        int carry = (a & b)<<1; and="" shift="" left="" to="" generate="" carry="" a="sum;" b="carry;" }="" return="" a;="" better="" solution="" int="" add(int="" a,="" b){="" char="" *c="(char" *)a;="" convert="" address="" (int)&c[b];="" using="" array="" add="" <="" pre="">

20.2 Write a method to shuffle a deck of cards. It must be a perfect shuffle in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.

Randomly pick up a card from total and remove it in the next turn, code like build heap.

def shuffle(cards):
    for i in range(0, len(cards)):
        j= random() % (len(cards)-i) + i #key step
        cards[i],cards[j]=cards[j],cards[i]
    return cards

20.3 Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen

almost the same as the upper question.

20.4 Write a method to count the number of 2s between 0 and n.

check every factor and count by caculation.

20.5 You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solution?

It must be solved by using hash table, yet it should be build by traverse the file and record every two words’ min distance and hash key is based on the sum of words and takes O(n^2) time and space to build that hash table. We assume that word order does not matter.

20.6 Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers

It’s easy to do with the min-heap and replacement algorithm (STL partial sort) or use O(n) partition algorithm (kth biggest elem) as all datas can be hold in memory.

20.7 Write a program to find the longest word made of other words in a list of words EXAMPLE Input: test, tester, testertest, testing, testingtester Output: testingtester

Sort the words from long to short by length firstly and check every word’s prefix and rest letters if they appears in the words array and we could use hash table to optimize the check so the whole takes O(nlgn)+O(n1d) time.

20.8 Given a string s and an array of smaller strings T, design a method to search s for each small string in T

Using tire tree yet you must know how to build one. We can build one based on suffix of the string s (taking O(m^2) time and space to build the tree and judge in kO(n) time) or better we can construct an AC automachine(taking O(m) time to build and kO(n) + O(s) time to judge)

20.9 Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated

We can build max-heap on the first half and min-heap on the second half then it takes O(1) to get median and O(nlgn) to maintain. In fact, we only need four(or five) numbers (min and max in two halfs) to get median and maintain.

20.10 Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary EXAMPLE Input: DAMP, LIKE Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

It could be solved by BFS and trace back method.

20.11 Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels

It ask to find the biggest subsquare in black, just go though the square matrix and check. Remember we are deal with the square thus every line length should be equal so if col is smaller than current max then it’s impossible to find a bigger subsquare and we can stop traverse.

20.12 Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum

We can combine row i to j and form a new one-dimension array. It takes O(n) time to find largest sum in a one-dimension array and we get n^2 that kind of arrays in all, thus takes O(n^3) time as a whole.

20.13 Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom)

It ask to form a largest matrix of words so all the chosen words must be in the same length and we could use tire tree to judge prefix of the colums’ words ever exists.

Cracking the coding interview Q13-18

13.1 Write a method to print the last K lines of an input file using C++.

int tail(const string &fname, int lines, list &res)
{
    ifstream fs(fname.c_str());
    if(!fs)
        return -1;
    int status = 0;
    int bytes_perline = 100;
    fs.seekg(0, fs.end);//fs.end
    streamoff end_pos = fs.tellg();
    streamoff start_pos = end_pos - bytes_perline*lines;
    if(start_pos < 0) start_pos = 0;
    fs.seekg(start_pos, fs.beg);

    string line;
    list::iterator it = res.begin();
    while(res.size() < lines){         
       getline(fs, line);         
       it = res.insert(it, line);         
       ++it;         
       if(status == 0){ //find last lines             
         if(fs.eof()){                 
                if(res.size() > lines)
                    break;
                end_pos = start_pos;
                start_pos>>=1;
                fs.clear();
                fs.seekg(start_pos, fs.beg);
                res.erase(--it);
                it=res.begin();
                status = 1;
            }
        }else if(status > 0){ // look up in the front
            if(fs.tellg() >= end_pos){
                if(res.size() > lines)
                    break;
                end_pos = start_pos;
                start_pos>>=1;
                fs.clear();
                fs.seekg(start_pos, fs.beg);
                res.erase(--it);
                it=res.begin();
                 if(start_pos <= 0) // reach the top                     
                    break;             
             }                  
        }    
   }         
   if(res.size()> lines ){
       int i = res.size()-lines;
       for(;i>0;--i)
          res.erase(res.begin());
   }

   return res.size();
}

int main(int argc, char const *argv[])
{
    int ret;
    list res;
    ret = tail(argv[1], atoi(argv[2]), res);
    if(ret>0)
        copy(res.begin(), res.end(), ostream_iterator(cout, "\n"));
    return 0;
}
**13.2 Compare and contrast a hash table vs an STL map. How is a hash table implemented? If the number of inputs is small, what data structure options can be used instead of a hash table.** STL map's pairs are in sorted order but hash table don't and STL map takes O(nlgn) to find a elm yet hash table takes O(1) time. When implement a hash table you should find a hash function, deal with collision and size of table. If inputs is small then RB tree would be a a alternative way for hash table. **13.3 How do virtual functions work in C++?** A virtual function depends on a "virtual table". If any function or class is declared as virtual, a v-table is constructed which stores addresses of the virtual functions of this class. The compiler also adds a hidden vptr in all such classes which points to the vtable. If a virtual function is not overriden in the derived class, the vtable of the derived class stores the adress of the function in his parent class. The vtable is used to resolve the address of the function. Dynamic binding in C++ is therefore performed though the vtable mechanism. **13.4 What is the difference between deep copy and shallow copy? Explain how you would use each.** Shallow copy just copy the address of the object's ptr field yet deep copy also copy the values of that ptr points to which need dynamic allocated space. The default copy constructor and assignment operator make shallow copies. Deep copy usually are used to deal with the string or buffer. **13.5 What is the significance of the keyword “volatile” in C** Volatile informs the compiler that the value of the variable can change from the outside, without any update done by the code, thus just don't optimize the variable related code and fetch the variable value from memory instead of the register. **13.6 What is name hiding in C++? ** "Name hiding is particularly tricky if the derived class's method has a different signature than the base class's method of the same name." Base class's method would be hidden if the derived class overrides that method (no-virtual function) and overloaded in the same time. (see Effective C++ rule 33) **13.7 Why does a destructor in base class need to be declared virtual?** If we delete on the base ptr which points to the derived class object, the base class destructor called first (for no-virtual function) which would lead to a memory leak for the derived part. We should declare base class's destructor in virtual so that derived destructor would be called first and destroy all parts of the object as we expected. **13.8 Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed-in data structure.The Node structure contains two pointers to other Node structures.** It's mush alike deep copy a binary tree.
typedef struct Node Node_t;
struct Node{
   struct Node* ptr1;
   struct Node* ptr2; 
};
typedef set<Node_t*> NodeMap;

Node_t* copy_recursive(Node_t* cur, NodeMap &map){
    if(cur == NULL) return NULL;
    NodeMap::iterator it = map.find(cur);
    if(it != map.end())
       return *it;
    Node_t* node = new Node_t;
    map.insert(node);
    node->ptr1 = copy_recursive(cur->ptr1, map);
    node->ptr2 = copy_recursive(cur->ptr2, map);
    return node;
} 

Node_t* copy_node(Node_t* root){
     NodeMap map;
     return copy_recursive(root, map);
}
**13.9 Write a smart pointer (smart_ptr) class. ** Check Effective C++ rule 14.
template <class T>
class smart_ptr {
public:
    smart_ptr(T *ptr){
        //cout<<"default"<<endl;
        ref = ptr;
        ref_count = new unsigned int();
        *ref_count = 1;
    }

    smart_ptr(smart_ptr &sptr){
        //cout<<"copy assign"<<endl;
        ref = sptr.ref;
        ref_count = sptr.ref_count;
        ++*ref_count;
    }

    smart_ptr& operator=(smart_ptr &sptr){
        //cout<<"= assign"<<endl;
        if(this != &sptr && ref != sptr.ref) {
            if (--*ref_count == 0){ // this may already got a ptr
                clear();
                //cout<<"= clear"<<endl;
            }

            ref = sptr.ref;
            ref_count = sptr.ref_count;
            ++*ref_count;
        }
        return *this;
    }

        T operator*() { return *ref; }

    ~smart_ptr(){
        //cout<<*ref_count<<endl;
        if(--*ref_count == 0){
            clear();
            //cout<<"clear"<<endl;
        }
    }
private:
    void clear(){
        delete ref;
        delete ref_count;
        ref = NULL;
        ref_count = NULL;
    }
protected:
    T *ref;
    unsigned int *ref_count;
};

int main(int argc, char const *argv[])
{
    int *p1 = new int();
    *p1 = 100;
    smart_ptr sp1(p1), sp2(p1);
    smart_ptr spa = sp1; // copy assign not = assign
    sp2 = sp1; // = assign
    cout<<*spa<<endl; // spa is the same of sp1
    return 0;
}
**15.1 Write a method to find the number of employees in each department**
SELECT Departments.name, count(Employees.id) FROM Departments, Employees WHERE Employees.depid = Departments.id(+) GROUP BY Departments.id

SELECT Departments.name, count(Employees.id) FROM Departments LEFT JOIN Employees ON Employees.depid = Departments.id GROUP BY Departments.id
**15.2 What are the different types of joins? Please explain how they differ and why certain types are better in certain situations.** ** ** There are innerjoin, left outer join, right outer join, full outer join and cross join. INNER JOIN result set will only contain datas where the criteria match.
SELECT * FROM Employees, Departments WHERE Employees.dpid = Departments.id;
CROSS JOIN returns the Cartesian product of rows from tables in the join. It will produce rows which combine each row from the first table with each row from the second table.
SELECT * FROM Employees, Departments;
LEFT OUTER JOIN returns all the values from an inner join plus all values in the left table that do not match to the right table(NULL in the case of no matching join predicate).
SELECT * FROM Employees, Departments WHERE Employees.dpid = Departments.id(+);
RIGHT OUTER JOIN returns all the values from the right table and matched values from the left table (NULL in the case of no matching join predicate). Right and left outer joins are functionally equivalent. FULL OUTER JOIN combines the effect of applying both left and right outer joins. Some database systems do not support the full outer join functionality directly.
SELECT * FROM Employees INNER JOIN Departments ON Employees.dpid = Departments.id UNION ALL;
**15.3 What is denormalization? Explain the pros and cons.** denormalization is the process of attempting to optimize the read performance of a database by adding redundant data or by grouping data, like storing the count of the "many" objects in a one-to-many relationship as an attribute of the "one" relation or adding attributes to a relation from another relation with which it will be joined. It's do good in performance yet more redundant data. **15.5 Imagine a simple database storing information for students’ grades. Design what this database might look like, and provide a SQL query to return a list of the honor roll students (top 10%), sorted by their grade point average.**
CREATE TABLE Students(
    'sid' INT NOT NULL AUTO_INCREMENT,
    'name' varchar(20) NOT NULL,
    'sex' enum(f,m),
    PRIMARY KEY('sid')
);

CREATE TABLE Courses(
    'cid' INT NOT NULL AUTO_INCREMENT,
    'name' varchar(20) NOT NULL,
    'description' text,
    PRIMARY KEY('cid')
);

CREATE TABLE Enrollment(
     'eid' INT NOT NULL AUTO_INCREMENT,
     'cid' INT NOT NULL,
     'sid' INT NOT NULL,
     'grade' INT NOT NULL,
     PRIMARY KEY('eid')
);

SELECT Students.name, GPA 
FROM (
     SELECT TOP 10 percent Avg(Enrollment.grade) AS GPA, Enrollment.sid 
     FROM Enrollment 
     GROUP BY Enrollment.sid 
     ORDER BY Avg(Enrollment.grade)
) Honors, Students 
WHERE Students.sid = Honors.sid;
**16.1 Explain the following terms: virtual memory, page fault, thrashing.** _Virtual memory_ maps memory addresses used by programs to physical addresses in memory hardware, thus Main storage as seen by a process or task appears as a contiguous address space. _Page fault_ is a trap raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. _Thrashing_ occurs when a computer's virtual memory subsystem is in a constant state of paging, rapidly exchanging data in memory for data on disk, to the exclusion of most application-level processing, which causes the performance of the computer to degrade or collapse. **16.2 What is a Branch Target buffer? Explain how it can be used in reducing bubble cycles in cases of branch misprediction** The _branch target buffer_ is a true cache, the full PC value must be conpared to validate that this is a branch instruction before taking any action which reduces the penalty by predicting the path of the branch, computing the target of the branch and caching the information used by the branch. There will be no stalls if the branch entry found on BTB and the prediction is correct, otherwise the penalty will be at least two cycles. **16.3 Describe direct memory access (DMA). Can a user level buffer/pointer be used by kernel or drivers? ** _DMA_ is a feature that allows certain hardware subsystems within the computer to access system memory independently of the CPU. By using DMA, drivers can access the memory allocated to the user level buffer/pointer. **16.5 Write a program to find whether a machine is big endian or little endian.**
bool check_little_endian()
{
   union{
       int a;
       char b;
   }c;
   c.a = 1;
   return c.b ? true : false;
}

bool check_little_endian()
{
    short int a = 0x0001;
    char* b = (char*)&a;
    return b[0] ? true : false;
}
**16.6 Discuss how would you make sure that a process doesn’t access an unauthorized part of the stack ** For native code there is the possiblility of stack overflow and remember in a multi-threaded environment, there can be multiple stacks in a process and nothing can fully prevent process access memory addresses. We can build a sandbox for the program and vm is a good example. **16.8 A device boots with an empty FIFO queue. In the first 400ns period after startup, and in each subsequent 400ns period, a maximum of 80 words will be written to the queue. Each write takes 4ns. A worker thread requires 3ns to read a word, and 2ns to process it before reading the next word. What is the shortest depth of the FIFO such that no data is lost?**   **16.9 Write an aligned malloc & free function that takes number of bytes and aligned byte (which is always power of 2) EXAMPLE align_malloc(1000,128) will return a memory address that is a multiple of 128 and that points to memory of size 1000 bytes aligned_free() will free memory allocated by align_malloc **
void* align_malloc(size_t bytes, size_t aligned){
    void* p1; // original block
    void** p2; // aligend block
    // extra space for storing p1 and alignment
    int offset = aligend - 1 + sizeof(void*); 
    if ((p1 = (void*)malloc(bytes + offset)) == NULL)
        return NULL;
    // make sure p2 minus the extra space address and the result is aligned
    p2 = (void**)(((size_t)(p1) + offset) & ~(aligend - 1)); 
    p2[-1] = p1; //store p1 for free operation
    return p2;
}

void align_free(void* p){
    free(((void**)p)[-1]);
}
**16.10 Write a function called my2DAlloc which allocates a two dimensional array. Minimize the number of calls to malloc and make sure that the memory is accessible by the notation arr[i][j] **
int** my2DAlloc(int r, int c){
    int header = r * sizeof(int*);
    int data = r * c * sizeof(int);
    int** arr = (int**)malloc(header + data);
    int* buf = (int*)(arr + r); // save space for r ptrs
    for(int i =0; i< r; ++i)
        arr[i] = buf + i * c; //every ptr points to the right place which works for arr[i][j]
    return arr;
}
**17.1 Explain what happens, step by step, after you type a URL into a browser. Use as much detail as possible.** In an extremely rough and simplified sketch, assuming the simplest possible HTTP request, no proxies and IPv4 (this would work similarly for IPv6-only client): 1. browser checks cache; if requested object is in cache and is fresh, skip to #9 2. browser asks OS for server's IP address 3. OS makes a DNS lookup and replies the IP address to the browser 4. browser opens a TCP connection to server (this step is much more complex with HTTPS) 5. browser sends the HTTP request through TCP connection 6. browser receives HTTP response and may close the TCP connection, or reuse it for another request 7. browser checks if the response is a redirect (3xx result status codes), authorization request (401), error (4xx and 5xx), etc.; these are handled differently from normal responses (2xx) 8. if cacheable, response is stored in cache 9. browser decodes response (e.g. if it's gzipped) 10. browser determines what to do with response (e.g. is it a HTML page, is it an image, is it a sound clip?) 11. browser renders response, or offers a download dialog for unrecognized types Again, discussion of each of these points have filled countless pages; take this as a starting point. Also, there are many other things happening in parallel to this (processing typed-in address, adding page to browser history, displaying progress to user, notifying plugins and extensions, rendering the page while it's downloading, pipelining, connection tracking for keep-alive, etc.). **17.5 What are the differences between TCP and UDP?** TCP is a connection-oriented protocol and it's reliable, ordered and heavyweight. UDP is connectionless protocol and it's unreliable, not ordered and lightweight. **18.1 What’s the difference between a thread and a process?** A process can be thought of as an instance of a program in execution. Each process is an independent entity to which system resources (CPU time, memory, etc ) are allocated and each process is executed in a separate address space. A thread uses the same heap space of a process. A process can have multiple threads. Each thread still has its own registers and its own stack, but other threads can read and write the heap memory. **18.2 How can you measure the time spent in a context switch?** If the total timeof execution of all the processes was T, then the context switch time = T – (SUM for all processes (waiting time + execution time)). Overall, we can say that this is mostly an approximate calculation which depends on the underlying OS. **18.3 Implement a singleton design pattern as a template such that, for any given class Foo, you can call Singleton::instance() and get a pointer to an instance of a singleton of type Foo. Assume the existence of a class Lock which has acquire() and release() methods How could you make your implementation thread safe and exception safe?**
class Lock {
public:
    Lock();
    ~Lock();
    void AcquireLock(){};
    void RelaseLock(){};
};

template  class Singleton{
public:
    Singleton();
    ~Singleton(){
        if (object != 0)
            delete object;
    }
    static T* instance();
private:
    static Lock lock;
    static T* object;
};

template 
Lock Singleton::lock;

template 
T* Singleton::object;

template 
T* Singleton::instance(){
    if(object == 0){
        lock.AcquireLock();
        if (object == 0) {
            object = new T;
        }
        lock.RelaseLock();
    }
    return object;
}

int main(int argc, char const *argv[])
{
    int* stest = Singleton::instance();
    return 0;
}
**18.5 i) Can you design a mechanism to make sure that B is executed after A, and C is ex - ecuted after B? ii) Suppose we have the following code to use class Foo We do not know how the threads will be scheduled in the OS Foo f; f.A(.....); f.B(.....); f.C(.....); f.A(.....); f.B(.....); f.C(.....); Can you design a mechanism to make sure that all the methods will be executed in sequence?** i)
Semaphore a(0),b(0);
A {
   ...
   a.Release(1);
}
B {
   a.Acquire(1);
   ....
   b.Release(1);
}
C {
   b.Acquire(1);
   ...
}
ii)
Semaphore a(0),b(0),c(1);
A {
   c.Acquire(1);
   ...
   a.Release(1);
}
B {
   a.Acquire(1);
   ....
   b.Release(1);
}
C {
   b.Acquire(1);
   ...
   c.Release(1);
}

Cracking the coding interview Q7-12

7.7 Explain how you would design a chat server In particular, provide details about the various backend components, classes, and methods. What would be the hardest problems to solve?

We can learn from twitter and QQ server design. The main concepts of the chat server would be user(status), chat group and messages.

enum Status{offline, online, away}
struct Message{ User from_user; User to_user; String post_message;}
class User {Status type; Message posts[]; sendMessage(); addGroup(); updateStatus(); createGroup(); }
struct Group { Message posts[]; User list[];}

Information sync with memory cache and database; Server scale; User session management;

7.9 Explain the data structures and algorithms that you would use to design an in-memory file system. Illustrate with an example in code where possible

File system must inlude dir and file structure. The key points are design of super block, directory and inodes. Super block mainly deal with namespace and organize inodes, which we could use hash table for fast fetching. Inodes contains meta data and organize datas, which we could use B tree (memory efficient) or radix tree(linux, fast fetching) or log structure (journaling tech for availability). Directory mainly deal with file lookup operations which convert string path to the rightful inode.

7.10 Describe the data structures and algorithms that you would use to implement a garbage collector in C++

Organize object with Smart ptr using reference counting tech(bad with dead lock). Will java’s mark-sweep tech work?

8.1 Write a method to generate the nth Fibonacci number

def fibonacci(n):
a,b=0,1
while(n>0):
a,b,n=b,a+b,n-1
return a

8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot? FOLLOW UP Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

Using DFS and traceback to print all paths.

8.3 Write a method that returns all subsets of a set.

It’s easy to solve this problem using 2^n bitmap for all subsets status and go thourgh to print corresponding subset.

def subsets(a, idx, len):
sbs = []
if idx == len:
sb = []
sbs.append(sb) #empty set
print(sb)
else:
rsb = subsets(a, idx+1, len)
e = a[idx]

    #print(idx,rsb)
    for i in rsb:
        t1 = i[:]
        sbs.append(t1) #keep origin
        t2 = i[:]
        t2.append(e) #add new elm
        sbs.append(t2)
        print(t2)
return sbs</pre>

8.4 Write a method to compute all permutations of a string.

void permutations(const string &s, vector &v){
if (s == “”){
v.push_back(s);
}else{
string c = s.substr(0, 1); // substr(offset, len)
vector vt;

    permutations(s.substr(1), vt); // get rest permutations
    for (std::vector::iterator i = vt.begin(); i != vt.end(); ++i)
    {
        v.push_back(*i);
        //insert in any space between the character to get permutation
        for (int j = 0; j &lt;= i-&gt;length(); ++j)
        {
            string st = *i; //copy one
            st.insert(j, c);
            v.push_back(st);
        }

    }
}

}
if duplicate character is allowed which may result in duplicate answers then

void unique_permutations(const string &s, set &v){
if (s == “”){
v.insert(s);
}else{
for (int i = 0; i < s.length(); ++i){
string c = s.substr(i, 1); // substr(offset, len)
string t = s; //copy one for erase
set vt;
unique_permutations(t.erase(i, 1), vt); // get rest permutations
for (std::set::const_iterator i = vt.begin(); i != vt.end(); ++i)
{
v.insert(i);
v.insert(c +
i);
}
}
}
}

8.5 Implement an algorithm to print all valid (e g , properly opened and closed) combi -nations of n-pairs of parentheses EXAMPLE: input: 3 (e g , 3 pairs of parentheses) output: ()()(), ()(()), (())(), ((()))

void paretheses(int n, int idx, int len, string res){
int i, j;
int remain = idx + 1;
if(n == len){
res += “(“;
for(j = remain; j > 0; –j){
res += “)”;
}
cout<<res<<”,”;
}else{
res += “(“;
for(i = remain; i >= 0; –i){
string tmp = res;

        for(j = i; j &gt; 0; --j){
            tmp += ")";
        }

        paretheses(n + 1, remain - i, len, tmp);

    }
}

}
8.6 Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2 dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color’.

Using recursive DFS or better using BFS way to search, no need to traceback so pretty easy.

8.7 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents

It could be solved by generating function, but a little bit complicate:

int cents[] = {1, 5, 10, 25};
int caculate(int n){
int i, j, k, res;
int c1 = new int[n+1];
int
c2 = new int[n+1];
for(i=0; i<=n; ++i){
c1[i] = 1; //firstly one cent
c2[i] = 0;
}

//then 5, 10, 25 cents
for(i=1; i&lt;=3; ++i){

    for(j=0; j&lt;=n; ++j){
        for(k=0; k+j&lt;=n; k+=cents[i]){
            c2[j+k] += c1[j];
        }
    }

    for(j=0; j&lt;=n; ++j){
        c1[j] = c2[j];
        c2[j] = 0;
    }
}

res = c1[n];

delete[] c1;
delete[] c2;

return res;

}
or using a recursive method:

int caculate2(int sum, int c, int n){
int ways = 0;
int i;
if(sum <= n){
if(sum == n) return 1;
for(i=3; i>=0; –i){
if(c >= cents[i])
ways += caculate2(sum+cents[i], cents[i], n);
}
}
return ways;
}

9.2 Write a method to sort an array of strings so that all the anagrams are next to each other

Simply sort every string alphabetically first and then compare with other strings (c++ string could use “>” op to compare).

9.3 Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array.You may assume that the array was originally sorted in increasing order EXAMPLE: Input: find 5 in array (10 14 15 16 19 20 25 1 3 4 5 7) Output: 10 (the index of 5 in the array)

int search(int n, int a[], int len){
int low, high, mid;
low = 0, high = len-1;
while(low<=high){
mid = (low + high)/2;
if(a[mid] == n){
return mid;
}else if (a[mid] < n){ //25 1 3 4 5 7 10 14 15 16 19 20
if(a[mid] < a[low]){
if(a[low] < n) high = mid -1;
else low = mid + 1;
}else
low = mid + 1;
}else if (a[mid] > n){
if(a[mid] < a[low]) high = mid -1;
else{
if(a[low] < n) high = mid - 1;
else low = mid + 1;
}
}
}
}

9.4 If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?

 

9.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

Using binary search method just moving right to neglect empty strings.

9.6 Given a matrix in which each row and each column is sorted, write a method to find an element in it.
Just search line by line in O(m+n) time:

int search_matrix(int mat[][], int m, int n, int x){
int row = 0, col = n-1;
while(row<=m && col >=0){
if(mat[row][col] == x) return row * n + col;
else if(mat[row][col] > x) –col;
else ++row;
}
}

Binary search method also works:

int search_matrix(int mat[][], int m, int n, int x){
int r1 = 0, c1 = 0;
int r2 = m-1, c2 = n-1;
int i = (r1+r2)/2, j = (c1+c2)/2;
while((i!=r1||i!=r2) && (j!=c1||j!=c2)){ //may have some problems
if(mat[i][j] == x)
return in+j;
else if(mat[i][j] < x){
r2 = i, c2 = j;
}else {
r1 = i, c1 = j;
}
i = (r1+r2)/2, j = (c1+c2)/2;
}
}

*9.7 A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output:The longest tower is length 6 and includes from top to bottom: (56,90) (60,95) (65,100) (68,110) (70,150) (75,190)

It’s a LIS problem which can be solved in O(nlgn) by mento and binary search. (hdu1025)

10.2 There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.

Q1:For three ants and triangle, every ant has two directions and vertices to crawl, so there will be 2^3 conditions and only when all ants choose the same direction(clockwise or anticlockwise) will lead them not to collision. So probability of collision is 1 - 2/2^3

Q2: Similarly, probability of collision is 1 - 2/2^n

10.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect.

line is different from segment, but the latter is more difficlut to judge if intersect with each other which could be solved by vector multiply.

10.4 Write a method to implement *, - , / operations You should use only the + operator

For multiply operation:

for i in range (1,n):
res+=m

For minus operation:

for i in range(0,n):
if (i + m == n):
return i

For division operation:

res=0
for i in range(1,m):
res+=n
if(res==m):
return i
if(res>m):
return i-1

10.5 Given two squares on a two dimensional plane, find a line that would cut these two squares in half

Any line go though the center of square would cut it in half, so a line go though both squares’ center would be the answer. Just be careful with the case that both sqaures’ center are the same point.

10.6 Given a two dimensional graph with points on it, find a line which passes the most number of points

Rather than using two points pair methond to represent the segment(we could also go though and check every pair in O(n^3) time), we could use slope and y-intercept thus this problem is no different than finding most common number in a list of numbers.

10.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7

Using O(n^2) time to caculate one by one, which can be accelerated by hash list to reduce repeated aculation(hdu1058)

11.2 You are given the source to an application which crashes when it is run. After running it ten times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

Memory leak causes out of memory and leads to crash or variable is not initialized with proper value. Unproper system configuration could also leads to crash (eg. max fd or max thread numbers) and sometimes interacting with hardware may also cause such problems.

11.3 We have the following method used in a chess game: boolean canMoveTo(int x, int y) x and y are the coordinates of the chess board and it returns whether or not the piece can move to that position. Explain how you would test this method

Invalid conditions for four corners and all possible move in board.
Valid conditions for all direction and all pieces.

11.4 How would you load test a webpage without using any test tools?

Load test usaually includes thoughput, response time, resource utilization and pressure tests.

11.5 How would you test an ATM in a distributed banking system?

Test should include UI test (accessiblity test) and functional test (single machine test and ditributed system test).

12.1 If you were integrating a feed of end of day stock price information (open, high, low, and closing price) for 5,000 companies, how would you do it? You are responsible for the development, rollout and ongoing monitoring and maintenance of the feed. Describe the different methods you considered and why you would recommend your approach.The feed is delivered once per trading day in a comma separated format via an FTP site. The feed will be used by 1000 daily users in a web application.

This problem actually ask you how to store this feed. SQL Database would be a good choice. NoSQL storage engine like mogodb would also do the job. Format could be XML or JSON.

12.2 How would you design the data structures for a very large social network (Facebook, LinkedIn, etc)? Describe how you would design an algorithm to show the connection, or path, between two people (eg, Me->Bob->Susan->Jason->You)

Using array to store friends’ id so a graph in general. We could use other information to seperate people’s information cleverly.

12.3 Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory. FOLLOW UP What if you have only 10 MB of memory?

If 1 GB memory we could simply use bitmap approach. For 10 MB memory we have to deal with blocks of numbers firstly using counting method and then deal with proper blocks using bitmap.

12.4 You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array?

Just use bitmap method as we have space for 0 ~ 42^108 which is exactly bigger than 32,000.

12.5 If you were designing a web crawler, how would you avoid getting into infinite loops?

Simply try DFS or BFS approach to go through the whole gragh which means you have got a map to store the all urls as points.

12.6 You have a billion urls, where each is a huge page. How do you detect the duplicate documents?

You have to check the content of huge web page for url rather than url it self. To content comparing we could use hash finger method(or other similar method), then we’ve got a billion finger prints which is still a large number. We could hash those finger prints to different files and deal with every file in memory one by one or hash those to different machine.

12.7 You have to design a database that can store terabytes of data. It should support efficient range queries. How would you do it?

Using B+ tree to build the database.

Cracking the coding interview Q1-6

1. 1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

It’s means to check if a string has repeated character or not. It can be solved by using a bitmap and Assic table(128 for normal and 256 with special). key: using n=(int)string[i] to get Assic number and (bitmap[n/32] &amp; 1&lt;&lt;(n%32)) to check if repeated.

1.2 Write code to reverse a C-Style String (C-String means that “abcd” is represented as five characters, including the null character )?

Exchange characters between start index 0 and end index string length - 1, stop when two pointers meet.

1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not. FOLLOW UP Write the test cases for this method ?

Not allowed to apply for new arrays. Compare each characters in the string and if duplicated just remove in place, key: using null character to replace duplicated character. Test cases should include unique characters string, null string, string with only one character, common string with sequence duplicate characters or with not.

1.4 Write a method to decide if two strings are anagrams or not ?

If new array is allowed to apply for, it can be solved by counting table in O(n) time. Actually sort two strings and compare each characters is enough to get the answer in O(nlgn) time.

1.5 Write a method to replace all spaces in a string with ‘%20’ .

Firstly count the ectra space needed by replacing, two chars’ space for each character. If space is enough then just fill and move, otherwise you should realloc space and copy whole string, don’t forget the null character.

1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees Can you do this in place ?

To rotate 90 degrees in clockwise just exange M[i][j] with M[j][N-i], implementation could firstly exange elms between diagonal and then exange columns i with N-i

1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

Go through the matrix only to register which column or row has zero and then go through the matrix again to set those rows or columns to zero which takes O(mn) time, key: only need array row[m] nd column[n]

1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”)

To use isSubstring function we need string s1 is longer than s2, so just duplicate s1 by s1’ = s1 + s1 (s1’ contains all rotations of s1) then check if s2 is substring of s1’ to judge rotaion.

2.1 Write code to remove duplicates from an unsorted linked list FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?

Using hash table could be the best way. If temporay buffer is not allowed then just using algorithm in 1.3 taking O(n^2) time.

2.2 Implement an algorithm to find the nth to last element of a singly linked list.

Using two pointers at a distance of n to solve. Another way is using recursion as stack.

2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node

EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

Just copy the data from next node and delete next node by pointing the next pointer field to the node after next node. Note that there would be a problem if the node is the last node in the list.

2.4 You have two numbers represented by a linked list, where each node contains a single digit The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list

EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

Just pay attention to null list and list in different length.

3.1 Describe how you could use a single array to implement three stacks

It’s easy to implement with three stack top pointers to seperate space.

3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time

It’s hard to deal with the pop when min element was on the top of the stack. So extra space are needed to store those bigger elms. An extra stack could be used to store min elms. Every time you push a new elem, compare it with the top of extra stack and smaller one has to be pushed into extra stack. The same, when pop out a elem you should check if it equal to the top of extra stack and if so you have to pop it out from the extra stack.

3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks push() and SetOfStacks pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack) FOLLOW UP Implement a function popAt(int index) which performs a pop operation on a specific sub-stack

It’s worth implementing in C++

3.4 In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower The puzzle starts with disks sorted in ascending order of size from top to bottom (e g , each disk sits on top of an even larger one) You have the following constraints:
(A) Only one disk can be moved at a time
(B) A disk is slid off the top of one rod onto the next rod
(C) A disk can only be placed on top of a larger disk
Write a program to move the disks from the first rod to the last using Stacks

void hanoi(int n, char src, char bri, char dst){
    if(n==1){
        cout&lt;&lt;"Move disk "&lt;&lt;n&lt;&lt;" from "&lt;&lt;src&lt;&lt;" to "&lt;&lt;dst&lt;&lt;endl;
    }
    else{
        hanoi(n-1, src, dst, bri);
        cout&lt;&lt;"Move disk "&lt;&lt;n&lt;&lt;" from "&lt;&lt;src&lt;&lt;" to "&lt;&lt;dst&lt;&lt;endl;
        hanoi(n-1, bri, src, dst);
    }
}
`</pre>
You should change it with using stack

**3.5 Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.**

If only stack could be used then an extra stack is needed to simulate insert sort

**4.1 Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one**

Just get every leaf node's depth by tree walk(time O(n)) and store them (space O(n/2)) then go through the array to judge if the tree is unbalanced or check the tree in a postorder that is recursively down and then judge.

**4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes**

Using BFS to find.

**4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height **

It's easy to use recursion way to build the tree with limited length. You can use binary search way to build binary search tree.

**4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (ie , if you have a tree with depth D, you’ll have D linked lists) **

Just walk though the tree and link those nodes to the linked lists based on the depth of the nodes. A better solution is using BFS way to walk though the tree.
<pre>`void tree_level_walk(struct bt_tree* root, vector&lt;list&gt; &amp;res){
    list ltmp;
    list::iterator it;
    struct bt_tree* tmp;
    int depth = 1;

    ltmp.push_back(root);
    res[depth].push_back(ltmp);

    while(!res[depth].empty()){ // check every level
        ltmp.clear();
        for(it=res[depth].begin(); it!=res[depth].end(); ++it){ // using list as queue to store all next level nodes
            tmp = *it;
            if(tmp-&gt;left) ltmp.push_back(tmp-&gt;left);
            if(tmp-&gt;right) ltmp.push_back(tmp-&gt;right);
        }
        ++depth;
        res[depth].push_back(ltmp);
    }
}
`</pre>
**4.5 Write an algorithm to find the ‘next’ node (ie , in-order successor) of a given node in a binary search tree where each node has a link to its parent**
<pre>`def tree_successor(self, node):
     if node.right != None:
          return tree_min(node.right)
     tmp = node.parent
     while tmp != None and node == tmp.right:
          node = tmp
          tmp = node.parent
     return tmp
`</pre>
**4.6 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree **

If you want store all ancestor of one node to check then using hash table instead of simple array. But it requires every node has a link to its parent and additional space. Else you can start from root and using recursive way to find result and take over very time you find a closer one.
<pre>`bool father(struct bt_tree* n1, struct bt_tree* n2){
    if(n1 == NULL) return false;
    else if(n1 == n2) return true;
    else return father(n1-&gt;lchild, n2) || father(n1-&gt;rchild, n2);
}

void find_ancestor(struct bt_tree* head, struct bt_tree* n1, struct bt_tree* n2, struct bt_tree** res){
    if(head == NULL) return;
    if(head &amp;&amp; father(head, n1) &amp;&amp; father(head, n2)){
        res = head; 
        find_ancestor(head-&gt;left, n1, n2, res);
        find_ancestor(head-&gt;right, n1, n2, res);
    }
}`</pre>
Here is a better solution to check less node
<pre>`struct bt_tree* find_ancestor(struct bt_tree* head, struct bt_tree* n1, struct bt_tree *n2){
     if(head == NULL) return NULL;
     if(head == n1 || head == n2) return head; //check if ancestor
     struct bt_tree* left = find_ancestor(head-&gt;left, n1, n2);
     struct bt_tree* right = find_ancestor(head-&gt;right, n1, n2);
     if(left &amp;&amp; right) return head;
     return left?left:right;
}`</pre>
**4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1**

Using BFS way to go though T1 and compare with T2 if the node is equal with T2's root. Using string comparing technique is a better way for it's easier to store in disk file so just compare inorder and preoder sequence. It's a really hard to deal with such big data.

**4.8 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree it does not have to start at the root. **

You can walk though the tree and backtrace every node if it has a link to parent to calculate the sum and judge.

**5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (eg, M becomes a substring of N located at i and starting at j)
EXAMPLE:
Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100**

(N ^ ~(1&lt;&lt;(j-i+1)-1)&lt;&lt;i) | (M&lt;&lt;i)

**5.2 Given a (decimal - eg 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”**

Using '%' op to deal with integer part and  multiply op to deal with decimal part which should be finished the same time s as its length, for example  decimal part of 3.72  should be finished in two times of multiply or should print "ERROR"

**5.3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation**

To make a larger number just find the 1st zero bit after 1 bits and change that bit into 1 and set all lower bit into 0, in the mean time of going though the number remember to count the number of 1 bit (not including the last 1 bit before the changed bit) and then set the same number of 1 bit from the lowest bit place. A better way to count 1 bit is using following method:
<pre>`
int count_one(int x){
    x = (x &amp; (0x55555555)) + ((x &gt;&gt; 1) &amp; (0x55555555));
    x = (x &amp; (0x33333333)) + ((x &gt;&gt; 2) &amp; (0x33333333));
    x = (x &amp; (0x0f0f0f0f)) + ((x &gt;&gt; 4) &amp; (0x0f0f0f0f));
    x = (x &amp; (0x00ff00ff)) + ((x &gt;&gt; 8) &amp; (0x00ff00ff));
    x = (x &amp; (0x0000ffff)) + ((x &gt;&gt; 16) &amp; (0x0000ffff));
    return x;
}

To make a lower number is the same just find the 1st 1 bit after zero bits and count 1 bits(including the changed bit) and then set.
Yet you should be careful with the negative numbers.

5.4 Explain what the following code does: ((n & (n-1)) == 0)

To check if n is power of 2.

5.5 Write a function to determine the number of bits required to convert integer A to integer B
Input: 31, 14
Output: 2

Using (1<<i) and operation and to go though two number and count how many bit are different. A better way is to count the 1 in result of A ^ B.

5.6 Write a program to swap odd and even bits in an integer with as few instructions as possible (eg, bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc)

((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)

5.7 An array A[1…n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

Testing number of every bit in the array to select the minimal part and make the missing element.

def find_missing(a[], n):
len = n-1
column = lg(n)
res = 0
for j in range(column-1, 0, -1):
count0=count1=0
a1=a2=[]
for i in a:
if (getBit(i, j)):
a1[count1++]=i
else:
a0[count0++]=ai
if count1 >= count0: #may have problem when count eqs to zero
a=a0, len = count0
else:
a=a1, len = count1
res+=(1<<j)
return res

Remember missing one number problem can always be solved by sumup(1,n)-sumup(a[1],a[n])

6.1 Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8 You can use any parentheses you’d like

(3+1)/3*6=8

6.2 There is an 8x8 chess board in which two diagonally opposite corners have been cut off You are given 31 dominos(多米诺骨牌), and a single domino can cover exactly two squares Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible)

As two corners painted in the same color are cut off. It’s imporssible to cover with uncoupled numbers of squares.

6.3 You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups) How would you come up with exactly four quarts of water? NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible

Firstly using full five quart jug minus three quart jug(5-3=2), then put the rest in three quart jug(3-2=1) and then use full five quart jug to fill three quart jug(5-1=4).

6.4 A bunch of men are on an island A genie comes down and gathers everyone together and places a magical hat on some people’s heads (ie , at least one person has a hat) The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.

All men on the island knowns there exists at least one hat. So one hat takes one day, two hats take two days and c hats take c days to remove.

6.5 There is a building of 100 floors If an egg drops from the Nth floor or above it will break If it’s dropped from any floor below, it will not break You’re given 2 eggs Find N, while minimizing the number of drops for the worst case.

Using section to reduce number of drops, x + (x-1) + (x-2) + ... + 1 &gt;= 100 and x eqs to 14 then sections will be 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 and then first egg to test the section and second egg to test level sequencely.

6.6 There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (eg , he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

Except 1 and the number itself, if the number i can be divided exactly by factor a then it can be diveded exactly by factor i/a meaning that number of factors would be even. Only when i=i/a the number of factors will become odd and the number i must be the full square so from 1 to 100 will be 10 lockers remain open.

本站总访问量