2020年BATJ最新面试414道题（含部分答案解析）阿里篇

VIP免费

2024-12-10 3 0 824.7KB 19 页 5.9玖币

侵权投诉

阿里篇

•1.1.1 如何实现一个高效的单向链表逆序输出？

出题人：阿里巴巴出题专家：昀龙／阿里云弹性人工智能负责人

参考答案：下面是其中一种写法，也可以有不同的写法，比如递归等。供参考。

typedef struct node{

int data;

struct node* next;

node(int d):data(d), next(NULL){}

}node;

void reverse(node* head)

{

if(NULL == head || NULL == head->next){

return;

}

node* prev=NULL;

node* pcur=head->next;

node* next;

while(pcur!=NULL){

if(pcur->next==NULL){

pcur->next=prev;

break;

}

next=pcur->next;

pcur->next=prev;

prev=pcur;

pcur=next;

}

head->next=pcur;

node*tmp=head->next;

while(tmp!=NULL){

cout<<tmp->data<<"\t";

tmp=tmp->next;

}

• 1.1.2 已知 sqrt(2)约等于 1.414，要求不用数学库，求 sqrt(2)精确到小数点后 10

位

出题人：——阿里巴巴出题专家：文景／阿里云 CDN 资深技术专家

参考答案：

* 考察点

1. 基础算法的灵活应用能力（二分法学过数据结构的同学都知道，但不一定往这个方

向考虑；如果学过数值计算的同学，应该还要能想到牛顿迭代法并解释清楚）

2. 退出条件设计

* 解决办法

1. 已知 sqrt(2)约等于 1.414，那么就可以在(1.4, 1.5)区间做二分

查找，如： a) high=>1.5 b) low=>1.4 c) mid => (high+low)/2=1.45 d) 1.45*1.45>2 ?

high=>1.45 : low => 1.45 e) 循环到 c)

2. 退出条件

a) 前后两次的差值的绝对值<=0.0000000001, 则可退出

const double EPSINON = 0.0000000001;

double sqrt2( ){

double low = 1.4, high = 1.5;

double mid = (low + high) / 2;

while (high - low > EPSINON){

if (mid*mid > 2){

high = mid;

}

else{

low = mid;

}

mid = (high + low) / 2;

}

return mid;

}

• 1.1.3 给定一个二叉搜索树(BST)，找到树中第 K 小的节点

出题人：阿里巴巴出题专家：文景／阿里云 CDN 资深技术专家

参考答案：

* 考察点

1. 基础数据结构的理解和编码能力

2. 递归使用

* 示例

/ \

3 6

/ \

2 4

说明：保证输入的 K 满足 1<=K<=(节点数目）

树相关的题目，第一眼就想到递归求解，左右子树分别遍历。联想到二叉搜索树

的性质，root 大于左子树，小于右子树，如果左子树的节点数目等于 K-1，那

么 root 就是结果，否则如果左子树节点数目小于 K-1，那么结果必然在右子树，

否则就在左子树。因此在搜索的时候同时返回节点数目，跟 K 做对比，就能得

出结果了。

/**

* Definition for a binary tree node.

**/

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

class Solution {

private class ResultType {

boolean found; // 是否找到

int val; // 节点数目

ResultType(boolean found, int val) {

this.found = found;

this.val = val;

}

public int kthSmallest(TreeNode root, int k) {

return kthSmallestHelper(root, k).val;

}

private ResultType kthSmallestHelper(TreeNode root, int k) {

if (root == null) {

return new ResultType(false, 0);

}

ResultType left = kthSmallestHelper(root.left, k);

// 左子树找到，直接返回

if (left.found) {

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

阿里篇•1.1.1如何实现一个高效的单向链表逆序输出？出题人：阿里巴巴出题专家：昀龙／阿里云弹性人工智能负责人参考答案：下面是其中一种写法，也可以有不同的写法，比如递归等。供参考。typedefstructnode{intdata;structnode*next;node(intd):data(d),next(NULL){}}node;voidreverse(node*head){if(NULL==head||NULL==head->next){return;}node*prev=NULL;node*pcur=head->next;node*next;while(pcur!=NULL){if(...

展开>> 收起<<

2020年BATJ最新面试414道题（含部分答案解析）阿里篇.pdf

共19页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

2020年BATJ最新面试414道题（含部分答案解析）阿里篇

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: