2014网易实习生招聘面试题

http://blog.csdn.net/silangquan/article/details/18969875

不拼搏,枉少年

网易游戏2014年实习生招聘。

过程:无电面,笔试半小时,两道算法题,面试一小时。

结果:7进2,扑街。

这是我最接近网易游戏的一次。

下面大部分的内容是没有答上来的。

1.算法题:Write a method to replace all spaces in a string with ‘%20’.

2.算法题:Implement a function to check if a tree is balaned. For the purpose of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

3.Linux权限有哪几种?什么是文件夹的执行权限?

4.什么叫做守护进程?

5.git中 branch命令的用法。

6.如何修改git中一个commit的注释?

7.C中static函数有什么作用?

8.如何扩展红黑树,能够得到树中某个节点的秩。

9.X是整数,X>=5,X与X+2都是素数,请证明:X+1一定是6的倍数.

笔试题

1.字符串替换

Write a method to replace all spaces in a string with ‘%20’.

Cracking the Coding Interview 原题

[cpp] view plaincopy

  1. /* 
  2. 思路: 
  3. 0.使用每个空格表示一个字符。 
  4. 1.遍历字符串,求出空格数目。 
  5. 2.计算当前字符串总长度,包括'\0'。 
  6. 3.计算替换后需要的长度(增加空间:空格数*2)。 
  7. 4.创建两个指针分别指向当前字符串末尾和替换后的字符串的末尾。 
  8. 5.由后向前复制字符串内容,直到第一个指针遇到空格为止。 
  9. 6.把空格替换成'%20',并第一个指针前移1格,第二个指针前移3格。 
  10. 7.重复步骤5和6。 
  11. */
  12. #include <iostream>  
  13. using namespace std;    
  14. //length表示字符数组line[]的总容量,而非表示数组实际长度,可以自己给定.  
  15. int replaceBlank(char line[],int length)    
  16. {    
  17. //line = new char[length];  
  18. int flag = 0;    
  19. //字符数组line为空字符数组.  
  20. if(line == NULL || length <= 0)    
  21.     {    
  22.         flag = -1;    
  23. return flag;    
  24.     }    
  25. //odlLength表示替换前字符串实际长度.  
  26. int odlLength = 0;    
  27. int blankNumber = 0;    
  28. int i = 0;    
  29. //计算字符串总长度和其存在空格数.  
  30. while (line[i] != '\0')    
  31.     {    
  32.         ++odlLength;    
  33. if(line[i] == ' ')    
  34.             ++blankNumber;    
  35.         ++i;    
  36.     }    
  37. //末尾'\0'也占用一个空格.  
  38.     odlLength += 1;    
  39. //若不存在空格,直接结束程序.  
  40. if(blankNumber == 0)    
  41.     {    
  42.         flag = 1;    
  43. return flag;    
  44.     }    
  45. //newLength表示替换后的字符串实际长度.  
  46. int newLength = odlLength + blankNumber * 2;    
  47. //替换后的字符串长度大于原字符数组总容量.  
  48. if (newLength > length)    
  49.     {    
  50.         flag = 2;    
  51. return flag;    
  52.     }    
  53. //定义数组下标.  
  54. int p = odlLength - 1;    
  55. int q = newLength - 1;//cout << "p: " << p << ", q: " << q;  
  56. while (p >= 0 && q > p)    
  57.     {    
  58. //不管是字符还是'\0'均替换.  
  59. if(line[p] != ' ')    
  60.         {    
  61.             line[q] = line[p];////////////////////////////////////////////////////////////  
  62.             --q;    
  63.             --p;    
  64.         }    
  65. //若为空格  
  66. else
  67.         {    
  68. //第二个指针前移3格  
  69.             line[q--] = '0';    
  70.             line[q--] = '2';    
  71.             line[q--] = '%';    
  72. //第一个指针前移1格  
  73.             --p;    
  74.         }    
  75.     }    
  76. return flag;    
  77. }    

2.判断一棵树是否是平衡树。

Implement a function to check if a tree is balaned. For the purpose of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

Cracking the Coding Interview 原题

注:书上的解答直接以 二叉树为准,但题目中没有说是二叉树,但平衡就默认指二叉树。

结构体定义:

[cpp] view plaincopy

  1. struct node   
  2. {  
  3. int data;  
  4. struct node * lchild;  
  5. struct node * rchild;  
  6. };  

下面正确地示范以下错误的解法.

思路:

分别求最大深度和最小深度,得到的结果相减,然后判断。

