吉比特 认领
能源/原材料 10-50人 外企代表处
到底有多少疯狗?
吉比特的一个智力题：村子里有50户人家，每家都有一条狗。这些狗中间，有n条疯狗。不过，n是未知的，n>=1；每个人只能看别人家的狗是不是疯狗。不能看自己家的。如果他推断出来自己家的狗是疯狗。那么，可以把自己家的狗杀了。但是不能杀别人家的疯狗，也不能告诉别人对方的狗是疯狗。第一天，没有枪声，第二天也是，第三天。有枪声了。然后，连续有n声枪声。问到底有多少疯狗。我当时没时间做。就看了一眼题，然后就交卷了。后来分析了一下。如果只有一条狗，那么，疯狗的主人一看到别人家的都不是疯狗，自然就知道自己家的是疯狗了。那么，第一天就应该有枪声的。第一天没有枪声，所以n大于等于 2.如果是2，那么，有疯狗的两户人家之中的任意一家，他都之鞥看到另外一家的狗是疯狗，那么，他就能推断出来自己家的狗是疯狗。因为只有他自己家的狗也是疯狗的情况下才能凑足2，这样一来，他就能知道自己家的狗是疯狗，从而把狗杀了。第二天没有枪声，所以，n大于等于3.第三天，有枪声，所以，肯定就是 3了。当时没时间做。幸亏吉比特给我面试通知了，要不得气死。吉比特还有一道题，一个整数数组。长度为n，如何找到第i大的数。我用的是类似于快速排序的方法。每一次，找到一个元素，以他为中点，把数组分成前后两部分。前半部分的每个元素都小于他，后半部分的都大于等于他。这个操作完成以后，就知道他这个中点是从小到大应该排在第几位了。如果刚好是i，那么就返回他。如果小于i，则在后半部分数组中继续找。如果大于i，则在前半部分找。继续找的过程，当然可以用递归了。不用递归，就得用栈来模拟。有点麻烦。还是递归算了。思路也清晰。
正在加载验证码...
进行了难度一般1对1面试
面试问题
到底有多少疯狗?
面试过程
吉比特的一个智力题：村子里有50户人家，每家都有一条狗。这些狗中间，有n条疯狗。不过，n是未知的，n>=1；每个人只能看别人家的狗是不是疯狗。不能看自己家的。如果他推断出来自己家的狗是疯狗。那么，可以把自己家的狗杀了。但是不能杀别人家的疯狗，也不能告诉别人对方的狗是疯狗。第一天，没有枪声，第二天也是，第三天。有枪声了。然后，连续有n声枪声。问到底有多少疯狗。我当时没时间做。就看了一眼题，然后就交卷了。后来分析了一下。如果只有一条狗，那么，疯狗的主人一看到别人家的都不是疯狗，自然就知道自己家的是疯狗了。那么，第一天就应该有枪声的。第一天没有枪声，所以n大于等于 2.如果是2，那么，有疯狗的两户人家之中的任意一家，他都之鞥看到另外一家的狗是疯狗，那么，他就能推断出来自己家的狗是疯狗。因为只有他自己家的狗也是疯狗的情况下才能凑足2，这样一来，他就能知道自己家的狗是疯狗，从而把狗杀了。第二天没有枪声，所以，n大于等于3.第三天，有枪声，所以，肯定就是 3了。当时没时间做。幸亏吉比特给我面试通知了，要不得气死。吉比特还有一道题，一个整数数组。长度为n，如何找到第i大的数。我用的是类似于快速排序的方法。每一次，找到一个元素，以他为中点，把数组分成前后两部分。前半部分的每个元素都小于他，后半部分的都大于等于他。这个操作完成以后，就知道他这个中点是从小到大应该排在第几位了。如果刚好是i，那么就返回他。如果小于i，则在后半部分数组中继续找。如果大于i，则在前半部分找。继续找的过程，当然可以用递归了。不用递归，就得用栈来模拟。有点麻烦。还是递归算了。思路也清晰。