一道面试题:比较两个集合是否相等?

简介:

先声明:本文内容是偏向于应用开发的,分析解答过程不适用于纯算法研发岗位。

 

朋友小P近来参加某互联网公司的电话面试,被问到一道题:怎么判断两个集合是否相等?注意,这是面试官的原话,一字不多,一字不少。

 

小P迅速回答道用哈希,对方在电话里也没有要求给出具体的解决方案,就问除了哈希还有别的方法吗?小P回答暂时没想到别的方法,对方也没继续追问,就进入到其它题目的问答。

 

今天聊起时感觉这是道不错的面试题:难度合适,可以根据不同的回答考察出不同类型的面试者,以及在整个展开的过程中可以初步了解到面试者水平层次,和其分析、解决问题的综合能力。

 

小P的回答,其实不是让人很满意——起码我是面试官的话我会觉得还有可以提升的地方。我不知道面试官的本意,但是在我看来,这么简短的一道题,应该本身就是设置了很多“坑”的——条件是缺失的,简短的题目并没有给出足够多的信息以便答题者“对症下药”。当然,考虑到是电话面试,以及小P较为欠缺的面试经验来看,其能迅速答出用哈希应该也算反应快且基础较为扎实。但是面试官没有进一步的去考察,猜测可能是对小P的“快速解答”有所失望(或者说没达到其预期),所以该题也就“点到为止”。

 

根据不同的面试职位,本题应该是有不同的侧重点的。小P面的是偏业务、应用的开发工程师。对于一名应用工程师而言,当碰到这么一道信息不足的题时,想到的是怎么来完善这些信息,然后再根据不同的场景以给出最优方案。这时的沟通、分析、探讨都很重要——其实还可以分享一个“秘密”:在一流的企业里,coding这项技能,应该只占应用开发工程师30%左右的比重,除此之外需要综合考虑的“软”能力还有很多。

 

回到这道题上。判断两个集合是否相等,我们最好先清楚这些:这是两个什么样的集合?有序的还是无序的?里面是有重复元素的还是已经各自去重的?集合的数据量大概是有多大?知道这个集合里数据的大概范围吗?相等的定义是什么?当两个集合里元素一样时还要求其顺序也一样吗?size==0的集合和null算相等吗?

 (ps:思考一下,如果自己面试算法类的,应该考虑到什么盐的问题??)

 

如果小P是按这个思路去跟面试官沟通,也许效果会更好。其实通过这些提问式的沟通,并不是说要炫我们的面试技巧,而是实事求是的去思考、分析题目。

 

如果说两个集合是去重的小范围内的正整数,那题目就退化的很简单了:此时我们可以用一个辅助数组来轻松解答。如集合A和集合B是落在[0,99]范围的去重正整数集合,那么new一个int[100]数组t,然后扫一遍A,把t[A[i]]赋值为非零(数组t的初始化各元素均为0)。再用一样的操作对B扫一遍,不过此时是对t[B[i]]赋值为0。最后第三遍扫数组t,如果t的元素还全是0则两集合相等。时间复杂度O(n)。其实这个思路也类似于小P提到的哈希,不过他回答的让人感觉太过于草率,没有任何分析,直接就答,搞的整个效果就是——你就那么一问,我就这么一答。

(ps:map比较)

 

继续侃下这道题,如果没有这么多“恰当好处”的前提条件帮助,那又怎么解决呢?其实谁都懂的一个算法就是蛮力法:两个集合里的元素一一做比较呗。很多人看到这里是很不屑的:这有什么好答的。其实不然,最直观的方法最不容易出错。该题里用蛮力法的话时间复杂度是O(n^2)。如果集合的元素个数不多(多少算多呢?),答题者直接回答这个也OK的——因为在我们最常用的JDK里,集合类的equals方法,都是这么实现的,我们来看下:

 

