數據結構面試題與答案
數據結構面試的時(shí)候我們需要面試題，大家可以看看下面的數據結構面試題與答案哦！
數據結構面試題與答案
1、給出一個(gè)函數來(lái)輸出一個(gè)字符串的所有排列。
ANSWER 簡(jiǎn)單的回溯就可以實(shí)現了。當然在排列的產(chǎn)生也有很多種算法，去看看組合數學(xué)，
還有逆序生成排列和一些不需要遞歸生成排列的方法。
印象中Knuth 的第一卷里面深入講了排列的生成。這些算法的理解需要一定的數學(xué)功底，也需要一定的.靈感，有興趣最好看看。
ANSWER:
Have done this.
2、題目：設計一個(gè)類(lèi)，我們只能生成該類(lèi)的一個(gè)實(shí)例。
分析：只能生成一個(gè)實(shí)例的類(lèi)是實(shí)現了Singleton 模式的類(lèi)型。
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、題目：實(shí)現函數double Power(double base, int exponent)，求base 的exponent 次方。
不需要考慮溢出。
分析：這是一道看起來(lái)很簡(jiǎn)單的問(wèn)題�？赡苡胁簧俚娜嗽诳吹筋}目后30 秒寫(xiě)出如下的代碼：
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、輸入一個(gè)字符串，輸出該字符串中對稱(chēng)的子字符串的最大長(cháng)度。比如輸入字符串“google”，由于該字符串里最長(cháng)的對稱(chēng)子字符串是“goog”，因此輸出4。
分析：可能很多人都寫(xiě)過(guò)判斷一個(gè)字符串是不是對稱(chēng)的函數，這個(gè)題目可以看成是該函數的
加強版。
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.數組中超過(guò)出現次數超過(guò)一半的數字
題目：數組中有一個(gè)數字出現的次數超過(guò)了數組長(cháng)度的一半，找出這個(gè)數字。
分析：這是一道廣為流傳的面試題，包括百度、微軟和Google 在內的多家公司都
曾經(jīng)采用過(guò)這個(gè)題目。要幾十分鐘的時(shí)間里很好地解答這道題，
除了較好的編程能力之外，還需要較快的反應和較強的邏輯思維能力。
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;
}
【數據結構面試題與答案】相關(guān)文章：
數據結構試題答案04-26
數據結構考試題及答案04-26
android面試題及答案03-11
面試題目及答案12-29
會(huì )計面試題及答案04-12
IBM面試題及答案03-14
java面試題及答案03-14
交警面試題及答案03-24
經(jīng)典面試題及答案分析08-13