IEG 一面 1h

• golang 协程机制
• 协程的栈空间大小有限制吗？会主动扩展吗？
• golang context 应用场景
• context 的数据结构（树）
• golang 的 waitGroup 用法
• golang 性能问题怎么排查？（profile）
• HTTP 请求的报文格式
• x^2=n 怎么求 x？（二分）
• 海量数字，范围都是 1～10000，怎么排序？（计数排序）
• 算法题：
  • 点分十进制 ip 地址转为 32 位整数
  • 实现一个位图，包含 constructor(int size)、check(int val)、put(int val) 三个方法

// 位图
package main

import (
    "fmt"
)

type BitMap struct {
    bits []byte
}

func NewBitMap(capacity int) BitMap {
    return BitMap{make([]byte, (capacity+7)/8)}
}

func (bitmap *BitMap) Set(num int) {
    if (num > 8*len(bitmap.bits)) {
        return
    }
    pos := num / 8
    offset := uint(num % 8)
    bitmap.bits[pos] |= (0x80 >> offset)
}

func (bitmap *BitMap) Check(num int) bool {
    if (num > 8*len(bitmap.bits)) {
        return false
    }
    pos := num / 8
    offset := uint(num % 8)
    return bitmap.bits[pos] & (0x80 >> offset) > 0
}

func main() {
    bitmap := NewBitMap(15)
    bitmap.Set(2)
    bitmap.Set(15)
    bitmap.Set(30)
    fmt.Println(bitmap.Check(2))
    fmt.Println(bitmap.Check(3))
    fmt.Println(bitmap.Check(15))
    fmt.Println(bitmap.Check(30))
}

WXG 一面 1h

• 20mins 实习经历、项目经历
• 算法题：

(1) 给定一个二叉树，从根节点出发，按照前序遍历的顺序打印每个节点，最后回到根节点，比如：

    1
   /  \
  2    3
 / \  /  \
4   5 6  7

打印的结果是：1 2 3 2 5 2 1 3 6 3 7

(2) 根据这个打印结果，把树给建立起来

#include <iostream>
#include <vector>
using namespace std;

typedef struct Node {
  Node *left;
  Node *right;
  int value;
  Node(int val) : value(val), left(NULL), right(NULL) {}
} Node;

// 1. 打印
void solve(Node *root) {
  if (!root) return;
  cout << root->value << " ";
  if (root->left) {
    solve(root->left);
    cout << root->value << " ";
  }
  if (root->right) {
    solve(root->right);
    cout << root->value << " ";
  }
}

// 2. 建树
Node *buildTree(vector<int> nums) {
  if (nums.size() == 0) return NULL;
  Node *root = new Node(nums[0]);
  if (nums.size() == 1) return root;

  int i = 0, cnt = 0;  // i: 左子树最后一个位置
  while (i < nums.size() - 1 && nums[i + 1] < nums[i]) {
    i++;
    cnt++;
  }
  i += cnt;

  // 如果 i < 1，不会越界，返回空 vector
  // 左子树, [1, i)
  root->left = buildTree(vector<int>(nums.begin() + 1, nums.begin() + i));
  // 右子树，[i+1, n-1)
  root->right = buildTree(vector<int>(nums.begin() + i + 1, nums.end() - 1));
  return root;
}

int main() {
  solve(buildTree({3, 2, 3, 6, 5, 6, 7, 6, 3}));
  return 0;
}

WXG 二面 40mins

• 自我介绍
• 构造函数、析构函数的执行顺序
• 编写一个string类，实现：构造函数、析构函数、拷贝构造函数、operator =、c_str方法（返回const char*）
• sizeof 的输出：

// 64位机器
char str[] = "Hello"; sizeof (str); // 6
char* pstr = str; sizeof (pstr); // 8
const char* str_list[] = {"Hello", "World"}; sizeof (str_list); // 8
void* pbuf = malloc(100); sizeof ( pbuf ); // 8
int n = 10; sizeof (n); // 4

WXG 三面 1h

• 实习经历
• RPC 基本概念
• TIME_WAIT？有什么方法可以避免 TIME_WAIT？TIME_WAIT 是主动断开连接的一方还是被动断开的一方？
• 算法题：
  • 判断一个点是否在封闭图形里边，封闭图形所有点坐标都给出，说思路（这个查了下有个专门的算法 https://www.zhihu.com/question/26551754 任一射线穿过多边形，奇数个交点则位于多边形之内，偶数个交点则位于多边形之外）
  • 不区分大小写的 C 字符串比较
  • 搜索旋转数组最小值
  • 二叉树中任意 3 个节点的最近公共祖先

// 不区分大小写的 C 字符串比较
char toLowerCase(char c) {
  if (c >= 'A' && c <= 'Z') c = 'a' + c - 'A';
  return c;
}

int strcasecmp(const char *s1, const char *s2) {
  if (!s1 && !s2) return 0;
  if (!s1) return -1;
  if (!s2) return 1;
  int i = 0, j = 0, m = strlen(s1), n = strlen(s2);
  while (i < m && j < n) {
    char a = toLowerCase(s1[i]), b = toLowerCase(s2[j]);
    if (a == b) {
      i++;
      j++;
    } else if (a > b) {
      return 1;
    } else {
      return -1;
    }
  }
  if (i < m) return 1;
  if (j < n) return -1;
  return 0;
}

// 搜索旋转数组最小值
int findmin(int array[], int count) {
  int left = 0, right = count - 1;
  while (left <= right) {
    if (array[left] <= array[right]) {
      return array[left];
    }
    int mid = (left + right) / 2;
    if (array[left] <= array[mid])
      left = mid + 1;
    else
      right = mid;
  }
  return -1;
}

// 二叉树中任意 3 个节点的最近公共祖先
struct Node {
  struct Node *left, *right;
  int val;
  Node(int v) : val(v), left(NULL), right(NULL) {}
};

// 如果 a、b 都在 root 中，返回 a、b 的最小公共祖先，否则返回 a 或者 b 或者 NULL
Node* getAncestors(Node* root, int a, int b) {
  if (!root) return NULL;
  if (root->val == a || root->val == b) return root;
  Node* left = getAncestors(root->left, a, b);
  Node* right = getAncestors(root->right, a, b);

  // 当 a、b 分别位于 root 左右子树时，root 是它们的最小公共祖先
  if (left && right) return root;

  // left、right 是否是 a、b 的最小公共祖先还不确定，返回到某个祖先节点后确定
  return left ? left : right;
}

Node* getAncestors(Node* root, int a, int b, int c) {
  return getAncestors(root, getAncestors(root, a, b)->val, c);
}

int main() {
  Node* root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(3);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->right->left = new Node(6);
  root->right->right = new Node(7);
  cout << getAncestors(root, 1, 2, 3)->val << endl;
  cout << getAncestors(root, 2, 3, 4)->val << endl;
  cout << getAncestors(root, 2, 4, 5)->val << endl;
  cout << getAncestors(root, 3, 4, 5)->val << endl;
  cout << getAncestors(root, 3, 6, 7)->val << endl;
  return 0;
}