简单的面试思考题
思考题一
有64瓶疫苗, 其中一瓶不小心混入了有害物质, 现在要利用小白鼠找出那一瓶!
注意:小白鼠只要喝一点点混入有害物质的在30分钟就是死亡, 那么现在只剩下30分
钟了(只能进行一次实验), 问最少需要几只小白鼠可以找出那瓶混入有害物质的疫苗
使用二进制编码
1.将64瓶疫苗从0~63进行编号
2.将每一瓶疫苗的编号转为二进制表示
package cn.itcast.test; /** * Author itcast * Desc */ public class Test01 { public static void main(String[] args){ for (int i = 0; i <= 63; i++) { System.out.println(i+":"+Integer.toBinaryString(i)); } } }
00:000000 01:000001 02:000010 03:000011 04:000100 05:000101 06:000110 07:000111 08:000000 09:000001 10:000010 11:000011 12:000100 13:000101 14:000110 15:000111 16:010000 17:010001 18:010010 19:010011 20:010100 21:010101 22:010110 23:010111 24:011000 25:011001 26:011010 27:011011 28:011100 29:011101 30:011110 31:011111 32:100000 33:100001 34:100010 35:100011 36:100100 37:100101 38:100110 39:100111 40:101000 41:101001 42:101010 43:101011 44:101100 45:101101 46:101110 47:101111 48:110000 49:110001 50:110010 51:110011 52:110100 53:110101 54:110110 55:110111 56:111000 57:111001 58:111010 59:111011 60:111100 61:111101 62:111110 63:111111 ----------- ******
3.拿出6只小白鼠和上面的6个二进制位一一对应
4.然后这6只小白鼠喝对应的二进制位是1的疫苗(只喝一点点即可)
如左边第一只,喝32~63
如右边第一只,喝编号是奇数的
...其他的类似
5.30分钟后观察结果,看哪些小白鼠死了既可以推断出混入有害物质的疫苗
如: 都没死, 那么0号000000混入有害物质
如: 都死了, 那么63号111111混入有害物质
如: 从左边开始135死了,那么 42号101010混入有害物质
- 原理:
现代科学实验思想: 通过现象猜想本质 , 通过本质/原理,也可以推导可能发生的现象
- 如:
观察到先看见闪电, 后听到雷声, 我猜想: 光速比声速快
而事实也是确实是光速比声速快,所以先看见闪电, 后听到雷声
思考题二
有 1~ n, n个数字(n很大,但不一定有序),
但是不小心丢了其中一个,
让写代码找出丢的哪一个! 要求效率最高
可能的解法
1.排序+二分(效率太低,因为要排序) 2.先求1~n的和((1+n)*n/2)再减去n-1个数,最后的结果的数就是丢失的数(已经很快了,但是还是要进行加减法) 3.位运算比加减法还要快 &与 |或 !非 ^异或 ^异或的特点: 二进制: 1001 ^1001 ----- 0000 1001 ^0110 ------ 1111 所以异或的特点是二进制位相同为0,不同为1 那么推广到1~n,相同的数据异或为0,不同的先不管 1010 ^0000 ----- 1010 一个数和0进行异或等于这个数本身 且异或满足交换律,异或顺序可以随便调 1 ^ 2 ^ 3 ....^n--这是有丢失的 ^1 ^ 2 ^ 3 .x..^n--这是没有丢失的 ----------------- 0^0^0....^x = x
代码实现
package cn.itcast.test; /** * Author itcast * Desc */ public class Test02 { public static void main(String[] args) { int result = 0; int[] arr1 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};//完整的 int[] arr2 = new int[]{1, 2, 3, 4, 0, 6, 7, 8, 9, 10};//丢失了一个数的 for (int i = 0; i < arr1.length; i++) { if (i == 0) { result = arr1[i] ^ arr2[i]; } else { //result = result ^ (arr1[i] ^ arr2[i]); result ^= (arr1[i] ^ arr2[i]); } } System.out.println("丢失的数为:" + result); } }
思考题三
有1个桶里面有100个黑球,100个白球, 桶外还有足够的黑球白球
现在从桶里每次随机取出2个球,
如果颜色相同就放回一个白球,
如果颜色不同就放回一个黑球,
问最后桶里剩下的一个球是什么颜色的球?
使用位运算异或^ 相同为0,不同为1 所以令白球为0,黑球为1 那么题目就变成了100个0和100个1进行^ 0 ^ 0 ^ 0....^ 0 ==0 1 ^ 1 ^ 1....^ 1 == 0 ------------------ 0是白球
package cn.itcast.test; import java.util.ArrayList; import java.util.List; import java.util.Random; /** * Author itcast * Desc */ public class Test03 { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i = 1; i <= 100; i++) { list.add(0);//白球 list.add(1);//黑球 } Random random = new Random(); while (list.size() > 1) { Integer i1 = list.get(random.nextInt(list.size())); Integer i2 = list.get(random.nextInt(list.size())); list.remove(i1);//移除该对象 list.remove(i2);//移除该对象 list.add(i1 ^ i2); } System.out.println(list); } }
