网易互娱面试总结

网易互娱面试总结

现场二面技术总监面试

这个人看起来挺和善的,实际上还是有一套的,让你写代码,然后眼睛编译给你指出错误,然后修改,然后他就去玩手机了…

  1. linux env multi-thread gdb debug 多线程调试 (回答对一半)
    首先介绍下基本命令

    • info threads 显示当前可以调试的所有线程,gdb会为每一个线程分配一个唯一ID,利用这个唯一Id可以切换到这个线程上下文环境中,并且前面有*标识的是当前调试的线程
    • thread ID 切换调试的线程为指定ID的线程。这个Id是gdb为每个线程分配的,并不是操作系统分配的PID,可以通过info threads命令查看
    • break xx.cpp:123 thread all 在所有线程中相应的行上设置断点
    • break apply ID1 ID2 cmd 让一个或者多个线程执行gdb命令cmd
    • break apply all cmd 让所有被调试线程执行GDB命令command
    • set print thread-events 设置线程创建提醒 当运行过程总产生新线程的时候会打印
    • set scheduler-locking off|on|step 这个是重点,经常被问到,在使用step或者continue命令调试当前被调试线程的时候,其他线程也是同时执行的,怎么只让被调试程序执行呢?通过这个命令就可以实现这个需求。
      • off 不锁定任何线程,也就是所有线程都执行,这是默认值。
      • on 只有当前被调试程序会执行。.
      • step 在单步的时候,除了next过一个函数的情况(熟悉情况的人可能知道,这其实是一个设置断点然后continue的行为)以外,只有当前线程会执行。该模式是对single-stepping模式的优化。此模式会阻止其他线程在当前线程单步调试时,抢占当前线。因此调试的焦点不会被以外的改变。其他线程不可能抢占当前的调试线程。其他线程只有下列情况下会重新获得运行的机会:当你‘next’一个函数调用的时候。当你使用诸如‘continue’、‘until‘、’finish‘命令的时候。其他线程遇到设置好的断点的时候。
  • 调试C++或者C的宏
    在编译程序的时候,加上-ggdb3参数,这样就可以调试宏

    • info macro – 你可以查看这个宏在哪些文件里被引用了,以及宏定义是什么样的。
    • macro –你可以查看宏展开的样子。
  • 关联源文件
    • 如果在编译情况下加上-g参数,那么就可以包含debug信息,否者gdb找不到符号表
    • 可以使用directory命令来设置源文件的目录
  • 条件断点
    基本语法break [where] if [condition] 尤其是在一个循环或递归中,或是要监视某个变量。注意,这个设置是在GDB中的,只不过每经过那个断点时GDB会帮你检查一下条件是否满足。
  • 添加参数
    1. gdb命令行的 –args 参数
    2. gdb环境中 set args命令。
  • 设置变量
    1. 可以直接使用set命令 设置上下文环境变量值,可以模拟一些很难在测试中出现的情况,以防未来程序出错
    2. 声明变量,然后使用,语法为$name = 1
  • X命令
    平时我们一般使用p命令打印参数值,但是这个命令必须指定变量名,不知道变量名的时候,我们可以使用X命令

    1. x\x 以十六进制输出
    2. x\d 以十进制输出
    3. x\c 以单字符输出
    4. x\i 反汇编 – 通常,我们会使用 x\10i KaTeX parse error: Expected ‘EOF’, got ‘来’ at position 7: ip-20 来̲查看当前的汇编(ip是指令寄存器)
    5. x\s 以字符串输出
  • command命令 把一组命令录制下来打包成‘宏’
  1. 循环队列判空 (OK)
    有三种方式处理这种问题

    1. 队列Queue结构中保存一个计数器count表示当前队列元素个数(最简单粗暴),但count等于队列cap的时候就队列满,count为0的时候队列空
    2. 少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。这种方法比较常用,但是面试官不让用… front指向队首元素,rear指向队尾元素的下一个元素。即:
      • 队空时: front=rear
      • 队满时: (rear+1)%maxsize=front
    3. 还有一个比较取巧的办法,优化第一种方案:使用一个状态flag变量,初始值为0,但入队成功置flag = 1,当出队成功设置flag = 0。我们可以使用 front == rear && flag 表示队列满(在入队操作之后导致front=rear),可以使用front == rear && !flag表示队列空(出队后导致f==r,显然是队列空)
  2. 单向队列反转 (OK) 很简单

现场面一面回忆总结

估计是小组长之类的面试官吧,去之前我还特意看下自己的衣装是否整洁,这个面试官感觉是从工地上回来的,衣服上很脏,典型程序员面孔,他问的问题算是比较全面
操作系统(linux)、数据库(mysql)、算法、数据结构、计算机网络基础、网络编程、语言基础(C++语言)、并发、以及具体业务设计,还有项目基本介绍,游戏服务器架构简单介绍

