实习与工作

摩根士丹利宣讲会

jxtxzzw · 3月14日 · 2019年 · · 80次已读

今天晚上参加了摩根士丹利的宣讲会,结束以后有一个快速的现场笔试,3 道编程题。我觉得还是有点难度的,如果想要优化的话。当然 WillowTY 说都是傻*题。

这张图是笔试结束的时候我偷拍的,最后一问没有想明白,所以想要再想一想。

第 1 题没什么好说的,就是看两个单词用的字母的个数是不是一样的。

由于只有 26 个字母,所以开一个数组,统计 word1word2 中每个单词出现的次数,看次数是不是相等。

对于 word1,做 count++,对于 word2,做 count--,最后只要所有的 count 都为 0,那就是 Anagram,任意一个 count 不是 0,就不是 Anagram

boolean isAnagram(String word1, String word2) {
    int[] count = new int[26];
    for (int i = 0; i < word1.length(); i++) {
        int index = word1.charAt(i) - 'a';
        count[i]++;
    }
    for (int i = 0; i < word2.length(); i++) {
        int index = word2.charAt(i) - 'a';
        count[i]--;
    }
    for (int i = 0; i < count.length; i++) {
        if (count[i] != 0) {
            return false;
        }
    }
    return true;
}

第 2 题就是遍历 dictionary,对于某一个 item,如果和 word 互为 Anagram,那么就返回这个单词。

由于可以使用第 1 问的函数,那事情就很简单了。

String findAnagram(String word, List<String> dictionary) {
    for (String s : dictionary) {
        if (isAnagram(s, word)) {
            return s;
        }
    }
    return null;
}

最关键的是第 3 题,题目也明确说了,简单的做法是,分别遍历 wordsdictionary,每一次都调用第 2 问的函数来计算,只是这样效率太低了。

由于我前 2 问陷入了思维盲区,所以这一问没有一下子想到最优的方案。

在继续之前,先说一下前两问还有什么做法。

有一种是 WillowTY 跟我说的。

他的做法是,将 word1word2 的每一位按字典序排序,例如 bbdas 排序后就变成 abbds。那么,显然,如果 word1word2 互为 Anagram,显然他们每一位字符重新排序后形成的单词应该是一样的。

由此,可以得到第 1 问的伪代码是:

boolean isAnagram(String word1, String word2) {
    char[] c1 = word1.toCharArray();
    char[] c2 = word2.toCharArray();
    Arrays.sort(c1);
    Arrays.sort(c2);
    String s1 = new String(c1);
    String s2 = new String(c2);
    return s1.equals(s2);
}

我们假设每个单词的平均长度为 $a$,那么,这样的复杂度就是 $O(a \log a)$。

而我之前的做法的复杂度是 $O(a)$。

第 2 问,如果在这种排序的思路下,还是对 dictionary 的每一个单词做内部排序,包括 word

List<String> newDictionary = new List<>();
for (String s : dictionary) {
    char[] c = s.toCharArray();
    Arrays.sort(c);
    newDictionary.add(new String(c));
}
// word 排序类似

之后对 newDictionary 排序,还是按照字典序。

Collections.sort(newDictionary);

这样一来,问题就变成了,找 newWord 是不是在 newDictionary 里面。

for (String s : newDictionary)
    if (s.euqals(newWord))
        // return

当然,由于这里的 s 已经是排序后的了,所以势必还要加一个 Map,完成排序前后的映射。

for (String s : dictionary) {
    // ...
    String t = new String(c);
    map.put(t, s);
    newDictionary.add(t);
}
for (String t : newDictionary)
    if (t.euqals(newWord))
        return map.get(t);

运用到的数据结构复杂了,但是可以降低复杂度。

假设 dictionary 长度为 $m$,则对字典排序 $O(m \log m)$,之前说每个单词排序的时间是 $O(a \log a)$,所以,所有的排序时间是 $O(m a \log a + m \log m)$,最后查找的时间是线性的, $O(m)$。

比较两个字符串的复杂度不是 O(1) ,所以排序复杂度不是 O(mlogm)


2019-03-16 经 zerol 指出后修订

甚至,由于字典已经有序,甚至可以用二分查找进一步加速。不过由于排序花的时间太长了,所以只能优化常数了。

