名企的一些面试题，看你能做出几道

最近一段时间因为要准备微软面试，所以看了不少资料，也遇到不少挺有意思的题目，与大家分享一下，下面贴出的所有代码，思路不一定是自己原创的，但是代码基本都是按照自己的理解重写的，并且经过编译运行的。暂时只贴出这些，以后还会继续贴出更多，如果有任何问题，欢迎交流哈！

 

1. 输入一个二元查找树，将该二元查找树转换成一个排序的双向链表，要求不能创建任何新的节点，只调整指针的指向。

static tree_t *
_tree_to_list(tree_t *root, tree_t *last)
{
    if (root == NULL)
        return last;

    if ((last = _tree_to_list(root->left, last)) != NULL)
        last->right = root;

    root->left = last;

    return _tree_to_list(root->right, root);
}

static tree_t *
tree_to_list(tree_t *root)
{
    tree_t *last = _tree_to_list(root, NULL);
    for ( ; last->left; last = last->left);
    return last;
}

 

2. 设计包含 max 函数的栈，定义栈的数据结构，假设栈中元素都是非负整数，要求添加一个 max 函数，能够得到栈的最大元素，要求函数 max , push 以及 pop 的时间复杂度都是O（1）.

struct stack {
    int        *array;
    int        *link;
    int         size;
    int         top;
    int         maxidx;
};
typedef struct stack stack_t;

static stack_t *
stack_new(int n)
{
    stack_t *stack = calloc(1, sizeof *stack);
    stack->array = calloc(n, sizeof(int));
    stack->link = calloc(n, sizeof(int));
    stack->size = n;
    stack->top = 0;
    stack->maxidx = -1;
    return stack;
}

static int
stack_empty(stack_t *s)
{
    return s->top <= 0;
}

static int
stack_full(stack_t *s)
{
    return s->top >= s->size;
}

static int
stack_max(stack_t *s)
{
    if (s->maxidx == -1)
        return    -1;
    else
        return s->array[s->maxidx];
}

static void
stack_push(stack_t *s, int n)
{
    if (stack_full(s))
        return;

    s->array[s->top] = n;

    if (n > stack_max(s)) {
        s->link[s->top] = s->maxidx;
        s->maxidx = s->top;
    }
    else {
        s->link[s->top] = -1;
    }

    s->top++;
}

static int
stack_pop(stack_t *s)
{
    int     n;

    if (stack_empty(s))
        return -1;

    n = s->array[--s->top];
    s->array[s->top] = 0;

    if (s->maxidx == s->top)
        s->maxidx = s->link[s->top];

    return n;
}

 

3. 给定一个数组，元素为正负整数都可能，求其子数组的最大和。

static int
max_sum(int arr[], int n)
{
    int sum = 0, max = INT_MIN, i;
    for (i = 0; i < n; i++) {

        if (sum < 0)
            sum = arr[i];
        else
            sum += arr[i];

        if (sum > max)
            max = sum;
    }

    return max;
}

 

4. 输入一个整数和一颗二元树，从树的根节点开始往下访问一直到叶节点所经过的所有节点形成一条路径
找出其各节点的和与输入整数相等的所有路径

static void
helper(tree_t *root, int sum)
{
    stack_push(s, root->n);

    sum -= root->n;

    if (sum == 0) {
        stack_show(s);
        goto done;
    }

    if (root->left != NULL)
        helper(root->left, sum);
    if (root->right != NULL)
        helper(root->right, sum);

done :
    stack_pop(s);
    sum += root->n;
}

 

5. 输入n个整数，输出其中最大的k个

static heap_t *h;

static void
heap_choose(int arr[], int n, int k)
{
    h = heap_init(k);

    int i;
    for (i = 0; i < n; i++) {
        if (i < k) {
            heap_insert(h, arr[i]);
        } else {
            if (arr[i] > heap_min(h)) {
                heap_delete(h);
                heap_insert(h, arr[i]);
            }
        }
    }
}

 

6. 输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果

#if 0
即数组最后一个为根，由该根可将数组分为两部分，左边即为左子树，右边为右子树，
先遍历数组直到遇到一个元素大于根，则可认为该点为分界，左边为左子树，右边为
右子树，继续遍历数组，倘若发现右边有元素小于根，说明出错，否则递归即可
#endif

static int
is_post_order_result(int arr[], int n)
{
    int i, j;

    if (n == 0 || n == 1)
        return 1;

    int head = arr[n - 1];
    for (i = 0; arr[i] < head; i++) ;
    for (j = i; j < n; j++)
        if (arr[j] < head)
            return 0;

    return is_post_order_result(arr, i)
        && is_post_order_result(&arr[i], n - i - 1);

}

 

7. 求一颗二叉树中相距最远的两个节点之间的距离

static int
helper(tree_t *root, int *depth)
{
    if (root == NULL) {
        *depth = 0;
        return 0;
    }

    int ld, rd;
    int maxleft = helper(root->left, &ld);
    int maxright = helper(root->right, &rd);

    *depth = MAX(ld, rd) + 1;

    return MAX3(maxleft, maxright, ld + rd);
}

 

8. 求 1 + 2 + 3 + ... + n ,要求不能用乘除，循环, if/else, switch/case 及A ？B ：C等语句

typedef int (*func)(int);

static int nofunc(int n);
static int yesfunc(int n);

func dispatch[] = {yesfunc, nofunc};

static int nofunc(int n) {return 0;}

static int range;

static int
yesfunc(int n)
{
    return n + dispatch[n / range](n + 1);
}

还有一种方法，更简洁一些

static int
sum(int n)
{
    int val = 0;
    (void) (n > 0 && (val = n + sum(n - 1)));
    return val;
}

