程序员日志

Java 面试题 - Arrays and Strings

Java容器类库图


HashMap和Hashtable

  • HashMap不是线程安全的，由于非线程安全，效率上可能高于Hashtable；
  • Hastmap是Java 1.2引进的Map interface的一个实现；其中键和值都是对象，可以包含重复值。HashMap允许null key和null value，而hashtable不允许;
  • 为一个HashMap提供外同步。其中一个方法就是利用Collections类的静态的synchronizedMap()，它创建一个线程安全的Map对象，并返回一个封装的对象。这个对象的方法可以让你同步访问潜在的HashMap;
  • HashMap去掉了HashTable的contains方法，但加上了containsValue()和containsKey()方法;
  • HashTable是线程安全的一个Collection，继承自陈旧的Dictionary类；

Set集合

  • 可以实例化的类为：CopyOnWriteArraySet(线程安全，使用CopyOnWriteArrayList为容器)，HashSet，LinkedHashSet，TreeSet；
  • TreeSet 和 HashSet 把 set 中的元素作为 Map 中的“键”，从而保持元素的唯一性。
  • 加入在 Set 中存放的是自定义的类实例的时候，这时候要重新定义 hashcode 和 equal 方法，用自己的关键字段来重写，因为当使用 HashSet 时，hashCode() 方法就会得到调用，判断已经存储在集合中的对象的 hashcode 值是否与增加的对象的 hashcode 值一致；如果不一致，直接加进去；如果一致，再进行 equals() 方法的比较，equals() 方法如果返回true，表示对象已经加进去了，就不会再增加新的对象，否则加进去。
  • TreeSet使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。
  • Set中实现元素互异的各种方法差异很大，大致可以分为三种：使用equals；使用hashCode；使用compareTo。
  • 通常都会选择一个 HashSet，因为它专门对快速查找进行了优化。

ArrayList、LinkedList和Vector

  • ArrayList和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，但是插入数据要涉及到数组元素移动等操作，所以索引数据快而插入数据慢;
  • ArrayList，长于随机访问元素，但在中间插入和移除元素时较慢；
  • ArrayList和Vector的访问性能是 O(1); 尽管扩展长度时将花费 O(n) 的时间, 但由于很少发生，通常情况下摊销(amortize)后的性能仍是 O(1)；
  • Vector由于使用了synchronized方法，所以性能上比ArrayList要差；
  • Vector缺省情况下自动增长原来一倍的数组长度，而ArrayList是原来的50% (但CareerUp 150这本书则是说Double)；
  • LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！
  • LinkedList，较之ArrayList在中间插入和移除元素时代价低，但随机访问方面相对较慢，不过它的特性集较ArrayList更大；
  • ListIterator，更强大的 Iterator 子类型，可以创建一个一开始就指向列表索引为 n 的元素处的 ListIterator。

StringBuffer 和 StringBuilder

《Java编程思想》:
其实，每当把String对象作为方法的参数时，都会复制一份引用，而该引用所指的对象其实一直待在单一的物理位置上，从未动过；
对一个方法而言，参数是为该方法提供信息的，而不是想被该方法改变；
如果知道最终字符串大概有多长，那预先指定StringBuilder的大小可以避免多次重新分配缓冲；
StringBuffer是线程安全的，因此开销较大；

Question: What is the running time of this code?

1
2
3
4
5
public String makeSentence(String[] words) {
  StringBuffer sentence = new StringBuffer();
  for (String w : words) sentence.append(w);
  return sentence.toString();
}
  • Answer: O(n^2), where n is the number of letters in sentence.
  • Here’s why: each time you append a string to sentence, you create a copy of sentence and run through all the letters in sentence to copy them over If you have to iterate through up to n characters each time in the loop.

面试题补充

1、Implement an algorithm to determine if a string has all unique characters What if you can not use additional data structures?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// first solution:
public static boolean isUniqueChars2(String str) {
  boolean[] char_set = new boolean[256];
  for (int i = 0; i < str.length(); i++) {
    int val = str.charAt(i);
    if (char_set[val]) return false;
    char_set[val] = true;
  }
  return true;
}
// second:
public static boolean isUniqueChars(String str) {
  int checker = 0;
  for (int i = 0; i < str.length(); ++i) {
    int val = str.charAt(i) - ‘a’;
    if ((checker & (1 << val)) > 0) return false;
    checker |= (1 << val);
  }
  return true;
}
// third:
// Check every char of the string with every other char of the string for duplicate occurrences. 
// This will take O(n^2) time and no space.

2、Write code to reverse a C-Style String.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void reverse(char *str) {
  char * end = str;
  char tmp;
  if (str) {
    while (*end) {
      ++end;
    }
    --end;
    while (str < end) {
      tmp = *str;
      *str++ = *end;
      *end-- = tmp;
    }
  }
}

