兔云论坛

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 26|回复: 0

互联网大厂笔试题目综合

[复制链接]

84

主题

86

帖子

311

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
311
发表于 2019-11-5 00:40:02 | 显示全部楼层 |阅读模式
1.1ABCD四个人,要在夜里过一座桥。
他们通过这座桥分别需要耗时12510分钟,只有一支手电,并且同时最多只能两个人一起过桥。
请问,如何安排,能够在17分钟内这四个人都过桥?
答案A & B -->2 mins
     1 mins <-- A
     C & D -->10 mins
     2 mins <-- B
     A & B --> 2 mins
一共 2 1 10 2 2 17 mins
1.2  1-20的两个数把和告诉A,积告诉BA说不知道是多少,
B也说不知道,这时A说我知道了,B接着说我也知道了,问这两个数是多少?
答案:23
1.3 爸爸,妈妈,妹妹,小强,至少两个人同一生肖的概率是多少?
1-12*11*10*9/12*12*12*12 = 1-55/96 = 41/96
1.4 某人去玩具店买小熊,单价30. 付给玩具店老板100元玩具店老板没零钱,
去水果店换了100元零钱回来找给那人70. 那人走后, 水果店老板找到玩具店老板说刚才的100元是假币,玩具店老板赔偿了水果店老板100元。
问:玩具店老板损失了多少钱?
答案: 70+小熊的进价
2 请定义一个宏,比较两个数ab的大小,不能使用大于、小于、if语句
答案:
#define   max(ab)   ((((long)((a)-(b)))&0x80000000)?b:a)
a > b ,则a-b的二进制最高位为0,与上任何数还是0,所以大数为a
否则,a-b为负数,二进制最高位为1,与上0x80000000(最高位为1其他为0)之后为1,所以此时的大数为b.
3 计算 a^b << 2
答案:运算符优先级:括号,下标,->.(成员)最高:
              单目的比双目的高;
              算术双目的比其他双目的高;
              位运算 高于 关系运算;
              关系运算 高于 按位运算(与,或,异或);
              按位运算 高于 逻辑运算;
              三目的只有一个 条件运算,低于逻辑运算;
              赋值运算仅比 (顺序运算)高。
在此题中,位左移"<<" 优先级高于按位异或"^",所以b先左移两位(相当于乘以4),
再与a异或。
例如: a = 6b = 4 时; 则 a^b<<2 = 22
4 如何输出源文件的标题和目前执行行的行数?
答案: printf("The file name: %d\n"__FILE__);
       printf("The current line No:%d\n"__LINE__);
ANSI C标准预定义宏:
_ _LINE_ _
_ _FILE_ _
_ _DATE_ _
_ _TIME_ _
_ _STDC_ _        当要求程序严格遵循ANSI C标准时该标识符被赋值为1
__cplusplus__   当编写C++程序时该标识符被定义
5 a[3][4]哪个不能表示 a[1][1]: *(&a[0][0]+5) *(*(a+1)+1) *(&a[1]+1) *(&a[0][0]+4)
答案: *(*(a+1)+1)
a是数组的首地址,a+1相当于&a[0][1]*(a+1)=a[0][1],则*(*(a+1)+1)= *(a[0][1]
+ 1) =/= a[1][1]
6 fun((exp1exp2)(exp3exp4exp5))有几个实参?
答案:两个。
形式参数:在声明和定义函数时,写在函数名后的括号中的参数。
实参是调用参数中的变量,行参是被调用函数中的变量。
7. 希尔 冒泡 快速 插入 哪个平均速度最快?
答案:快速排序
快速排序、归并排序和基数排序在不同情况下都是最快最有用的。
8. enum的声明方式
答案:enum 枚举类型名 {
               枚举常量1
               枚举常量2
                                …
               枚举常量n
              };
