一面:
自我介绍,做题,不用跑,解释就行,都不难。
//笔试要求
//1. 独立完成。可以搜任何资料,但是不能直接搜题解。
//2. 允许使用本地IDE,限时内确保代码都贴上来即可。
/*第1题
给定一个整数 n ,返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 :
输入:n = 3
输出:0
解释:3! = 6 ,不含尾随 0
*/
// 5, 10, 15 .. 100 = 5(1, 2, 3, 4, 5 .. 20)
// 对于每个 5k,会贡献 1 个 0,
#include <cstdio>
int main() {
int n; scanf("%d", &n);
int ans = 0;
while(n) {
ans += n /= 5;
}
printf("%d\n", ans);
}
/* 第2题
给你两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除,并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果:
https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/28/fig1.png
请你返回结果链表的头指针。
示例 1::list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出:[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释:下图中蓝色的边和节点为答案链表。
https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/28/merge_linked_list_ex2.png
数据范围:
3 <= list1.length <= 10^4
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10^4
*/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
#include <cstdio>
struct Node {
int val;
struct Node *next;
}*head_a, *head_b;
// we assume a & b are malloced
void merge_between(int a, int b) {
struct Node *p = head_a, *q = head_a;
// assume a, b > 0;
a --;
while(a -- ) p = p->next;
while(b -- ) q = q->next;
q = q->next;
struct Node *cur = p->next;
// delete from a to b;
while(cur != q) {
struct Node *tmp = cur;
cur = cur->next;
free(tmp);
}
p->next = head_b;
p = head_b;
while(p->next != NULL) p = p->next;
p->next = q;
}
/* 第3题
实现支持下列接口的「快照数组」- SnapshotArray:
- SnapshotArray(int length) // 初始化一个与指定长度相等的 类数组 的数据结构。初始时,每个元素都等于 0。
- void set(index, val) // 会将指定索引 index 处的元素设置为 val。
- int snap() // 获取该数组的快照,并返回快照的编号 snap_id(快照号是调用 snap() 的总次数减去 1)。
- int get(index, snap_id) // 根据指定的 snap_id 选择快照,并返回该快照指定索引 index 的值。
内存用量不超过32MB,请注意算法复杂度。
// COW
实现一个链表数组,长度为 N,节点包括nxt, val, snp, 对于每次 Set(k, v), 在第 K 位的 节点的最后一个链表节点上,若有 snp 标记,则挂一个新节点,否则直接修改,
当 snp 时,给数组中所有的节点的标记打好
示例:
输入:
["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
输出:
[null,null,0,null,5]
解释:
SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5); // 令 array[0] = 5
snapshotArr.snap(); // 获取快照,返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // 获取 snap_id = 0 的快照中 array[0] 的值,返回 5
提示:
1 <= length <= 50000
题目最多进行50000 次set,snap,和 get的调用 。
0 <= index < length
0 <= snap_id < 我们调用 snap() 的总次数
0 <= val <= 10^9
*/
//请补充下面类的实现:
#include <cstdio>
#define QUERY_NUMS 1
struct Node {
int val;
int snp;
struct Node* next;
}pool[101001];
struct Array {
struct Node* head, *tail;
}a[500100];
#include <stack>
using std :: stack;
stack<Node*> changed;
char op[50010][15];
int opval[50010][2], pool_cur, snp;
int main() {
// assume input :
int T = QUERY_NUMS;
for(int i = 0; i < QUERY_NUMS; i ++ ) {
if(op[i][0] == 'S') {
// init
for(int j = 0; j < opval[i][0]; j ++ ) {
a[j].head = a[j].tail = pool[cnt ++];
a[j].head->val = 0;
a[j].head->snp = -1;
changed.push(a[j]);
}
puts("null");
} else if(op[i][0] == 's' && op[i][1] == 'e') {
if(a[opval[i][0]].tail.snp != -1) {
struct Node* tmp = pool[cnt ++ ];
a[opval[i][0]].tail->next = tmp;
tmp->val = opval[i][1];
tmp->snp = -1;
changed.push(tmp);
}
puts("null")
// set
} else if(op[i][1] == 'n') {
// snap
while(!change.empty()) {
Node * tmp = change.top();
change.pop();
tmp->snp = snp;
}
printf("%d\n", snp);
snp ++;
} else {
// get
struct Node * head = a[opval[i][0]].head;
while(head->next && head->next->snp < opval[i][1]) {
head = head->next;
}
printf("%d\n", head->val);
}
}
}
给了一个思考题,m 个棕眼睛,n 个蓝眼睛,每天公布是否有蓝眼睛,如果确定自己是蓝眼睛,就要离开,问多少天会全部离开。
一开始没想出来,面试官提示假设说 n=1,发现可以递推,答案是 n+1。
聊实习:
你说高光链路建设,怎么个建设法
录制和裁剪是同步异步的?怎么实现的?
聊八股:
函数调用影响哪些寄存器?
Linux、Android 的系统的内存排布
浏览器输入链接按下回车都发生了啥
问那 HTTPS 多了啥
你没提到 TCP,不用 TCP,还能 HTTP 么?
评论 (0)