情况
我的任务是在一次现场编码面试中实现一个字符串变位问题。问题是给定两个字符串，为方法boolean isAnagram(String str1, String str2)编码逻辑。
解决方案
我提出了以下解决方案(mergeSort是我自己的一个实现，containsChar使用的是二进制搜索，这也是我自己的实现)
public static boolean isAnagram(String value, String valueToCompare) {
String temp = valueToCompare.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
String t = value.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
if (t.length() == temp.length()) {
char[] c = t.toCharArray();
char[] orderedChars = MergeSort.mergeSort(temp.toCharArray());
for (int i = 0; i < orderedChars.length ; i++) {
if (!containsChar(orderedChars, c[i], 0, orderedChars.length - 1))
return false;
}
return true;
}
return false;
}
解决方案的效率是多余的，我更关心的是后台发生了什么。
问题
当我提出解决方案时，面试官问我，假设我有一台内存非常低的计算机，并且我想运行算法10000次，大小在1000到10000之间的随机字符串，你的代码会发生什么？。我不知道该回答什么，所以他告诉我，我会得到一个OutOfMemoryError异常。我知道(或者我至少认为)由于算法的效率，我会得到这样的例外。所以我的问题是：
- 为什么抛出OutOfMemoryError异常
- 如果我调用该方法1000次，是不是因为完成一次调用需要很长时间才能引发这样的异常
- 当我调用该方法x次时，后台发生了什么
让我们明确这一点。
- 面试官问了你一个假设性的问题
- 面试官没有正确说明条件(稍后会详细说明)
- 面试官断言将会发生一些事情。。。没有证据，也没有办法验证这个断言
假设我有一台内存明显不足的计算机。。。所以他告诉我，我会得到一个
OutOfMemoryError异常。
我认为面试官可能错了。
首先，您的代码没有明显的内存泄漏。这不是我能看到的，也不是其他评论者能看到的。
您的解决方案代码在每次调用中都会生成一些临时对象。我最多可以计算6个临时字符串和1或2个临时数组，以及一些库方法创建的其他可能的临时对象。你可能会减少是否值得花费开发人员的时间进行优化。
但是临时对象本身不应该导致OOME。现代Oracle/OpenJDK垃圾收集器非常擅长收集短期对象。
除了几种病理情况：
场景#1
假设您已经处于内存不足的边缘。例如，假设在启动1000个方法调用之前，在运行完整的GC之后，您只有少量的可用(eden)空间。
为了完成任务，它将生成1000次x 10个对象x 10000字节的临时空间。这大约是100MB。
-
如果你有10MB的伊甸园空间可用，这意味着你需要在短时间内收集大约10个伊甸园空间。
-
如果你有1MB的伊甸园空间可用，这意味着你需要在短时间内收集大约100个伊甸园空间。
10个伊甸园空间背靠背收集可能足以导致OOME"超出开销限制"。有了100，可能性就大得多。
但最重要的是，如果您的运行距离满堆足够近，任何分配对象的代码都可能是最后一根稻草。真正的问题是您的堆太小，无法完成任务。。。或者其他正在创建/保留太多长期对象。
场景#2
假设您的应用程序有严格的延迟要求。为了实现这一点，您将JVM配置为使用低暂停收集器，并为收集器设置一些非常激进的延迟目标。而且你也没有太多的记忆力。
现在，如果您的应用程序生成的垃圾太多太快，那么低暂停的收集器可能无法跟上。如果您将其推到极限之外，GC将返回到进行"停止世界"收集以尝试恢复。你可能会得到OOME。。。尽管我对此表示怀疑。但你肯定无法实现延迟目标。
但最重要的是，如果你有一个有这样需求的应用程序，那么你必须在有足够资源的机器上运行它；即足够的备用存储器、足够的(并行)GC能够保持的核。您可能会将isAnagram方法设计为在创建临时对象的方式上更加小心。。。但你会提前知道你需要这样做。
回顾
回到面试官提出的问题(如您转述)：
-
访问者没有说明有多少可用堆空间，所以我们不能说场景#1是否适用。但如果真的发生了，真正的问题可能是堆大小和问题之间的不匹配，或者是应用程序中其他地方的内存泄漏。
-
面试官没有提到延迟限制。即使它们存在，第一步也是指定硬件并使用适当的(即现实的)JVM GC设置。
-
如果你确实遇到了问题(OOME，错过了延迟目标)，然后你开始寻找解决方案。使用内存分析来识别问题的性质(例如，它是由临时对象、长期对象、内存泄漏等引起的)，并追踪问题对象的来源。
不要只是假设的特定代码位会导致OOME。。。就像面试官正在做的那样。过早优化是个坏主意。
让它发挥作用。让它正确。快一点
现在考虑性能或内存使用情况还为时过早。您的方法返回假阳性，因为它只检查第一个单词中的每个字母是否包含在第二个单词中。
通过这种检查，'aaa'和'abc'被认为是变位词，而不是'abc'和'aaa'。
这里有一个完整的类来测试你的代码：
import java.util.Arrays;
public class AnagramTest
{
public static void main(String[] args) {
String[][] anagrams = {
{ "abc", "cba" },
{ "ABC", "CAB" },
{ "Clint Eastwood", "Old West action" }
};
for (String[] words : anagrams) {
if (isAnagram(words[0], words[1])) {
System.out.println(".");
} else {
System.out.println(
"OH NO! '" + words[0] + "' and '" + words[1] + "' are anagrams but isAnagram returned false.");
}
}
String[][] notAnagrams = {
{ "hello", "world" },
{ "aabb", "aab" },
{ "abc", "aaa" },
{ "aaa", "abc" },
{ "aab", "bba" },
{ "aab", "bba" },
};
for (String[] words : notAnagrams) {
if (isAnagram(words[0], words[1])) {
System.out.println(
"OH NO! '" + words[0] + "' and '" + words[1] + "' are not anagrams but isAnagram returned true.");
} else {
System.out.println(".");
}
}
}
public static boolean isAnagram(String value, String valueToCompare) {
String temp = valueToCompare.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
String t = value.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
if (t.length() == temp.length()) {
char[] c = t.toCharArray();
char[] orderedChars = mergeSort(temp.toCharArray());
for (int i = 0; i < orderedChars.length; i++) {
if (!containsChar(orderedChars, c[i], 0, orderedChars.length - 1))
return false;
}
return true;
}
return false;
}
// Dummy method. Warning: sorts chars in place.
private static char[] mergeSort(char[] chars) {
Arrays.sort(chars);
return chars;
}
// replace with your binary search if you want.
private static boolean containsChar(char[] orderedChars, char c, int m, int n) {
for (int i = m; i <= n; i++) {
if (orderedChars[i] == c) {
return true;
}
}
return false;
}
}
它输出：
.
.
.
.
.
.
OH NO! 'aaa' and 'abc' are not anagrams but isAnagram returned true.
OH NO! 'aab' and 'bba' are not anagrams but isAnagram returned true.
OH NO! 'aab' and 'bba' are not anagrams but isAnagram returned true.
下面是一个应该通过所有测试的示例实现：
public static boolean isAnagram(String word1, String word2) {
word1 = word1.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
word2 = word2.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
return Arrays.equals(mergeSort(word1.toCharArray()), mergeSort(word2.toCharArray()));
}
我的最佳猜测：
- 您的MergeSort有问题，您没有向我们展示
- 它并不是发生在每一个输入上，所以面试官希望你用随机输入运行它10000次，以使它以高概率发生
- 这个问题可能会导致合并排序重复出现得太深。也许是O(N)而不是O(log N)深度，或者可能是无限递归；以及
- 合并排序不必要地在每个递归调用中分配一个新的临时数组。由于它们太多，这会导致内存不足错误