EFI interview - 6

最后一个进来的是一个技术主管的Director，问了我几个理论问题，一个都没答上来。

1. TCP协议和UDP协议的区别？
还真不知道，以前做工作的时候是直接用网络工具WireShark捕捉网络传输的packet，WireShark上面会直接标出这个包是TCP的包还是UDP的包，所以从来没有关心过。后来面试官告诉我，TCP协议更严格一些，要求一个handshake的过程，比如一个request从client发到server上之后，必须得到server端发回来的acknowledgement才可以继续进行下去，否则就hang在那里等待，要么就timeout中止这个过程。作为对比，UDP就比较宽松一些，这个协议不要求server发回ack，可以继续把数据发向server端。然后他又问我UDP在现实中有哪些应用？也不知道。又是他告诉我说主要用于video的传输或者voice chat，因为这个过程中由于数据量大，delay很常见，无法很奢侈地等待每一个ack回来。


2. 加密算法，何谓symmetric，何谓assymmetric？我说不知道。面试官问我当一台机器让我敲了username和password之后，该怎样验证我的身份？我说它应该用与加密算法相逆的算法将密码还原，他说这样不好。就好象如果他注册了一个网站，结果忘记密码了，问网站要回密码。如果网站真的将他原来的密码找出来寄回给他，他反而会不高兴，因为这意味着网站的服务器有办法反编译他的密码，并有可能泄漏给第三方。相反，很多网站会reset他的密码之后给他寄一个新的密码，这样他登录之后可以立即修改，这样就很安全。

所谓asymmetric的方法，就是当一个密码被加密得到一个hash key之后，当你登录之后，把你敲进来的密码再用同样的算法加密，然后比较两次hash key的结果。

EFI interview - 5

问题：怎样判断一个年份是否是闰年？

这个问题也栽了，当时对if-else的条件捣鼓了半天，还是没有捣鼓对。感觉上，面试官对判断闰年与否的条件给得不是很清楚，算是找个借口吧。

http://support.microsoft.com/kb/214019

In the Gregorian calendar, a normal year consists of 365 days. Because the actual length of a sidereal year (the time required for the Earth to revolve once about the Sun) is actually 365.25635 days, a "leap year" of 366 days is used once every four years to eliminate the error caused by three normal (but short) years. Any year that is evenly divisible by 4 is a leap year: for example, 1988, 1992, and 1996 are leap years.

However, there is still a small error that must be accounted for. To eliminate this error, the Gregorian calendar stipulates that a year that is evenly divisible by 100 (for example, 1900) is a leap year only if it is also evenly divisible by 400.

For this reason, the following years are not leap years: 1700, 1800, 1900, 2100, 2200, 2300, 2500, 2600. This is because they are evenly divisible by 100 but not by 400.

The following years are leap years: 1600, 2000, 2400. This is because they are evenly divisible by both 100 and 400.

To determine whether a year is a leap year, follow these steps:

1). If the year is evenly divisible by 4, go to step 2. Otherwise, go to step 5.
2). If the year is evenly divisible by 100, go to step 3. Otherwise, go to step 4.
3). If the year is evenly divisible by 400, go to step 4. Otherwise, go to step 5.
4). The year is a leap year (it has 366 days).
5). The year is not a leap year (it has 365 days).

这里的算法逻辑很清楚。


http://en.wikipedia.org/wiki/Leap_year

if year modulo 400 is 0
    then is_leap_year
else if year modulo 100 is 0
    then not_leap_year
else if year modulo 4 is 0
    then is_leap_year
else
    not_leap_year

这里的算法非常简洁。

EFI interview - 4

这回是以前一个在Qualcomm面试中问过的问题，关于volatile关键字的作用。我跟面试官谈了一下，不过他说我说的原理是对的，但没有说出volatile的用法的intention所在，真是个傻逼。

再复习一下
－－－
在K&R的Bible的附录A.8.2里面，提到了这么一段：
The purpose of volatile is to force an implementation to suppress optimization that could otherwise occur. For example, for a machine with memory-mapped input/output, a pointer to a device register might be declared as a pointer to volatile, in order to prevent the compiler from removing apparently redundant references through the pointer.

