首页 > 腾讯 WXG 后端开发一二三面面经
头像
ShowMeTheCodee
编辑于 2020-09-30 10:44
+ 关注

腾讯 WXG 后端开发一二三面面经

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;
}

更多模拟面试

全部评论

(7) 回帖
加载中...
话题 回帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