达观数据面经

一轮笔试

二分查找 (Binary Search)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return -1

输入M、N，1 < M < N < 1000000，求区间[M,N]内的所有素数的个数。素数定义：除了1以外，只能被1和自己整除的自然数称为素数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def count_primes(self, m, n):
        primes = []
        for i in range(m, n):
            for j in range(2, i):
                if i % j == 0:
                    break
            else:
                primes.append(i)
        return len(primes)

1
2
3
4


class Solution:
    def count_primes(self, m, n):
        primes = filter(lambda x: not [x % i for i in range(2, x) if x % i == 0], range(m, n))
        return len(list(prime_list))

for/else

1
2
3
4
5
6
7
8


for n in range(2, 10):
    for x in range(2, n):
        if n % x == 0:
            print( n, 'equals', x, '*', n/x)
            break
    else:
        # loop fell through without finding a factor
        print(n, 'is a prime number')

最长无重复子字符串 (Longest Substring Without Repeating Characters)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        # mp stores the current index of a character
        mp = {}

        i = 0
        # try to extend the range [i, j]
        for j in range(n):
            if s[j] in mp:
                i = max(mp[s[j]], i)

            ans = max(ans, j - i + 1)
            mp[s[j]] = j + 1

        return ans

合并两个有序链表 (Merge Two Sorted Lists)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

删除排序链表中的重复元素 (Remove Duplicates from Sorted List)

1
2
3
4
5
6
7
8
9


class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

两个有序链表合并，去除相同值，要求辅助空间O（1）(merge two sorted linked list without duplicates)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def mergeSortedListWithouDuplicates(self, l1: ListNode, l2: ListNode) -> ListNode:
    	dummy = cur = slow = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                slow = l1
                l1 = l1.next
            else:
                slow = l2
                l2 = l2.next
            if curr.val != slow.val:
                curr.next = slow
                cur = cur.next
        cur.next = l1 or l2
        return dummy.next

最大子序和 (Maximum Subarray)

动态规划

1
2
3
4
5
6
7
8


class Solution:
    def maxSubArray(self, A):
        curSum = maxSum = A[0]
        for num in A[1:]:
            curSum = max(num, curSum + num)
            maxSum = max(maxSum, curSum)

        return maxSum

从一堆海量的数据中，选出前100大的数据，剑指offer上的原题

求最小k个数用最大堆，求最大k个数用最小堆。

1
2
3


>>> import heapq
>>> heapq.nlargest(3, [9, 8, 2, 4, 3, 5, 1])
[9, 8, 5]

用 python 实现链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


class Node(object):

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next_node

    def set_next(self, new_next):
        self.next_node = new_next
        
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
    def insert(self, data):
        new_node = Node(data)
        new_node.set_next(self.head)
        self.head = new_node
    def size(self):
        current = self.head
        count = 0
        while current:
            count += 1
            current = current.get_next()
        return count
    def search(self, data):
        current = self.head
        found = False
        while current and found is False:
            if current.get_data() == data:
                found = True
            else:
                current = current.get_next()
        if current is None:
            raise ValueError("Data not in list")
        return current
    def delete(self, data):
        current = self.head
        previous = None
        found = False
        while current and found is False:
            if current.get_data() == data:
                found = True
            else:
                previous = current
                current = current.get_next()
        if current is None:
            raise ValueError("Data not in list")
        if previous is None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

python 实现栈

1
2
3


list=[]
list.append(1)
list.pop() 

python队列

1
2
3


queue = []
queue.append('a')
queue.pop(0)

希尔排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def shellSort(arr):
    gap = n/2
    while gap > 0:
        for i in range(gap,n):
            temp = arr[i]
            j = i
            while  j >= gap and arr[j-gap] >temp:
                arr[j] = arr[j-gap]
                j -= gap
            arr[j] = temp
        gap /= 2

冒泡排序

1
2
3
4
5
6


def bubbleSort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

two-sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for i, n in enumerate(nums):
            complement = target - n
            if complement in d:
                return [d[complement], i]
            d[n] = i

给定一个字符串，去除字符串开头结尾中的空格，字符中间的多个空格转换成一个空格。(Remove extra spaces from a string)

1
2


def normalizeString(s):
    return ' '.join(s.strip().split())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


def normalizeString(s):
  listStr = list(s) # Convert to string for modifying list
  ind = 0
  while ind < len(listStr) - 1:
    if listStr[ind] == listStr[ind+1] and listStr[ind] == ' ':
      listStr.pop(ind+1)
    else:
      ind += 1

  # Check if first and last have spaces, if so remove them
  if listStr[0] == ' ':
    listStr.pop(0)
  if listStr[-1] == ' ':
    listStr.pop(-1)
  return ''.join(listStr)

