前言
这应该是我第一次分享面试经验，其实一直再期待这么一天了，从8月份开始我就为能进入阿里进行各种模拟面试，期间通过了（陌陌、36氪、创新工厂、行云、涂鸦移动、去哪儿、阿里）的技术面，一直在纠结究竟第一次面试失败会在神马时候出现，导致每次面试都有些变态的期待，唉，人是一种很奇怪的生物
在今天高烧38度，然后因为消炎药无法吃中饭的我，还是选择去面试豌豆荚（ps：哈哈，夸自己一下吧，确实守时守信）
面试过程
1、我想自我介绍，失败，每次碰到不让自我介绍的面试官，我都知道接下来就是恶战
2、项目介绍，无奈我是基于LNMP架构做项目，豌豆荚后台都是java，也不知道面试官是否听进去了
3、算法题目，两道算法题目，我被第一道轴对称二叉树搞蒙了，唉，写了半小时貌似还不对
4、一面跪了，走人
算法题目
1、城市的环路有n个加油站，第i个加油站的油量用gas[i]表示，你有如下的一辆车：
- 它的油缸是无限的，初始为空
- 它从第i个加油站到第i+1个加油站消耗的油量为cost[i]
现在你可以从任意一个加油站开始，通过加油站可以不断的加油，问是否能够走完环形路。如果可以返回开始加油站的编号，如果不可以返回-1
思路：
（1）暴力破解法，从第0个加油站起判断是否能走完，不行的话，再从第1个加油站起
代码：
/**
* 暴力破解法
*
* T = O(n^2)
*/
int violenceGas(int *gas, int *cost, int n)
{
int i, j, total, flag;
for (i = 0; i < n - 1; i ++) {
total = gas[i] - cost[i];
if (total < 0) {
flag = 0;
continue;
}
for (j = i + 1, flag = 1; j != i; j = (j + 1) % n) {
total += gas[j] - cost[j];
if (total < 0) {
flag = 0;
break;
}
}
if (flag) {
break;
}
}
if (flag) {
return i;
} else {
return -1;
}
}
（2）双向查找法，total表示当前车的油缸里的油量：
- 从第0个站开始，total = gas[0] - cost[0]，只要total >= 0, 我们就继续下一个加油站
- 当不满足total >= 0, 顺着环路从前一个站开始，比如n-1,此时total += gas[n - 1] - cost[i - 1]，如果total还是小于0,继续向前找
- 直到满足total >= 0,再进行第一步，依此类推
代码：
/**
* 双向查找法
*
* T = O(n)
*/
int trickGas(int *gas, int *cost, int n)
{
int bt, ed, total;
total = gas[0] - cost[0];
for (bt = 0, ed = 1; bt != ed;) {
if (total >= 0) {
total += gas[ed] - cost[ed];
ed = (ed + 1) % n;
} else {
bt = (bt - 1 + n) % n;
total += gas[bt] - cost[bt];
}
}
if (total >= 0) {
return bt;
} else {
return -1;
}
}
（3）完整测试代码：
/**
* 测试用例：
* n = 5
*
* gas ： 3, 5, 8, 7, 10
* cost： 4, 6, 6, 7, 2
*
*/
#include <stdio.h>
#include <stdlib.h>
/**
* 暴力破解法
*
* T = O(n^2)
*/
int violenceGas(int *gas, int *cost, int n)
{
int i, j, total, flag;
for (i = 0; i < n - 1; i ++) {
total = gas[i] - cost[i];
if (total < 0) {
flag = 0;
continue;
}
for (j = i + 1, flag = 1; j != i; j = (j + 1) % n) {
total += gas[j] - cost[j];
if (total < 0) {
flag = 0;
break;
}
}
if (flag) {
break;
}
}
if (flag) {
return i;
} else {
return -1;
}
}
/**
* 双向查找法
*
* T = O(n)
*/
int trickGas(int *gas, int *cost, int n)
{
int bt, ed, total;
total = gas[0] - cost[0];
for (bt = 0, ed = 1; bt != ed;) {
if (total >= 0) {
total += gas[ed] - cost[ed];
ed = (ed + 1) % n;
} else {
bt = (bt - 1 + n) % n;
total += gas[bt] - cost[bt];
}
}
if (total >= 0) {
return bt;
} else {
return -1;
}
}
int main(void)
{
int i, n, st, *gas, *cost;
while (scanf("%d", &n) != EOF) {
gas = (int *)malloc(sizeof(int) * n);
cost = (int *)malloc(sizeof(int) * n);
for (i = 0; i < n; i ++) {
scanf("%d", gas + i);
}
for (i = 0; i < n; i ++) {
scanf("%d", cost + i);
}
st = violenceGas(gas, cost, n);
printf("%d\n", st);
st = trickGas(gas, cost, n);
printf("%d\n", st);
free(gas);
free(cost);
}
return 0;
}
2、判断二叉树是否为轴对称二叉树
不得不说我当时真的是烧晕了，这道题目我竟然用非递归中序遍历，然后存储到数组里，再挨个比较，写了半小时证明思路还是错的，直接导致面试跪了，想想递归实现还是不难的
轴对称二叉树示例：
算法思路：
其实思路不难，递归判断左节点的左孩子是否等于右节点的右孩子，并且左节点的右孩子等于右节点的左孩子
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
struct node *left;
struct node *right;
char value;
} node;
char str[1000];
int count;
int judegTree(node *lchild, node *rchild)
{
if (lchild != NULL && rchild != NULL && lchild->value == rchild->value) {
return judegTree(lchild->left, rchild->right) && judegTree(lchild->right, rchild->left);
} else if (lchild == NULL && rchild == NULL) {
return 1;
} else {
return 0;
}
}
int isPair(node *root)
{
if (root == NULL) return 1;
int flag;
flag = judegTree(root->left, root->right);
return flag;
}
void createBtree(node **t)
{
if (str[count ++] == '#') {
*t = NULL;
} else {
*t = (node *)malloc(sizeof(node));
(*t)->value = str[count - 1];
createBtree(&(*t)->left);
createBtree(&(*t)->right);
}
}
int main(void)
{
int flag;
node *root;
while (scanf("%s", str) != EOF) {
count = 0;
createBtree(&root);
flag = isPair(root);
printf("%d\n", flag);
}
return 0;
}
后记
博主连续挂在hr面上，而且阿里目测会被分配到杭州，心乱如麻啊，考虑周六要不要顶着重感冒去百度霸面