For example:
enum weekday { sundaymondaytuesdaywednesdaythursdayfridaysaturday};
enum weekday week_day;//week_day 就是一个枚举类型变量
9. 频繁的插入删除操作使用什么结构比较合适,链表还是数组?
答案:链表
10. *p=NULL *p=new char[100] sizeof(p)各为多少?
答案:都为4。因为都是指针类型,所占存储空间必然为4
11. 顺序查找的平均时间
答案:(1+2+3+...+n)/n = (n+1)/2
12. for(i=0sum=0; i<10; ++isum+=i);的运行结果
答案:sum = 55
13. 不能做switch()的参数类型是:
答案:switch的参数不能为浮点型。
14.不使用其他变量,交换两个整型ab的值
答案x = x+y; y = x-y; x = x-y
15. 写出float x 与“零值”比较的if语句。
if(x>=0.000001 && x<=-0.000001)x不为0的比较)
float: 6位精度
double: 16位精度
16.两个数相乘,小数点后位数没有限制,请写一个高精度算法
****************************************************************************
数据库
****************************************************************************
1. 有个表tableQQ,有整型的ID项和字符类型的Nickname项,这两个项都不允许为空
(1)写出建立该表的SQL语句
(2)找出NicknameQQ的用户,按ID降序排列的SQL语句
(3)写出删除ID1234用户记录的SQL语句
(4)写出添加ID5555Nickname'1234'SQL语句
答案:
(1) CREATE TABLE tableQQ
      (
       ID NUMBER(12) NOT NULL
       Nickname Varchar2(30) NOT NULL
       );
(2) select * from tableQQ where Nickname = 'QQ' order by ID desc;
(3) delete from tableQQ where >
(4) insert into tableQQ values(5555'1234');
//删除表
(5)drop table tableQQ;
2. 有关系 s(snosname) c(cnocname) sc(snocnograde)
1 问上课程 "db"的学生
2 成绩最高的学生号
3 每科大于90分的人数
答案:
    (1)select a.snoa.cnob.cnob.cname from sc ac b where a.cno = b.cn
o and b.cname = 'db';
    (2)select snomax(grade)from sc group by sno;
    (3)select cnocount(sno) from sc where grade > 90 group by cno;
****************************************************************************
操作系统 网络
1. 描述实时系统的基本特性
答案:在特定时间内完成特定的任务,实时性与可靠性。
2. Internet采用哪种网络协议?该协议的主要层次结构?
答案:TCP/IP协议。应用层、传输层、网络层、数据链路层和物理层。
3. Internet物理地址和IP地址转换采用什么协议?
答案:地址解析协议ARP address resolution protocol
4. IP地址的编码分为哪俩部分?
答案:网络号和主机号。不过是要和“子网掩码”按位与上之后才能区分哪些是网络位
哪些是主机位。
二分查找
快速排序
双向链表的删除结点
12个小球,外形相同,其中一个小球的质量与其他11个不同
给一个天平,问如何用3次把这个小球找出来
并且求出这个小球是比其他的轻还是重
解答:
哈哈,据说这是微软前几年的一个面试题。很经典滴啊!三次一定能求出来,而且能确定是重还是轻。
数据结构的知识还没怎么学透,不过这个题我到是自己研究过,可以分析下。
12个球分别编号为a1a2a3.......a10a11a12.
第一步:将12球分开3拨,每拨4个,a1~a4第一拨,记为b1a5~a62拨,记为b2,其余第3拨,记为b3
第二步:将b1b2放到天平两盘上,记左盘为c1,右为c2;这时候分两中情况:
1.c1c2平衡,此时可以确定从a1a8都是常球;然后把c2拿空,并从c1上拿下a4,从a9a12四球里随便取三球,假设为a9a11,放到c2上。此时c1上是a1a3c2上是a9a11。从这里又分三种情况:
     A:天平平衡,很简单,说明没有放上去的a12就是异球,而到此步一共称了两次,所以将a12随便跟11个常球再称一次,也就是第三次,马上就可以确定a12是重还是轻;
     B:若c1上升,则这次称说明异球为a9a11三球中的一个,而且是比常球重。取下c1所有的球,并将a8放到c1上,将a9取下,比较a8a11(第三次称),如果平衡则说明从c2上取下的a9是偏重异球,如果不平衡,则偏向哪盘则哪盘里放的就是偏重异球;
     C:若c1下降,说明a9a11里有一个是偏轻异球。次种情况和B类似,所以接下来的步骤照搬B就是;