找出一个数组的最大的两个值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def twoLargest(list1):
    maximum = max(list1[0],list1[1])
    secondmax = min(list1[0],list1[1])
    for i in range(2,len(list1)):
        if list1[i] > maximum:
            secondmax = maximum
            maximum = list1[i]
        elif list1[i] > secondmax and maximum != list1[i]:
            secondmax=list1[i]
    return maximum,secondmax

有序数组右移n位后查找某个元素 (Search in Rotated Sorted Array)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution:
    # @param {integer[]} numss
    # @param {integer} target
    # @return {integer}
    def search(self, nums, target):
        if not nums:
            return -1

        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) / 2
            if target == nums[mid]:
                return mid

            if nums[low] <= nums[mid]:
                if nums[low] <= target <= nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                if nums[mid] <= target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return -1

红黑树

堆排序

动态规划

二叉树

机器学习相关算法

写strcpy函数

柯里化通用实现和问题

求中位数

1
2
3
4
5
6
7
8
9


def median(lst):
    sortedLst = sorted(lst)
    lstLen = len(lst)
    index = (lstLen - 1) // 2
   
    if lstLen % 2:
        return sortedLst[index]
    else:
        return (sortedLst[index] + sortedLst[index + 1])/2.0

快排 (quicksort)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


def partition(arr, low, high):
    i = low - 1      
    pivot = arr[high]    
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
    
def quickSort(arr, low, high):
    if len(arr) == 1:
        return arr
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
        
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 

计算二叉树深度 (Maximum Depth of Binary Tree)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution(object):
    def maxDepth(self, root):
        depth = 0
        level = [root] if root else []
        while level:
            depth += 1
            queue = []
            for el in level:
                if el.left:
                    queue.append(el.left)
                if el.right:
                    queue.append(el.right)
            level = queue
            
        return depth

判断二叉树是否平衡二叉树 (Balanced Binary Tree)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution(object):
    def isBalanced(self, root):
            
        def check(root):
            if root is None:
                return 0
            left  = check(root.left)
            right = check(root.right)
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return 1 + max(left, right)
            
        return check(root) != -1

算法有旋转数组，快排等。

二轮技术初面

Python基础

Python列表去重
深浅拷贝
性能优化方面
装饰器
列表推导和生成器推导区别
init和new区别
讲一下面向对象中的多态
实现一个 Singleton 模式，不限用法。
问了一些语法糖执行的结果，列表推导等
随机数重新定范围

Network

udp和tcp区别

基于连接与无连接；

对系统资源的要求（TCP较多，UDP少）

UDP程序结构较简单

流模式与数据报模式

TCP保证数据正确性，UDP可能丢包

TCP保证数据顺序，UDP不保证
get 和 post 的区别

最直观的就是语义上的区别，get用于获取数据，post用于提交数据。

GET实际上也可以带body，POST也可以在url上携带数据

只要记得一般情况下，私密数据传输用POST + body就好。

为了避免传输中数据被窃取，必须做从客户端到服务器的端端加密。业界的通行做法就是https. 因此单独讨论POST和GET本身哪个更安全意义并不是太大
cookies 和 session 的区别，cookie 的安全性

这个Session是保存在服务端的，有一个唯一标识。在服务端保存Session的方法很多，内存、数据库、文件都有。集群的时候也要考虑Session的转移，在大型的网站，一般会有专门的Session服务器集群，用来保存用户会话，这个时候 Session 信息都是放在内存的，使用一些缓存服务比如Memcached之类的来放 Session。

实际上大多数的应用都是用 Cookie 来实现Session跟踪的，第一次创建Session的时候，服务端会在HTTP协议中告诉客户端，需要在 Cookie 里面记录一个Session ID，以后每次请求把这个会话ID发送到服务器

1，session 在服务器端，cookie 在客户端（浏览器） 2，session 默认被存在在服务器的一个文件里（不是内存） 3，session 的运行依赖 session id，而 session id 是存在 cookie 中的，也就是说，如果浏览器禁用了 cookie ，同时 session 也会失效（但是可以通过其它方式实现，比如在 url 中传递 session_id） 4，session 可以放在文件、数据库、或内存中都可以。 5，用户验证这种场合一般会用 session

因此，维持一个会话的核心就是客户端的唯一标识，即 session id
jwt token 和 session 的区别
目前主流的用户认证方法有基于token和基于session两种方式。

基于session的用户认证

基于session的认证流程如下：
1. 用户输入其登录信息
2. 服务器验证信息是否正确，并创建一个session，然后将其存储在数据库中
3. 服务器为用户生成一个sessionId，将具有sesssionId的Cookie将放置在用户浏览器中
4. 在后续请求中，会根据数据库验证sessionID，如果有效，则接受请求
5. 一旦用户注销应用程序，会话将在客户端和服务器端都被销毁
基于token（令牌）的用户认证

