近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1271|回复: 2
收起左侧

Twitch 电面经

[复制链接] |试试Instant~ |关注本帖
rcholic 发表于 2016-10-27 09:00:32 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Twitch - 内推 - 技术电面 |Other在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
板上很少有人面这个Twitch,上个月通过mitbbs的论坛找人内推,今天电面,45分钟;
可以说是只有一个题目,就是在Tree上找word,之后又变化成Graph找word

在coderpad上写的代码,感觉写起来还不错
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
上来就问我是否知道BFS,我说知道
让我在一个tree上找是否存在word并写test cases

在我写完第一遍代码之后,又让我clean up,就大概变成了下面的:
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
public class FindWordBFS {

    private class TreeNode {
        String data;
        TreeNode left;. 1point3acres.com/bbs
        TreeNode right;
        
        public TreeNode(String data) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            this.data = data;
        }. 鍥磋鎴戜滑@1point 3 acres
    }
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
    public boolean find(TreeNode root, String word) {. 1point3acres.com/bbs
        if (root == null || word == null || word.isEmpty()) return false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.鐣欏璁哄潧-涓浜-涓夊垎鍦
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        while (q.size() > 0) {.1point3acres缃
            TreeNode node = q.poll();
            if (node == null) continue;
            if (node.data.equals(word)) return true;
            q.offer(node.left);
            q.offer(node.right);. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
        
        return false;.1point3acres缃
    }. more info on 1point3acres.com

}
test cases:find(null, null);find(root, null);find(root, "");find(root, "hello");  // 树上有hellofind(null, "hello"); // 树上有hellofind(root, "world"); // 树上不存在world
一开始以为是二叉树,所以开始加了条件是往左还是往右转,但是电话那边说是unbalanced tree,我追问他澄清说:树上的 string 没有顺序,所以去掉了判断往左还是往右的两行
改完之后还是不满意,又说tree上可能有cycle,也就是说 两个节点可能有共享的 children 或 孙子节点索性,他让我改成了graph的写法, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
所以,不得不把TreeNode class 重写成这个:
private class TreeNode {
    String data;
    List<TreeNode> children;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

    public TreeNode(String data) {
        this.data = data;
        this.children = new ArrayList<>();. from: 1point3acres.com/bbs
    }
}
所以在while里面又潜逃了一个for-loop来加children nodes, 但是还是有共享children 或 孙子节点的问题,所以我又不得不加了一个HashSet来存已经遍历过的节点。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
整个40分钟用以上两种方法,很简单的问题,但是因为没问清楚,显得有点磨叽,最后我心里感觉不适很好。。。。
希望能过,但是也做好跪的准备了。
发一下面经,为明天的狗家店面攒人品!谢谢各位!. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

1

查看全部评分

susan_dly 发表于 2017-1-19 10:12:32 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主后来去onsite了吗?
回复 支持 反对

使用道具 举报

水花舞林 发表于 2017-4-2 04:31:35 | 显示全部楼层
关注一亩三分地微博:
Warald
楼主去onsite了吗
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-26 15:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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