微芯研究院面试

1. 算法

一、 给定一个无序、无重复元素的整数数组和一个目标值,如果数组中有两个数之差等于目标值,就输出这两个数。请找到所有这样的整数对,且时间复杂度尽可能小∶
示例输入∶ array=[1,9,3,8,7,6,5,-9],t=5;
示例输出∶ result=[[6,1], [8,3]]。

二、 字符串原地压缩
压缩函数，void compress(char[] str):
示例输入∶ str= [“a”,”a”,”b”,”b”,”e”,”c”,”e”]
示例输出∶ 无，str 此时变为[“a”,”2”,”b”,”2”,”c”,”3”

三、 给定一组数据,求 W 树的树根值
注 1∶W树是一种叶子节点为整型数据，其余节点为子节点的加权乘法值的一类完全二叉树，子节点为空可视为此处数值为 0，如下图所示。
注2∶加权乘法具体为∶parent= 2 left+3 right。




输入∶ 叶子节点数据,用数组 int[]data 表示；
输出∶W树的树根值 int root 。
示例输入∶ data=[2,3,1]
示例输出∶root=32

20分钟，写两道

2. 区块链

• 对区块链了解多少啊，共识知道吗
  • pow 工作量证明
  • pos 股权证明
  • dpos 委托权益证明法
• 说说pos
  • 由系统权益代替算力来决定区块记账权，拥有的权益越大获得记账权的概率就越大

3. go

• 觉得go那儿设计的比较好
  • channel
    • 有缓冲，无缓冲
    • 数据结构
• mutex
  • 两种工作模式
    • 饥饿模式
    • 正常模式
• map
  • 线程安全吗
  • 为什么线程不安全
    • 增删改会触发标志位，导致panic
  • 怎么实现高并发map
    • 只说了使用RWmutex
• slice如何扩容
  • 小于1024，复制2倍
  • 大于1024，内存对齐，大于1.25倍或2倍