干货,算法工程师必备面试题1算法工程师
1.把二元查找树转变成排序的双向链表(树)
题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。
10
/ /
6 14
/ / / /
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树 节点的数据结构如下:
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
答案:void change(Node *p, Node *&last) //中序遍历
{
if (!p)
return;
change(p->left, last);
if (last)
last->right = p;
p->left = last;
last = p;
change(p->right, last);
}
void main()
{
Node *root = create();
Node *tail = NULL;
change(root, tail);
while (tail)
{
cout << tail->data << " ";
tail = tail->left;
}
cout << endl;
}
2.求子数组的最大和(数组)
题目:
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。
之前上传的答案是:
int maxSum(int* a, int n)
{
int sum=0; int b=0;
for(int i=0; i<n; i++)
{
if(b<0)
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}
答案:int get_sub_sum_max(int *arr, int len)
{
int max, sum;
max = arr[0];
sum = 0;
while (len--)
{
sum += *arr++;
if (sum > max)
max = sum;
else if (sum < 0)
sum = 0;
}
return max;
}
3.数组
腾讯面试题:
给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下:
【0,1,2,3,4,5,6,7,8,9】
举一个例子,
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次,1在下排出现了2次,
2在下排出现了1次,3在下排出现了0次....
答案分析:说实话,这题除了一次次迭代尝试外,我没想到什么好的处理办法。假设上排的数组为a,下排对应的数组为b,元素个数为n,按照题目的意思可以得到以下公式:
b1+b2+...+bn=na1*b1+a2*b2+...+an*bn=nb
中的元素来源于a这种一次多项表达式的求解我不会。
我觉得这题比实际上还要复杂,以下情况是必须要考虑的:
1、上排的数据元素并不一定是排序的。
2、上排的数据元素并不一定就有0,可能还有负数。
3、上排的数据元素可能会有重复的。
4、未必有对应的下排数据。
除了上面提到的,就楼主的程序而言,个人觉得有以下几个改进建议:
1、类中success是个多余的东西,如果设置这么一个成员变量,就不应该在函数setNextBottom中再无谓多一个reB变量。
2、由于未必有解,getBottom可能限于死循环。
3、getBottom中变量i完全是多余的。
4、getFrequecy中判断有些是多余的,可以考虑把我上面提到的公司考虑进去。
等有时间了,我再好好考虑如何写个比较好的程序。
4.链表
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针,比如h1,h2,判断这俩个链表是否相交。
为了简化问题,我们假设俩个链表均不带环。
问题扩展:
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
答案分析:如果不需要求出两个链表相交的第一个节点,楼主提出的方法挺好的。
如果需要求出相交第一个节点,我有以下思路:
以链表节点地址为值,遍历第一个链表,使用Hash保存所有节点地址值,结束条件为到最后一个节点(无环)或Hash中该地址值已经存在(有环)。再遍历第二个链表,判断节点地址值是否已经存在于上面创建的Hash表中。
这个方面可以解决题目中的所有情况,时间复杂度为O(m+n),m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型,假设链表都是在堆中动态创建的,可以使用堆的起始地址作为偏移量,以地址减去这个偏移量作为Hash函数。
5.树
判断整数序列是不是二元查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ /
6 10
/ / / /
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
答案:
int is_post_traverse(int *arr, int len)
{
int *head, *pos, *p;
if (arr == NULL || len <= 0)
return 0;
if (len == 1)
return 1;
head = arr + len - 1;
p = arr;
while (*p < *head)
p++;
pos = p;
while (p < head)
{
if (*p < *head)
return 0;
p++;
}
if (!is_post_traverse(arr, pos - arr))
return 0;
return is_post_traverse(pos, head - pos);
}
6.链表:
题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
答案: list *list_find_desc(list *head, int k)
{
list *p, *q;
if (head == NULL || k < 0)
return NULL;
p = head;
while (p != NULL && k-- >= 0)
{
p = p->next;
}
if (p == NULL)
return k < 0 ? head : NULL;
q = head;
while (p != NULL)
{
p = p->next;
q = q->next;
}
return q;
}


1914篇文章