腾讯wxg C++一面

写面经攒人品、攒运气

腾讯wxg企业微信实习基地 C++一面(2.20) --挂

开局1小时算法题手撕：

1. 给出循环节长度，和分母，是否存在一个分子，使得其为无限循环小数，并且存在指定长度的循环节 (不会，想到数论，但是没推出来，没咋做过这种题)

2. 有一个最大承重为m的篮子，和n个桃子，a[i]表示第几个桃子的重量，不能使用相同重量的桃子，解决篮子最多放几个桃子

3. 给出一个x，和一个数组，可以对数组元素随机异或x，求最大的异或后的和是多少

实习项目拷打(1h)

场景题

- 有一个服务端，多个终端通过websocket方式与服务端连接，当一个客户端发送一个websocket请求包给服务端，服务端接收后，但是此时客户端挂掉了，然后重连，因为服务端任务重，所以在客户端重新建立连接后再将回应包发出，此时客户端需要识别这个包是上一个连接的包来防止冲突，使用什么方式解决

--- 开始说使用tcp的合法序列号校验和时间戳校验，因此面试官增加了回应包是在客户端重新连接后发出的

--- 思考了一会，说了用cookie，比对包cookie和当前客户端cookie就知道了

八股：

- 消息队列用过吗？

- 关系型数据库和非关系型数据库区别

- 用过哪些数据库？ ---(mysql,redis)

- redis你一般用来干嘛? ---(缓存)

- 如果redis节点挂了咋办呢？ ---(配置使用redis主从节点，利用哨兵模式，主节点挂了，从节点提上去)

其他：

- 对实习有啥期望，进来想做啥，为啥想做后台开发? ---(感兴趣，希望做个方向的东西)

- 用过AI工具吗？你用这些AI工具用来干嘛呢？

- 什么时候能来实习呢？ ---(面试官看了一下后台发现我写的暑期)

反问：

- 面试轮数 ---(3-4轮)

- 能否暑期 ---(可以，但是说越早越好)

过了3小时挂了

后面整理了算法第一题的解题，一下是代码和一些思路：

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;


int q;
ll k, p;
// 别人解题地址：https://blog.csdn.net/lt6666678/article/details/136705090
// 利用质因数2和5，当分母因子只有2或者5时，则可以确定不会存在任意一个分子x能使得x/p是无限小数-->x/p是有限小数
// 我们可以发现一个循环数可以拆分成一个循环节和一个基数，比方说676767=67*010101，这样换算成小数也是同理
// 我们可以发现1/9会产生一个小数基数：0.111111....，1/99=0.010101...,1/999=0.001001...，这样其实我们发现10^k-1就是一个无限循环小数的基数，k位循环节长度
// 1/3=0.33333...=3*1/9->x/p=a/10^k-1->x/a=p/(10^k-1),**可以标明只要10^k-1能整除p，那么就存在一个x可以通分成a**
// 但是我们可以发现1/6=0.16666...这种小数并非只是利用上面发现的基数*循环节这么简单，我们可以将这种数称为无限混合循环小数，虽然他不是简单的循环节*基数能解决，但是我们只需将其拆分就会发现其实还是可以基于基数构造的，0.16666...=0.1+(0.6666....)/10->1/6=1/10+(6*1/9)/10
// 6/90+9/90=(6+9)/90=(a+(10^k-1))/((10^k-1)*10)
// x/p=(a+(10^k-1))/((10^k-1)*10)
ll qpow(int a, int b, int mod) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}
bool solve(int k, int p) {
    while (!(p & 1)) p /= 2;
    while (p % 5 == 0) p /= 5;
    if (p == 1) return false;
    return (qpow(10, k, p) - 1) % p == 0;
}


int main() {
    cin >> q;
    while (q--) {
        cin >> k >> p;
        cout << (solve(k, p) ? "YES" : "NO") << endl;
    }


    return 0;
}