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. 以此类推
上一篇: #define
下一篇: .Net 双向链表实现