algorithm-sorting-and-searching

Sorting And Searching

Group Anagrams

Write a method to sort an array ot strings so that all tne anagrnms are next to each other.

anagrams are words that have the 相同的字符 but in 不同的顺序.


1
2
3
4
5
6
7
8
9
10
11
12
13
class AnagramComparator implements Comparator<String> {
public String sortChars(String s) {
char[] content = s.toCharArray();
Arrays.sort(content);
return new String(content);
}

public int compare(String s1, String s2) {
return sortChars(s1).compareTo(sortChars(s2));
}
}

Arrays.sort(array, new AnagramComparator());

This algorithm will take O(n log(n)) time.

Sort Big File

Imagine you have a 20 GB file with one string per line. Explain how you would sort the file.

We’ll divide the file into chunks, which are x megabytes each, where x is the amount of memory we have available. Each chunk is sorted separately and then saved back to the file system.

Once all the chunks are sorted, we merge the chunks, one by one. At the end, we have a fully sorted file. This algorithm is known as external sort.

Missing Int

Given an input file with four billion non-negative integers, provide an algorithm to generate an integer that is not contained in the file. Assume you have 1 GB of memory available for this task.

FOLLOW UP

What if you have only 10 MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.

  • 使用 BitVector

JDK 1.8 - Arrays.sort

  • 当元素数量小于 47 个的时候,使用 InsertionSort
  • 当元素数量小于 286 个的时候,使用 DualPivotQuickSort

查找重复数字

限制: 只有 4KB 内存,N 最大 32000

  • 4KB = 4 * 2^10 * 8bit 位 > 32000
  • new BitSet(32000)

推荐文章