一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2779|回复: 10
收起左侧

10/22 qumulo

[复制链接] |试试Instant~ |关注本帖
mumuzi 发表于 2015-10-24 03:52:51 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Qumulo - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
网上海投,收到OA 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
题目和这个帖子一样,2个小时,4题
http://www.1point3acres.com/bbs/thread-143954-1-1.html. more info on 1point3acres.com

说说第四题
Knight's Adventure:一个Chess Board,你要把一个Knight从给定起点跳到给点重点,棋盘上有一些blocked square不能走,求最短步数。Warning:最后三个test case非常大,长宽都是10000+,大数据测试。

LZ用BFS做的,也通过了所以的test cases, 希望对大家有帮助

PS, 之前的号被盗,新开一号,求大米啊!

评分

6

查看全部评分

molt 发表于 2015-10-27 01:16:28 | 显示全部楼层
lz能讲一下怎么处理大testcase的吗
回复 支持 反对

使用道具 举报

pfczwxcd 发表于 2015-10-27 11:38:18 | 显示全部楼层
楼主您好,关于OA中的BST PreOrder to PostOrder这道题,我的解法大致如下:
public void preToPost(int[] pre, int l, int r, ArrayList<Integer> tmp) {. from: 1point3acres.com/bbs
        if (l == r) {
                tmp.add(pre[l]); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                return;-google 1point3acres
        }
        int i = l + 1;. visit 1point3acres.com for more.
        for (; i <= r; ++i) {
                if (pre > pre[l])
                        break;. visit 1point3acres.com for more.
        }
        preToPost(pre, l + 1, i - 1, tmp);
        preToPost(pre, i, r, tmp);
        tmp.add(pre[l]);
}

但有两个case报了stackoverflow error。意思是这里不能用递归吗?您的解法是怎样的?谢谢~

补充内容 (2015-10-27 11:51):. from: 1point3acres.com/bbs
漏了一个递归结束条件:.鐣欏璁哄潧-涓浜-涓夊垎鍦
if (l > r)
                return;
回复 支持 反对

使用道具 举报

 楼主| mumuzi 发表于 2015-10-27 11:39:51 | 显示全部楼层
molt 发表于 2015-10-27 01:16. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
lz能讲一下怎么处理大testcase的吗
. 1point3acres.com/bbs
就BFS, 然后用hashset存访问过的节点就好,复杂度就是O(MN)
回复 支持 反对

使用道具 举报

 楼主| mumuzi 发表于 2015-10-27 11:43:46 | 显示全部楼层
pfczwxcd 发表于 2015-10-27 11:38
楼主您好,关于OA中的BST PreOrder to PostOrder这道题,我的解法大致如下:
public void preToPost(int[] ...

我就按照leetcode construct tree from preorder and inorder来做的,得到tree的root, 然后再post order traversal一次
回复 支持 反对

使用道具 举报

 楼主| mumuzi 发表于 2015-10-28 05:54:05 | 显示全部楼层
有朋友问第四题,我没短消息权限,就写这里了,我好像用的hashset, 记录访问过的grid,应该不是每个grid都要被访问,所以可以省一些空间
回复 支持 反对

使用道具 举报

zws0818 发表于 2015-11-5 07:53:23 | 显示全部楼层
mumuzi 发表于 2015-10-27 11:43
我就按照leetcode construct tree from preorder and inorder来做的,得到tree的root, 然后再post order ...

楼主怎么按照construct tree from preorder and inorder来做?题目不是没给inorder吗?可否详细讲一下思路?
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2015-12-25 05:14:52 | 显示全部楼层
zws0818 发表于 2015-11-5 07:53
楼主怎么按照construct tree from preorder and inorder来做?题目不是没给inorder吗?可否详细讲一下思 ...

BST,直接把preorder的数排个序不就inorder了?
回复 支持 反对

使用道具 举报

cucucucu123 发表于 2016-1-20 09:08:34 | 显示全部楼层
楼主最后一题能看看代码吗
回复 支持 反对

使用道具 举报

BrilliantBean 发表于 2016-2-5 00:34:49 | 显示全部楼层
楼主可以分享你一下你的oa代码吗? huangrui6556@gmail.com 拜谢楼主
回复 支持 反对

使用道具 举报

hotinherre 发表于 2016-2-5 16:11:43 | 显示全部楼层
谎言之躯 发表于 2015-12-25 05:14
BST,直接把preorder的数排个序不就inorder了?

好棒!! 我没想到这点。。 我直接 在preorder里,找的区间,你这么说就超级简单了。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 08:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表