coding复习笔记共享 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

coding复习笔记共享

coding复习笔记共享# JobHunting - 待字闺中

s*u2013-10-10 07:10

1 楼

发现markdown编辑器很好用，还可以拿来共享笔记。
http://www.zybuluo.com/smilence/note/76
接下去10天准备把所有做过的coding题目分类整理一下，着重总结“什么样的题目怎么
做”这个核心问题。
题目绝大多数都是careercup书上的题和leetcode上面相对常见的一些，还有就是从面
经里找的。
拿出来共享，一个是希望对跟我一样的新手有帮助，另一个督促自己每天努力更新。
如果大家看了，如果觉得思路上有补充的话，非常欢迎讨论补充，假以时日，我coding
水平入门之后，倒是可以集思广益把这个弄成一个tutorial。

u*o2013-10-10 07:10

2 楼

用C++的，怒赞！
你这么用心，假以时日水平肯定可以去flag的，为啥不等再准备准备再去面google呢？

s*u2013-10-10 07:10

3 楼

少壮不努力，老大徒伤悲啊，我已经耽误许多时间了。其实对我来说，因为并不打算久
留美国，所以去一家适合自己水平的it公司历练下就好。
写这些东西，主要就是为了复习准备接下去的面试，次要是为了增加自己复习动力和兴
趣，最后就是如果能对别人有所帮助，那是更好。至于结果，我看的也不是很重。
享受过程也不错！

【在 u*****o 的大作中提到】

: 用C++的，怒赞！
: 你这么用心，假以时日水平肯定可以去flag的，为啥不等再准备准备再去面google呢？

c*p2013-10-10 07:10

4 楼

Mark

f*l2013-10-10 07:10

5 楼

这个一定要顶。

h*o2013-10-10 07:10

6 楼

这是个什么网站啊，是不是把note写在上面给大家看得？
我写了好多notes. 写完就忘了，如果放上面，也督促自己经常复习。

coding

【在 s********u 的大作中提到】

: 发现markdown编辑器很好用，还可以拿来共享笔记。
: http://www.zybuluo.com/smilence/note/76
: 接下去10天准备把所有做过的coding题目分类整理一下，着重总结“什么样的题目怎么
: 做”这个核心问题。
: 题目绝大多数都是careercup书上的题和leetcode上面相对常见的一些，还有就是从面
: 经里找的。
: 拿出来共享，一个是希望对跟我一样的新手有帮助，另一个督促自己每天努力更新。
: 如果大家看了，如果觉得思路上有补充的话，非常欢迎讨论补充，假以时日，我coding
: 水平入门之后，倒是可以集思广益把这个弄成一个tutorial。

m*i2013-10-10 07:10

7 楼

Mark & Thank you for sharing!

d*n2013-10-10 07:10

8 楼

赞一个
我们用过markdown写过小的文档
感觉挺有意思的
能把human readable text file格式化得很好
简洁有效
不过还没有看到有大规模用过markdown的

x*u2013-10-10 07:10

9 楼

谢大牛分享.

h*y2013-10-10 07:10

10 楼

赞!!
有木有oo design的? 最期盼有c++版的oo design, 到处都找不到

coding

【在 s********u 的大作中提到】

s*u2013-10-10 07:10

11 楼

凡是careercup书上有的章节，我准备10天之内都整理进来。
其他的容易被考的知识性问题，之后也尽量补充，如操作系统的、计算机网络的一些核
心知识。
我没学过java，不过感觉在oo design这一块，区别不大，可能需要注意的是：
1.C++里，class里的变量不能直接初始化，要在constructor里初始化，而java可以
2.public，protected，private的格式略有不同
3.C++一个class可以继承多个class，java不行，但java可以用interface
4.多态的区别，C++是用virtual function来实现多态和表示抽象类的。

【在 h****y 的大作中提到】

: 赞!!
: 有木有oo design的? 最期盼有c++版的oo design, 到处都找不到
:
: coding

h*y2013-10-10 07:10

12 楼

灰常期待, 正好对上我的timing, 10天后狗家昂赛

【在 s********u 的大作中提到】

: 凡是careercup书上有的章节，我准备10天之内都整理进来。
: 其他的容易被考的知识性问题，之后也尽量补充，如操作系统的、计算机网络的一些核
: 心知识。
: 我没学过java，不过感觉在oo design这一块，区别不大，可能需要注意的是：
: 1.C++里，class里的变量不能直接初始化，要在constructor里初始化，而java可以
: 2.public，protected，private的格式略有不同
: 3.C++一个class可以继承多个class，java不行，但java可以用interface
: 4.多态的区别，C++是用virtual function来实现多态和表示抽象类的。

