微软、Google等面试题

所需积分/C币:10 2012-08-14 19:25:12 955KB PDF
13
收藏 收藏
举报

程序员面试100题完整版,微软、Google等名企面试题。
http:/zhedahht.blog163.com/blog/static/254111742007127104759245/ 程序员面试题精选100题(01)一把元查找树转变成排序的双向链表 题目:输入一棵二元査找树,将该二元査找树转换成一个排序的双向链表。要求不能创建任何 新的结点,只调整指针的指向。 比如将二元查找树 10 14 4812 16 转换成双向链表 4=6=8=10=1214=16。 分析:本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决,本题也不例外 下面我们用两种不同的递归思路来分析 思路一:当我们到达某一结点准备调鍪以该结点为根结点的子树时,先调整其左子树将左子树 转换成一个排好序的左子链表,再调整其石子树转换石子链表。最近链接片子链表的最右结点(左子树的 最大结点)、当前结点和右了链表的最左结点(右子树的最小结点)。从树的根结点片始递归调整所有结点。 思嵱二:我们可以中序遍历整棵树。按照这个方式遍历树,比较小的结点宄访问。如果我们每 访问一^结点,假设之前访问过的结点已经啁整成一个排序双向链表,我们再把调整当前结点的指针将其 链接到链表的末尾。当所有结点都访问过之后,整棵树也就转换成一个排序双向链表了。 参考代码 首先我们定义二元查找树结点的效据结构如下 struct BSTreeNode / a node in the binary search tree 1n二 m nValue;// value of ncde BSTreeNode *m plefti //lef. child of node BSTreeNode *m pRight; / right child of node 思路一对应的代 / Covert a sub birary-search-tree into a sorted double-linked list / Input: pNode- the head of the sub tree arIght - whethe pNode is the right child of its parent Outout: asRignt is true, return the least node in he sub-tree else return the greatest node in he sub-tree BSTreeNode* ConvertNode (BsTreeNode* pNode, bool arIght) if(! pNode) return NULL BSTreeNode *pleft= NULL BSTreeNode pRight= NULLi Convert the left sub-tree if (oNode->m pLeft) pLeft ConvertNode (pNcde->m pLeftr false)i 7/ Connect the greatest node in the left sub-tree to the current node if(oLeft) pLeft->m pRight Node pNode->m pLeft pleft // Convert the right sub-tree if(oNode->m pRicht) pRight ConvertNode (rnode->m pRight, true)i // Connect the least ncde ir. the riot sub-tree to the current node if(pRight) pNode->m pRight pRight pRight->m pleft- pNod BSTr≈ e node Temo pNode; // If the current node is the right child of its parent 7/ return the least node in the tree whose root is the current node if(arIght while(pTemp->m pleft pTemr= pTemp->m plefti 7/ If the current node is the left child of its parent // return the createst node in the tree whose root. is the current node 1 se while(ptemp->n pRight) pTemp= pTemp->m pRighti return tEmp; , Covert a binary search tree into a sorted double-linked list / Input: the head of tree // Cutout: the head of sorted double-linked list //1/11//1//// BSTreeNode* Convert(bstreeNodex oheadofTree) // As we want to return the head cf the sorted double-linked list // we set the second parameter to be true return ConvertNode(pHeadcfTree, true)i 思路二对应的代码 / Covert a sub birary-search-tree into a sorted double-linked list / Input: pNode che head of the sub tree pLas-NodeInList - the tail of the double-linked list ////// void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList if (pNode return BSTreeNode *cUrrent- pNcce / Convert the left sub-tree if (pCurrent->m pLeft -NULL) ConvertNcce (pcurrent->m pLeft, plastNodeInList)i // Put the current node into the double-linked list pCu1rrent->m pLeft- pLastNodeinlisti if (oLastNodeirList ! = NULL) pLastNodeinList->m pRight pCurrenti plastNodeinlist pcurrenti // Convert the right sub-tree f (pCurrent->m pRight != NUL) ConvertNcce(pcurrent->m pRight, pLastNodeInList)i / Covert a binary search tree into a sorted double-linked list // Input: pHeadofTree the head of tree // Outout: the head of sorted double-linked list BSTreeNode* Convert Solutionl(BSTreeNode* pHeadofTree BSTreeNode *plastNode - NULL ConvertNode(pheadofTree, plastNodeInlis=)i // Get the heac of the double-linked list BSTreeNode *pHeadoflist pLastNode-nlisti while(pHeadCflist & pHeadofList->m pLeft) pHeadoflist= pHeadoflist->m pLeft return pHeadoflist 博主何海涛对本博客文章享有版权。网络转载请注明出处 http:/zhedahht.blog163.com整理出版物请和作者联系。对解题思路有任何建议,欢迎在 评论中告知,或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht与我 讨论。谢谢 6 http:/zhedahht.blog163.com/blog/static/25411174200712895228171/ 程序员面试题精选100题(02)设计包含mn函数的栈 题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及 pop的时间复杂度都是o(1) 分析:这是去年 google的道面试题。 我看到这道题目时,第一反应就是每次push一个新元素时,将栈里所有逆序元索排序。这样栈顶元素将 是最小元素。但由于不能保证最后push进栈的元素最先出栈,这种思路设训的数据结构已经不是一个栈 在梭里添加一个成员变量存放最小元素(或最小元素的位置)。每次push一个新元素进栈的时候,如果该 元素比当前的最小元素还要小,则史新最小元素 乍一看这样思路挺好的。但仔细一想,该思路存在一个重要的问题:如果当前最小元素被pop出去,如何 才能得到下一个最小元素? 因此仅仅只添加一个成员变量存放最小元素(或最小元素的位置)是不够的。我们需要一个辅助栈。每次 push一个新元素的时候,同时将最小元素(或最小元索的位置。考虑到梭元素的类型可能是复杂的数据结 构,用最小元素的位置将能减少空间消耗)push到辅助梭中;每次pop一个元素岀栈的时候,同忖pop 辅助栈。 参考代码 include <deque> include <assert. h> template <typename T> class CstackwithMin public: CStackWithMin(void) virtual ncstackwithMin(void)( T& top(void)i const T& tor(void)const void push(const t& value)i (void) const T& min(void) consti private: T>m data;// theelements of stack size t>m minIrcex:// the indicesof minimum elements / get the last element of mutable stack template <typename T> T& CStackwithMin<T>:: top() 7 return m data back()i // get the last element of non-mutable stack template <typename T> const T& CStackWithMin<T>:: top()corst data back(i 7/ insert an elment at the end of stack template <typename T> void CscackithMin<r>:: push(const T& value // append the cata into the end of m daca m data push hack(value)i // set the index of minimum elment in m data at the end of m minindex if(n minIndex size()==0) m minIndex. push back(0)i else if(value m datalm minIndex back()]) m minIncex. push back(m data size()-1)i else m minIrcex. push back(m minIndex back()) // erease the element at the erd of stack template <typename T> void CS-ackwithMin<T>:: pop( data m data. pop back()i //pop m mincex m minIndex pop back()i / get the minimum element of stack template <typename T> const. T& C5tackWithMin<T>:: min( const assert(m data. size assert(m minIrcex size()>0)i return m data [m minindex back()]i 举个例子演小上述代码的运行过程: 步骤 数据栈 辅助栈 最小值 1. push 3 push 4 0 3.psh23,4,2 0,0,2 4. push 3,4,2,1 0,0,2 6. pcp 3,4 0;0 7.pish03,4,0 0;0,2 讨论:如果思路正确,编写上述代码不是一件很难的事情。但如果能注意一些纠节无疑能在面试中加分。 比如我在上面的代码中做了如下的工作: 用模板类实现。如果别人的元素类型只是int关型,模板将能给面试官带来好印象: ·两个版本的tp函数。在很多类中,都需要提供 const和非 const版本的成员访问函数; ·min函数中 assert。把代与的尽量安全是每个软件公司对程序员的要求 添加一些注释。注释既能提髙代码的可读性,又能增加代码量,何乐而不为? 总之,在面试时如果时间允许,尽量把代码写的漂亮一些。说不定代码中的几个小亮点就能让自己轻松拿 到心仪的Ofer。 博主何海涛对本博客文章享有版权。网络转载请注明出处 http://zhedahht.blog163.com/整理出版物请和作者联系。对解题思路有任何建议,欢迎在 评论中告知,或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht与我 讨论。谢谢。 9 http:/zhedahht.blog163.com/blog/static/254111742007219147591/ 程序员面试题精选100题(03)-求子数组的最大和 题目:输入一个整形数组,数组里有正数也有负数。数组中迄续的一个或多个整数组成一个子数组,每个 子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n) 例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,-4,7,2,因此输出为该子数组的和18。 分析:本题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题,在2006年里包括 google 在内的很多知名公司都把本题当作面试题。由于本题在网终中广为流传,本题也顺利成为2006牛程序员 面试题中经史中的经典。 如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是,由于长度为n 的数组有O(n2)个子数组;而日求一个长度为n的数组的和的时间复杂度为on)。因此这种思路的时间是 O(n)。 很容易理解,当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和 是个负数,那么这个和在接下来的累加中应该抛齐并重新清零,不然的话这个负数将会减少接下来的和。 基于这样的思路,我们可以写出如下代码。 参考代码 ////1// / Find the greatest sum of all sub-arrays / Return value: if the input is valid, return true, otherwise return false ////////1/// ///1/ bool FindGreatestsumofSubArray int *pData, unsigned int nLength, / the length of array int &ngreatestsum / the greatest sum of all sub-arrays // if the input is invalid, return false f((pData = NULL) (length == 0)) return false; int nCurSum nGreatestsum =0 for(unsigned int i=0; i< nLength n Sum + pData[i] // if the current sum is negative, discard it if(nCur Sum< 0) n Cur Sum =0

...展开详情
试读 127P 微软、Google等面试题
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
微软、Google等面试题 10积分/C币 立即下载
1/127
微软、Google等面试题第1页
微软、Google等面试题第2页
微软、Google等面试题第3页
微软、Google等面试题第4页
微软、Google等面试题第5页
微软、Google等面试题第6页
微软、Google等面试题第7页
微软、Google等面试题第8页
微软、Google等面试题第9页
微软、Google等面试题第10页
微软、Google等面试题第11页
微软、Google等面试题第12页
微软、Google等面试题第13页
微软、Google等面试题第14页
微软、Google等面试题第15页
微软、Google等面试题第16页
微软、Google等面试题第17页
微软、Google等面试题第18页
微软、Google等面试题第19页
微软、Google等面试题第20页

试读结束, 可继续阅读

10积分/C币 立即下载