面试题

二叉树

非递归实现二叉树遍历

节点:

class Node(object):
    value = 0
    left = None
    right = None

前序遍历

def func(root):
    s = []
    p = root
    while s or p is not None:
        while p is not None:
            print p.value
            s.append(p)
            p = p.left

        if s:
            p = s.pop()
            p = p.right

中序遍历

def func(root):
    s = []
    p = root
    while s or p is not None:
        while p is not None:
            s.append(p)
            p = p.left

        if s:
            p = s.pop()
            print p.value
            p = p.right

后序遍历

def func(root):
    s = []
    p = root
    b = None
    s.push(root)
    while s:
        p = s[-1]
        # 只有这个节点没有子节点，或者这个节点右节点被访问过，或者这个节点没有右节点且左节点被访问过，这个节点才可以被访问
        if (p.left is None and p.right is None) or (
            b == p.right or (b == p.left and p.right is None)):
            print p.value
            s.pop()
            b = p
        else:
            if p.right:
                s.push(p.right)
            if p.left:
                s.push(p.left)

排序

快速排序

#include<stdio.h>
void quickSort(int a[],int left,int right) {
　　int i = left;
　　int j = right;
　　int temp = a[left];
　　if(left >= right)
　　　　return;
　　while(i != j) {
　　　　while(i < j && a[j] >= temp) 
　　　　    j--;
　　　　if(j > i)
　　　　　　a[i] = a[j];//a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完之后a[j],有空位
　　　　while(i < j && a[i] <= temp)
　　　　    i++;
　　　　if(i < j)
　　　　　　a[j] = a[i];
　　}
　　a[i] = temp;//把基准插入,此时i与j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
　　quickSort(a, left, i - 1);/*递归左边*/
　　quickSort(a, i+1, right);/*递归右边*/
}

int main()
{
    int a[9]={8,2,6,12,1,9,5,5,10};
    int i;
    quickSort(a,0,8);/*排好序的结果*/
    for(i=0;i<8;i++)
        printf("%4d",a[i]);
    getchar();
    return 0;
}

def qsort(a, left, right):
    i = left
    j = right
    temp = a[i]
    if left >= right:
        return
    while i != j:
        while i < j and a[j] >= temp:
            j -= 1
        if j > i:
            a[i] = a[j]
        while i < j and a[i] <= temp:
            j += 1
        if i < j:
            a[j] = a[i]
    a[i] = temp
    qsort(a, left, i -1)
    qsort(a, i + 1, right)

其他问题

算法题

给一个长度为 n 的字符串，找出其中最长的回文串长度。

解法一：暴力

效率： n^3

解法二：字符串翻转，最长公共子序列

效率：n^2

解法三：Manacher

效率：n

工程题

假设我们有一个敏感词词库，1000万个词，如何判断一个词是否是敏感词，如何判断一句话中是否有敏感词。

布隆过滤器

链接

面试题