h*o2013-10-10 07:10

13 楼

@smilence: 你怎么整理很多notes那？
怎样把你的link改写成http://www.zybuluo.com/smilence/c++/chapter1
之类的那？
我试了一下我的，不行

coding

【在 s********u 的大作中提到】

s*u2013-10-10 07:10

14 楼

整理很多notes就要很多链接了，不过我暂时想放在一个文档里，就是好像这东西不支
持索引。目前只是写起来方便，权宜之计。
其实你想改link的话，不如写好了导出成html，然后存到dropbox里，或者博客里。。

【在 h**o 的大作中提到】

: @smilence: 你怎么整理很多notes那？
: 怎样把你的link改写成http://www.zybuluo.com/smilence/c++/chapter1
: 之类的那？
: 我试了一下我的，不行
:
: coding

s*u2013-10-10 07:10

15 楼

今天写前两章，欢迎建议和纠错！

u*o2013-10-10 07:10

16 楼

smilenceyu, 我想问问bst为什么比hashtable要memory efficient呢？

l*g2013-10-10 07:10

17 楼

hashtable本来就是空间换时间的，能做到O(1), 当然要多用很多space了。

【在 u*****o 的大作中提到】

: smilenceyu, 我想问问bst为什么比hashtable要memory efficient呢？

u*o2013-10-10 07:10

18 楼

能再说的具体些吗？例如维护一个size为n的hashtable,或bst,
两种不都应该是O(N)吗？hashtable即使有很多collision,也到不了o(n^2)吧？

【在 l*******g 的大作中提到】

: hashtable本来就是空间换时间的，能做到O(1), 当然要多用很多space了。

l*g2013-10-10 07:10

19 楼

看到这句有点问题:
Hash table还可以用Balanced BST来实现，如std::map, lookup的时间由O(1)增长为lo
g(n)，但节省space cost ,且可以按照key的值有序输出pairs。
log(n)的应该叫普通symbol tabel了，不能叫hash table了，就是一个black-red tree
. hash table应该是O(1)的，不过也是average case, worst case还是O(n)

【在 s********u 的大作中提到】

: 今天写前两章，欢迎建议和纠错！

l*g2013-10-10 07:10

20 楼

不是o(n), 一个是o(1)常数，一个是O(logN), 插入查找就是O(n)效率太低了。

【在 u*****o 的大作中提到】

: 能再说的具体些吗？例如维护一个size为n的hashtable,或bst,
: 两种不都应该是O(N)吗？hashtable即使有很多collision,也到不了o(n^2)吧？

u*o2013-10-10 07:10

21 楼

谢谢，你说的是time complexity,我问的是space complexity方面这两者的区别。
我觉得是O(n),或者说hashtable如果hash function不好的话，有可能达到o(n^2),但
bst一直都是o(n),所以bst更memory efficient,这样说可以吗?

【在 l*******g 的大作中提到】

: 不是o(n), 一个是o(1)常数，一个是O(logN), 插入查找就是O(n)效率太低了。

s*u2013-10-10 07:10

22 楼

这一段参考careercup书第一章：
Alternatively, we can implement the hash table with a binary tree.We can
then guarantee an O(log n) lookup time, since we can keep the tree balanced.
Additionally, we may use less space, since a large array no longer needs to
be allocated in the very beginning.
具体其实还是要看implementation的，比如closed hashing也有很多算法。

【在 u*****o 的大作中提到】

: smilenceyu, 我想问问bst为什么比hashtable要memory efficient呢？

l*g2013-10-10 07:10

23 楼

差不多，hashtable也有很多种变形的，最典型的就是seperate chaining, 和linear p
robing, linear probing一般要维持2N space, seperate chaining就有可能增加到n^2
了

【在 u*****o 的大作中提到】

: 谢谢，你说的是time complexity,我问的是space complexity方面这两者的区别。
: 我觉得是O(n),或者说hashtable如果hash function不好的话，有可能达到o(n^2),但
: bst一直都是o(n),所以bst更memory efficient,这样说可以吗?

s*u2013-10-10 07:10

24 楼

是的，这个我以前也是这么理解的，map就是个红黑树。
这一段参考careercup书：
Alternatively, we can implement the hash table with a binary tree.We can
then guarantee an O(log n) lookup time, since we can keep the tree balanced.
Additionally, we may use less space, since a large array no longer needs to
be allocated in the very beginning.
个人理解是hash table只是个数据结构，bst是一种implementation，array+list也是
一种implementation。
对于大O我准备加一句说明，就是不特别注明都是指average case。