[cpp] view plaincopy

  1. int maxDepth(struct node *root)  
  2. {  
  3. if (root == NULL)   
  4.   {  
  5. return 0;  
  6.   }  
  7. else
  8.   {  
  9. return 1 + max(maxDepth(root->lchild), maxDepth(root->rchild));  
  10.   }  
  11. }  
  12. int  minDepth(struct node *root)  
  13. {  
  14. if (root == NULL)   
  15.   {  
  16. return 0;  
  17.   }  
  18. else
  19.   {  
  20. return 1 + min(minDepth(root->lchild), minDepth(root->rchild));  
  21.   }  
  22. }  
  23. // 分别求出树的最大深度和最小深度,然后判断它们的差是不是大于1
  24. // 该算法遍历了二叉树两遍
  25. bool isBalanced1(struct node *root)  
  26. {  
  27. return (maxDepth(root) - minDepth(root) >= 1);  
  28. }  

尼玛!哪来的最小深度。除非上面的节点全是满的。只能求二叉树的最大深度好么。

未优化的正确解法

[cpp] view plaincopy

  1. int maxDepth(TreeNode *root){  
  2. if(NULL == root){  
  3. return 0;  
  4.     }  
  5. int maxL = maxDepth(root->left);  
  6. int maxR = maxDepth(root->right);  
  7. return 1 + (maxL > maxR ? maxL : maxR);  
  8. }  
  9. bool isBalanced(TreeNode *root) {  
  10. // Start typing your C/C++ solution below
  11. // DO NOT write int main() function
  12. if(NULL == root){  
  13. return true;  
  14.     }  
  15. int diff = maxDepth(root->left) - maxDepth(root->right);  
  16. if((diff>1) || (diff<-1)){  
  17. return false;  
  18.     }  
  19. return isBalanced(root->left) && isBalanced(root->right);  
  20.  }  

优化后的解法,加了一点DP

使用后序遍历二叉树的节点,遍历时记录节点深度,同时也可以更快的判断出二叉树不平衡的情况。

[cpp] view plaincopy

  1. bool isBalanced(TreeNode *root, int *depth){  
  2. if(NULL == root){  
  3.          *depth = 0;  
  4. return true;  
  5.      }  
  6. int left, right;  
  7. if(isBalanced(root->left, &left) && isBalanced(root->right, &right)){  
  8. int diff = left - right;  
  9. if((diff>1) || (diff<-1)){  
  10. return false;  
  11.        }  
  12.         *depth = 1 + (left > right ? left : right);  
  13. return true;  
  14.     }  
  15. }   
  16. bool isBalanced(TreeNode *root) {  
  17. // Start typing your C/C++ solution below
  18. // DO NOT write int main() function
  19. int depth = 0;  
  20. return isBalanced(root, &depth);  
  21. }  

面试问题

Linux相关

3.Linux权限有哪几种?什么是文件夹的执行权限?

用ls-l命令来查看文件权限

第一个字符表示文件类型,第2~10个字符当中的每3个为一组,左边三个字符表示所有者权限,中间3个字符表示与所有者同一组的用户的权限,右边3个字符是其他用户的权限。这三个一组共9个字符,代表的意义如下: r(Read,读取):对文件而言,具有读取文件内容的权限;对目录来说,具有浏览目 录的权限。 w(Write,写入):对文件而言,具有新增、修改文件内容的权限;对目录来说,具有删除、移动目录内文件的权限。 x(eXecute,执行):对文件而言,具有执行文件的权限;对目录了来说该用户具有进入目录的权限。

4.什么叫做守护进程?

Linux Daemon(守护进程)是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务,不是对整个系统就是对某个用户程序提供服务。Linux系统的大多数服务器就是通过守护进程实现的。常见的守护进程包括系统日志进程syslogd、 web服务器httpd、邮件服务器sendmail和数据库服务器mysqld等。 守护进程一般在系统启动时开始运行,除非强行终止,否则直到系统关机都保持运行。守护进程经常以超级用户(root)权限运行,因为它们要使用特殊的端口(1-1024)或访问某些特殊的资源。 一个守护进程的父进程是init进程,因为它真正的父进程在fork出子进程后就先于子进程exit退出了,所以它是一个由init继承的孤儿进程。守护进程是非交互式程序,没有控制终端,所以任何输出,无论是向标准输出设备stdout还是标准出错设备stderr的输出都需要特殊处理。 守护进程的名称通常以d结尾,比如sshd、xinetd、crond等。

5.git中 branch命令的用法。

如果不加任何参数,它会给出当前所有分支的清单,加*号的表示当前分支。

git branch -v 查看各个分支最后一个提交对象的信息;

git branch --merged 查看哪些分支已被并入当前分支;

git branch --no-merged 查看尚未合并的工作;

git branch -d 强制删除该分支上的改动;

6.如何修改git中一个commit的注释?

对于修改最后一次修改,

git commit --amend 然后在出来的编辑界面,直接编辑 注释的信息。

