Chinaunix

标题: 微软面试中简单的算法题目(转) [打印本页]

作者: ubuntuer 时间: 2008-11-09 12:53
标题: 微软面试中简单的算法题目(转)

（说明：这些题就不是什么花样了，考的是你的基础知识怎么样。再聪明而没有实学的人都将会被这些题所淘汰。）
1.链表和数组的区别在哪里？
ANSWER 主要在基本概念上的理解。但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，谁比较仔细，谁获胜的机会就大。
1）数组在内存中是逐个存放的，也就是说倘若数组的第一个元素在地址A,则数组第二个元素就在地址A+1。而链表则不是，链表每个节点没有相对固定的位置关系。某个节点在地址A其后的节点不一定是A+1,而在内存的其他空闲区域，呈现一种随机的状态。
2）数组一旦显式的被申明后，其大小就固定了，不能动态进行扩充。而链表则可以，可以动态生成节点并且添加到已有的链表后面。
3) …… （大家一起想想）

2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
ANSWER
链表通常是插入排序,为什么呢？在数组中插入排序实现时会大量的移动数据从而删除位置不正确的元素，这是顺序表删除操作的低效性。从数学的角度，顺序表
（即数组）的删除操作是O(n).链表就不同，由于其存储位置的不固定性，其删除固定位置的元素只需要O(1)的时间，所以整体性能上获得比较大的提高。

3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
ANSWER
排序算法非常成熟了，实际上排序是研究算法的很有效例子。回答的时候尽量找一些比较有技术性的算法，比如堆排序或者快速排序，如果写冒泡什么的，别人都会
写，也就显示不出你的优秀了。当然一定要注意给定的条件。不至于三个数让你排序，你搞个快排，这就有点“宰牛刀杀鸡”了。