再举个类似的例子，如果要你依序打印出从 1 到 10000 的所有整数，也按同样的要求，你该如何做

int main(int i)
{
    printf("%d ", i);
    (main + (exit - main) * (i / 10000))(i + 1);
    return 0;
}

注意，如果编译有问题的话就给后面两个相减的函数地址都强制转换成int或char *什么的，还有运行时不用跟任何命令行参数，所以 i 的起始值就是 1。

9. 输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的节点都大于右子树的节点，用递归和非递归两种方法完成树的镜像转换

static void
tree_mirror_recursive(tree_t *root)
{
    if (root) {
        tree_mirror_recursive(root->left);
        tree_mirror_recursive(root->right);
        swap(root->left, root->right);
    }
}

static void
tree_mirror_nonrecursive(tree_t *root)
{
    stack_t *s = stack_init();
    stack_push(s, root);
    while (!stack_empty(s)) {
        tree_t *p = stack_pop(s);
        swap(p->left, p->right);
        if (p->left != NULL)
            stack_push(s, p->left);
        if (p->right != NULL)
            stack_push(s, p->right);
    }
}

10. 输入一颗二元树，分层遍历，同一层中按照从左往右的顺序打印，给出递归和非递归方法

static int
_tree_show_levelorder_recursive(tree_t *root, int depth)
{
    if (root == NULL)
        return 0;

    if (depth == 0)
        tree_print_node(root);
    else {
        return _tree_show_levelorder_recursive(root->left, depth - 1)
                + _tree_show_levelorder_recursive(root->right, depth - 1);
    }
}

static void
_tree_show_levelorder_nonrecursive(tree_t *root)
{
    if (root == NULL)
        return;

    seq_t *seq = seq_init();
    seq_push(seq, root);

    while (!seq_empty(seq)) {
        root = seq_pop(seq);
        tree_print_node(root);
        if (root->left)
            seq_push(seq, root->left);
        if (root->right)
            seq_push(seq, root->right);
    }
}

 

11. 在一个字符串中找到第一个只出现一次的字符，如输入abaccdeff，则输出b

static char
first_single(char *str)
{
    int arr[255];
    memset(arr, 0, sizeof(int) * 255);

    char *p;
    for (p = str; *p != '\0'; p++)
        arr[*p]++;

    for (p = str; *p != '\0'; p++) {
        if (arr[*p] == 1)
            return *p;
    }

    return '\0';
}

12. n个数字(0,1,2,...n-1)形成一个圆圈，从数字0开始，每次从这个圈中删除第m个数字(第一个为当前数字本身，第二个为当前数字的下一个数字)当一个数字删除后，从被删除数字的下一个继续删除第m个数字，求出在这个圆圈中剩下的最后一个数字

static int
circle(int n, int m)
{
    int fn = 0, i;
    for (i = 2; i <= n; i++)
        fn = (fn + m) %i;
    return fn;
}

 

13. 给定两个正整数n和sum，打印出1到n之间整数和为sum的所有组合。如对于n = 6, sum = 10, 有10 = 2 + 3 + 5 = 1 + 2 + 3 + 4 ...

static stack_t *s;

static void
find_sum(int sum, int n)
{
    if (n <= 0 || sum <= 0)
        return;

    stack_push(s, n);

    if (sum == n)
        stack_show(s);

    find_sum(sum - n, n - 1);

    stack_pop(s);

    find_sum(sum, n - 1);
}

如果可以让整数重复的话，如10 = 3 + 3 + 4, 只需将上面的find_sum(sum - n, n - 1)改为find_sum(sum - n, n)即可

 

14. 输入一个字符串，打印出该字符串中所有字符的所有排列，如输入bac，则打印出abc, acb, bac, bca, cab, cba

static void
helper(char *str, char *begin)
{
    char    *p;

    if (str == NULL || begin == NULL)
        return;

    if (*begin == '\0')
        printf("%s\n", str);
    else {
        for (p = begin; *p != '\0'; p++) {
            swap(p, begin);
            helper(str, begin + 1);
            swap(p, begin);
        }
    }
}

15. 计算字符串的距离。我们定义了一套操作方法把两个不相同的字符串变为相同，如修改一个字符或增删一个字符，而需要操作的最小次数即为字符串的距离，给定任意两个字符串，写一个函数求其距离

static int
distance(char *strA, int aleft, int aright,
            char *strB, int bleft, int bright)
{
    if (aleft > aright) {
        if (bleft > bright)
            return 0;
        else
            return bright - bleft + 1;
    }

    if (bleft > bright) {
        if (aleft > aright)
            return 0;
        else
            return aright - aleft + 1;
    }

    if (strA[aleft] == strB[bleft])
        return distance(strA, aleft + 1, aright, strB, bleft + 1, bright);
    else {
        int t1 = distance(strA, aleft + 1,     aright, strB, bleft,         bright);
        int t2 = distance(strA, aleft,         aright, strB, bleft + 1,     bright);
        int t3 = distance(strA, aleft + 1,     aright, strB, bleft + 1,     bright);
        return min(t1, t2, t3) + 1;
    }
}

 

16. 写一个轻量级的正则表达式的匹配引擎，如给定a*b?c和"aufbec"，返回1，其中*表示0或多个字符，?表示1个字符

static int
match(char *pat, char *str)
{
    switch (*pat) {
        case '\0' : return !*str;
        case '*' :    return match(pat + 1, str) || *str && match(pat, str + 1);
        case '?' : return *str && match(pat + 1, str + 1);
        default     : return *pat == *str && match(pat + 1, str + 1);
    }
}