倚楼听风雨
淡看江湖路

Java十道由浅入深的面试题第一期(下) 详细解析

作为一名Java开发工程师,几乎所有的笔试题都有某一方面的考点,开坑这个系列主要原因除了共同进步以外,更多的是想了解更多的Java知识点,最后总结出常见的笔试中出题者大多都远考Java中那些比较常用的知识点。如果在老四一期一期的面试题当中也能够为你带来一点点的帮助,也算是功德一件了。

6.Java拷贝内存,实现类似C++中的memcpy函数。

解析:memcpy函数用到了很多内存操作,目的其实是实现从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。但是在Java中是无法直接对内存进行操作的,所以往往有的时候我们需要借助未操作来实现内存的拷贝。一下是memcpy函数的基本源码:

因为学艺不精,其实老四对内存拷贝这类知识也比较一塌糊涂,所以不敢妄自菲薄,找了一段网上的代码供大家参考。除此之外,你可能需要了解的一些知识:

  • Arrays.copyof方法 实现数组拷贝
  • Java的深拷贝与浅拷贝
  • system.arraycopy() 上述Arrays.copyof方法的底层使用的就是这个
  • Java的nio,nio之bytebuffer相关知识

以上这些老四会陆续写文章记录这些技术的知识点。

7.有一个已排序的整数数组,但其中可能存在重复的数字,请编写函数,去除数组中的重复数据(重复数保留1个),返回去重后的数组长度N,同时,原数组的前N个成员是去重后的结果。要求算法的空间复杂度为O(1)。

解析:首先我们来了解一下数据结构当中空间复杂度的概念。

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

这种语言多半比较晦涩难懂,再次引用程杰在《大话数据结构》中关于空间复杂度的说法:

我们在写代码时,完全可以用空间来换取时间,比如说,要判断某某年是不是闰年,你可能会花一点心思写了一个算法,而且由于是一个算法,也就意味着,每次给一个年份,都是要通过计算得到是否是闰年的结果。还有另一个办法就是,事先建立一个有2050个元素的数组(年数略比现实多一点),然后把所有的年份按下标的数字对应,如果是闰年,此数组项的值就是1,如果不是值为0。这样,所谓的判断某一年是否是闰年,就变成了查找这个数组的某一项的值是多少的问题。此时,我们的运算是最小化了,但是硬盘上或者内存中需要存储这2050个0和1。

这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好,其实要看你用在什么地方。

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数,则称这个算法的辅助空间为O(1);

所以,如题中所要求O(1)那样,其实就是要求你别再去声明一个新的数组或者集合来解决这个问题。要不然反手就是一个list加遍历最后在转换为数组就解决问题了。那么在这个前提之下我们怎么实现的更好、更有效率一些呢?少啰嗦,先看代码!!!

如果我们需要删除数组中的重复元素,那我们旺旺需要两个指针,一个存储新的元素,另一个用来遍历,而这道题要求你反悔去重后数组的长度并排序就行了,所以一个指针判断不同就可以了。

8.并发编程。请编写2个线程,线程1顺序输出1,3,5,.....,99等奇数序列,每个数一行。同理,线程2顺序输出2,4,6,.....100等偶数,每个数一行。最终的结果要求是输出为自然数序列顺序:1,2,3,4,......99,100。

解析:先来复习一下如何如何创建并运行java线程的基本知识(此处引用并发编程网-ifeve.com相关介绍,你也可以直接参考并发编程网):

创建Thread的子类

实现Runnable接口

线程老四以后一定会各种文章来写的,这里就是简单的复习一下。说会这道题,是怎样的一个实现思路呢?其实这道题是考验我们主对多线程创建以及多线程执行顺序的应用,难点是通过对一个对象的加锁,避免多线程随机打印,用一个开关控制打印奇数还是偶数。

9.请编写一段代码,删除掉Java源代码中的全部注释,保留其他代码。

解析:还真是什么题都能让他们想得出来呢~~~先来复习一下Java中的三种注释:

  • 单行注释 //
  • 多行注释 /* */
  • 文档注释 /** */ JDK提供的javadoc工具可以直接将源代码里的文档注释提取成一分系统的API文档。

所以,要删除这些源代码,你需要考虑这三种注释的字符串格式,从而下手。关于字符串的处理,估计网上已经有很多了,所以就不给出我的代码了,给出来也是老四抄袭的。如果你喜欢用正则表达式,可以考虑一下,老四四这里就放出来一个,还是比较方便的。。。

10.有一个超过10亿行的大文本文件file1.txt,每一行包含一个整数,整数的顺序是杂乱无章的,整数的取值范围:0-42亿之间。请编写函数,读取文件,找出其中最大的1000个整数,并打印出来。

对于这道题,老四学艺不精,找了一下资料,也简单说一下思路。对于海量数据处理的问题,我们很难写出精确地代码,多数都要用伪代码来替代。而面试官也主要是考察你解决问题的能力和掌握的方法有多少,对相关数据结构(排序、查找等)是否有比较熟练的行为。

  • 用一个含100个元素的最小堆完成,复杂度为O(10y*lg1000)
  • 采用快速排序的思想,每次分割之后只考虑比轴大的一部分,直到比轴大的一部分在比1000多的时候,采用传统排序算法排序,取前1000个,复杂度为O(10y*1000)。
  • 采用局部淘汰法。选取前1000个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的1000个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(10y*1000)。
  • 建立一个临时数组,数组大小为K,从N中读取K个数,降序全排序(排序算法可以自行选择,考虑数组的无序性,可以考虑选择快速排序算法),然后依次读入其余N - K个数进来和第K名元素比较,大于第K名元素的值则插入到合适位置,数组最后一个元素溢出,反之小于等于第K名元素的值不进行插入操作。只待循环完毕返回临时数组的K个元素,即是需要的K个最大数。同算法一其平均时间复杂度为O(KLogK + (N - K))。

源码包结合第一期源码包都放在一起,文末自助获取下载。

更博不易,如果觉得文章对你有帮助并且有能力的老铁烦请赞助盒烟钱,点我去赞助。抱拳。

资源下载

隐藏内容:******,购买后可见!

下载价格:0 G币

您需要先后,才能购买资源

欢迎访问高老四博客(glorze.com),本站技术文章代码均为老四亲自编写或者借鉴整合,其余资源多为网络收集,如涉及版权问题请与站长联系。如非特殊说明,本站所有资源解压密码均为:glorze.com。

赞(1) 给你买杜蕾斯
本站原创文章受自媒体平台原创保护,未经允许不得转载高老四博客 » Java十道由浅入深的面试题第一期(下)
分享到: 更多 (0)

开始你的表演 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下老四,鼓励我更好的创作

支付宝扫一扫打赏

微信扫一扫打赏