jingchi.ai 2017.11.25-26 Onsite面试

时间:2023-03-08 21:49:49

时间:2017.11.25 - 11.26

地点:安徽安庆

来回路费报销,住宿报销。

day1: 大哥哥问了我一个实际中他们遇到的问题。有n个点,将点进行分块输出,输出各个块的均值点。具体就是100*100的矩形区域内,以0.01*0.01为一小格进行分块,输出块内的均值。n的大小大概是1e9 ~ 1e11级别的(具体忘了),很多块会是空的,没有任何点。 大概就是权衡时间与空间,但大哥哥提示我说有什么数据结构嘛,大概是提示我四叉树那种?我说来说去都是排序。。。总的排序时间复杂度太高,就分出一维枚举再排序。。汗。。大哥哥还给了我一个数据,两条对角线上的格子里有点,其他格子都是空的。。回去稍微想了一想,可能就是递归划分这种吧。。。菜爆了。。

day2: 另一个大哥哥问了C++相关。如何写一个函数判断传入参数的类型,把每一个类型映射到一个数字。不会。又换成实现printf函数,可以输出整型,浮点型,字符串型等。函数重载?之后又说函数传入参数不定。好吧,都不会。(重载,模板特化,或者RTTI可以实现根据不同类型执行不同代码)  (C++11可以实现变长参数模板) emmm,可能我需要恶补C++了。。。。(已update code.)看C++面不出什么东西,问我,相比其他语言,C++有什么特点?想了几秒钟,答:模板。面试官一脸惊讶:”那不应该啊,刚才考你的就是模板。“好吧我知道我菜爆了。之后就问算法题了,最长上升子序列(中间代码写错了一次尴尬),又问了一下k近邻的做法。得知我acm抄过kd-tree的代码后就没让我写了。 然后另一个大哥哥过来了解了一下我的情况,面了一些leetcode easy题以及推了一道概率题。n个人坐n个位置,第1个人等概率随机坐,余下的,第i个人在第i个位置空的情况下,直接坐第i个位置,否则等概率在剩下的空位置里找位置坐,问第n个人坐在第n个位置的概率。想了五六分钟想出了O(n)的递推公式。面试到此结束。

体验:第一次Onsite面试,有点小紧张与兴奋。本来以外能顺便旅游旅游不过没时间了,附件有一座山叫天柱山。嗯。。。。以后恐怕也不会来天柱山玩了,sad....旅途奔波有点累,没有旅游,纯面试屯了一波onsite面经。因为没有买好回来的票在安庆从中午逗留到了晚上T_T。回来享受了一下商务座(反正不是我出钱2333)。

=================这里是分割线=================

https://www.cnblogs.com/qicosmos/p/4325949.html

http://blog.****.net/qq_35280514/article/details/51637920

后续:为什么函数参数是自右向左压栈的?考虑printf()函数,printf()是可变参数函数,第一个参数是参数格式字符串,自右向左压栈能保证栈顶是参数格式字符串,可以通过栈顶参数格式字符串得知后续参数的个数与类型。理论上来说,自左向右压栈,可变参数标记格式字符串的参数放最后也可行,不过最早设计C语音的人采用了这种方式,后续就延续下来了。

jingchi.ai 2017.11.25-26 Onsite面试

如上图,ebp是帧指针寄存器,一般用来存取堆栈,自右向左压栈可方便得知Arg1的地址,(Arg1比较重要,参考printf,通过Arg1可方便得知参数的个数和各参数的类型)。

C版本

 #include <bits/stdc++.h>
#include <stdarg.h>
void print(char *fmt, ...) {
va_list ap;
char *p, *sval;
int ival;
double dval;
char cval; va_start(ap, fmt);
for(p = fmt; *p; p++) {
if(*p != '%') { putchar(*p); continue ; }
switch(*++p) {
case 'd':
ival = va_arg(ap, int);
printf("%d", ival);
break;
case 'f':
dval = va_arg(ap, double);
printf("%f", dval);
break;
case 's':
for (sval = va_arg(ap, char *); *sval; sval++)
putchar(*sval);
break;
case 'c':
cval = va_arg(ap, int); //'char' is promoted to 'int' when passed through '...', you should pass 'int' not 'char' to 'va_arg'
putchar(cval);
break;
default:
putchar(*p);
break;
}
}
va_end(ap);
} int main(){
print("%f%s%d%c%d", 3.14, "hello world!\n", , 'h', );
return ;
}

=================update:跟着空明流转学C++template学到了本次C++面试题的解法=================

面试时的原话:工程代码中可能定义了很多类,你有什么办法写一个函数能输出它们的类型?。。。。你可以一一映射到数字中。。。。你能不能写一个类似printf的函数,可以接受任意个数的参数,输出映射后的值?

以上类似于:

把bool, int, char, double映射到不同的数字,print(var)会根据var的不同类型,输出其映射过去的数字,且print输入参数个数任意。

 #include <bits/stdc++.h>

 template <typename T> class TypeToID
{
public:
static int const ID = -;
}; template<> class TypeToID<int>
{
public:
static int const ID = ;
};
template<> class TypeToID<char>
{
public:
static int const ID = ;
}; template<typename T> class TypeToID<T*>
{
public:
static int const ID = ;
}; template<> class TypeToID<int*>
{
public:
static int const ID = ;
}; /*****print ID*******/
template<typename T>
void print(T ID) {
std::cout << TypeToID<T>::ID << std::endl;
} template<typename T, typename... Args>
void print(T ID, Args... rest) {
print(ID);
print(rest...);
}
/********************/ int main(){
bool a;
int b;
char c;
void *p;
int *q;
print(a, b, c, p, q);
return ;

什么时候<>, 什么时候<typename T>?

显然当T未声明,需要声明是一个typename的时候...

点评:如果单单输出ID其实函数重载就OK了,用template特化还是要一个一个写一遍,但大哥哥还要求能传入任意个数的参数,这就需要template大法了!查漏补缺了一个自己的知识盲点。