4.请编写能直接实现strstr()函数功能的代码。
ANSWER
首先要知道strstr()这个函数是干什么的，自己去查查C语言的书，一般附录后面会给出C语言标准库的。这个题目实际上也是一类重要的算法门类，叫做
“字符串的模式匹配”。它有很多的现成算法，其中最简单的要数朴素的匹配算法，还有KMP,BM这些高级算法，笔试估计是来不及写的。下面给出朴素的匹配
算法。
int stringMatching(char* pattern,char* text)
{
      int pLen = strlen(pattern),tLen = strlen(text);
      for(int i = 0;i ANSWER: 显然只需要判断是否存在回溯指针就行了。判断，是否存在某个节点的后继指向其前面位置的指针。具体实现的时候可以模仿DFS中的访问标志数组的方法，我们可以在struct node中设计该节点的一个访问标志位，设为visited 。每访问一个节点就将其visited域置为1。这样的话，一次遍历下来，如果发现某个后续节点的visited域已经是1，那么就可以判定其存在循环链接。具体的代码就不写了，太简单了。

7.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）
分析：简单！扫描一遍，每次生成对应整数的最高位。一行也就搞定了！
long convert(char* s_string,long s_integer)
{
for(int sLen = strlen(s_string), i = 0; i 第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，也需要一定的灵感，有兴趣最好看看。
void permStr(char* str,int i)
{
      if(i == strlen(str) - 1)
         printf("%s\n",str);
      else
      {
         for(int j = i;j  aLen || n > bLen)
               return NULL; // Error
      for(int i = 0;i ANSWER
:二叉搜索树的建树方法。简单的递归结构。实在不理解，干脆记下来好了。关于树的算法设计一定要联想到递归，因为树本身就是递归的定义。这里的递归应该是
理所当然的吧，不过，学会把递归改称非递归也是一种必要的技术。毕竟，递归会造成栈溢出，关于系统底层的程序中不到非不得以最好不要用。但是对某些数学问
题，就一定要学会用递归去解决。
void insertNode(bTree** root,int val)
{
bTree* newNode = (bTree* ) malloc(sizeof(bTree));
      newNode->data = val;
      newNode->lChild = NULL;
      newNode->rChild = NULL;
   if(!(*root))
         *root = newNode;
else if(newNode->data data)
      insertNode(&(*root)->lChild,val);
      else
      insertNode(&(*root)->rChild,val);
}

11.怎样从顶部开始逐层打印二叉树结点数据？请编程。
ANSWER 二叉树的层次遍历没什么好说的，如果你不会还是早点把基础复习一下。一个劲的往后学，才会发现原来最最重要的还是以前最基础最简单的。
typedef struct myBinaryTree
{
      int data;
      struct myBinaryTree* lChild;
      struct myBinaryTree* rChild;
} bTree;

struct myQueen
{
      bTree* que[QSIZE];
      int front;
      int rear;
} binQueue; // Global var

void initQueue()
{
      // front == real makes the queue empty
      binQueue.rear = QSIZE - 1;
      binQueue.front = binQueue.rear;
      for(int i = 0;i = 1)
      binQueue.que[binQueue.front--] = newNode;

      else return 0;
      return 1;
}

bTree* deQueue()
{
      int t;
   if(binQueue.front != binQueue.rear){
      t = binQueue.rear;
      binQueue.rear--;
return binQueue.que[t];
      }
      else return NULL;
}
int levelTraversal(bTree** root)
{
      initQueue();
      bTree* lc = (bTree* ) malloc(sizeof(bTree));
      bTree* rc = (bTree* ) malloc(sizeof(bTree));
      bTree* p = (bTree* ) malloc(sizeof(bTree));
      if((!lc) || (!rc) || (!p)){
      printf("OVERFLOW\n");
      exit(OVERFLOW); // Allocation Error
      }
      p = *root;
      if(!p) {
               printf("Empty Tree,build it first !\n");
         return 0;
      }
      enQueue(p); // enqueue the root of the tree
   while (binQueue.front != binQueue.rear){
   p = deQueue();
         printf("%d ",p->data);
         lc = p->lChild;
         rc = p->rChild;
         if(lc != NULL)
                  enQueue(lc);
      if(rc != NULL)
                  enQueue(rc);
      }
      printf("\n");
      return 1;
}

12.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？
ANSWER 前面说了，最基本的是最重要的。线性数据结构是学习数据结构的入门，一定要掌握好。微软的题目还是跟国内的公司不一样。国内的一上来就是些概念，跟考历史一样。
typedef struct listNode
{
      struct listNode* link;
      int data;
}node;

node* getNode(node* newNode,int val)
{
if(!newNode)
               exit(OVERFLOW);
      newNode->link = NULL;
      newNode->data = val;
      return newNode;
}
/*
  Insert a new node after p
*/
int insertNode(node* prev,node* newNode)
{
      if(!prev) return 0;
      newNode->link = prev->link;
      prev->link = newNode;
return 1;
}
/*
delete the node after the node prev
*/
int eraseNode(node*prev,node* p)
{
      if(p == NULL)
               return 0;
      prev->link = p->link;
      free(p);
      return 1;
}
void buildList(node* head)
{
      int value;
      node* newNode = (node* ) malloc(sizeof(node));
      node* p = head;
      scanf("%d",&value);
      while(value != -1){
      newNode = getNode(newNode,value);
      insertNode(p,newNode);
      p = p->link;
      newNode = (node* ) malloc(sizeof(node));
      scanf("%d",&value);
      }
}

int reverseList(node* head)
{
      node* p = head->link;
      node* q = p->link;
      if(p == NULL){
      printf("The list is empty!\n");
      return 0;
      }
      while(q != NULL){
node* newNode = (node* ) malloc(sizeof(node));
      newNode = getNode(newNode,q->data);
      insertNode(head,newNode);
      eraseNode(p,q);
      q = (node* ) malloc(sizeof(node)); // Allocate again
      q = p->link;
      }
      p->link = NULL;
   return 1;
}

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76292/showart_1388527.html

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)