欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JAVA实习生面试笔记(一)

程序员文章站 2024-03-22 10:59:28
...

面试时间:2021-01-06-15:30

1、找素数

1) 暴力遍历:判断一个素数的方法,2~sqrt(n)中没有它的因子
2) 优化遍历的条件:存入数组,标记所有奇数为1,偶数为0,遍历所有奇数,判断方法还是遍历2~sqrt(n),若为质数,把该质数的所有倍数标记为0,否则将该数标记为0,继续遍历奇数。

2、如何交换两个变量值

1) 设置中间变量
2) 算术运算:a=b-a; b=b-a; a=b+a  缺点:只能用于数字类型	
3) 位运算:异或运算(相同为0,不同为1): a=a^b; b=a^b; a=a^b
4) 栈实现:先push再pop
5) 指针地址运算:两个变量地址相减找到偏移量,改变变量指向的地址。

3、Hash了解多少?如果两个变量hash值相同会怎样?

1) 概念:Hash是一种信息摘要算法,通过输入key进行hash计算就可以获取key的HashCode(),是一个本地方法,实质是地址取样运算。
2) 碰撞:如果出现了重复的HashCode,即产生哈希碰撞,若key相同则替换旧值,否则以链表的方式链接到后面,如果链表长度超过8转为红黑树存储
3) HashMap的工作原理:
	a. HashMap是一个散列桶(数组+链表+红黑树),存储的内容是key-value映射;
	b. 通过put和get存储和获取对象,put()方法传递键和值时,先对key做一个hashCode()计算(与高16位做异或运算)得到它在bucket数组中的位置来存储Entry对象,重复则以链表形式存储;获取对象时,通过get()获取bucket的位置,再通过键对象的equals()方法找到正确的键值对,然后返回值对象。

4、反转

1) 反转字符串
	a. StringBuilder的reverse()方法;
	b. toCharArray() 变为字符串数组,然后调用swap()交换字符反转;
	c. 转为ArrayList,然后调用Collections.reverse()实现反转;
	d. 利用charAt倒序输出;
	e. https://blog.csdn.net/heinara/article/details/87897602
2)    反转链表
	a. 迭代反转:从当前链表的首节点开始,一直遍历到链表的最后一个节点,逐个改变所遍历的节点的指针域,令其指向前一个节点;
	b. 递归反转链表:从链表的尾节点开始向前遍历,遍历过程依次改变各节点的指向,令其指向前一个节点;
	c. 头插法反转链表:创建新链表,遍历原有链表,依次摘下院链表的头节点以头部插入的方式插入到新链表中;
	d. 就地逆置法反转链表:从头节点开始,将后面的节点摘下,以头部插入的方式插入到新链表中。

5、从大量数中快速找到指定的数,判断一个数是否存在

1) 分治法
	a. 根据实际可用内存的情况,确定一个Hash函数将这些数据划分到多个文件中;
	b. 对待查找的数字使用同样的Hash函数求出Hash值 i,若存在,则一定在第 i个文件中;
	c. 如果该文件较小直接装载到内存中,保存在HashSet中,然后判断查找的数字是否存在;
	d. 否则使用步骤a继续将该文件划分为更小的文件。
2) 位图法
	a. 以32位整型为例,它可以表示的数字个数为2^32,可以申请一个位图,让每个整数对应位图中的一个bit。具体如下:
	b. 申请一个512MB的位图(2^32bit),并把所有的位都初始化为0;
	c. 遍历所有的整数,对遍历到的数字对应位置的bit标记为1;
	d. 判断待查找的数对应的位图的值时多少,如果是0,表示不存在,否则存在。
3) 二分法(姑且这么叫吧)
	a. 将这40亿数分为两类:最高位是0和最高为是1,并分别写入到两个文件中;
	b. 进入与待查找的数的最高位相对应的文件,继续用步骤a的方法将该文件分为两类:次高位为0和次高位为1;
	c. 以此类推
相关标签: JAVA

上一篇: #define

下一篇: .Net 双向链表实现