數據結構面試的時候我們需要面試題，大家可以看看下面的數據結構面試題與答案哦！
數據結構面試題與答案
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;
}
- 相關推薦