Garena游戏公司秋招笔经（好题！附代码）
笔试时间：2022.9.2 19:00-21:00
岗位：游戏开发-服务器开发工程师
笔试平台：牛客
常规八股文19题（20分钟）
算法题（100分钟）
第一题（超难，好题！）
题目
求杨辉三角第n行的乘积，对10^9+7取模，n <= 10^6；
例如 3 = 1 * 2 * 1 = 2， 4 = 1 * 3 * 3 * 1 = 9；
想法与思路
如果要用动态规划计算第n行，需要O(n^2)的时间，太慢了。应该是找规律。
找来找出，好像某一行没有明显数值规律。
灵光一闪想到，杨辉三角和二项式定理有关，于是立马尝试了组合数学，果然可以！
令n=n-1，第n行（按照题目定义是n-1，用n表示比较方便）的数字分别为 ，分别相乘。
问题来了，正常乘肯定爆数字范围，取模的话可能会导致某步不整除，怎么办？
提取分子分母
分子为
分母为
此时只要预处理，就能在O(n)时间内计算出分子和分母。
令P=10^9+7，当前问题变为求
运用费马小定理（考场记得个大概，用了一堆例子硬生生试出来的），
因此，当前问题变成
剩下最后一步啦！
数值范围太大了，不能for循环计算
使用快速幂。
代码如下，欢迎参考！
真是我笔试中遇到最难的题了。
代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int Mod = 1000000007;
int n;
unsigned long long F[1000005];
unsigned long long Pow(unsigned long long x, int y) {
unsigned long long res = 1, a = x;
for (; y > 0; y >>= 1){
if (y&1) res = res * a % Mod;
a = a * a % Mod;
}
return res;
}
int main() {
cin >> n;
unsigned long long res = 1;
n--;
F[0] = 1;
for (int i = 1; i <= n; ++i) {
F[i] = F[i - 1] * i % Mod;
}
unsigned long long x = 1, y = 1;
for (int i = 0; i <= n; ++i) {
x = x * F[n] % Mod;
y = y * F[i] % Mod * F[n - i] % Mod;
}
res = x * Pow(y, Mod - 2) % Mod;
cout << res;
return 0;
}第二题
题目
给定一个表达式，包含数字，和+,-,^三个符号。假定^的优先级比+,-高。
保证符号个数+1 = 数字个数，保证表达式格式正确。求表达式的解。
例如：输入3+5^2-9，输出1。
想法与思路
从右往左，遇到数字累计，遇到符号操作。如果是加减，考虑是否需要先异或。如果是异或，打个标记，记录累计的异或和（异或满***换律和结合律）。
注意，开头的数字得特殊计算，比如4^4+5 = 5（大坑，不注意这个只有50分）
代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
string s;
int n;
long long res;
int main() {
cin >> s;
n = s.length();
long long last = 0, now = 0, p = 1;
bool flag = 0;
for (int i = n - 1; i >= 0; --i) {
if (s[i] == '+' || s[i] == '-' || s[i] == '^') {
if (s[i] == '+') {
if (flag == 0)
res += now;
else {
last ^= now;
res += last;
flag = 0; last = 0;
}
}
else if (s[i] == '-') {
if (flag == 0)
res -= now;
else {
last ^= now;
res -= last;
flag = 0; last = 0;
}
}
else if (s[i] == '^') {
last ^= now;
flag = 1;
}
now = 0; p = 1;
}
else {
now = now + (s[i] - '0') * p;
p = p * 10;
}
}
if (flag == 1)
cout << res + (last^now);
else
cout << res + now;
return 0;
}第三题
题目
递归，求前n项和
想法与思路
这么水的题为什么放第三题。。
代码
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
* C语言声明定义全局变量请加上static，防止重复定义
*/
int recursion(int n ) {
// write code here
if (n == 0)
return 0;
return recursion(n - 1) + n;
}第四题
题目
机器学习分大端存储和小端存储，给定一个小端数字，求大端。
样例：输入1，输出16777216。
想法与思路
太坑了！考场我根本不知道什么是大端小端，完全忘记了！
从样例开始猜，计算器一通乱试，发现16777216 = 2^24
以为是24位进制反转，试了一下，得了40分。
想来想去，灵光乍现，如果按照8位分割（Byte概念），分成4块，会不会所谓的“大端”和“小端”是块替换。一想觉得非常合理，样例给定2^0，输出2^24，假设0-31位，刚好符合要求。
又写了一通，拿了80分，最后一个点怎么都调不过了，估计概念漏了啥符号位吧。
输出了一通怨念，最后考完想明白了
正解如下：
输入是正数，就按照现在代码中的方法，分成4块算。
输入是负数，使用去掉符号位，使用补码（原码，反码，补码那块转换）计算出对应每一位的0/1状态，类似的计算。
代码（只拿了80分，没有考虑输入是负数）
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 * C语言声明定义全局变量请加上static，防止重复定义 */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 * C语言声明定义全局变量请加上static，防止重复定义 */ int convert(int n) { int temp_a[32]; memset(temp_a, 0, sizeof(temp_a)); for (int i = 0; n > 0; n>>=1, ++i) temp_a[i] = n&1; int p = 1; int res = 0; for (int i = 24; i < 32; ++i) { res = res + p * temp_a[i]; p *= 2; } for (int i = 16; i < 24; ++i) { res = res + p * temp_a[i]; p *= 2; } for (int i = 8; i < 16; ++i) { res = res + p * temp_a[i]; p *= 2; } for (int i = 0; i < 8; ++i) { res = res + p * temp_a[i]; p *= 2; } return res; // write code here }
算法题总得分：100+100+100+80 = 380。做过最难的一次秋招笔试了。
#秋招##笔经##2023一起秋招吧##Garena##23届秋招笔面经#