作者：半路、出家

鏈接：nowcoder.com/discuss/19來源：牛客網

今天下午給了結果，結果是筆試——不合適。

不合適 是不合格還是其他的什麼原因嗎？

題目類型

  • 18道選擇題（多選）37分。主要涉及數據機構、操作系統、計算機網路、少許數學概率和智力題
  • 5道填空題 15分。主要涉及演算法和數學智力題
  • 2道簡單的編程題 48分。

選擇題

以下是我還記得的題目：

1.給定樹的前序遍歷和中序遍歷，選擇樹的後序遍歷

2.給定一個入棧序列 ，判斷以下哪一個是合法的出棧序列

3.從四個選項中選擇穩定的、時間複雜度是O(NlogN)的排序演算法

4.一個有序數組，從四個選項中選擇查找演算法時間複雜度在O(logN) 以下的選項 （為了保守，沒選二分查找）

5.公交站每一分鐘出現公交車的概率是5%，15分鐘之後仍然沒有公交車的概率是多少

6.超大的一個稀疏hash表，選擇2個好的解決衝突的辦法。

7.操作系統的，給定5個進程，3類資源，給定T0時5個進程佔有的資源和3類資源的總數。從四個選項中選擇安全的進程調度序列（一個進程執行完，下一個進程才執行）

8.操作系統的，一個進程在地址p寫入一個字元串，該進程派送了一個子進程，然後問子進程訪問字元串啥的。

9.操作系統的，一個進程以讀寫的方式打開一個文件，該進程fork了一個子進程，然後子進程對該文件的訪問許可權是如何的

10.計算機網路的，一直沒時間學習計算機網路，所以隨便選了一個。

11.計算機網路的，同上。

12.一個智力題，給定一個數列0，3，8，15，24，15，8，3，0，3，8，... ,問這個數列的第1024個數是多少。

13.考察C語言中的宏定義在執行時的替換.#define MOD(X,Y) X%Y 然後在主函數中 求MOD(X,Y+2) * 2

14.考察C語言中指針的移動。 一個字元串char s[] = 「abc def」; char *p=s; print("%c",*p+4);結果是什麼。

15.64為系統，char **a[3][4],佔多少位元組。

其他不太記得了。

填空題

1) 一個縣城3個城市A,B,C，分別占城市面積的20%， 32%，48%。然後給出A,B,C房子，工廠，都市的面積占自身的面積的百分比，求A工廠佔全縣城工廠面積的百分比。（送分題）

2) 給定一個3*4的方格如下：

從A走到B，一下走一個單位（小方格的長度），只能向下或者右走。有多少條路徑。（動態規劃）

3) 1234567的987654321次方之後，個位數是多少？

4) 一個概率題，感覺是用狀態轉移做，我不會。

5) （感覺這題沒這麼簡單）三扇門，一扇門後面有豪車，A同學選擇了一扇門還沒有打開，主持人是知道豪車位置的，然後主持人把剩下兩扇的中一個不存在豪車的門打開，然後A同學也確認了。問如果A重新選擇，A選中豪車的概率是多少？ 我頭腦簡單，我覺得是0.5.

編程題

1.給定棧的輸入I， 和輸出O，判斷這個出棧序列是否合法。

題目的輸入是T， I， O， T 表示測試用例的個數，意思就是你得用一個循環測試T組 I、O。

演算法

模擬棧就可以。

1.初始化一個棧stack，用來裝入棧序列，初始化一個j=0,用來指向出棧序列的第一個字元。

2.順序遍歷入棧序列，遍歷一個，就入棧一個元素到stack。

每入棧一個元素到stack，就作如下檢查：

棧不空且棧頂元素與出棧序列元素相等，把stack中的元素出棧，並且j自增1。

如果棧空或出棧序列與stack棧頂元素不等,就繼續遍歷入棧序列的下一個元素（即進入2）。

以下是代碼：

import java.util.*;public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
for(int i=0; i<T;i++) {
String I = input.next();
String O = input.next();
if(helper(I, O)== true)
System.out.println(Y);
else
System.out.println(N);
}
}
private static boolean helper(String I, String O) {
Stack<Character> stack = new Stack<>();
int j = 0;
for(char c: I.toCharArray()) {
stack.push(c);
while(!stack.isEmpty() && O.charAt(j)==stack.peek()) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}

2.一個24進位數轉換為10進位數。

同上，題目輸出是T和M，T 表示測試用例得個數。M是一個24進位的字元串。

演算法

用歐幾里德演算法就可以，就是a?x^3+b?x^2+c?x+d=((a?x+b)?x)+c)?x+d a*x^3+b*x^2+c*x+d

但是我的Java代碼 只通過了90%的用例，提示是時間按複雜度過大，不知道是Java語言的原因還是演算法有改進的地方。

以下是代碼：

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
for(int i=0; i<T;i++) {
String M = input.next();
int N = helper(M);
System.out.println(N);
}
}
private static int helper(String s) {
int answer = 0;
int size = s.length();
for(int i=0; i< size; i++) {
char c = s.charAt(i);
if(c>=0 && c<=9)
answer = answer *24 +(c-0);
else
answer = answer * 24 + (c-a+10);
}
return answer;
}
}

與作者交流：nowcoder.com/discuss/19

更多筆經面經：nowcoder.com/discuss?


推薦閱讀：
相关文章