最常用的是JSON Web Token（jwt）：
1. 用户输入其登录信息
2. 服务器验证信息是否正确，并返回已签名的token
3. token储在客户端，例如存在local storage或cookie中
4. 之后的HTTP请求都将token添加到请求头里
5. 服务器解码JWT，并且如果令牌有效，则接受请求
6. 一旦用户注销，令牌将在客户端被销毁，不需要与服务器进行交互一个关键是，令牌是无状态的。后端服务器不需要保存令牌或当前session的记录。
由于jwt具有一次性的特性。单点登录和会话管理非常不适合用jwt

适合使用jwt的场景：
- 有效期短
- 只希望被使用一次

Operating systems

进程和线程区别

Databases

设计表结构，怎么优化

MySQL中你用过哪些引擎，说说他们的区别，谈谈索引，以及它的优缺点，手写SQL，

区别：

InnoDB 支持事务，MyISAM 不支持事务。这是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；

InnoDB 支持外键，而 MyISAM 不支持。对一个包含外键的 InnoDB 表转为 MYISAM 会失败；

InnoDB 是聚集索引，MyISAM 是非聚集索引。聚簇索引的文件存放在主键索引的叶子节点上，因此 InnoDB 必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。而 MyISAM 是非聚集索引，数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。

InnoDB 不保存表的具体行数，执行 select count(*) from table 时需要全表扫描。而MyISAM 用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快；

InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其他查询和更新都会被阻塞，因此并发访问受限。这也是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；

如何选择：

是否要支持事务，如果要请选择 InnoDB，如果不需要可以考虑 MyISAM；

如果表中绝大多数都只是读查询，可以考虑 MyISAM，如果既有读写也挺频繁，请使用InnoDB。

系统奔溃后，MyISAM恢复起来更困难，能否接受，不能接受就选 InnoDB；

MySQL5.5版本开始Innodb已经成为Mysql的默认引擎(之前是MyISAM)，说明其优势是有目共睹的。如果你不知道用什么存储引擎，那就用InnoDB，至少不会差。

mysql 的联合索引、覆盖索引

mysql的b+树索引遵循“最左前缀”原则，添加了一个联合索引（username,password）,特别注意这个联合索引的顺序。联合索引的多个字段中，只有当查询条件为联合索引的一个字段时，查询才能使用该索引。索引可以用于查询条件字段为索引字段，根据字段值最左若干个字符进行的模糊查询。

覆盖索引（covering index）指一个查询语句的执行只用从索引中就能够取得，不必从数据表中读取。也可以称之为实现了索引覆盖。如果一个索引包含了（或覆盖了）满足查询语句中字段与条件的数据就叫做覆盖索引。

当一条查询语句符合覆盖索引条件时，sql只需要通过索引就可以返回查询所需要的数据，这样避免了查到索引后再返回表操作，减少I/O提高效率。使用覆盖索引Innodb比MyISAM效果更好—-InnoDB使用聚集索引组织数据，如果二级索引中包含查询所需的数据，就不再需要在聚集索引中查找了

注：遇到以下情况，执行计划不会选择覆盖查询 1.select选择的字段中含有不在索引中的字段，即索引没有覆盖全部的列。 2.where条件中不能含有对索引进行like的操作。
1
explain

Redis有哪些数据结构

string(字符串)、list(列表)、hash(字典)、set(集合) 和zset(有序集合)

redis 的数据类型，hash 类型的应用场景

Redis 中的字典相当于 Java 中的 HashMap，内部实现也差不多类似，都是通过 “数组 + 链表” 的链地址法来解决部分 哈希冲突，同时这样的结构也吸收了两种不同数据结构的优点。

举个实例来描述下Hash的应用场景，比如我们要存储一个用户信息对象数据，包含以下信息：用户ID为查找的key，存储的value用户对象包含姓名，年龄，生日等信息

Redis的Hash实际是内部存储的Value为一个HashMap，也就是说，Key仍然是用户ID,value是一个Map，这个Map的key是成员的属性名，value是属性值，这样对数据的修改和存取都可以直接通过其内部Map的Key(Redis里称内部Map的key为field),也就是通过 key(用户ID) + field(属性标签)就可以操作对应属性数据了，既不需要重复存储数据，也不会带来序列化和并发修改控制的问题。

Debugging

调试采用什么手段

DevOps

Docker，docker compsoe以及swarm

docker 的镜像和容器的区别

images很好理解，跟平常使用的虚拟机的镜像一个意思，相当于一个模版 container是images运行时的的状态。 docker对于运行过的image都保留一个状态container，可以使用命令docker ps来查看正在运行的container，对于已经退出的container，则可以使用docker ps -a来查看。如果你退出了一个container而忘记保存其中的数据，你可以使用docker ps -a来找到对应的运行过的container使用docker commit命令将其保存为image然后运行。