3、Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine, An extra copy of the array is not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// first solution:
public static void removeDuplicates(char[] str) {
  if (null == str) return;
  int len = str.length;
  if (len < 2) return;
  int tail = 1;
  for (int i = 1; i < len; ++i) {
    int j;
    for (j = 0; j < tail; ++j) {
      if (str[i] == str[j]) break;
    }
    if (j == tail) {
      str[tail] = str[i];
      ++tail;
    }
  }
  str[tail] = 0;
}
// second:
public static void removeDuplicatesEff(char[] str) {
  if (str == null) return;
  int len = str.length;
  if (len < 2) return;
  boolean[] hit = new boolean[256];
  for (int i = 0; i < 256; ++i) {
    hit[i] = false;
  }
  hit[str[0]] = true;
	int tail = 1;
  for (int i = 1; i < len; ++i) {
    if (!hit[str[i]]) {
      str[tail] = str[i];
      ++tail;
      hit[str[i]] = true;
    }
  }
  str[tail] = 0;
}

Test Cases:

  1. abcd;
  2. aaaa;
  3. null;
  4. aaabbb;
  5. abababa;

4、Write a method to decide if two strings are anagrams(回文) or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// first solution:
boolean anagram(String s, String t) {
  return sort(s) == sort(t);
}
// second
public static boolean anagram(String s, String t) {
  if (s.length() != t.length()) return false;
  int[] letters = new int[256];
  int num_unique_chars = 0;
  int num_completed_t = 0;
  char[] s_array = s.toCharArray();
  for (char c : s_array) { // count number of each char in s.
    if (letters[c] == 0) ++num_unique_chars;
    ++letters[c];
  }
  for (int i = 0; i < t.length(); ++i) {
    int c = (int) t.charAt(i);
    if (letters[c] == 0) { // Found more of char c in t than in s.
      return false;
    }
    --letters[c];
    if (letters[c] == 0) {
      ++num_completed_t;
      if (num_completed_t == num_unique_chars) { // it’s a match if t has been processed completely
        return i == t.length() - 1;
      }
    }
  }
  return false;
}

5、Write a method to replace all spaces in a string with ‘%20’ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void ReplaceFun(char[] str, int length) {
  int spaceCount = 0, newLength, i = 0;
  for (i = 0; i < length; i++) {
    if (str[i] == ‘ ‘) {
      spaceCount++;
    }
  }
  newLength = length + spaceCount * 2;
  str[newLength] = ‘\0’;
  for (i = length - 1; i >= 0; i--) {
    if (str[i] == ‘ ‘) {
      str[newLength - 1] = ‘0’;
      str[newLength - 2] = ‘2’;
      str[newLength - 3] = ‘%’;
      newLength = newLength - 3;
    } else {
      str[newLength - 1] = str[i];
      newLength = newLength - 1;
    }
  }
}

6、Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees Can you do this in place?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void rotate(int[][] matrix, int n) {
  for (int layer = 0; layer < n / 2; ++layer) {
    int first = layer;
    int last = n - 1 - layer;
    for(int i = first; i < last; ++i) {
      int offset = i - first;
      int top = matrix[first][i]; // save top
      matrix[first][i] = matrix[last-offset][first];      // left -> top
      matrix[last-offset][first] = matrix[last][last - offset]; // bottom -> left
      matrix[last][last - offset] = matrix[i][last]; 			// right -> bottom
      matrix[i][last] = top; 		// right <- saved top; top -> right
    }
  }
}

7、Assume you have a method isSubstring which checks if one word is a substring of another Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”)

1
2
3
4
5
6
7
8
9
10
public static boolean isRotation(String s1, String s2) {
    int len = s1.length();
    /* check that s1 and s2 are equal length and not empty */
    if (len == s2.length() && len > 0) { 
      /* concatenate s1 and s1 within new buffer */
      String s1s1 = s1 + s1;
      return isSubstring(s1s1, s2);
  }
  return false;
}

8、Given a circular linked list, implement an algorithm which returns node at the beginning of the loop

Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LinkedListNode FindBeginning(LinkedListNode head) {
  LinkedListNode n1 = head;
  LinkedListNode n2 = head; 
  while (n2.next != null) { 		// Find meeting point
    n1 = n1.next; 
    n2 = n2.next.next; 
    if (n1 == n2)  break; 
  }
  // Error check - there is no meeting point, and therefore no loop
  if (n2.next == null)  return null;
  /* Move n1 to Head. Keep n2 at Meeting Point.  Each are k steps from the Loop Start. 
	 * If they move at the same pace, they must meet at Loop Start. */
  n1 = head; 
  while (n1 != n2) { 
    n1 = n1.next; 
    n2 = n2.next; 
  }
  return n2; 		// Now n2 points to the start of the loop.
}

一些补充：
$ javap -c SampleClass # 反编译命令使用示例
《Java编程思想》:
无意识的递归，ArrayList.toString(), public String toString() { return “ InfiniteRecursion address: “ + this + “\n”; }， Object.toString();