|
美團網(wǎng)研發(fā)工程師筆試題
1. 有一個隨機數(shù)發(fā)生器，以概率P產(chǎn)生0，概率(1-P)產(chǎn)生1，請問能否利用這個隨機數(shù)發(fā)生器，構(gòu)造出新的發(fā)生器，以1/2的概率產(chǎn)生0和1。請寫明結(jié)論及推理過程。
2. 一個棧的入棧序列是A,B,C,D,E,則棧的不可能的輸出序列是( ) A. EDCBA; B. DECBA; C.DCEAB D,ABCDE
3. 4個足球隊打小組單循環(huán)，計分方式：勝3分平1分負0分，如果計分相同，則凈勝球多的隊伍排名靠前，如果凈勝球還一樣，則進球多的球隊排名靠前。小組前兩名出線。問可能出線的最低分數(shù)是多少。請說明推理過程。 備注：單循環(huán)賽是指所有參加比賽的隊兩兩之間都比賽一次，最后按各隊在全部比賽中的積分，得失分率排列名次。 4. 從1到1000000的所有自然數(shù)，數(shù)字“1”一共出現(xiàn)了多少次？例：自然數(shù)101中，數(shù)字“1”出現(xiàn)了2次，自然數(shù)1011中，數(shù)字“1”出現(xiàn)了3次，請寫明計算過程及結(jié)果
5. 以下代碼是把一個字符串倒序，如“abcd”倒序后變?yōu)椤?/font>dcba”。請找出下面代碼中的所有錯誤，直接在代碼的右側(cè)空白處修改。
#include"string.h" main() { char*src="hello,world"; char*dest=NULL; int len = strlen(src); dest = (char*)malloc(len); char* d = dest; char* s = src[len]; while(len--!=0) d++ = s --; printf("%s",dest); return 0; } 6. 以下代碼功能：找出一個有序(字典序)字符串數(shù)組arr種值等于字符串v的元素的符號，如果有多個元素滿足這個條件，則返回其中序號最大的。請找出下面代碼中所有錯誤，直接在代碼右側(cè)空白處修改
Int bisearch(char**arr, int b, int e, char*v){ Int minIndex = b, maxIndex = e, midIndex; while(minIndex<maxIndex){ midIndex=(minIndex+maxIndex)/2; if(strcmp(arr[midIndx],v<=0)){ minIndex = midIndex; }else{ maxIndex=minIndex; } } if(!strcmp(arr[maxIndex],v)){ return maxIndex; }else{ return -1; }
}
7. 字符串ABCD，可以由字符串BCDA或者CDAB通過循環(huán)移位而得到。請編程實現(xiàn)以下 檢測：字符串S1是否可以由字符串S2通過循環(huán)移位而得到。 語言不限（推薦C/C++,不推薦寫偽碼）
------------------------------------ 2014美團網(wǎng)筆試題目 1、一堆硬幣，一個機器人，如果是反的就翻正，如果是正的就拋擲一次，無窮多次后，求正反的比例 解答：是不是題目不完整啊，我算的是3：1 2、一個汽車公司的產(chǎn)品，甲廠占40%，乙廠占60%，甲的次品率是1%，乙的次品率是2%，現(xiàn)在抽出一件汽車時次品，問是甲生產(chǎn)的可能性 解答：典型的貝葉斯公式，p(甲|廢品) = p(甲 && 廢品) / p(廢品) = （0.4 × 0.01） /（0.4 × 0.01 + 0.6 × 0.02） = 0.25 3、k鏈表翻轉(zhuǎn)。給出一個鏈表和一個數(shù)k，比如鏈表1→2→3→4→5→6，k=2，則翻轉(zhuǎn)后2→1→4→3→6→5，若k=3,翻轉(zhuǎn)后3→2→1→6→5→4，若k=4，翻轉(zhuǎn)后4→3→2→1→5→6，用程序?qū)崿F(xiàn) 非遞歸可運行代碼： #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct node { struct node *next; int data; } node; void createList(node **head, int data) { node *pre, *cur, *new; pre = NULL; cur = *head; while (cur != NULL) { pre = cur; cur = cur->next; } new = (node *)malloc(sizeof(node)); new->data = data; new->next = cur; if (pre == NULL) *head = new; else pre->next = new; } void printLink(node *head) { while (head->next != NULL) { printf("%d ", head->data); head = head->next; } printf("%d\n", head->data); } int linkLen(node *head) { int len = 0; while (head != NULL) { len ++; head = head->next; } return len; } node* reverseK(node *head, int k) { int i, len, time, now; len = linkLen(head); if (len < k) { return head; } else { time = len / k; } node *newhead, *prev, *next, *old, *tail; for (now = 0, tail = NULL; now < time; now ++) { old = head; for (i = 0, prev = NULL; i < k; i ++) { next = head->next; head->next = prev; prev = head; head = next; } if (now == 0) { newhead = prev; } old->next = head; if (tail != NULL) { tail->next = prev; } tail = old; } if (head != NULL) { tail->next = head; } return newhead; } int main(void) { int i, n, k, data; node *head, *newhead; while (scanf("%d %d", &n, &k) != EOF) { for (i = 0, head = NULL; i < n; i ++) { scanf("%d", &data); createList(&head, data); } printLink(head); newhead = reverseK(head, k); printLink(newhead); } return 0; } 5、利用兩個stack模擬queue 劍指offer上的原題，九度oj有專門的練習，這里貼一下我的ac代碼： #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct stack { int top; int seq[100000]; } stack; /** * 入隊操作 * * T = O(1) * */ void pushQueue(stack *s1, int data) { s1->seq[s1->top ++] = data; } /** * 出隊操作 * * T = O(n) * */ void popQueue(stack *s1, stack *s2) { if (s2->top > 0) { printf("%d\n", s2->seq[-- s2->top]); } else { while (s1->top > 0) { s2->seq[s2->top ++] = s1->seq[-- s1->top]; } if (s2->top > 0) printf("%d\n", s2->seq[-- s2->top]); else printf("-1\n"); } } int main(void) { int data, n; stack *s1, *s2; char str[5]; while (scanf("%d", &n) != EOF) { // 初始化 s1 = (stack *)malloc(sizeof(stack)); s2 = (stack *)malloc(sizeof(stack)); s1->top = s2->top = 0; while (n --) { scanf("%s", str); if (strcmp(str, "PUSH") == 0) { // 入隊列 scanf("%d", &data); pushQueue(s1, data); } else { // 出隊列 popQueue(s1, s2); } } free(s1); free(s2); } return 0; } 6、一個m*n的矩陣，從左到右從上到下都是遞增的，給一個數(shù)elem，求是否在矩陣中，給出思路和代碼 楊氏矩陣，簡單題目： #include <stdio.h> #include <stdlib.h> /** * 有序矩陣查找 * * T = O(n + n) * */ void findKey(int **matrix, int n, int m, int key) { int row, col; for (row = 0, col = m - 1; row < n && col >= 0;) { if (matrix[row][col] == key) { printf("第%d行，第%d列\n", row + 1, col + 1); break; } else if (matrix[row][col] > key) { col -= 1; } else { row += 1; } } printf("不存在!\n"); } int main(void) { int i, j, key, n, m, **matrix; // 構(gòu)造矩陣 scanf("%d %d", &n, &m); matrix = (int **)malloc(sizeof(int *) * n); for (i = 0; i < n; i ++) matrix[i] = (int *)malloc(sizeof(int) * m); for (i = 0; i < n; i ++) { for (j = 0; j < m; j ++) scanf("%d", &matrix[i][j]); } // 查詢數(shù)據(jù) while (scanf("%d", &key) != EOF) { findKey(matrix, n, m, key); } return 0; }
|
|
|
