一亩三分地论坛

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

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

Google 面经

[复制链接] |试试Instant~ |关注本帖
wzf1943 发表于 2015-9-3 02:00:41 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
两个题
1. Find closest bianry search tree value. leetcode 原题
2. Give you a sorted dictionary and a prefix. Find the first valid prefix string for this dictionary.

. 1point3acres.com/bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| wzf1943 发表于 2015-9-3 02:01:25 | 显示全部楼层
BTW 第二题有 1 million 个 word
回复 支持 反对

使用道具 举报

discoveryi 发表于 2015-9-3 02:02:26 | 显示全部楼层
啊,第一题是leetcode的付费题啊。
LZ有代码吗?
回复 支持 反对

使用道具 举报

 楼主| wzf1943 发表于 2015-9-3 02:05:07 | 显示全部楼层
discoveryi 发表于 2015-9-2 12:02
啊,第一题是leetcode的付费题啊。-google 1point3acres
LZ有代码吗?

class Solution {
    int res = INT_MAX;
public:
    int closestValue(TreeNode* root, double target) {
        if (root == NULL) return res;. 鍥磋鎴戜滑@1point 3 acres
        double cur = (double) (root -> val);
        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        if (root -> val == target) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
            return root -> val;
. 鍥磋鎴戜滑@1point 3 acres        }
-google 1point3acres        
        if (res == INT_MAX || abs (res - target) > abs (cur - target)) {
            res = cur;
        }
        
        if (cur > target) {
         return    closestValue (root -> left, target); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        } else {. from: 1point3acres.com/bbs
         return    closestValue (root -> right, target);
        }
      
    }

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

hello2pig 发表于 2015-9-3 02:22:39 | 显示全部楼层
楼主第二题的思路能说说么?

补充内容 (2015-9-3 02:25):.1point3acres缃
可以对prefix逐个char依次二分搜索吗
回复 支持 反对

使用道具 举报

ppiglett 发表于 2015-9-3 04:01:05 来自手机 | 显示全部楼层
第二题用trie tree?
回复 支持 反对

使用道具 举报

hanchen999 发表于 2015-9-3 04:24:02 | 显示全部楼层
第二题是用二分么?但是很多重复所以找到一个之后向左遍历?
回复 支持 反对

使用道具 举报

mint0715 发表于 2015-9-3 04:46:54 | 显示全部楼层
我猜第二题二分,即使mid匹配了prefix,也要递归调用(start, mid)继续找就行了。
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-8 07:34:59 | 显示全部楼层
wzf1943 发表于 2015-9-3 02:01
BTW 第二题有 1 million 个 word

问一下LZ first valid prefix 是什么意思? 原本给定的一个input prefix 是什么作用?
回复 支持 反对

使用道具 举报

wodemajia 发表于 2015-9-8 08:09:40 | 显示全部楼层
co ask, first valid prefix是什么意思?
回复 支持 反对

使用道具 举报

mint0715 发表于 2015-9-9 06:25:51 | 显示全部楼层
wodemajia 发表于 2015-9-8 08:09
co ask, first valid prefix是什么意思?

例子:
字典:abc, cab, cat, cataclysm, catch
prefix: cat
输出: cat
prefix: catc
输出:catch. Waral 鍗氬鏈夋洿澶氭枃绔,

我猜的
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-9 08:09:02 | 显示全部楼层
lz第二道, 您是用binary search吗?
回复 支持 反对

使用道具 举报

 楼主| wzf1943 发表于 2015-9-9 16:44:15 | 显示全部楼层
mint0715 发表于 2015-9-8 16:25
例子:
字典:abc, cab, cat, cataclysm, catch
prefix: cat

是这个意思~~~~
回复 支持 反对

使用道具 举报

easonliu 发表于 2015-9-9 19:38:23 | 显示全部楼层
第二题不就是lower_bound的变形吗?
回复 支持 反对

使用道具 举报

colfighter 发表于 2015-9-23 03:57:57 | 显示全部楼层
LZ能说下第二题思路么? 谢谢
回复 支持 反对

使用道具 举报

ck2016 发表于 2016-5-6 01:00:44 | 显示全部楼层
楼主现在不写驱动了么。。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 04:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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