資料結構面試題與答案
資料結構面試的時候我們需要面試題，大家可以看看下面的資料結構面試題與答案哦！
資料結構面試題與答案
1、給出一個函式來輸出一個字串的所有排列。
ANSWER 簡單的回溯就可以實現了。當然在排列的產生也有很多種演算法，去看看組合數學，
還有逆序生成排列和一些不需要遞迴生成排列的方法。
印象中Knuth 的第一卷裡面深入講了排列的生成。這些演算法的理解需要一定的數學功底，也需要一定的靈感，有興趣最好看看。
ANSWER:
Have done this.
2、題目：設計一個類，我們只能生成該類的一個例項。
分析：只能生成一個例項的類是實現了Singleton 模式的型別。
ANSWER
I’m not good at multithread programming... But if we set a lazy initialization, the “if” condition could be interrupted thus multiple constructor could be called, so we must add synchronized to the if judgements, which is a loss of efficiency. Putting it to the static initialization will guarantee that the constructor only be executed once by the java class loader.
public class Singleton {
private static Singleton instance = new Singleton();
private synchronized Singleton() {
}
public Singleton getInstance() {
return instance();
}
}
This may not be correct. I’m quite bad at this...
3、題目：實現函式double Power(double base, int exponent)，求base 的exponent 次方。
不需要考慮溢位。
分析：這是一道看起來很簡單的問題。可能有不少的人在看到題目後30 秒寫出如下的程式碼：
double Power(double base, int exponent)
{
double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result *= base;
return result;
}
ANSWER
…
double power(double base, int exp) {
if (exp == 1) return base;
double half = power(base, exp >> 1);
return (((exp & 1) == 1) ? base : 1.0) half half;
}
4、輸入一個字串，輸出該字串中對稱的子字串的最大長度。比如輸入字串“google”，由於該字串裡最長的對稱子字串是“goog”，因此輸出4。
分析：可能很多人都寫過判斷一個字串是不是對稱的函式，這個題目可以看成是該函式的
加強版。
ANSWER
Build a suffix tree of x and inverse(x), the longest anagram is naturally found.
Suffix tree can be built in O(n) time so this is a linear time solution.
74.陣列中超過出現次數超過一半的數字
題目：陣列中有一個數字出現的`次數超過了陣列長度的一半，找出這個數字。
分析：這是一道廣為流傳的面試題，包括百度、微軟和Google 在內的多家公司都
曾經採用過這個題目。要幾十分鐘的時間裡很好地解答這道題，
除了較好的程式設計能力之外，還需要較快的反應和較強的邏輯思維能力。
ANSWER
Delete every two different digits. The last one that left is the one.
int getMajor(int a[], int n) {
int x, cnt=0;
for (int i=0; i<n; i++) {
if (cnt == 0) {
x = a[i]; cnt++;
} else if (a[i]==x) {
cnt ++;
} else {
cnt --;
}
}
return x;
}