好猎友前端笔试

选择题(一半是逻辑题)

1.一只青蛙从21米的井里往上爬，白天爬7米，晚上跌4米，几天可以爬上去？

相当于每天爬3米，但是第5天已经爬了5*3=15米，所以第6天白天直接爬6米就出去了，因此总共需要6天。

2.有16瓶水，只有1瓶有毒，用老鼠检测，老鼠只要喝有毒的一滴水就会死亡，求最少用多少只老鼠可以检测出至少14瓶无毒的水？

采用二分处理法

首先将16只老鼠分为A，B两组，每组8只
死1只，可以检测8瓶无毒的水
再死1只，可以又得到4瓶无毒的水
再死1只，又得到2瓶
总共8+4+2=14
若想检测出有毒的那瓶，得用4只

简答题

1.秒杀活动中可能会出现超售(订单量大于设置的库存)的情况，出现的原因和解决思路。

原因：
同时下单人数超过了库存数量，就会导致商品超售问题
解决思路：

• 用额外的单进程处理一个队列，下单请求放到队列里，一个个处理，就不会有并发的问题了，但是要额外的后台进程以及延迟问题，不予考虑。
• 借助文件排他锁，在处理下单请求的时候，用flock锁定一个文件，如果锁定失败说明有其他订单正在处理，此时要么等待要么直接提示用户”服务器繁忙”
• 数据库乐观锁，大致的意思是先查询库存，然后立马将库存+1，然后订单生成后，在更新库存前再查询一次库存，看看跟预期的库存数量是否保持一致，不一致就回滚，提示用户库存不足

2.什么是死锁？如何避免死锁？

定义：
是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
避免(从产生的必要条件出发)，死锁的发生必须具备以下四个必要条件：

• 互斥条件
• 不可抢占条件
• 占有且申请条件
• 循环等待条件
  即只要打破上述四个必要条件中的任意一个条件，死锁就不会发生

3.有25匹马，5个赛道，每个赛道只能有一匹马赛跑，比赛时只能得出相对快慢，不能得出准确速度，求得出1,2,3名要比赛几次？

每匹马只有跑了才能看出速度，所以25匹马都至少跑了一次，最少5轮，由于只要最终前3，所以后面的比赛只有每轮的1,2,3有意义继续比下去，4、5名直接淘汰。首先前5轮得出每组第一，这5个第一再比一次，最快的就是最终第一。然后将这次4、5名及其所在的组全部淘汰。
然后第一组的2、3名，第二组的1、2名，第三组的第1名比最后一次。
因此总共需要7轮。

编程题

1.以时间复杂度不超过O(N)的方法求斐波拉契数列的第N项的值。

• 递归算法(时间复杂度为O(2n)=O(n))

  1 2 3 4 5 6 7 8

  function f1(n) { if(n<=2) { return 1; } else { return f1(n-1)+f1(n-2); } }

• 循环算法(时间复杂度为O(n))

  1 2 3 4 5 6 7 8 9 10 11 12

  function f1(n) { if(n<=2) { return 1; } var a1=1,a2=1,a3; for(var i = 3;i <= n;i++) { a3 = a1 + a2; a1 = a2; a2 = a3; } return a2; }