1. 大公司经典

1.1.1. 一个大的含有50M个URL的记录,一个小的含有500个URL的记录,找出两个记录里相同的URL

点击显示

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

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

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

1.1.2. 海量日志数据,提取出某日访问百度次数最多的那个IP

点击显示

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

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

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

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

1.1.3. 有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。如何按照query的频度排序?

点击显示

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

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

1.1.4. 蚂蚁爬木杆的问题?

点击显示

题目:

  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
    }

1.1.5. 三个警察和三个囚徒过河问题?

点击显示

题目:

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

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

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

答:

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

    看网上给的解答:

    • 第一次:两囚徒同过,回一囚徒
    • 第二次:两囚徒同过,回一囚徒
    • 第三次:两警察同过,回一囚徒一警察(此时对岸还剩下一囚徒一警察,是安全状态)
    • 第四次:两警察同过,回一囚徒(此时对岸有3个警察,是安全状态)
    • 第五次:两囚徒同过,回一囚徒
    • 第六次:两囚徒同过;over

    我简单想了一下:

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

代码:

我得想想怎么写



1.1.6. 从300万字符串中找到最热门的10条?

点击显示

题目:

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

解答:

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

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

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

以上题目和解答来自网络

欢迎加入PHP交流群(QQ群号):PHP编程技术交流群 440221268

欢迎加入Golang交流群(QQ群号):PHP/Golang技术交流群 423069874

results matching ""

    No results matching ""