倚楼听风雨
淡看江湖路

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

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

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

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

void *memcpy(void *dst, const void *src, size_t len)  
{  
    if(NULL == dst || NULL == src){  
        return NULL;  
    }  
      
    void *ret = dst;  
      
    if(dst <= src || (char *)dst >= (char *)src + len){  
        //没有内存重叠,从低地址开始复制  
        while(len--){  
            *(char *)dst = *(char *)src;  
            dst = (char *)dst + 1;  
            src = (char *)src + 1;  
        }  
    }else{  
        //有内存重叠,从高地址开始复制  
        src = (char *)src + len - 1;  
        dst = (char *)dst + len - 1;  
        while(len--){  
            *(char *)dst = *(char *)src;  
            dst = (char *)dst - 1;  
            src = (char *)src - 1;  
        }  
    }  
    return ret;  
}

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

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

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

package com.glorze.interview.one;

import java.nio.ByteBuffer;

/**
 * Java拷贝内存的简单实现
 * @ClassName MemCpy 
 * @author: glorze.com  
 * @since: 2018年4月9日 下午11:18:39
 */
public class MemCpy {
	public static void memcpy(Integer src, ByteBuffer buffer, Integer size) {
		if (size > 4) {
			size = 4;
		}
		for (int i = 0; i < size; i++) {
			byte temp = (byte) (((src >> (3 - i)) * 8) & 0xff);
			buffer.put(temp);
		}
	}

	public static void main(String[] args) {
		// 分配直接缓冲区
		ByteBuffer buf = ByteBuffer.allocateDirect(1024);
		memcpy(12345678, buf, 5);
		System.out.print(buf.get(0));
		System.out.print(buf.get(1));
		System.out.print(buf.get(2));
		System.out.print(buf.get(3));
		System.out.print(buf.get(4));
	}
}

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加遍历最后在转换为数组就解决问题了。那么在这个前提之下我们怎么实现的更好、更有效率一些呢?少啰嗦,先看代码!!!

package com.glorze.interview.one;

/**
 * 数组去重并返回去重之后的数组长度
 * @ClassName RemoveDuplicates
 * @author: glorze.com
 * @since: 2018年4月10日 下午10:35:48
 */
public class RemoveDuplicates {

	/**
	 * 用一个指针遍历,相同继续遍历,不同保存。
	 * @Title: removeDuplicates
	 * @param nums
	 * @return int
	 * @author: 高老四博客
	 * @since: 2018年4月10日 下午10:36:13
	 */
	public int removeDuplicates(Integer[] nums) {
		int index = 1;
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] != nums[i - 1])
				nums[index++] = nums[i];
		}
		return index;
	}

	public static void main(String[] args) {
		RemoveDuplicates rd = new RemoveDuplicates();
		Integer[] nums = { 1, 1, 2, 3, 3, 4, 5, 5 };
		System.out.println(rd.removeDuplicates(nums));
		for (Integer num : nums) {
			System.out.println(num);
		}
	}
}

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

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

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

创建Thread的子类
package com.glorze.interview.one;

/**
 * 继承Thread类开启线程
 * @ClassName ThreadPrint 
 * @author: glorze.com  
 * @since: 2018年4月10日 下午10:57:50
 */
public class ThreadPrint extends Thread {
	public void run() {
		System.out.println("运行一个Java线程");
	}

	public static void main(String[] args) {
		ThreadPrint threadPrint = new ThreadPrint();
		threadPrint.start();

		// Thread的匿名子类
		Thread thread = new Thread() {
			public void run() {
				System.out.println("匿名运行一个Java线程");
			}
		};
		thread.start();
	}
}
实现Runnable接口
package com.glorze.interview.one;

/**
 * 实现Runnable接口开启Java线程
 * @ClassName ThreadPrint
 * @author: glorze.com
 * @since: 2018年4月10日 下午10:57:50
 */
public class ThreadPrint implements Runnable {
	public void run() {
		System.out.println("运行一个Java线程");
	}