2.c1c2不平衡,这时候又分两种情况,c1上升和c1下降,但是不管哪种情况都能说明a9a12是常球。这步是解题的关键。也是这个题最妙的地方。
     Ac1上升,此时不能判断异球在哪盘也不能判断是轻还是重。取下c1中的a2a4三球放一边,将c2中的a5a6放到c1上,然后将常球a9放到c2上。至此,c1上是a1a5a6c2上是a7a8a9。此时又分三中情况:
    1)如果平衡,说明天平上所有的球都是常球,异球在从c1上取下a2a4中。而且可以断定异球轻重。因为a5a8都是常球,而第2次称的时候c1是上升的,所以a2a4里必然有一个轻球。那么第三次称就用来从a2a4中找到轻球。这很简单,随便拿两球放到c1c2,平衡则剩余的为要找球,不平衡则哪边低则哪个为要找球;
     2c1仍然保持上升,则说明要么a1是要找的轻球,要么a7a8两球中有一个是重球(这步懂吧?好好想想,很简单的。因为a9是常球,而取下的a2a4肯定也是常球,还可以推出换盘放置的a5a6也是常球。所以要么a1轻,要么a7a8重)。至此,还剩一次称的机会。只需把a7a8放上两盘,平衡则说明a1是要找的偏轻异球,如果不平衡,则哪边高说明哪个是偏重异球;
    3)如果换球称第2次后天平平衡打破,并且c1降低了,这说明异球肯定在换过来的a5a6两求中,并且异球偏重,否则天平要么平衡要么保持c1上升。确定要找球是偏重之后,将a5a6放到两盘上称第3次根据哪边高可以判定a5a6哪个是重球;
     B:第1次称后c1是下降的,此时可以将c1看成c2,其实以后的步骤都同A,所以就不必要再重复叙述了。至此,不管情况如何,用且只用三次就能称出12个外观手感一模一样的小球中有质量不同于其他11球的偏常的球。而且在称的过程中可以判定其是偏轻还是偏重。
给一个奇数阶N幻方,填入数字123...N*N,使得横竖斜方向上的和都相同
答案:
#include<iostream>
#include<iomanip>
#include<cmath>
usingnamespace std;
int main()
{
int n;
cin>>n;
int i;
int **Matr=newint*[n];//动态分配二维数组
for(i=0;i<n;++i)
      Matr[ i ]=newint[n];//动态分配二维数组
//j=n/2代表首行中间数作为起点,即1所在位置
int j=n/2num=1;//初始值
i=0;
while(num!=n*n+1)
{
//往右上角延升,若超出则用%转移到左下角
      Matr[(i%n+n)%n][(j%n+n)%n]=num;
    //斜行的长度和n是相等的,超出则转至下一斜行
    if(num%n==0)
          i++;
   else
&nb
sp;  
        {
i--;
          j++;
      }
      num++;
}
for(i=0;i<n;i++)
{
      for(j=0;j<n;++j)
         cout<<setw((int)log10(n*n)+4)<<Matr[ i][ j ];//格式控制
      cout<<endl<<endl;//格式控制
}
for(i=0;i<n;++i)
      delete [ ]Matr[ i ];
return1;
}
腾讯的一道面试题与百度相似,可惜昨天百度死在这方面了)////
在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可。
答案:
1,把整数分成256M段,每段可以用64位整数保存该段数据个数,256M*8 = 2G内存,先清0
2,读10G整数,把整数映射到256M段中,增加相应段的记数
3,扫描256M段的记数,找到中位数的段和中位数的段前面所有段的记数,可以把其他段的内存释放
4,因中位数段的可能整数取值已经比较小(如果是32bit整数,当然如果是64bit整数的话,可以再次分段),对每个整数做一个记数,再读一次10G整数,只读取中位数段对应的整数,并设置记数。
5,对新的记数扫描一次,即可找到中位数。
如果是32bit整数,读10G整数2次,扫描256M记数一次,后一次记数因数量很小,可以忽略不记
(设是32bit整数,按无符号整数处理整数分成256M段? 整数范围是0 - 2^32 - 1 一共有4G种取值,4G/256M = 16,每16个数算一段 0-151段,16-31是一段,... 整数映射到256M段中? 如果整数是0-15,则增加第一段记数,如果整数是16-31,则增加第二段记数,... 其实可以不用分256M段,可以分的段数少一写,这样在扫描记数段时会快一些,还能节省一些内存)
腾讯题二:
一个文件中有40亿个整数,每个整数为四个字节,内存为1GB,写出一个算法:求出这个文件里的整数里不包含的一个整数
:
方法一: 4个字节表示的整数,总共只有2^32约等于4G个可能。
为了简单起见,可以假设都是无符号整数。
分配500MB内存,每一bit代表一个整数,刚好可以表示完4个字节的整数,初始值为0。基本思想每读入一个数,就把它对应的bit位置为1,处理完40G个数后,对500M的内存遍历,找出一个bit0的位,输出对应的整数就是未出现的。
算法流程:
1)分配500MB内存buf,初始化为0
2)unsigned int x=0x1;
   for each int j in file
   buf=buf ¦x < <j;
   end