回过来看我之前的方法,$O(ma)$。

这时候再考虑第 3 问,我当时笔试的时候能想到的只有 2 个优化。

第一,不是取出一个 s in words 去看是不是有 t in dictionary 满足 t.equals(s),而是取出一个 t in dictionary 去看是不是有 s in words 满足 t.equals(s),在这个过程中,维护一个可以被删除的 words 列表,一旦某一个位置填充了,就立刻将这个 wordwords 移除,这样就相当于没有被找到的单词会越来越少,仅仅优化了常数,复杂度不变。

第二,对字典和原始列表排序,有一个显然的事实是如果两个单词互为 Anagram,他们的长度一定相等,所以只需要比较长度相等的部分就可以了。

这里需要自定义一个 Comparator,在调用 Collections.sort() 的时候传入这个 new Comparator() {},比较的标准是,谁更短,谁排前面。

遍历字典的时候维护一个 leftPointerrightPointer,分别表示长度为 $x$ 的单词是在字典的哪个区域。

也是常数优化。

按照 Willow 的方法,一劳永逸地对 wordsdictionary 按照第 2 问的方法排序。

排序之前用 HashMap 记录原始单词和调换过顺序的单词之间的一一映射。

对字典排序 $O(m \log m)$,之前说每个单词排序的时间是 $O(a \log a)$,所以,所有的排序时间是 $O(m a \log a + m \log m)$,类似地,假设 words 的长度是 $n$,那么,对单词表的排序时间是 $O(n a \log a + n \log n)​$。

然后遍历 words,去找是不是在字典中出现,如果出现,则返回其 Map 的值。

除去排序用的时间,查找的时间只是遍历 words 的时间,如果查找字典用的也是遍历,那么查找部分就是平方的复杂度,如果用的是有序列表的二分查找或者树形结构的查找,那么总的查找复杂度是线性的。

加上排序用的时间,其实能接受。

后来我在写这篇文章的时候,想到,其实 WillowTY 的这个方法有一定的小瑕疵。

假设字典中有 doggod,由于他们排序以后都是 dgo,所以,当 dgo 去反向查 Map 的时候,输出的就是只有一个,而不会有另一个。当然题目本来就只要求输出一个,所以这个不算是 BUG。

但是当 WillowTY 说出哈希的时候,我突然有了一个大胆想法。

假设存在一个哈希函数 $f$,计算字符串的哈希值,$f$ 使得两个字符串的哈希值相等,当且仅当这两个字符串中出现的每个字母的数量相同的时候,$f$ 的值相等。例如,$f(dog)=f(god)=f(ogd)$。

显然这样一个函数存在,因为有一个 a[26],对这个数组哈希

2019-03-16 经 zerol 指出后修订

假设存在这样一个函数,那么,只需要重写 equals() 方法为 return hashcode(this) == hashcode(that) 即可,即,只要两个单词的每个字母出现次数一样,那么他们的 hashcode()euqals() 是一样的。

于是,只需要:

for (String word : words) {
    if (dictionary.contains(word))
        // do something
}

并且,假设我们把字典做成了一个 K-V 键值对,键是字典中的每一个元素,值是键本身,那么,其实上面的代码就被简化成:

for (String word : words) {
    return dictionaryMap.get(word);
}

这里的含义就是,如果 dictionaryMapword,由于重写了 hashcode()equals(),所以说明字典中有一个单词和给定单词有着相同的字母数量,即互为 Anagram,所以直接返回 dictionaryMap.get(word),而如果没有匹配的,那么 get() 本来返回的就是 null

当然,这样一个哈希函数可能很难找,这是硬伤,决定了这个方法能不能用。

假设存在的话,就是这么简单。

况且,即便找到,也不建议重写 String 类的 hashcode()euqals(),风险有点大。

仓促之间,感觉这次笔试非常不尽如人意,匆匆忙忙想好,然后写下来,很多细节都没有考虑到,所以有预感要凉凉。

这 3 道题肯定还有更好的方法,欢迎你留言与我探讨。

1 条回应
    luxuantao 2019-3-15 · 8:49
    Chrome 72.0.3626.121 Windows 10

    放心,有我给你垫底