May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

Google OA题目变了

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

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

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

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

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

第一题:.鐣欏璁哄潧-涓浜-涓夊垎鍦
input: 给一个string, 这个string包含英文,数字,或dash("-"),给一个K.鏈枃鍘熷垱鑷1point3acres璁哄潧
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] . visit 1point3acres.com for more.
要求找出最大的substree, return 最大的size, 其中所有node的值都在[A, B]之内,[A, B]有没有包含A和B题目没说清楚,我当有做了-google 1point3acres
example:   
A, B = 2, 5   

      5
    /
1
   \
     2 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
       \. 1point3acres.com/bbs
         3
           \
             4
output: 3(root为2的subtree). Waral 鍗氬鏈夋洿澶氭枃绔,

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

评分

2

查看全部评分

 楼主| jacky841102 发表于 2016-10-16 14:08:30 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
wzyath 发表于 2016-10-16 13:21. from: 1point3acres.com/bbs
求问第二题该怎么做啊?是要用 in-order traversal吗?

我是recursion下去,
def recur(A, B, node) 返回以当前node为root的最大的subtree,其所有node都在A,B之间
base cases:
1. Null -> return 0.鏈枃鍘熷垱鑷1point3acres璁哄潧
2. 叶节点
    if  A <= node.val <= B -google 1point3acres
        return 1
    else
        return 0
  
general cases:.1point3acres缃
1. node.val < A:
recur(A,B, node.right)
return 0
2. node.val > B:
recur(A, B, node.left). Waral 鍗氬鏈夋洿澶氭枃绔,
return 0
3. A <= node.val <= B
分成三种
  (1) node.left == null
       m = recur(A, B, node.right)
       return m + 1 if m != 0 else return 0
  (2) node.right == null. From 1point 3acres bbs
        m = recur(A, B, node.left). 鍥磋鎴戜滑@1point 3 acres
       return m + 1 if m != 0 else return 0.鏈枃鍘熷垱鑷1point3acres璁哄潧
   (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

在每次return之前另外用个global variable 存找到的最大值

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

回复 支持 1 反对 0

使用道具 举报

grace828822 发表于 2016-10-16 03:21:54 | 显示全部楼层
关注一亩三分地微博:
Warald
感谢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
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是面明年何时的全职?

.鏈枃鍘熷垱鑷1point3acres璁哄潧我是面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开始算起的吗?
. 鍥磋鎴戜滑@1point 3 acres
是从后面算起
回复 支持 反对

使用道具 举报

dokolo 发表于 2016-10-24 13:43:40 | 显示全部楼层
不是太懂第一题的意思,想请教一下。. more info on 1point3acres.com
例如输入是 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- ...

原来dash的个数不重要,.1point3acres缃
13aw-qwe-e 和 2

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
楼主你好, 请问这个OA 能不能 自己跑 custom testcase??

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

使用道具 举报

luna29 发表于 2016-12-12 23:47:38 | 显示全部楼层
想请问楼主 如果第一题给出的情况是“14-----------” k = 4的话应该怎么考虑呢 输出的话是不是就应该是“14-----------” ?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-23 00:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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