对于不是最后一次修改的情况,就必须使用rebase了。 git rebase -i HEAD~3 表示要修改当前版本的倒数第三次状态。 这个命令出来之后,会出来三行东东: pick:******* pick:******* pick:******* 如果你要修改哪个,就把那行的pick改成edit,然后退出。 这时通过git log你可以发现,git的最后一次提交已经变成你选的那个了,这时再使用: git commit --amend 来对commit进行修改。 修改完了之后,执行 git rebase --continue

保存修改。

C/C++

7.C中static函数有什么作用?

在函数的返回类型前加上关键字static,函数就被定义成为静态函数。 函数的定义和声明默认情况下是extern的,但静态函数只是在声明他的文件当中可见,不能被其他文件所用。 定义静态函数的好处: <1> 其他文件中可以定义相同名字的函数,不会发生冲突 <2> 静态函数不能被其他文件所用。 存储说明符auto,register,extern,static,对应两种存储期:自动存储期和静态存储期。 auto和register对应自动存储期。具有自动存储期的变量在进入声明该变量的程序块时被建立,它在该程序块活动时存在,退出该程序块时撤销。 关键字extern和static用来说明具有静态存储期的变量和函数。用static声明的局部变量具有静态存储持续期(static storage duration),或静态范围(static extent)。虽然他的值在函数调用之间保持有效,但是其名字的可视性仍限制在其局部域内。静态局部对象在程序执行到该对象的声明处时被首次初始化。

8.如何扩展红黑树,能够得到树中某个节点的秩。

参考:剑指XX游戏(六) - 轻松搞定面试中的红黑树问题

证明题

9.X是整数,X>=5,X与X+2都是素数,请证明:X+1一定是6的倍数。

真是一道超简单的题,但当时就是没有想出来。

解:X,X+1,X+2,为三个连续数,那么,X,X+1,X+2,三个数中一定有个数是3的整数倍。而X,X+2都是素数,那么,X+1肯定是3的整数倍。 又,X是素数,且X>5,则X肯定是奇数。X+1肯定为偶数,所以X+1是2的倍数。 故,X+1是2的倍数,且是3的倍数。由此可证明,X+1是6的倍数。

总结

1.算法是重中之重!Cracking the coding interview, leetcode 刷起;

2.把握好节奏。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

linux命令行文本操作一文就够

主要是 awk/grep/sed这三驾马车,加上vi这个神器,最后辅助一些小工具,包括 wc,cat,diff,join,paste,cut,uniq 这里 简...

4539
来自专栏Java架构沉思录

伪共享和缓存行填充,Java并发编程还能这么优化!

关于伪共享的文章已经很多了,对于多线程编程来说,特别是多线程处理列表和数组的时候,要非常注意伪共享的问题。否则不仅无法发挥多线程的优势,还可能比单线程性能还差。...

1192
来自专栏木宛城主

Unity应用架构设计(6)——设计动态数据集合ObservableList

什么是 『动态数据集合』 ?简而言之,就是当集合添加、删除项目或者重置时,能提供一种通知机制,告诉UI动态更新界面。有经验的程序员脑海里迸出的第一个词就是 O...

1927
来自专栏Hongten

java开发_UUID(Universally Unique Identifier,全局唯一标识符)和GUID(Globally Unique Identifier,全球唯一标识符)

GUID: 即Globally Unique Identifier(全球唯一标识符) 也称作 UUID(Universally Unique IDentifie...

1071
来自专栏用户2442861的专栏

unix 的 bash shell 脚本

1. test01   test02 1 200    1 100 2 500    2 300 3 200    3 50 4 100    4 ...

1312
来自专栏蓝天

使用可重入函数进行更安全的信号处理

在早期的编程中,不可重入性对程序员并不构成威胁;函数不会有并发访问,也没有中断。在很多较老的 C 语言实现中,函数被认为是在单线程进程的环境中运行。

812
来自专栏从零开始学自动化测试

pytest文档9-参数化parametrize

这将运行测试,参数设置为x=0/y=2,x=1/y=2,x=0/y=3,x=1/y=3组合参数。

1752
来自专栏JackeyGao的博客

Django小技巧22: 设计一个好的模型

本篇将分享一些技巧,用户改进 Model 的设计。其中有很多与命名约定有关, 这可以大大的提高代码的可读性。

1452
来自专栏cmazxiaoma的架构师之路

【分布式架构之旅】Redis入门

2513
来自专栏草根专栏

使用 Moq 测试.NET Core 应用 -- Mock 属性

第一篇文章, 关于Mock的概念介绍: https://www.cnblogs.com/cgzl/p/9294431.html

1084

扫码关注云+社区

领取腾讯云代金券