public boolean equals(Object o) {
        if (o == this)
            return true;

        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        try {
            return containsAll(c);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

以上代码是JDK AbstractSet类里equals方法的实现,如果跟进去看到最后发现就是一个蛮力法一一比较的,没有什么技巧。什么,你不知道这个?JDK是最优秀的Java源码之一,你用Java没理由不去研读学习吧——不然确实是要对你的钻研精神、技术热情等持怀疑态度了——在优秀企业里,想招的都是那种真正有N年工作经验的人,而不是用一招鲜重复工作了N年的人。知其然更要知其所以然,这也是区分优秀者和平庸者的一个方法。

如果两个需要比较的集合数据量特别大怎么办?这时候我们可以考虑用下预处理了:是否能对两个集合提前排好序,然后在比较过程中查找元素时是否要用上二分查找?排序的开销,和直接查找的开销,是否要根据不同的业务场景来做个折中?如果只是一次性的操作也许排序的意义不大,但如果是需要大量重复操作的呢?如果是集合不变的,以及集合经常会发生变化的,采用的策略也不一样——经常发生变化的是否要去维护一个堆排序?

如果参加过ACM的同学也许还会想到蒙特卡罗算法(详情见这里)

如果这道题是可以直接用现成第三方库类的,那JDK里已经有可以满足的了。

虽然在纯算法方面我也没能给出特别巧妙的解法,但我相信如果小P当时能按这个思路来回答,也许这道题就不会是草草收场,没准能跟面试官一起讨论出一个满意的结局。如果有谁有特别好的思路,欢迎留言探讨,共同进步。

目录
相关文章
|
3月前
|
安全 Java 容器
【Java集合类面试二十七】、谈谈CopyOnWriteArrayList的原理
CopyOnWriteArrayList是一种线程安全的ArrayList,通过在写操作时复制新数组来保证线程安全,适用于读多写少的场景,但可能因内存占用和无法保证实时性而有性能问题。
|
3月前
|
存储 安全 Java
【Java集合类面试二十五】、有哪些线程安全的List?
线程安全的List包括Vector、Collections.SynchronizedList和CopyOnWriteArrayList,其中CopyOnWriteArrayList通过复制底层数组实现写操作,提供了最优的线程安全性能。
|
3月前
|
Java
【Java集合类面试二十八】、说一说TreeSet和HashSet的区别
HashSet基于哈希表实现,无序且可以有一个null元素;TreeSet基于红黑树实现,支持排序,不允许null元素。
|
3月前
|
Java
【Java集合类面试二十三】、List和Set有什么区别?
List和Set的主要区别在于List是一个有序且允许元素重复的集合,而Set是一个无序且元素不重复的集合。
|
3月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
3月前
|
存储 Java 索引
【Java集合类面试二十四】、ArrayList和LinkedList有什么区别?
ArrayList基于动态数组实现,支持快速随机访问;LinkedList基于双向链表实现,插入和删除操作更高效,但占用更多内存。
|
18天前
|
存储 安全 算法
Java面试题之Java集合面试题 50道(带答案)
这篇文章提供了50道Java集合框架的面试题及其答案,涵盖了集合的基础知识、底层数据结构、不同集合类的特点和用法,以及一些高级主题如并发集合的使用。
43 1
Java面试题之Java集合面试题 50道(带答案)
|
2月前
|
安全 Java API
【Java面试题汇总】Java基础篇——String+集合+泛型+IO+异常+反射(2023版)
String常量池、String、StringBuffer、Stringbuilder有什么区别、List与Set的区别、ArrayList和LinkedList的区别、HashMap底层原理、ConcurrentHashMap、HashMap和Hashtable的区别、泛型擦除、ABA问题、IO多路复用、BIO、NIO、O、异常处理机制、反射
【Java面试题汇总】Java基础篇——String+集合+泛型+IO+异常+反射(2023版)
|
3月前
|
存储 安全 Java
Java集合类面试十七】、介绍一下ConcurrentHashMap是怎么实现的?
ConcurrentHashMap在JDK 1.7中通过分段锁实现线程安全,在JDK 1.8中则采用Node数组配合链表和红黑树,并使用Synchronized和CAS操作提高并发性能。
Java集合类面试十七】、介绍一下ConcurrentHashMap是怎么实现的?
|
3月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别?
该CSDN博客文章讨论了Map和Set的区别,但提供的内容摘要并未直接解释这两种集合类型的差异。通常,Map是一种键值对集合,提供通过键快速检索值的能力,而Set是一个不允许重复元素的集合。