另外，相关的资料也可参见下面的link：
http://en.wikibooks.org/wiki/Embedded_Systems/C_Programming
http://vault.embedded.com/story/OEG20010615S0107
http://publications.gbdirect.co.uk/c_book/chapter8/const_and_volatile.html

EFI interview - 3

Problem: Two integers given, N and M. Suppose M = 10101 (binary system), write code to change N's 2nd to 6th bits to M. For example, N = 100001000, M = 10101, the result is expected to be 101010100.

当时瞎折腾了一通，并没有完全解出来。不过基本思路是有的，回到旅馆之后整理了一下思路，大致应该这么做：

M << 2 first, to move the binary numbers into bit 2~6. Then if we can clear bits 2~6 in N, say the cleared N is N1, then what left is to do N1 | M<<2.

But how to clear bits 2~6 in N? It seems N & ~1111100 can do it. So, could it be done with (N & (~1111100)) | M<<2?

不那么精巧，但似乎可以达成目标。MITBBS上有朋友提出了另外几种答案，不过我看不明白。比较典型的利用类似Bit Twiddling Hacks中的技巧的方法是MITBBS的FCer提出来的：(~k)&N | (M<<2)，where k = (1<<7)-(1<<2)。不过看不懂为什么k要这样计算。

EFI interview - 2

问题：什么是callback function？

这个还真的问到我的痛脚了。以前写code的时候倒是见过几个callback function，用过，但是自己没有写过。只是有印象它们是用函数指针（function pointer）实现的，经常用于对某种event或是signal的相应，有点类似于微软可视化编程里面的消息驱动机制。不过，说实话，怎样把某个event和某个function pointer联系起来，我还不是很清楚。以前在code里面看到要register一下，不过怎样register呢？细节还是有点模糊。

可以读一读下面这几篇文章：
http://stackoverflow.com/questions/142789/what-is-a-callback-in-c-and-how-are-they-implemented
http://stackoverflow.com/questions/2738463/implementing-callback-functions-in-c
http://www.cprogramming.com/tutorial/function-pointers.html

EFI interview - 1

题目：打印一个Pascal's Triangle（也称杨辉三角）。

解开这个题目，至少有三种方法。前两个方法可以在Wikipedia上面得到启示：http://en.wikipedia.org/wiki/Pascal's_triangle

1. 利用二项式展开的方法，启示杨辉三角的每一个元素都是二项式(x+y)^n的系数，可以用下面的公式来计算：

值得注意的是，如果行数从0算起，那么杨辉三角每一行的列数都等于行数+1。



2. 任意一行的任意一个元素，其实都是其所在的行数、列数以及其前一个元素的某种组合（函数）。
This algorithm is an alternative to the standard method of calculating individual cells with factorials. Starting at the left, the first cell's value v0 is 1. For each cell after, the value is determined by multiplying the value to its left by a slowly changing fraction:






where r = row + 1, starting with 0 at the top, and c = the column, starting with 0 on the left. For example, to calculate row 5, r = 6. The first value is 1. The next value is 1 × 5/1 = 5. The numerator decreases by one, and the denominator increases by one with each step. So 5 × 4/2 = 10. Then 10 × 3/3 = 10. Then 10 × 2/4 = 5. Then 5 × 1/5 = 1. Notice that the last cell always equals 1, the final multiplication is included for completeness of the series.



3. 利用杨辉三角的一个重要性质：底下一个元素是其上一层两个元素之和。下面的代码是MITBBS的网友speeddy提供：

int p1[20];
memset(p1, 0, 20*4);
p1[0] = 1;

for(int i=0; i<10; i++) {
  int next = 0;
  int prev = 0;

  for (int j = 0; j < i+1; j++) {
    if (j == 0) {
      p1[j] = 1;
      prev = 1;
    } else if (j == i) {
      p1[j] = 1;
    } else {
      next = p1[j];
      p1[j] += prev;
      prev = next;
    }
    cout << p1[j] << " ";
  }
  cout << endl;
}

result:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1