	public static void main(String[] args) {
		Thread thread = new Thread(new ThreadPrint());
		thread.start();
		
		// 实现了Runnable接口的匿名类
		Runnable myRunnable = new Runnable(){
			   public void run(){
			     System.out.println("实现了Runnable接口的匿名类运行一个Java线程");
			   }
		};
		Thread thread2 = new Thread(myRunnable);
		thread2.start();
	}
}

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

package com.glorze.interview.one;

/**
 * 两个线程交替打印自然数
 * @ClassName ThreadPrint 
 * @author: glorze.com  
 * @since: 2018年4月10日 下午11:13:33
 */
public class ThreadPrint {

	/**
	 * 控制交替打印
	 */
	public boolean flag;

	/**
	 * 本线程打印奇数,则从1开始
	 * @ClassName OddClass 
	 * @author: glorze.com  
	 * @since: 2018年4月10日 下午11:14:00
	 */
	public class OddClass implements Runnable {

		public ThreadPrint tp;

		public OddClass(ThreadPrint tp) {
			this.tp = tp;
		}

		@Override
		public void run() {
			int i = 1;
			while (i < 100) {
				// 两个线程的锁的对象只能是同一个object
				synchronized (tp) {
					if (!tp.flag) {
						System.out.println(i);
						i += 2;
						tp.flag = true;
						tp.notify();
					} else {
						try {
							tp.wait();
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
					}
				}
			}
		}
	}

	/**
	 * 本线程打印偶数,则从2开始
	 * @ClassName EvenClass 
	 * @author: glorze.com  
	 * @since: 2018年4月10日 下午11:14:08
	 */
	public class EvenClass implements Runnable {

		public ThreadPrint tp;

		public EvenClass(ThreadPrint tp) {
			this.tp = tp;
		}

		@Override
		public void run() {
			int i = 2;
			while (i <= 100)
				synchronized (tp) {
					if (tp.flag) {
						System.out.println(i);
						i += 2;
						tp.flag = false;
						tp.notify();
					} else {
						try {
							tp.wait();
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
					}
				}
		}
	}

	public static void main(String[] args) {
		ThreadPrint tp = new ThreadPrint();
		OddClass oddClass = tp.new OddClass(tp);
		EvenClass evenClass = tp.new EvenClass(tp);
		new Thread(oddClass).start();
		new Thread(evenClass).start();
	}
}

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

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

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

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

package com.glorze.interview.one;

/**
 * 正则表达式删除Java代码的注释
 * @ClassName RemoveComments 
 * @author: glorze.com  
 * @since: 2018年4月10日 下午11:37:46
 */
public class RemoveComments {

    public static void main(String[] args) {

        String text = "package projectName;\n" +
                      "\n" +
                      "import java.util.ArrayList;\n" +
                      "\n" +
                      "/**\n" +
                      " * Created by martin on 2017/8/14.\n" +
                      " */\n" +
                      "public class Escape3 {\n" +
                      "\n" +
                      "    public static void main(String[] args) {\n" +
                      "\n" +
                      "        ArrayList<String> arrayList2=new ArrayList<String>();\n" +
                      "        arrayList2.add(\"14\");//编译通过\n" +
                      "        // arrayList2.add(12);//编译通过\n" +
                      "        Object object=arrayList2.get(0);//返回类型就是Object\n" +
                      "        System.out.println((String) object);\n" +
                      "    }\n" +
                      "}";

        System.out.println(removeComment(text));
    }

    private static  String removeComment(String text) {

        // 行级注释匹配 \/\/[^\n]*
        // 块级注释 \/\*([^\*^\/]*|[\*^\/*]*|[^\**\/]*)*\*\/  或者  \/\*(\s|.)*?\*\/
        // 因行级会与协议前缀冲突 需要特殊处理:(?<!http:)\/\/.*   或者  (?<!:)\/\/.*
        return text.replaceAll("(?<!:)\\/\\/.*|\\/\\*(\\s|.)*?\\*\\/","");
    }
}

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。

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

开始你的表演 抢沙发

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

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

支付宝扫一扫打赏

微信扫一扫打赏