这是一次体验,虽然最终没有去,也可以从中学到些东西,送给那些需要的人。 这篇文章主要想给大家介绍下面试过程中涉及到的算法。

我面试的部门是字节跳动,大家熟悉的今日头条,面试的岗位是后台开发, 面试的地点是武汉,面试的方式主要是牛客网的在线面试,涉及的方面, 主要有:

  • 自我介绍
  • 项目介绍
  • 问答交互
  • 算法代码

其中问答环节涉及的东西比较广,而且比较深,跟以前的工作内容没有什么 太大的关系,常见的组建都会涉及到,比如redis的底层原理和mysql的索引 设计,会当场给你一个场景,让你去设计,所以如果你平时没有这方面的积累 和学习的话,很难在现场做出来,基本上就是挂了。这里说一下出现比较多的 关键字:

  • redis
  • mysql
  • 算法
  • mongo
  • spark
  • python set/map 底层实现

其中关于语言层面的东西很少,所以你光会语言是没有什么用的,得深入才行, 这也说明每天在公司简单的ifelse写业务的话,出去除非业务很匹配,然后 以从业经验混,不然下家都非常的难找。

一面要求写出两个算法:

  • 36进制加减法
  • 单链表加法

36进制加法

使用0-9, a-z表示36进制的数,刚好是36个,实现两个36进制数的加法。

这个算法的难点是两个字符串按位相加的算法,还需要考虑到进位问题,总体来讲, 如果之前没有这类基础的人,也很难想出巧妙的办法,这里我直接给出我的思路, 由于是字符串加法,不考虑转成10进制在做加法,直接把0-9,a-z连接成一个环, 从字符串末尾开始计算,每次计算出本位和进位,进位参与下一次的计算。

# -*- coding:utf-8 -*-

from itertools import izip_longest

BASE = (
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
    'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
    'u', 'v', 'w', 'x', 'y', 'z'
)

def add (a, b):

    if not (isinstance(a, str) and isinstance(b, str)):
        raise Exception("operator a, b must be string, and character in [0-9a-zA-Z]")

    z = 0
    result = ""
    a = a.lower()
    b = b.lower()
    for x, y in izip_longest(a[::-1], b[::-1]):
        if not x:
            x = "0"
        if not y:
            y = "0"

        try:
            index_x = BASE.index(x)
            index_y = BASE.index(y)
        except ValueError:
            raise Exception("operator a, b must be string, and character in [0-9a-zA-Z]")

        z, rem = divmod(index_x + index_y + z, 36)
        result += BASE[rem]

    if z != 0:
        result += str(z)
    return result[::-1]



if __name__ == "__main__":
    print add("0", "3x")
    print add("1b", "2x")
    print add("zzz", "1")
    print add("1B", "2X")
    # print add(123, "5212l")
    print add("1B", "2$X")

这里思路就是在Base里面循环取数来作为计算值,免去了转换的麻烦,进位参与下一轮计算。

单链表加法

计算两个单链表的加法,给出最后的链表。

这个题目的难点是单链表遍历的问题,我们知道单链表是从头开始遍历的,而如果要计算加法的话, 我们需要从链表尾部开始计算,所以这个就是难点,考虑到二叉树的先序遍历方法,不妨我们拿过 来套用一下:

# -*- coding: utf-8 -*-

from itertools import izip_longest


class Node(object):

    def __init__(self, value):
        self.__value = value
        self.__next = None

    @property
    def value(self):
        return self.__value

    @property
    def next_node(self):
        return self.__next

    @next_node.setter
    def next_node(self, node):
        self.__next = node


class Tree(object):

    def __init__(self, header=None):
        self.__header = header

    @property
    def header(self):
        return self.__header

    def insert_from_header(self, node):

        if not isinstance(node, Node):
            raise ValueError("param node must be instance of Node")
        if not self.__header:
            node.next_node = None
            self.__header = node
        else:
            node.next_node = self.__header
            self.__header = node

    def reverse_travel(self):

        if not self.header:
            return iter([0])

        def travel(node):
            if not node.next_node:
                yield node.value
            else:
                for value in travel(node.next_node):
                    yield value
                yield node.value

        return travel(self.__header)

    def add_another_tree(self, tree):
        tree3 = Tree()
        z = 0
        for a, b in izip_longest(self.reverse_travel(), tree.reverse_travel()):
            if not a:
                a = 0
            if not b:
                b = 0
            z, rem = divmod(a + b + z, 10)
            tree3.insert_from_header(Node(rem))
        if z > 0:
            tree3.insert_from_header(Node(z))

        self.__header = tree3.header

    def print_reverse_tree(self):
        result = []
        for value in self.reverse_travel():
            result.append(value)
        print result

    def print_tree(self):
        result = []
        for value in self.reverse_travel():
            result.insert(0, value)
        print result


if __name__ == "__main__":

    tree = Tree()
    ## [3, 2, 1]
    tree.insert_from_header(Node(1))
    tree.insert_from_header(Node(2))
    tree.insert_from_header(Node(3))
    tree.print_tree

    tree1 = Tree()
    tree1.insert_from_header(Node(1))
    tree1.insert_from_header(Node(2))
    tree1.insert_from_header(Node(3))
    tree1.print_tree()

    tree2 = Tree()
    tree2.insert_from_header(Node(4))
    tree2.insert_from_header(Node(6))
    tree2.insert_from_header(Node(7))
    tree2.print_tree()

    # add
    tree1.add_another_tree(tree2)
    tree1.print_tree()

    tree3 = Tree()
    tree3.print_tree()
    # add none
    tree1.add_another_tree(tree3)
    tree1.print_tree()

    tree4 = Tree()
    tree4.insert_from_header(Node(-1))
    tree4.print_tree()
    tree1.add_another_tree(tree4)
    tree1.print_tree()

加法的算法和上一题思路差不多,难点设计在与如何先序遍历一个单链表,这里我使用了递归和 iterator来实现。

寻找峰值

对给定的数列,从其中找出第一个峰值,要求找出的这个数字比他左右都大,对于第一个和第二个数字 来说,如果第一个数大于第二个,那么第一个数字就是,如果倒数第一个数字和倒数第二个数字,倒数第一个 比较大,那么倒数第一个就是峰值,要求给出logn的时间算法。

# -*- coding: utf-8 -*-


def find_tall(boys):

    boy_len = len(boys)
    if boy_len == 0:
        raise ValueError("empty data array")
    if boy_len == 1:
        return boys[0]
    elif boy_len == 2:
        if boys[0] >= boys[1]:
            return boys[0]
        else:
            return boys[1]
    else:
        half = boy_len / 2
        mid = boys[half]
        left = boys[half-1]
        right = boys[half+1]
        if mid >= left and mid >= right:
            return mid
        elif mid < left:
            return find_tall(boys[:half])
        else:
            return find_tall(boys[half+1:])

该题的难点就是对于时间的控制,上面使用的思路是每次丢掉一半的数据,因为只要求找到一个即可,所以 每次遍历一半,只对大于中值的一半的数据进行比较,递归进行中值比较。

总体来讲算法不算是太难,但是对于平时没有积累的人来说,要想当场写出这些算法的话,还是很难的, 这次无论是一面还是二面,统统都有算法,这也证实了头条确实很喜欢考算法。