专栏首页逮虾户最近面试碰到的两道算法题|面试相关

最近面试碰到的两道算法题|面试相关

TopK 最大的K个数

10亿数据内筛选最大的100个,要求速度要快。

最近阿里的一道面试题,其实基于多层博弈论,我想我刷过这题,我知道如何偷鸡的。我以为我在第二层,没想到我只在第一层。

第一层

于大顶堆的方式的方式筛选出数组内最大的k个数。

先看看顶堆的数据结构,其中可以看出0位置是要么就是堆内最大或者最小,然后我们可以利用堆的特性,去把当前的数组的值和这个最大最小进行比较。堆的另外一个特性就是会重排序,参考堆排序算法。

当然你让我现场手写写我肯定是忘了,但是一个开发是可以偷鸡的呀,我们可以直接用优先级队列PriorityQueue的内部实现就是大顶堆。对于海量数据来说,优先级队列基本就是一个比较合适的答案了。

总数1万个取最大100,快排略快,最小堆偶尔快。

总数10万个取最大100,最小堆略快,快排偶尔快。

总数100万个取最大100,最小堆完胜,快排没戏,而且最小堆大概快了2倍。

总数1000万个取最大100,最小堆完虐,快排没戏,而且最小堆快了大概2倍。

结论:最小堆比快排优秀。

原因:

1.速度确实快。

2.最小堆不需要打乱原数据顺序,而快排会打乱。(并不是快的原因,而是最小堆的优点)

3.如果内存有限,无法加载所有数据,则最小堆快。

