面试被鄙视，经验不足，一败涂地！请看我被问的问题!（100％原版）

Arthur.Echo

Post by x11
循环链表的判断，查到这里 http://chinaunix.net/jh/23/410637.html
这个供参考 http://my.opera.com/XSK/blog/show.dml/334900
还有这个 http://www.nit-pro.org/ReadNews_ ... =%E8%A5%BF%E5%AE%89

X11兄提供的这个链接里的算法是错误的：

2. struct list{
3.         int data;
4.         struct list *next;
5. };
7. int has_circle(struct list *head)
8. {
9.         struct list *cur1 = head;
10.         int pos1 = 0;
13.         while(cur1){
14.                 struct list *cur2 = head;
15.                 int pos2 = 0;
16.                 pos1 ++;
17.                 while(cur2){
18.                         pos2 ++;
19.                         if(cur2 == cur1){
20.                                 if(pos1 == pos2)
21.                                         break;
22.                                 else
23.                                         return 1; //has circle
24.                         }
25.                         cur2 = cur2->next;
26.                 }
27.                 cur1 = cur1->next;
28.         }
30.         return 0;
31. }

复制代码

想像一下，如果链表的形状如数字”6“一样的话，且这时将head置于书写”6“的起笔处的话，这时内层while循环将陷入死循环.

dyte300

Post by 小锁
其实“有圆”和“是圆”是不同的。
我也贴一个有圆的算法：
[php]
int has_circle(struct list *head)
{
    struct list *ptr1, *ptr2;

    ptr1 = head;
    if (ptr1 == NULL)
        return 0;
    ptr2 = ptr1->next;

    while (1) {
        if (ptr2 == NULL)
            return 0;
        if (ptr2 == ptr1)
            return 1;
        ptr2 = ptr2->next;
        if (ptr2 == NULL)
            return 0;
        if (ptr2 == ptr1)
            return 1;
        ptr2 = ptr2->next;
        ptr1 = ptr1->next;
    }

    return 0;
}
[/php]

ptr2遍历表的速度是ptr1的两倍？

iveney

涉及到自旋锁了，一般的软件开发职位不是linux内核研发相关的我想不会出这道题吧？如果楼主没弄错的话看来是HR存心不让你进公司了

hoho_zhao

我也是认为这样，没办法，如果我强的话，他问什么我都不怕！。。。努力中。。。

ideawu

12字节是因为内存对齐(padding), 微机原理方面的材料有讲, 有些c语言的教材也有讲.

magang2

刚考完计算机系统结构，内存对齐，记忆犹新呵呵。其实，int和char在不同的机器里面占的位子不一样吧？bool型在一些编译器里还占4个字节呢。好好回想一下后面几个题嘛，大家一起讨论。

magang2

""如果链表的形状如数字”6“一样的话，且这时将head置于书写”6“的起笔处的话，这时内层while循环将陷入死循环.""

     的确，那么如果记录以前访问过的结点的话，代价又太大了。可以这样，每个节点都置标志位，初值为０，访问一个节点的时候就++，最后，如果有圈，就说明找到了一个环。如果找到了的这个就是当初的头节点，就说明是一个大圈，而不是"６"或其它的什么。

magang2

""如果链表的形状如数字”6“一样的话，且这时将head置于书写”6“的起笔处的话，这时内层while循环将陷入死循环.""

     的确，那么如果记录以前访问过的结点的话，代价又太大了。可以这样，每个节点都置标志位，初值为０，访问一个节点的时候就++，最后，如果有一个节点值被加到了２，就说明找到了一个环。如果找到了的这个就是当初的头节点，就说明是一个大圈，而不是"６"或其它的什么。

hoho_zhao

明天又面试，现在我没有时间思考，先谢谢magang2兄。不过明天把握更没有，
是“嵌入式工程师”，近期都做小东东，用的上的知识才用上，其它的，都忘罗。。。。

去，还是要去的，不会退缩！

wsw

公司苛刻了点，楼主兄的第一个问题是编译器相关的，也不是每个编译器都会有机器字对齐。刚毕业没经验很正常。关于第二个函数问题，一般都可以查到，就算不知道以后工作多man一下就可以了。关于数据结构的问题你写出伪代码就可以了吧。

我也面试过了，今天刚签，是做LInux＋C开发，关于驱动和操作系统有关的。笔试的时候就考了一些C的基础，一些指针的精巧运用，不见得很难。

可能做嵌入式的要求比较高吧。 楼主不要气馁，继续努力。好运！