(3) for(unsigned int i=0; i  <= 0xffffffff; i++)
       if (!(buf & x < <i))
       {
           output(i);
           break;
       }
以上只是针对无符号的,有符号的整数可以依此类推。
方法二:
文件可以分段读啊,这个是O2n)算法,应该是很快的了,而且空间也允许的。
不过还可以构造更快的方法的,更快的方法主要是针对定位输出的整数优化算法。
思路大概是这样的,把值空间等分成若干个值段,比如值为无符号数,则
00000000H-00000FFFH
00001000H-00001FFFH
......
0000F000H-0000FFFFH
.....
FFFFF000H-FFFFFFFFH
这样可以订立一个规则,在一个值段范围内的数第一次出现时,对应值段指示值Xn=Xn+1,如果该值段的所有整数都出现过,则Xn=1000H,这样后面输出定位时就可以直接跳过这个值段了,因为题目仅仅要求输出一个,这样可以大大减少后面对标志数值的遍历步骤。
理论上值段的划分有一定的算法可以快速的实现,比如利用位运算直接定位值段对应值进行计算。
腾讯面试题: 110w10w个数,去除2个并打乱次序,如何找出那两个数。(不准用位图!!)
位图解决:
  位图的方法如下
假设待处理数组为A[10w-2]
定义一个数组B[10w],这里假设B中每个元素占用1比特,并初始化为全0
for(i=0;i <10w-2;i++)
{
B[ A ]=1
}
那么B中不为零的元素即为缺少的数据
这种方法的效率非常高,是计算机中最常用的算法之一
其它方法:
    求和以及平方和可以得到结果,不过可能求平方和运算量比较大(用64int不会溢出)
腾讯面试题:
腾讯服务器每秒有2wQQ号同时上线,找出5min内重新登入的qq号并打印出来。
解答: 第二题如果空间足够大,可以定义一个大的数组
a[qq,初始为零,然后这个qq号登陆了就a[qq]++
最后统计大于等于2QQ
这个用空间来代替时间
第二个题目,有不成熟的想法。
2w x 300s
所以用 6000000 个桶。删除超时的算法后面说,所以平均桶的大小是 1
假设 qq 号码一共有 10^10 个,所以每个桶装的 q 号码是 10^10 / (6 * 10^6) 个,这个是插入时候的最坏效率(插入同一个桶的时候是顺序查找插入位置的)。
qq的节点结构和上面大家讨论的基本一样,增加一个指针指向输出列表,后面说。
struct QQstruct {
  num_type   qqnum;
  timestamp  last_logon_time;
  QQstruct   *pre;
  QQstruct   *next;
  OutPutList *out;    // 用于 free 节点的时候,顺便更新一下输出列表。
}
另外增加两个指针列表。
第一个大小 300 的循环链表,自带一个指向 QQStruct 的域,循环存 300 秒内的qq指针。时间一过
free 掉, 所以保证所有桶占用的空间在 2w X 300 以内。
第二个是 输出列表, 就是存放题目需要输出的节点。
如果登陆的用户,5分钟内完全没有重复的话,每秒 free 2w 个节点。
不过在 free 的时候,要判断一下时间是不是真的超时,因为把节点入桶的时候,遇到重复的,会更
新一下最后登陆的时间。当然啦,这个时候,要把这个 qq 号码放到需要输出的列表里面

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|兔云论坛 ( 粤ICP备18131279号 )

GMT+8, 2019-11-18 03:31 , Processed in 0.051104 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表