lo
tree

【在 l*******g 的大作中提到】

: 看到这句有点问题:
: Hash table还可以用Balanced BST来实现，如std::map, lookup的时间由O(1)增长为lo
: g(n)，但节省space cost ,且可以按照key的值有序输出pairs。
: log(n)的应该叫普通symbol tabel了，不能叫hash table了，就是一个black-red tree
: . hash table应该是O(1)的，不过也是average case, worst case还是O(n)

y*g2013-10-10 07:10

25 楼

table or map是数据结构
hash table是用hash的implementation, tree map是tree 的implementation 。list
map

balanced.
to

【在 s********u 的大作中提到】

: 是的，这个我以前也是这么理解的，map就是个红黑树。
: 这一段参考careercup书：
: Alternatively, we can implement the hash table with a binary tree.We can
: then guarantee an O(log n) lookup time, since we can keep the tree balanced.
: Additionally, we may use less space, since a large array no longer needs to
: be allocated in the very beginning.
: 个人理解是hash table只是个数据结构，bst是一种implementation，array+list也是
: 一种implementation。
: 对于大O我准备加一句说明，就是不特别注明都是指average case。
:

s*u2013-10-10 07:10

26 楼

不能认同hash table是一种implementation。因为不能理解一个implementation又有很
多种implementation方式啊。
一般都是说list( array-based or linked-based ),queue，stack，tree，graph，
hash table这些是数据结构吧，然后可以有很多种implementation

【在 y*******g 的大作中提到】

: table or map是数据结构
: hash table是用hash的implementation, tree map是tree 的implementation 。list
: map
:
: balanced.
: to

y*g2013-10-10 07:10

27 楼

你接着不能认同去吧

【在 s********u 的大作中提到】

: 不能认同hash table是一种implementation。因为不能理解一个implementation又有很
: 多种implementation方式啊。
: 一般都是说list( array-based or linked-based ),queue，stack，tree，graph，
: hash table这些是数据结构吧，然后可以有很多种implementation

s*u2013-10-10 07:10

28 楼

讨论而已，你说说理由也无妨。

【在 y*******g 的大作中提到】

: 你接着不能认同去吧

u*o2013-10-10 07:10

29 楼

明了，谢谢！

balanced.
to

【在 s********u 的大作中提到】

: 这一段参考careercup书第一章：
: Alternatively, we can implement the hash table with a binary tree.We can
: then guarantee an O(log n) lookup time, since we can keep the tree balanced.
: Additionally, we may use less space, since a large array no longer needs to
: be allocated in the very beginning.
: 具体其实还是要看implementation的，比如closed hashing也有很多算法。

u*o2013-10-10 07:10

30 楼

SOGA, 谢谢呀！

p
^2

【在 l*******g 的大作中提到】

: 差不多，hashtable也有很多种变形的，最典型的就是seperate chaining, 和linear p
: robing, linear probing一般要维持2N space, seperate chaining就有可能增加到n^2
: 了

f*y2013-10-10 07:10

31 楼

mark!!

o*72013-10-10 07:10

32 楼

4.C语言中2D-Array的初始化与参数传递
有bug

l*y2013-10-10 07:10

33 楼

lz好人那。我也跟着lz练练。我一个人总是懒，不能坚持复习。

s*u2013-10-10 07:10

34 楼

第7行笔误了。已更正。多谢！

【在 o********7 的大作中提到】

: 4.C语言中2D-Array的初始化与参数传递
: 有bug

s*u2013-10-10 07:10

35 楼

今天写前两章，欢迎建议和纠错！

h*e2013-10-10 07:10

36 楼

搂主，虽然我目前不需要，但是看了以后还是很感动啊！
花了这么多心血写的东西给版上的同胞share!
大大的赞！

c*s2013-10-10 07:10

37 楼

谢谢！！包子请查收

s*u2013-10-10 07:10

38 楼

多谢鼓励！我会加倍努力的。
下周四或者周五就有ebay第二轮电面，所以争取提前整理出来，至少能解决绝大多数的
基础题（难度基本就是careercup，leetcode大部分题（比如不涉及dp），ebay面经）
。一些难度更高或者更偏的东西，之后再慢慢补充。

【在 c*********s 的大作中提到】

: 谢谢！！包子请查收

C*y2013-10-10 07:10

39 楼

赞，收藏，谢谢分享

s*u2013-10-10 07:10

40 楼

已基本完成Chapter 1,2,4,5。睡觉去了。。

y*g2013-10-10 07:10

41 楼

收藏！感谢楼主！