智臾科技面经 一面（凉）

自我介绍

项目介绍

面试官：你这个15445项目运用到了RAII思想，可以介绍一下RAII思想嘛.

我：RAII思想就是利用生命周期来实现对资源控制.

比如mutex_lock，智能指针。然后我项目中运用RALL思想，实现了page_guard类。

面试官：RAII这么做的目的是什么？

我：拿page_guard来说，在构造时上锁，drop或生命周期结束时释放锁,这样极大的简化编程难度。如果没有实现这个，编程难度会变大，忘记释放锁或忘记上锁，容易造成死锁，或者是占用更多性能。

又或者是智能指针， 在智能指针没有出来之前，指针会经常遇到一些困境，比如 忘记delete造成内存泄漏，已经delete后指针忘记置空，变成野指针等问题。

总而言之，RAII方便了我们的资源管理.

面试官：15445中的做了事务隔离，可以简单介绍一下嘛.

我：p4太难，放弃了。

面试官：那你能介绍一下lab3中优化部分做了哪些嘛？

我：首先是实现了topn优化和hash_join的优化. 原本是使用 nest loop join方法，也就是一个两层循环，是最坏的情况，我们通过hash_join进行优化。

面试官：了解B+树嘛？

我：简历上写错了，因为2023 fall做的是可扩展哈希，所以没太了解B+树。

面试官：C++的内存空间是怎样的结构

我：栈区，堆区，全局/静态区，常量区。栈区相对较小,全局/静态区和堆区较大。

面试官：哪些情况用栈，哪些情况用堆，哪些情况用全局/静态区？

我：我们从main()函数执行前后来讲，在main函数执行之前，会先把 static变量，全局变量放进全局/静态区。

然后我们平时写函数的时候，在里面定义的变量会放到栈里又或者是递归的时候会压栈。至于堆，是由程序员主动申请的空间,什么时候用堆呢？首先第一点，因为栈区比较小，所以当我们开一个大数组，或者是动态数据结构（如set，map,动态开点线段树等）时，是需要放到堆里的。第二点是，当需要对象需要被多个函数共享时，这时候我们把该对象放到堆里面，就可以实现共享.这样就减少了内存开销.

面试官：堆和栈有什么差别？或者说栈相对与堆有什么优势？什么情况尽可能的放到栈上？什么情况尽可能的放到堆上？

我：首先是堆的，我们刚才有讲到过，就是动态数据结构（如set，map,动态开点线段树等）或共享对象时，是需要放到堆里的。

至于栈的话，比较小的变量就可以直接放。

(这题应该是G了。哎)

面试官：堆和栈在访问效率上有什么差别？

我：堆会快一点。（这里答错了，因为我不知道，所以我随便答了一个,正确答案是栈）

(面试官拿起来笔，在本本上画了两下。)

搜了一下：

优势和适用情况：

1. 栈的优势：快速分配和释放：栈上的内存分配和释放速度快，适用于需要频繁创建和销毁对象的情况。空间效率高：栈的空间有限，但是分配和释放的开销小，适用于存储较小的数据对象。
2. 堆的优势：动态分配：堆允许在程序运行时动态分配内存，适用于需要灵活管理对象生命周期的情况。大内存空间：堆的空间相对较大，适用于需要存储大型数据结构或对象的情况。共享数据：堆上的数据可以被多个模块或线程共享，适用于需要在不同的上下文中访问数据的情况。

一般情况下，以下准则可以作为选择栈或堆的一些参考：

• 当数据对象的大小较小且生命周期可以确定时，优先考虑将其放到栈上。
• 当数据对象的大小较大、生命周期不确定或需要动态分配时，考虑将其放到堆上。
• 需要注意的是，在堆上分配内存后，需要及时释放以避免内存泄漏。

面试官：还剩半小时我们来做一下算法题.

算法题1：一个骰子有n面，投到每一面的概率相同，问每一面都至少出现一次，需要投几次。

我：考了最不会的期望dp且一个月没写过题。。 想了20分钟，然后推了个期望方程。

设dp[i]表示n面中有i面出现了至少一次需要投的次数。

dp[i] = (n-i)/n *(dp[i+1] + 1) + i/n*(dp[i] +1 );

dp[i+1] = (n/(n-i))+dp[i];

算法题2：把至少出现一次改成至少两次。

我：没写过来。

面试官：其实算法题2跟算法题1是很像的，设dp[i][j]表示出现一次的有i面，至少出现了两面的有j面即可转移。

反问环节。

自我反思：

1.算法题考虑期望dp，一个月没写题加上期望dp不熟，菜是原罪。

2.项目最好完善一下，事务的隔离级别和B+树，就算没做也要了解一下。