以上数据引用自 topK问题最小堆和快排哪个快。所以偷鸡就可以解决第一层的问题。

  public int findKthLargest(int[] nums, int k) {
        PriorityQueue queue=new PriorityQueue(k,new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        for(int i=0;iif(queue.size()>k){
                queue.poll();
            }
        }
    
        return queue.peek();
    }
复制代码

这是我leetcode乱写的第k大个数啊。

第二层

面试官对我的偷鸡取巧并不满意啊,他需要我提速,这个速度不行啊。

What??是有时间复杂度更低的吗?不不不,这是一道核心竟然是一道多线程的题目。

  1. 将10亿的数据分片,通过分治的思维对数据进行第一次处理。
  2. 开启多线程然后对其进行这些分片的数据进行优先级队列操作。
  3. 然后每个子线程筛选出其中最大的k个数
  4. 当所有线程执行完毕之后合并数据

我猜测的第三层

  1. 是不是考虑下多少个数据一分片,然后如何把效能提升到最高的问题?
  2. 构建多少个线程读取效率是最高的?

这个都是我没想到的,各位大佬有想法的可以聊一下啊。

一篇文章内的单词数量

这题乍一看卧槽貌似不难,foreach循环碰到一个空格或者标点的情况下sum++,是不是就可以解决这个问题。

然而事情并没有想想的这么简单。面试被问到这种问题最难的是什么,可能是对于这题目真实的边界问题的思考。

  1. 如果这篇文章内容很大怎么办,会不会把内存吃光?
  2. 如何给单词去除重复?

是不是可以考虑逐行读取呢?

将其转化成IO流,逐行读取流,之后对这个输入内容进行一次计数操作,是不是就可以解决这个问题呢。

单词重复的问题

卧槽,这个真简单HashSet啊!!!!那么如果海量数据我是不是又炸了?

卧槽,死亡螺旋吗。或许我们可以考虑下用hash的方式来解决,只保留单词的hashcode,是不是可能可以解决呢。

同样的这个也可以使用多线程分片去优化

方式的话基本也和上面是完全一样的,只要把数据分片,之后多线程调度,然后合并结果就可以了。

总结

我问了下后端大神,这些应该都是mapreduce里面出现的原题啊,都是和海量数据相关的,有兴趣的可以自己去查下。

别说了,这些都是下场之后想了想总结的,当场面试就是懵逼的,边界个锤子。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NLP 算法工程师相关的面试题

    【导读】本项目记录了面试NLP算法工程师常会遇到的问题,作者songyingxin。

    代码医生工作室
  • 近期遇到的关于 Python 的面试题

    前段时间去面试了一些招聘 Python 软件开发的公司,看看现在的公司都关注 Python 的那些方面。因为疫情原因,现在面试都是电话或者视频面试,也可以约晚上...

    somenzz
  • 两道看似简单的面试高频算法题

    前几天写了一篇二分查找的文章如何理解二分查找?生活中还能用来设计骗局?,文章的末尾留下了两道题,这两道题是从 leetcode 的面试高频题的选的,也算是面试经...

    帅地
  • 两道看似简单的面试高频算法题

    当然,这道题你也可以采用 n 次循环让 n 个 x 相乘,不过,这样的做法毫无意义,因为估计小学生也会做。

    乔戈里
  • 面试真题 | 腾讯数据分析最爱考的两道面试题

    今天给各位分享两道数据分析试题,这是腾讯数据分析面试官在面试时考察候选人喜欢出的题,属于硬性技能考察题目,特别好用。

    咸鱼学Python
  • 最近刷爆朋友圈的一道面试题

    最近在网上有一道面试题掀起了劲爆的浪潮,好多家公司都模仿提问了这么一道面试题,而且好多人也都在讨论这道面试题要是自己回答的话该怎么回答!这道题也是在个网站上刷爆...

    烂猪皮
  • 【资源】NLP 算法工程师相关的面试题

    https://github.com/songyingxin/NLPer-Interview

    zenRRan
  • 分享三道面试的算法题

    你有一辆油箱容量无限的的Bytebus,从第 i 个工区开往第 i+1 个工区需要消耗汽油 cost[i] 升。你从其中的一个工区出发,开始时油箱为空。如果你

    java乐园
  • 几道和「二叉树」有关的算法面试题

    在遍历到一个结点之前已经遍历了它的左右子树,那么只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶结点的路径的长度),就可以一边遍历一边判断每个结点...

    五分钟学算法
  • 最近我遇到的10个Java面试问题

    最近,我参加了一些java的面试。突然,我有了一个想法,我想和大家分享我的经历。我希望我能通过分享我最近几个月遇到的10个Java面试问题来帮助大家。

    程序你好
  • 关于淘点点面试中碰到的架构问题​

    之前面试淘点点的时候被问倒得一个问题至今牵挂,由于工作环境的限制,我没能接触到一些大数据量的并发工作,也没能有机遇参与复杂系统的设计,而我学习复杂或高并发系统的...

    用户1257393
  • 几道和「堆栈、队列」有关的面试算法题

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    JAVA葵花宝典
  • 几道和「堆栈、队列」有关的面试算法题

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    zenRRan
  • 几道和「堆栈、队列」有关的面试算法题

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    五分钟学算法
  • 一道有意思的面试算法题

    前阵子突发奇想,突然开始刷leetcode。其中刷到了一道有意思的题目,发现这道题是当时秋招的时候,腾讯面试官曾经问过我的题目。于是分享给大家看下。

    嘿嘿嘿
  • Java:关于main方法的10道面试题

    大年初三好,春节第三天了。感觉假期过得好快,东西也丢得快。 假期吃喝玩乐之余也来温故一下Java知识,下面给大家整理了10道Java main方法的经典面试题,...

    Java技术栈
  • 面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?

    给定一个不确定的 Json 对象,求 Json 子节点的最大深度(编程语言不限,不可写伪代码)。如下:

    霍格沃兹测试开发
  • Vue相关的前端面试题,每道题都很经典~

    用户1687375
  • 几道和「广度优先搜索」有关的算法面试题

    2、从 V0 出发,访问 V0 的各个 未被访问 的邻接点 W1, W2,…, Wk ;然后依次从 W1, W2,…, Wk 出发访问各自未被访问的邻接点;

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券