一亩三分地论坛

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

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

G家第一轮电面,5分钟前的新鲜狗粮_(:3TZ)_

[复制链接] |试试Instant~ |关注本帖
CeciliaM 发表于 2016-8-5 07:01:19 | 显示全部楼层 |阅读模式

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

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

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

x
跪跪跪跪跪一紧张写了一堆bug,对不起这么好的题……(哭泣)发个贴求过面试……

和论坛里说的一样,对面惯常迟到5分钟。啥也没问,直入正题。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. Waral 鍗氬鏈夋洿澶氭枃绔,
第一题:Input一个string,判断它是否存在一种permutation是palindrome。.鏈枃鍘熷垱鑷1point3acres璁哄潧
follow up: 如何test这个function。


正确回答是阐述一遍测试体系unit test, integration test, leak test, performance test 等等……-google 1point3acres
小哥人很好,我没说到的他都给我科普了一遍。



.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题:Hamming Weight,也就是count bits 1 in a number.
写完O(n)了以后不出所料地让优化。
幸好我在对方说题目的时候就机智地打开了wiki,照着wiki上的敲了一遍。


感觉身体被掏空(捂心口)


. from: 1point3acres.com/bbs
yiwen_15 发表于 2016-8-5 10:09:10 | 显示全部楼层
请问楼主第一道题是怎么做的?复杂度如何?
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-8-5 10:17:44 | 显示全部楼层
yiwen_15 发表于 2016-8-5 10:09
请问楼主第一道题是怎么做的?复杂度如何?
.1point3acres缃
我在网上搜到这样的答案:
如果要有palindrome
如果字符串长度是奇数,那么只能有一个字符是奇数个数。
如果字符串长度是偶数,那么所有字符必须是偶数个数。
除此之外,就不会有Palindrome
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-8-5 10:56:51 | 显示全部楼层
yiwen_15 发表于 2016-8-5 10:09. 1point 3acres 璁哄潧
请问楼主第一道题是怎么做的?复杂度如何?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
同楼上说的,长度奇数的字符串只能有一个奇数字母,偶数字符串所有字母都必须是偶数。
用int map[128]来存,时间O(n),空间O(1)
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-8-5 12:18:26 | 显示全部楼层
谢谢楼主分享。这个哥哥还挺nice,
祝好运
回复 支持 反对

使用道具 举报

jellyld 发表于 2016-8-21 04:01:36 | 显示全部楼层
请问各路大神,how to test this function 具体要怎么答啊,有什么参考资料吗,跪谢!
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-8-24 15:58:22 | 显示全部楼层
jellyld 发表于 2016-8-21 04:01.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问各路大神,how to test this function 具体要怎么答啊,有什么参考资料吗,跪谢!

Integration test, Unit test, Leak test, Performance test
回复 支持 反对

使用道具 举报

dimi 发表于 2016-8-24 22:55:20 来自手机 | 显示全部楼层
第二题怎么优化的
回复 支持 反对

使用道具 举报

Olivialoveslife 发表于 2016-8-24 23:00:47 | 显示全部楼层
楼主出结果了吗?
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-8-24 23:01:38 | 显示全部楼层
第二题优化,我是想不出来的,等于在问我strstr怎么有话. haha我就挂了
回复 支持 反对

使用道具 举报

alyssum14 发表于 2016-8-24 23:13:19 | 显示全部楼层
第一题应该是leetcode 里的palindrome permutation, 第二题是 number of 1 bit. 关于测试体系那个部分,能不能麻烦楼主说的详细一点呢,谢谢了~
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-19 06:59:36 | 显示全部楼层
为啥楼主题如此之简单
回复 支持 反对

使用道具 举报

 楼主| CeciliaM 发表于 2016-9-19 07:53:28 | 显示全部楼层
zyoppy008 发表于 2016-9-19 06:59
为啥楼主题如此之简单

听对面的口吻,感觉主要是想考第一题follow up的测试体系,和第二题的分治法_(・ω・」 ∠)_  
“这道题本身很简单” 对方这样说
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-19 08:08:04 | 显示全部楼层
CeciliaM 发表于 2016-9-19 07:53
听对面的口吻,感觉主要是想考第一题follow up的测试体系,和第二题的分治法_(・ω・&#65379 ...

第二题咋个。。分治法。优化的话不是 稀疏1 或者密集1 的话优化吗?
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-9-20 02:30:00 | 显示全部楼层
zyoppy008 发表于 2016-9-19 08:08
第二题咋个。。分治法。优化的话不是 稀疏1 或者密集1 的话优化吗?

稀疏1 优化咋写程序?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-20 10:26:11 | 显示全部楼层
请问lz第二题怎么优化的?输入是binary形式的string吗
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-20 10:28:25 | 显示全部楼层
CeciliaM 发表于 2016-9-19 07:53
听对面的口吻,感觉主要是想考第一题follow up的测试体系,和第二题的分治法_(・ω・&#65379 ...

分治法 根据master theorem属于case 1吧?那不还是O(n)吗?
回复 支持 反对

使用道具 举报

hulahu 发表于 2016-9-24 08:40:38 | 显示全部楼层
Count 1 bits O(n)怎么做? 不是 32 bits 吗?
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-10-30 06:14:46 | 显示全部楼层
第一题 其实就是lc 原题 palindrome permutation
回复 支持 反对

使用道具 举报

coolkid11 发表于 2016-10-31 04:47:53 | 显示全部楼层
http://stackoverflow.com/questions/15233121/calculating-hamming-weight-in-o1

stackoverflow 上的O(1) 解法
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 11:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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