常见模块实现

  1. 定时器实现方式目前应用比较多的有时间轮和最小堆方式 , 优缺点其实就是算法复杂度:
    实现方式 StartTimer StopTimer PerTickBookkeeping
    基于链表 O(1) O(n) O(n)
    基于排序链表 O(n) O(1) O(1)
    基于最小堆 O(lgn) O(1) O(1)
    基于时间轮 O(1) O(1) O(1)
    https:\www.ibm.com\developerworks\cn\linux\l-cn-timers\

  2. 斐波那契数 多种实现

    1. 递归 最简单 粗暴 效率最低 存在大量重复计算
    2. 循环叠加 算法复杂度为O(n)
    3. 申请额外数组保存结果 去除重复计算 空间换时间
    4. 利用数学公式推导,矩阵相乘推导公式,算法复杂度为O(logn) 效率最高
      {f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1
      {f(n), f(n-1), f(n-1), f(n-2)}
      详情见 https:\www.cnblogs.com\python27\archive\2011\11\25\2261980.html
    5. 通项公式 这个实在是牛逼 一个公式搞定… 不是数学系 这些方法确实想不出 只能记忆

    1. 定理

  3. 敏感字过滤算法

    1. 正则匹配 面试官一般不会让你用这个 因为要匹配的内容太多 写正则表达式就很烦… 效率还不高 KMP算法 太慢 不能用
    2. 自己当时想到的一张方法为字典树TrieTree 这个方法太耗空间 时间复杂度为O(key_max_len) 很多生产环境确实是用这个实现的,别名有限状态机 DFA:DFA即Deterministic Finite Automaton,也就是确定有穷自动机
    3. 其他什么优化算法 其实也不用
  4. 数据库

    1. 数据库事务特性
      ACID 原子性 一致性 隔离性 持久性dura

    2. 事务隔离级别

      未提交读(Read uncommitted) 可能 可能 可能

      已提交读(Read committed) 不可能 可能 可能

      可重复读(Repeatable read) 不可能 不可能 可能

      可串行化(Serializable ) 不可能 不可能 不可能

      ·未提交读(Read Uncommitted):允许脏读,也就是可能读取到其他会话中未提交事务修改的数据(事务之间关系)
      ·提交读(Read Committed):只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别 (不重复读) (事务之间关系)
      ·可重复读(Repeated Read):可重复读。在同一个事务内的查询都是事务开始时刻一致的,InnoDB默认级别。在SQL标准中,该隔离级别消除了不可重复读,但是还存在幻象读 (事务内部)
      ·串行读(Serializable):完全串行化的读,每次读都需要获得表级共享锁,读写相互都会阻塞
      可重复读和提交读是矛盾的。在同一个事务里,如果保证了可重复读,就会看不到其他事务的提交,违背了提交读;如果保证了提交读,就会导致前后两次读到的结果不一致,违背了可重复读。
      可以这么讲,InnoDB提供了这样的机制,在默认的可重复读的隔离级别里,可以使用加锁读去查询最新的数据(提交读)。
      MySQL InnoDB的可重复读并不保证避免幻读,需要应用使用加锁读来保证。而这个加锁度使用到的机制就是next-key locks。
      总结:MySQL 四种事务隔离级的说明 – jyzhou – 博客园
      四个级别逐渐增强,每个级别解决一个问题。事务级别越高,性能越差,大多数环境read committed 可以用.记住4个隔离级别的特点(上面的例子);http:\\www.cnblogs.com\zhoujinyi\p\3437475.html

    3. 事务实现原理
      https:\draveness.me\mysql-transaction 介绍事务ACID的火滚日志实现 https:\www.cnblogs.com\wy123\p\8365234.html 具体日志格式

    4. innodb和myisam存储引擎的区别 https:\blog.csdn.net\xifeijian\article\details\20316775

      • MyISAM类型不支持事务处理等高级处理,而InnoDB类型支持,MyISAM类型的表强调的是性能,其执行数度比InnoDB类型更快,但是不提供事务支持,而InnoDB提供事务支持以及外部键等高级数据库功能。
      • InnoDB不支持FULLTEXT类型的索引。
      • InnoDB 中不保存表的具体行数,也就是说,执行select count() from table时,InnoDB要扫描一遍整个表来计算有多少行,但是MyISAM只要简单的读出保存好的行数即可。注意的是,当count()语句包含 where条件时,两种表的操作是一样的。
      • 对于AUTO_INCREMENT类型的字段,InnoDB中必须包含只有该字段的索引,但是在MyISAM表中,可以和其他字段一起建立联合索引。
      • 细节可以看链接 https:\blog.csdn.net\xifeijian\article\details\20316775和下面一个介绍
      • https:\www.jianshu.com\p\a957b18ba40d
    5. 对于like查询啥时候会用到索引 http:\thephper.com?p=142

    like 不能用索引? 这个确实不知道 难受
    尽量减少like,但不是绝对不可用,”xxxx%” 是可以用到索引的,
    想象一下,你在看一本成语词典,目录是按成语拼音顺序建立,查询需求是,你想找以 “一”字开头的成语(”一%“),和你想找包含一字的成语(“%一%”)
    除了like,以下操作符也可用到索引:
    <,<=,=,>,>=,BETWEEN,IN
    <>,not in ,!=则不行

    1. 索引类型
      https:\segmentfault.com\q\1010000003832312 http:\blog.codinglabs.org\articles\theory-of-mysql-index.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax