应聘驱动类的职位，竟然考这种数据结构与算法

idolspawn

我可是一直在等着回复呢,呵呵,因为我还在上学,专业跟计算机软件基本无关,只能得到来自网上大家伙的意见作参考,所以很期待大家的回复...

cugb_cat

原帖由 idolspawn 于 2008-12-2 18:24 发表
恩，确实有些浮躁吧。按LS所言，数据结构这课程是必须要多少领略一下的了。可能因为我是从单片机做起的原因，一直以为驱动的话，控制层面的东西居多，算法方面的居少。我最近也觉得这种想法可能有些不对，但是不 ...

已经跟你说了啊。

idolspawn

.
比如各种排序算法，二叉树什么的，做驱动开发目前没听说过有用的，学习这些的用处是什么？从整体把握编程麽？如果我把看这些的时间拿出来用来看CPU架构呢..死活体会不到某些结构的作用。
另，“括号匹配这样的，是很简单的了”...我丝毫没觉得简单，这种题感觉就跟高中做某类数学题似的，有特定解法，要是之前没接触过，水平一般的还真做不好

shan_ghost

第一，现在有几款CPU不是基于栈结构的？又有几款CPU没有内置的硬件栈支持？

栈这种“显学”都搞不明白，俺不相信你有能力写好汇编代码，更不用说去研究什么CPU架构了。


第二，驱动也有很多种。

最粗，也是最底层的，其实只是个翻译-转发过程——搞个功能-端口-命令字对照表出来，这玩意儿几乎都可以用程序自动生成。
——这种东西，除非根本招不到专业人才的小作坊；否则，随便找个人花两天时间到网上找个框架代码，一个星期就能搞定。

稍微靠上一点，比如为了避免别人下BT影响我玩wow，要写个简单的QOS——不懂队列的话，可能吗？
——我之前查过，即使是低速的ADSL路由器，真正提供了QOS功能的，价位基本没有低于2000的。

再比如，硬盘寻道很费时间，它的读写就要求实现“电梯算法”。
这种算法要按照磁头移动的方向为多个读写请求排序——其中一种可行方案，就是搞个双向链表，链表节点是请求队列，链表次序就是磁道顺序；然后，把对应磁道的读写请求挂到对应节点的队列末尾，然后不停以正-反-正-反的次序遍历链表即可。

实际工作中还要复杂很多。比如必须考虑请求提交时间，避免进程被“饿死”（这就要求优先队列）、以及可以调整同一个队列里对不同扇区的访问请求的次序（比如第1、2、3个请求分别要求访问第100、50、75扇区，而磁头当前位于第60扇区，那么显然应该按3、1、2的次序安排访问——注意硬盘不会倒转），以尽量减少等待时间等等。

简单的硬盘驱动已经如此；要实现同时管理多块硬盘的软raid，乐子才叫大呢。

至于更高级一点的，比如nvidia、ATI两大显卡巨头的驱动中用到的优化技法，不用说连栈都不懂的楼主你，恐怕全世界敢说能看懂的牛人都没多少。


画一横是一；画两横是二；画三横是三：很简单不是？
——你给我写个万字看看。

楼上各位说的好。栈无非就是“先进后出”四字而已。
如果这四个字的简单玩意儿都能把你吓回去，显然阁下的水平也确实够凄惨的。

cjaizss

连数据结构这种基础都不学,还能编程?

redspider

原帖由 idolspawn 于 2008-12-2 17:07 发表
昨天应聘某公司的linux驱动开发的职位（当然，本人目前相当菜，压根没抱什么希望，只是去体验下试题的内容），做了套笔试题，一做，傻眼了。怎么全是数据结构算法一类的题目？比如说，编程实现"{,[,("的匹配类似 ...

你用的什么方法，说说看

雨过白鹭洲

内核也是底层，还不是用了许多数据结构和算法

idolspawn

光是看各位的回帖脸上已经冷一阵热一阵了，要是直面真人，还不找地缝钻了...原来要走的路竟然还有这么长。不过14L，我不是"研究"CPU架构啦，是"学习"哈，这点自知之明俺还是有的。硬件的栈倒是用过，不过软件的栈还真是第一次知道，确实相当寒碜啊... 谢谢你解释的这么详细。
16L，我做时就用的字符串指针，唉，就没必要说了。
谢谢各位，各位真是严格呢，今晚收获不小。

new_learner

原帖由 shan_ghost 于 2008-12-2 22:03 发表
稍微靠上一点，比如为了避免别人下BT影响我玩wow，要写个简单的QOS——不懂队列的话，可能吗？
——我之前查过，即使是低速的ADSL路由器，真正提供了QOS功能的，价位基本没有低于2000的。

不是吧，现在的adsl路由器qos功能都差不多的，卖得都很便宜。
不知道你说的“真正提供了QOS功能”是啥意思？

uiamu

其实楼主也不必过于在意，毕竟你没有这方面的准备，不知道从哪位大牛的书里面看到，其实有50-60%的计算机专家无法一次写出完全正确的排序算法