[分享][請益] 廻文數/remove_dump_memory / MaxLevel

[tropical72 (藍影)]

最近拿到 C/C++ 面試卷，比較有印象的是其中三題，
由於時間有限，沒能把所有題目記下來，且為原文 (所以我的敘述可能有點差異)，
也僅憑印象一起來探討。

1. 迴文數

迴文數的定義版上很多人都知道了 < ACM 基礎題 >，
但這題隱喻中加了幾個限制：

a. effect
b. unsigned IsPalindrome(unsigned num);
c. 不可調用任何 C/C++ 函式庫完成

所以和 ACM 不同的是不可以用 char* 來存。

當下我想到的作法是二種，一種是用 while(num) {num/=10;} 技巧，每個位數塞到

const int MAX=20;
int dig[MAX];

裡面去，同時紀錄使用了 used_dig 位數，
問題便轉成了對一 array/string 判斷回文數 <最後是用這解法>。

另一想法是直接找 min pwr, st pwr>=num, 之後再做一個 rst 為 num 的 inverse，
最後再 return rst==num <直覺較麻煩，所以沒用這個>，
請教各版友針對此三限制之 Palindrome number 有何想法？

2. 移除陣列裡重覆之元素

unsigned remove_dumped_memory(unsigned *array, unsigned nItem);

假設一 array 已經過遞增排序, int array[] = {1,1,2,2,2,3,5,8,8,9}，
由於元素有 10 個，所以在傳入 nItem 的時候會先確定是 10 << 也就是元素個數 >>。

但題意是，經過 remove_dumped_memory 後，能把 array 重覆的拿掉，
然後傳回不重覆的元素個數，以上述為例，最後 array[] = {1,2,3,5,8,9};
傳回6  (如果問我 array[6]~array[9] 哪去了？我只能說從題意看不出來)。

同樣的題目裡有個 keyword : effective

直覺掃一遍即可，當時粗寫大概是

unsigned remove_dumped_memory(unsigned *array, unsigned nItem)
{
    int cnt=0, last_position=0;
    for(i=0; i<nItem-1; ++i){
        if(array[i]!=array[i+1]) {
            array[last_position++]=array[i];
            ++cnt;
        }
    }
    return cnt;
}

但還有另一份試題沒寫，沒再花時間磨這個。

3. MaxLevel

這個資料結構的東西我很亂，要求要 C 寫。題意是要求 binary tree deep level
( 如果我沒意會錯的話 ... )

typedef struct node{
    int value;
    struct node* left;
    struct node* right;
}mynode;

int MaxLevel(struct node* p);

因為不熟，時間也來不急，就亂寫了。大概是寫得像

int max(int a, int b) { return (a>b)? a : b; }

int MaxLevel(struct node* p) {
    if(p==NULL) return 0;
    else return 1+max(MaxLevel(p->left), MaxLevel(p->right));
}

最後這題反而被抓出來電 Orz

--
世界上有種，
將 不可能 轉換為 無限可能 的強大力量，
我稱它為 - 信念。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.165.40
※ tropical72:轉錄至看板 C_and_CPP                                 02/04 17:47
※ 編輯: tropical72      來自: 123.195.165.40       (02/04 17:51)
→ firejox:回文數就邊除編建inverse number就好了呀~
→ tkcn:第三題這樣寫有啥問題?  不過 function name 叫 depth 就夠了
→ suhorng:第二題a[6]...a[9]還在但是不重要不用管他
→ tropical72:我其實想知道是怎麼死的,最後只有提 "你這題好像沒解
→ tropical72:出來",所以想說是不是我解錯了 Orz
→ tropical72:前兩句是針對第三題。
→ tropical72:<<在想是不是我額外寫了一份 int max(int,int); 關係>>
推 DJWS:1其實不用開陣列  原數不斷 %10 /10  另一數不斷 +餘數 *10
→ DJWS:最後比較兩數是不是完全相等就可以了
→ DJWS:                                (順序寫反了)  *10 +餘數
→ DJWS:2就由小到大掃過陣列  遇到不一樣的數字就存起來
→ DJWS:一樣也不需要開新的陣列
→ DJWS:3的話，沒有額外資訊就只能DFS/BFS了
→ DJWS:或者寫成遞迴的模樣  答案 = max(左子樹高度,右子樹高度) + 1
推 DJWS:另外2有一個issue: 如果不開新陣列，就會浪費a[6]~a[9]記憶體
推 DJWS:to二樓: 也許原po的第三題寫得最好　面試官想要深入討論 XD
→ tropical72:謝謝各位意見,大概知道哪些地方沒做很好.感謝.
→ tropical72:oh,面試官是直接跟我說,"這題好像沒解出來",所以我想是
→ tropical72:不是我解得有問題 <如果誤會題意的話就另當別論便是>
推 DJWS:我在想是不是因為沒有呼叫 function 把 tree root 當作參數？
→ DJWS:使用者肯定不知道tree root在哪　所以要幫使用者處理到好
→ DJWS:可能要整個包成一個函數　裡面要呼叫你寫的maxheight(root)