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

[tropical72 (藍影)]

※ [本文轉錄自 Prob_Solve 看板 #1FBFuaqO ]

作者: tropical72 (藍影) 站內: Prob_Solve
標題: [分享][請益] 廻文數/remove_dump_memory / MaxLevel
時間: Sat Feb  4 17:45:04 2012


最近拿到 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

※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: tropical72 (123.195.165.40), 時間: 02/04/2012 17:47:22
※ 編輯: tropical72      來自: 123.195.165.40       (02/04 17:50)
→ diabloevagto:http://ideone.com/TGQtD 1-2的解法是這個意思嗎？
→ diabloevagto:我覺得1-2會比1-1好，1-1還要去判斷位數是基數還偶數
→ diabloevagto:1-2就很比較而已，感覺比較單純點
→ diabloevagto:我沒有用bool是想說c跟c++能通用
→ firejox:return num_2 == num;這樣就好了呀~~
→ tropical72:1-1應不用判斷奇偶問題,但1-2較佳應是真的。
→ diabloevagto:http://ideone.com/hQcw8  改這樣
→ diabloevagto:不判斷奇偶的話就全部跑過一遍了，假如不要全部跑過
→ diabloevagto:t大的意思是說for跑到lengh/2嗎？
→ firejox:拿兩根旗子 和拿一根旗子 都不需判斷奇偶阿~~
→ diabloevagto:抱歉...不太懂樓上的意思＝ ＝
→ firejox:兩根旗子(兩變數設頭尾) 一根旗子(一變數)
→ firejox:我比較喜歡用旗子(flag)來說
→ diabloevagto:但這樣不是就要全部跑過一遍...
→ tropical72:for(i=0,j=len-1;i>=j && a[i]==a[j]; ++i,--j);
→ tropical72:return i>=j;
→ diabloevagto:我想的比較不一樣
→ diabloevagto:for(i=0;i<len/2;i++) if(arr[i] != arr[len-i-1])
推 ALTandTAB:第二題的改進: http://ideone.com/5a81q
→ ALTandTAB:用二分法切不知道有沒有快一些
→ diabloevagto:樓上的發法感覺不錯說xd感覺會比較快說
推 ALTandTAB:發現有個地方寫錯了 更正後是: http://ideone.com/3Jj5d
→ ALTandTAB:不過worst case應該非常糟糕...
→ tropical72:!!A大的發文我突然想到 Fib 步進..感謝 !!
→ diabloevagto:a大的O(n)不是嗎？
→ tropical72:我覺得第二題部份會不會比較快實際是看資料而定,詳情看
→ diabloevagto:t大，search用goldren據說比fib快http://ppt.cc/Tdcd
→ tropical72:名則百題-搜尋篇,但若是面試卷的話,加點技巧"可能"不錯
→ tropical72:哈,先謝謝d大給的web.補一下,本身研究過一些特殊的魔術
→ tropical72:數字,所以後來覺得除非事先看過,不過再慢慢推有點..
推 ALTandTAB:不是O(n) 因為case: {1,1,2,2,3,3,4,4,5,5...}
→ diabloevagto:感謝各位指教！
→ stimim:第一題 http://ideone.com/IpTtK
→ adrianshum:我反而想知道最後一題被電的原因? 看起來蠻正常的呀
→ tropical72:@a大,那正是我想問題原因.