美团网2014校园招聘笔试试题
哈尔滨站 2013年9月10日版权所有, 禁止转载, 如有需要, 请站内联系.
本文地址: http://blog.csdn.net/caroline_wendy/article/details/20063229
1、一堆硬币，一个机器人，如果是反的就翻正，如果是正的就抛掷一次，无穷多次后，求正反的比例。
答:
正反比例是3:1, 因为反面的概率为1/2, 都被翻为正;
正面的概率为1/2, 再掷一次后, 正面的概率为1/4,反面的概率为1/4;
所以总概率正反比为: (1/2+1/4) / (1/4) = 3:1
2、一个汽车公司的产品，甲厂占40%，乙厂占60%，甲的次品率是1%，乙的次品率是2%，现在抽出一件汽车时次品，问是甲生产的可能性。
答:
甲生产次品占整个产品的概率为: 0.4*1%=0.4%;
乙生产次品占整个产品的概率为: 0.6*2%=1.2%;
所以一件次品是甲生产的概率为: 0.4% / (0.4%+1.2%) = 0.25;
3、k链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现。
答:
struct ListNode {int m_nKey;
ListNode* m_pNext;
};
ListNode* ReverseList (ListNode* pHead, ListNode* pTail) {
ListNode* pReversedList = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while (pNode != pTail) {
ListNode* pNext = pNode->m_pNext;
if (pNext == pTail)
pReversedList = pNode;
pNode->m_pNext = pPrev;
pPrev = pNode;
pNode = pNext;
}
return pReversedList;
}
ListNode* KReverseList (const int k, ListNode* pHead) {
ListNode* pReversedList = NULL;
ListNode* pReversedTail = NULL;
int index = 0;
ListNode* pStart = pHead;
ListNode* pEnd = pHead;
for(int i=0; i<k; ++i) {
pEnd = pEnd->m_pNext;
if (pEnd == NULL)
break;
}
pReversedList = ReverseList (pStart, pEnd);
pReversedTail = pStart;
pStart = pEnd;
while(1) {
if (pEnd == NULL)
break;
pEnd = pEnd->m_pNext;
++index;
if (index%k == 0) {
ListNode* pTemp = ReverseList (pStart, pEnd);
pReversedTail->m_pNext = pTemp;
pReversedTail = pStart;
pStart = pEnd;
}
}
if(pStart != NULL)
pReversedTail->m_pNext = pStart;
return pReversedList;
}
4、利用两个stack模拟queue。
答:
template<typename T> class CQueue {public:CQueue(void);~CQueue(void);void appendTail(const T& node);T deleteHead();private:stack<T> stack1;stack<T> stack2;};template<typename T> void CQueue<T>::appendTail(const T& node) {stack1.push(node);}template<typenameT> T CQueue<T>::deleteHead() {if(stack2.size() <= 0) {while(stack1.size() > 0) {T& data = stack1.top();stack1.pop();stack2.push(data);}}if (stack2.size() == 0)throw std::exception("queue is empty");T head = stack2.top();stack2.pop();return head;}
5.一个m*n的矩阵，从左到右从上到下都是递增的，给一个数elem，求是否在矩阵中，给出思路和代码。
答：
比较最右上角的值，大于elem，则列向前移动，小于elem，则行向下移动，等于elem，则返回真；
bool Find (int* matrix, int rows, int cols, int elem) {bool found = false;if (matrix != NULL && rows >0 && cols>0) {int row = 0;int col = cols-1;while (row < rows && col >= 0) {if(matrix[row*cols+col] == elem) {found = true;break;} else if (matrix[row*cols+col] > elem)--col;else++row;}}return found;}