k8s 的 pro 是什么算法

简历

介绍一下自己的项目经验

项目中遇到的问题，怎么解决的

之后问些项目经验之类的，还让画技术流程图。

你这些笔试算法的整个思路是怎么样的.

问了一些数据分析的问题，给的小场景，怎么去解决

NLP

公司是人工智能公司，岗位是要掌握一定的机器学习算法，一些关于NLP的领域知识。

重视NLP基础知识结构和算法思想

问了一些机器学习有关的算法，像支持向量机啊，隐马尔科夫原理啊，怎么分词之类的

在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中，状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。

F值怎么计算、信息增益

LR算法，SVM

问NLP中了解哪些问题？LSTM的作用是什么。

三轮技术二面

计算机网络

操作系统

计算机组成原理

问工作习惯和性格方面

比较喜欢Angular全家桶

问如果一个问题不止有一个答案，会用什么方法来选出一个最好的？

仿照波特五力模型, 供应商的议价能力, 购买者的议价能力, 新进入者的威胁, 替代品的威胁

四轮HR

薪资待遇方面

介绍一下你最有成就的工作经验？当时碰到什么问题，怎么做让你感觉有很大成就感？

Django ORM传入Pandas dataframe

你在面试之前了解我们公司嘛？知道我们公司是干什么的嘛？ – 搜你所想

Any

自我介绍

我叫郑烨，拥有5年的开发经验，上一份工作是在华为大学开发在线学习平台，我是开发主要负责人，期间与产品澄清需求，顺利上线整个项目。目前在华为科技有限公司OD外包担任软件工程师，期间同时承担SE和BA两个角色，输出IT方案以及技术方案，跟进开发进展保证，最终每个需求的版本都能够及时交付。展望未来，我希望能够在贵司这样以AI为导向的公司工作，我相信我的开发经验和业务分析能力是很好的助力，能够与贵司一起成长。

根据工作经验提两个问题

你工作中遇到的难点是什么，怎么克服的。

你的优点和缺点

解决问题的能力以及耐心

缺乏自控力能力，容易沉迷与网络游戏，但是是阶段性的，大学三年，大四一年

讲述一下你在学校学的某一个比较感兴趣的技术点

聊了聊个人的职业发展，规划，

短期内，我的目标之一是继续发展我的英语水平。能够在一个领域独挡一面，英语带来更多的机会。两年内。Coding不是我的远期目标。

Table of Contents

达观数据面经

一轮笔试

二分查找 (Binary Search)

输入M、N，1 < M < N < 1000000，求区间[M,N]内的所有素数的个数。素数定义：除了1以外，只能被1和自己整除的自然数称为素数

最长无重复子字符串 (Longest Substring Without Repeating Characters)

合并两个有序链表 (Merge Two Sorted Lists)

删除排序链表中的重复元素 (Remove Duplicates from Sorted List)

两个有序链表合并，去除相同值，要求辅助空间O（1）(merge two sorted linked list without duplicates)

最大子序和 (Maximum Subarray)

从一堆海量的数据中，选出前100大的数据，剑指offer上的原题

用 python 实现链表

python 实现栈

python队列

希尔排序

冒泡排序

two-sum

给定一个字符串，去除字符串开头结尾中的空格，字符中间的多个空格转换成一个空格。(Remove extra spaces from a string)

找出一个数组的最大的两个值

有序数组右移n位后查找某个元素 (Search in Rotated Sorted Array)

红黑树

堆排序

动态规划

二叉树

机器学习相关算法

写strcpy函数

柯里化通用实现和问题

求中位数

快排 (quicksort)

计算二叉树深度 (Maximum Depth of Binary Tree)

判断二叉树是否平衡二叉树 (Balanced Binary Tree)

算法有旋转数组，快排等。

二轮技术初面

Python基础

Network

Operating systems

Databases

Redis有哪些数据结构

redis 的数据类型，hash 类型的应用场景

Debugging

DevOps

简历

NLP

三轮技术二面

计算机网络

操作系统

计算机组成原理

问如果一个问题不止有一个答案，会用什么方法来选出一个最好的？

四轮HR

介绍一下你最有成就的工作经验？当时碰到什么问题，怎么做让你感觉有很大成就感？

你在面试之前了解我们公司嘛？知道我们公司是干什么的嘛？ – 搜你所想

Any

自我介绍

根据工作经验提两个问题

你工作中遇到的难点是什么，怎么克服的。

你的优点和缺点

讲述一下你在学校学的某一个比较感兴趣的技术点

聊了聊个人的职业发展，规划，