一亩三分地论坛

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

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

Google OA题目变了

[复制链接] |试试Instant~ |关注本帖
jacky841102 发表于 2016-10-15 17:26:54 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 实习@Google - 内推 - Onsite |Other其他

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

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

x
昨天收到的Google OA,两题跟之前的面经完全不同,发发面经攒人品

第一题:
input: 给一个string, 这个string包含英文,数字,或dash("-"),给一个K
ouput: 重新排列dash,除了第一组例外,使得dash的间隔长度是K,第一组的长度至少为一,另外所有的英文要转成大写 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
example:
s = '13aw-qwe-e', K=3  => 13-AWQ-WEE
s = '13aw-qwe-e', K=4 => 13AW-QWEE
s = '13aw-qwe-e', K=10 => 13AWQWEE. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

第二题:
给一个binary search tree 的root, 给一个范围[A, B] . Waral 鍗氬鏈夋洿澶氭枃绔,
要求找出最大的substree, return 最大的size, 其中所有node的值都在[A, B]之内,[A, B]有没有包含A和B题目没说清楚,我当有做了
example:   
A, B = 2, 5   

      5
    /
1
   \
     2 . 1point 3acres 璁哄潧
       \
         3
           \
             4
output: 3(root为2的subtree)

不知道这个OA是什么意思的,先安排了电面才接到这个OA

评分

1

查看全部评分

 楼主| jacky841102 发表于 2016-10-16 14:08:30 | 显示全部楼层
wzyath 发表于 2016-10-16 13:21
求问第二题该怎么做啊?是要用 in-order traversal吗?

我是recursion下去,
def recur(A, B, node) 返回以当前node为root的最大的subtree,其所有node都在A,B之间
base cases:. 鍥磋鎴戜滑@1point 3 acres
1. Null -> return 0
2. 叶节点
    if  A <= node.val <= B
        return 1
    else
        return 0. visit 1point3acres.com for more.
  
general cases:
1. node.val < A:
recur(A,B, node.right)
return 0
2. node.val > B:
recur(A, B, node.left)
return 0
3. A <= node.val <= B
分成三种. 1point3acres.com/bbs
  (1) node.left == null
       m = recur(A, B, node.right)
       return m + 1 if m != 0 else return 0. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  (2) node.right == null
        m = recur(A, B, node.left)
       return m + 1 if m != 0 else return 0
   (3) node.left 和 node.right 都不是 null:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        left = recur(A, B, node.left)
        right = recur(A, B, node.right)
        return left + right + 1 if left and right else 0
.1point3acres缃
在每次return之前另外用个global variable 存找到的最大值

我的方法感觉太麻烦,应该有比较好的方法
     

回复 支持 1 反对 0

使用道具 举报

grace828822 发表于 2016-10-16 03:21:54 | 显示全部楼层
感谢lz分享,想问lz是面明年何时的全职?
回复 支持 反对

使用道具 举报

monster_ustc 发表于 2016-10-16 03:22:50 | 显示全部楼层
size 是什么意思?是指depth还是number of nodes?
回复 支持 反对

使用道具 举报

zws1818918 发表于 2016-10-16 13:06:59 | 显示全部楼层
请问楼主是几号做的呢?
回复 支持 反对

使用道具 举报

wzyath 发表于 2016-10-16 13:21:16 | 显示全部楼层
求问第二题该怎么做啊?是要用 in-order traversal吗?
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-10-16 13:58:13 | 显示全部楼层
monster_ustc 发表于 2016-10-16 03:22. 1point 3acres 璁哄潧
size 是什么意思?是指depth还是number of nodes?

number of nodes
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-10-16 13:58:29 | 显示全部楼层
zws1818918 发表于 2016-10-16 13:06
请问楼主是几号做的呢?

10月15號
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-10-16 13:59:06 | 显示全部楼层
grace828822 发表于 2016-10-16 03:21
感谢lz分享,想问lz是面明年何时的全职?

我是面2017summer的实习
回复 支持 反对

使用道具 举报

zws1818918 发表于 2016-10-16 15:23:51 | 显示全部楼层
jacky841102 发表于 2016-10-16 13:59
我是面2017summer的实习

请问下楼主第二题是什么思路呢?感觉不太想得到什么方法。
回复 支持 反对

使用道具 举报

琐爱 发表于 2016-10-17 03:43:57 | 显示全部楼层
感谢楼主分享,请问这个OA可以用python写吗?
回复 支持 反对

使用道具 举报

azyuqian 发表于 2016-10-19 02:16:47 | 显示全部楼层
第一题的dash间隔是从最后一个char开始算起的吗?
回复 支持 反对

使用道具 举报

于夫罗 发表于 2016-10-20 07:21:33 | 显示全部楼层
同问第一题的dash间隔怎么算起,没太看懂
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-10-20 09:16:21 | 显示全部楼层
azyuqian 发表于 2016-10-19 02:16
第一题的dash间隔是从最后一个char开始算起的吗?

是从后面算起
回复 支持 反对

使用道具 举报

dokolo 发表于 2016-10-24 13:43:40 | 显示全部楼层
不是太懂第一题的意思,想请教一下。
例如输入是 13aw-qwe-e 和 2
输出应该是 13-AW-QW-EE 还是 13AW-QW-EE ?
给的例子里有输出的dash更少的情况, 但是没说明dash更多会如何
回复 支持 反对

使用道具 举报

 楼主| jacky841102 发表于 2016-10-24 20:59:04 | 显示全部楼层
dokolo 发表于 2016-10-24 13:43
不是太懂第一题的意思,想请教一下。
例如输入是 13aw-qwe-e 和 2
输出应该是 13-AW-QW-EE 还是 13AW-QW- ...
. 鍥磋鎴戜滑@1point 3 acres
原来dash的个数不重要,
13aw-qwe-e 和 2. visit 1point3acres.com for more.

output应该是13-AW-QW-EE
回复 支持 反对

使用道具 举报

笑眯眯的白云 发表于 2016-10-28 05:12:12 | 显示全部楼层
楼主你好, 请问这个OA 能不能 自己跑 custom testcase??
回复 支持 反对

使用道具 举报

Catherine8832 发表于 2016-11-24 09:25:56 | 显示全部楼层
楼主可以分享下电面的题目吗?非常感谢
回复 支持 反对

使用道具 举报

agraynel 发表于 2016-11-29 05:02:28 | 显示全部楼层
笑眯眯的白云 发表于 2016-10-28 05:12. 1point 3acres 璁哄潧
楼主你好, 请问这个OA 能不能 自己跑 custom testcase??

同问。。今晚做OA好怕
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 19:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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