Monday, November 5, 2007



发信人: strenuous (穿梭回来的感觉真好), 板面: CS
标  题: 我来做做贡献吧,回忆今天的网易笔试题目
发信站: 飘渺水云间 (Mon Nov  5 17:30:52 2007), 转信

1 CPU高级缓存的用处
高速缓存:Cache Memory,位于CPU与内存之间的临时存储器,它的容量比内存小但交换速度快。在Cache中保存了正在运行的程序的经常执行的数据和指令,就避免了通过BUS从内存读取数据和指令的瓶颈。
一般主流的CPU片内都有L1 Cache,在紧靠CPU还有L2 Cache;也有的将L1,L2 Cache都做到CPU上,紧靠CPU的芯片上还有L3 Cache。一般L1 Cache的运行节拍和CPU一致,L2 Cache的速度也是RAM的2~3倍。与此类似,硬盘也有Cache系统,叫做Disk Cache。Disk Cache和Memory Cache的功能类似。

2 用尽量少的矩形表示一个不规则形状,写算法

3 快速排序代码实现
void qsort(int a[], int left, int right)
  int i, k, last;
  last = left;
        printf("%d ",a[k]);

class A {...} typedef A* PTR;
Void foo (const PTR aptr)
Void foo(PTR const aptr)
哪个正确? 应该都正确吧。

4 什么叫 C++ Traits?  模板类的特化实现的类库?

泛型编程编出来的代码,适用於任何「吻合某种条件限制」的资料型别。这已成为撰写可复用代码时的一个重要选择。然而,总有一些时候,泛型不够好 ─ 有时候是因为不同的型别差距过大,难以产生一致的泛化实作版本。这个时候 traits 技术就变得相当重要。这种技术可以将那些需要被纳入考量的型别性质以一种 type by type 的原则,封装於一个 traits class 内,於是可以将「由於型别之间的差异,必须撰写出来以备用」的代码体积降至最低,并使泛用代码的体积提升到最高。

考虑一个例子:当我们处理字元字串(character strings)时,常见的一个操作行为就是决定「以 null 为结束符号」的字串的长度。很明显我们不可能写出一份泛型代码取代众所周知原本就存在的极有效率的解法:是的,C 标准函式 strlenwcslen 通常是以组合语言完成,如果再加上适量的硬体支援,就能够比 C++ 泛型版本有明显的速度优势。C++ 标准程式库的作者了解这一点,所以他们抽取出 charwchar_t 的性质,置於 class char_traits 内。於是,泛型代码一旦处理字元字串,便可以简单地使用 char_traits<>::length 来决定一个「以 null 为结束符号」的字串的长度,并且很安心地确知 char_traits 的特化版本将采用最适当的方法来完成任务。

5 Java题目:
interface 和 abstract的区别。如何选用。
Interfaces vs Abstract Classes
feature interface abstract class
multiple inheritance A class may implement several interfaces. A class may extend only one abstract class.
default implementation An interface cannot provide any code at all, much less default code. An abstract class can provide complete code, default code, and/or just stubs that have to be overridden.
constants Static final constants only, can use them without qualification in classes that implement the interface. On the other paw, these unqualified names pollute the namespace. You can use them and it is not obvious where they are coming from since the qualification is optional. Both instance and static constants are possible. Both static and instance intialiser code are also possible to compute the constants.
third party convenience An interface implementation may be added to any existing third party class. A third party class must be rewritten to extend only from the abstract class.
is-a vs -able or can-do Interfaces are often used to describe the peripheral abilities of a class, not its central identity, e.g. an Automobile class might implement the Recyclable interface, which could apply to many otherwise totally unrelated objects. An abstract class defines the core identity of its descendants. If you defined a Dog abstract class then Damamation descendants are Dogs, they are not merely dogable. Implemented interfaces enumerate the general things a class can do, not the things a class is.

In a Java context, users should typically implement the Runnable interface rather than extending Thread, because they're not really interested in providing some new Thread functionality, they normally just want some code to have the capability of running independently. They want to create something that can be run in a thread, not a new kind of thread.The similar is-a vs has-a debate comes up when you decide to inherit or delegate.

