《it面试100题》由会员分享，可在线阅读，更多相关《it面试100题（59页珍藏版）》请在金锄头文库上搜索。
1、1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/ 6 14/ / 4 8 12 16转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：struct BSTreeNodeint m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node;ANSWER:This is a traditional
2、 problem that can be solved using recursion. For each node, connect the double linked lists created from left and right child node to form a full list./* * param root The root node of the tree * return The head node of the converted list. */BSTreeNode * treeToLinkedList(BSTreeNode * root) BSTreeNode
3、 * head, * tail; helper(head, tail, root); return head;void helper(BSTreeNode *& head, BSTreeNode *& tail, BSTreeNode *root) BSTreeNode *lt, *rh; if (root = NULL) head = NULL, tail = NULL; return; helper(head, lt, root-m_pLeft); helper(rh, tail, root-m_pRight); if (lt!=NULL) lt-m_pRight = root; root
4、-m_pLeft = lt; else head = root; if (rh!=NULL) root-m_pRight=rh; rh-m_pLeft = root; else tail = root; 2.设计包含min 函数的栈。定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。要求函数min、push 以及pop 的时间复杂度都是O(1)。ANSWER:Stack is a LIFO data structure. When some element is popped from the stack, the status will recover to the orig
5、inal status as before that element was pushed. So we can recover the minimum element, too.struct MinStackElement int data; int min;struct MinStack MinStackElement * data; int size; int top;MinStack MinStackInit(int maxSize) MinStack stack; stack.size = maxSize; stack.data = (MinStackElement*) malloc
6、(sizeof(MinStackElement)*maxSize); stack.top = 0; return stack;void MinStackFree(MinStack stack) free(stack.data);void MinStackPush(MinStack stack, int d) if (stack.top = stack.size) error(“out of stack space.”); MinStackElement* p = stack.datastack.top; p-data = d; p-min = (stack.top=0?d : stack.da
7、tatop-1); if (p-min d) p-min = d; top +;int MinStackPop(MinStack stack) if (stack.top = 0) error(“stack is empty!”); return stack.data-stack.top.data;int MinStackMin(MinStack stack) if (stack.top = 0) error(“stack is empty!”); return stack.datastack.top-1.min;3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一
8、个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。ANSWER: A traditional greedy approach.Keep current sum, slide from left to right, when sum 0, reset sum to 0.int maxSubarray(int a, int size) if (size=0) error(“error array siz
9、e”); int sum = 0; int max = - (1 31); int cur = 0; while (cur max) max = sum; else if (sum left = NULL & root-right=NULL) if (sum = 0) printPath(path, top); else if (root-left != NULL) helper(root-left, sum, path, top); if (root-right!=NULL) helper(root-right, sum, path, top); top -; sum += root.dat
10、a; /.5.查找最小的k 个元素题目：输入n 个整数，输出其中最小的k 个。例如输入1，2，3，4，5，6，7 和8 这8 个数字，则最小的4 个数字为1，2，3 和4。ANSWER:This is a very traditional question.O(nlogn): cat I_FILE | sort -n | head -n KO(kn): do insertion sort until k elements are retrieved.O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down
11、k-1 times.So traditional that I dont want to write the codes.Only gives the siftup and siftdown function./* *param i the index of the element in heap a0.n-1 to be sifted upvoid siftup(int a, int i, int n) while (i0) int j=(i&1=0 ? i-1 : i+1); int p=(i-1)1; if (jn & ajai) i = j; if (ai ap) swap(a, i, p); i = p; void siftdown(int a, int i, int n) while (2*i+1n) int l=2*i+1; if (l+1n & al+1 al) l+; if (al ai) swap(a, i, l); i=l; 第6 题腾讯面试题：给你10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下：【0，1，2，3，4，5，6，7，8，
