首先使用包含500个url的文件创建一个hash_set

然后遍历50M的url记录,如果url在hash_set中,则输出此url并从hash_set中删除这个url

所有输出的url就是两个记录相同的url

分析： IP总个数2^32 = 4G，如果单机用一个hash表来存储，光IP部分就得4G*4 = 16G，不现实

把文件按照hash(IP)%1000的方式分割成1000个小文件，相同IP的日志肯定落到了同一个文件中，

针对每一个小文件，用hash_map统计出次数最多的那个IP，得到1000个“最多”的IP，

然后在这1000个“最多”的IP中找到最大的即可。

将所有查询进行hash(query)%10，映射成新的10个文件，大约每个1GB。

对每个文件使用hash_map统计频率并排序，然后对10个结果再归并排序。

题目:

1. 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
2. 木杆很细，不能同时通过两只蚂蚁。
3. 开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。
4. 当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。

5. 假设蚂蚁们每秒钟可以走一厘米的距离。

   编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间

题解:

• 木杆两边其实都是可以过去的..
• 蚂蚁每秒走1厘米!所以所有蚂蚁的速度都是一毛一样的!
• 蚂蚁的朝向不一定
• 因为速度一样,位置不一样,所以不可能在同一时间,某个点上有三个以上包括三个蚂蚁同时存在

思路:

• 脑子里先把木杆横着放!别竖着.. 哈哈哈.. 竖着放真的会限制很多思路.. 我本能的想着竖着放..
  • 先假设杆子上有ab两只蚂蚁,且是相向而行(面对面),a往右走,b往左走,当ab相遇后,a转头,往左走,b转头,往右走,因为他俩速度一样,其实就可以理解为,b还在往左走,a继续往右走!
  • 仔细品品上面这句话!
  • 假设有三只,其实也是一样的!(注意,速度相同,时间相同,所以同一位置最多只有两只会相遇,不可能有两只以上会同一时刻在一个点)
• 这样理解的话,最少时间好理解,肯定都是朝着自己木杆最近的一端走是最快的!(所以判断自己在木杆的左半部分还是右半部分)
• 最长时间,根据上面那个替换思路,那么最长时间肯定是谁离木杆的一端最远,就是最长时间!

代码:

我临时用go写的,

    func ant(arr []int,lens int) (min,max int) {
        limit := lens>>1
        // maxLi 最大值 左半部分与最右端距离 和 右半部分与最左端的距离 谁大  那么就是最大值
        // minLi 最小值 左半部分与最左端距离 与 右半部分与最右端的距离 谁大(没错,也是最大)  那么就是最小值
        var maxLi,minLi int
        for _,v := range arr {
            if v <= limit {
                if minLi <  v {
                    minLi =  v
                }

                if maxLi < lens - v {
                    maxLi = lens - v
                }

            } else {
                if minLi < lens - v {
                    minLi = lens - v
                }
                if maxLi <  v {
                    maxLi =  v
                }

            }
        }

        return minLi,maxLi
    }

题目:

• 三个警察和三个囚徒共同旅行。一条河挡住了去路，河边有一条船，但是每次只能载2人。

• 存在如下的危险：无论在河的哪边，当囚徒人数多于警察的人数时，将有警察被囚徒杀死。

问题：请问如何确定渡河方案，才能保证6人安全无损的过河。

答:

• 我个人看完后.. 感觉题目不太严谨..

  看网上给的解答:

  • 第一次：两囚徒同过，回一囚徒
  • 第二次：两囚徒同过，回一囚徒
  • 第三次：两警察同过，回一囚徒一警察（此时对岸还剩下一囚徒一警察，是安全状态）
  • 第四次：两警察同过，回一囚徒（此时对岸有3个警察，是安全状态）
  • 第五次：两囚徒同过，回一囚徒
  • 第六次：两囚徒同过；over

  我简单想了一下:

  • 第一次: 两囚徒同过，回一囚徒 (左边3警察2囚徒,右边1个囚徒)
  • 第二次: 一个警察过去,不用回(左边2警察2囚徒,右边1警察1囚徒)
  • 第三次: 一个警察一个囚徒一起过(左边1个警察1个囚徒,右边2警察2囚徒)
  • 第四次: 一个警察一个囚徒一起过(全到右边了) 我的思路里,就是第二次,只有一个人过去,且没人回..所以说题目不严谨,没要求必须有人回或者有人必须两人一起过去! 写完才发现.. 如果按照我这思路. 每次都过一个警察1个囚徒,别回来人了.. 三次不就直接过去了么.. 哈哈哈哈哈哈

代码:

我得想想怎么写

题目:

搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前10条，我们每次输入的一个字符串为不超过255byte，内存使用只有1G。请描述思想，写出算法，空间和时间复杂度。

解答:

300万个字符串最多（假设没有重复，都是最大长度）占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理。

可以使用key为字符串（事实上是字符串的hash值），值为字符串出现次数的hash来统计每个每个字符串出现的次数。并用一个长度为10的数组/链表来存储目前出现次数最多的10个字符串。

这样空间和时间的复杂度都是O(n)。