multiple inheritance for further discussion of is-a vs has-a
plug-in You can write a new replacement module for an interface that contains not one stick of code in common with the existing implementations. When you implement the inteface, you start from scratch without any default implementation. You have to obtain your tools from other classes; nothing comes with the interface other than a few constants. This gives you freedom to implement a radically different internal design. You must use the abstract class as-is for the code base, with all its attendant baggage, good or bad. The abstract class author has imposed structure on you. Depending on the cleverness of the author of the abstract class, this may be good or bad.
homogeneity If all the various implementaions share is the method signatures, then an interface works best. If the various implementations are all of a kind and share a common status and behaviour, usually an abstract class works best. Another issue that's important is what I call "heterogeneous vs. homogeneous." If implementors/subclasses are homogeneous, tend towards an abstract base class. If they are heterogeneous, use an interface. (Now all I have to do is come up with a good definition of hetero/homo-geneous in this context.) If the various objects are all of-a-kind, and share a common state and behavior, then tend towards a common base class. If all they share is a set of method signatures, then tend towards an interface.
maintenance If your client code talks only in terms of an interface, you can easily change the concrete implementation behind it, using a factory method. Just like an interface, if your client code talks only in terms of an abstract class, you can easily change the concrete implementation behind it, using a factory method.
speed Slow, requires extra indirection to find the corresponding method in the actual class. Modern JVMs are discovering ways to reduce this speed penalty. Fast
terseness The constant declarations in an interface are all presumed public static final, so you may leave that part out. You can't call any methods to compute the initial values of your constants. You need not declare individual methods of an interface abstract. They are all presumed so. You can put shared code into an abstract class, where you cannot into an interface. If interfaces want to share code, you will have to write other bubblegum to arrange that. You may use methods to compute the initial values of your constants and variables, both instance and static. You must declare all the individual methods of an abstract class abstract.
adding functionality If you add a new method to an interface, you must track down all implementations of that interface in the universe and provide them with a concrete implementation of that method. If you add a new method to an abstract class, you have the option of providing a default implementation of it. Then all existing code will continue to work without change.

俩对象相等( x.equals(y)==true),则x,y有不同hash数值吗?
Equal objects must produce the same hash code as long as they are equal, however unequal objects need not produce distinct hash codes.
hashcode相同的两个对象不一定 x.equals(y)==true,但是 x.equals(y)==true的一定hashcode相等。

6 Windows题目:
7 linux: 如何进程间通信?

8 数据库:

事务是作为单个逻辑工作单元执行的一系列操作。一个逻辑工作单元必须有四个属性,称为原子性、一致性、隔离性和持久性 (ACID) 属性,只有这样才能成为一个事务。




事务在完成时,必须使所有的数据都保持一致状态。在相关数据库中,所有规则都必须应用于事务的修改,以保持所有数据的完整性。事务结束时,所有的内部数据结构(如 B 树索引或双向链表)都必须是正确的。


由 并发事务所作的修改必须与任何其他并发事务所作的修改隔离。事务识别数据时数据所处的状态,要么是另一并发事务修改它之前的状态,要么是第二个事务修改它 之后的状态,事务不会识别中间状态的数据。这称为可串行性,因为它能够重新装载起始数据,并且重播一系列事务,以使数据结束时的状态与原始事务执行的状态 相同。



索引如何建? 建的原则是?
9 web题目:
java servlet api里的forward 和 redirect() 是?

A Controller servlet may perform either a forward or a redirect operation at the end of processing a request. It is important to understand the difference between these two cases, in particular with respect to browser reloads of web pages.


  • a forward is performed internally by the servlet
  • the browser is completely unaware that it has taken place, so its original URL remains intact
  • any browser reload of the resulting page will simple repeat the original request, with the original URL
  • a redirect is a two step process, where the web application instructs the browser to fetch a second URL, which differs from the original
  • a browser reload of the second URL will not repeat the original request, but will rather fetch the second URL
  • redirect is marginally slower than a forward, since it requires two browser requests, not one
  • objects placed in the original request scope are not available to the second request
In general, a forward should be used if the operation can be safely repeated upon a browser reload of the resulting web page; otherwise, redirect must be used. Typically, if the operation performs an edit on the datastore, then a redirect, not a forward, is required. This is simply to avoid the possibility of inadvertently duplicating an edit to the database.

More explicitly :

  • for SELECT operations, use a forward
  • for INSERT, UPDATE, or DELETE operations, use a redirect
In HTML, a <FORM> tag can either GET or POST its data. In this context, a GET corresponds to a SELECT-then-forward, and a POST corresponds to an edit-then-redirect. It is strongly recommended that forms for the input of search criteria should use GET, while forms for editing database records should use POST.




Jijun MA
Zhejiang University-Intel Technology Center
College of Computer Science, Zhejiang University, China

No comments: