推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

paypal 电面

[复制链接] |试试Instant~ |关注本帖
ft3085273 发表于 2017-8-1 00:54:05 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Paypal - 内推 - 技术电面 |Other其他

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

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

x
Timeline:7/19晚内推 20收到邮件约电面
本来是一个三姐面,接到电话临时变三哥,好像叫Brownie,也没解释为啥临时换人。
先问了经验,再问了两个基础知识,问的相当细。
然后直接上题,题目是给一串单词,找到包含不重复单词的最长sequence
举个例子 List<String> words: cars, turtles, cats, rats, dogs, rabitts,...
要求返回 List<String> 例子要返回turtles, cats, rats, dogs, rabitts,...
因为第一个单词和第三个单词都是cats,所以要把第一个cats丢掉

写的代码用的for loop里套while loop,双指针加set。
面完发现代码有点问题,就不放出来错的代码了。另外三哥也没有说是不是所有最长的sequence都要加到结果里,我当时也没有跟他确认这个问题,估计没戏了。
大家有好的解法欢迎分享。
目前想到可以的思路是dequeue。
p..s.: 在LC里没找到原题,知道题号的麻烦告诉我一下好嘛?


. Waral 鍗氬鏈夋洿澶氭枃绔,补充内容 (2017-8-1 02:27):
忘了补充一点,返回的单词顺序要保持和原list里一样,不可以改变单词顺序。

补充内容 (2017-8-2 00:40):
可能我之前没说清楚,举个例子:“A”,"B“,“C”,"A","B","C",那么我返回[“A”,"B“,“C”],["B“,“C”,"A"], [“C”,"A","B"]都可以,都是长度为3,但是我面的时候就想当然的以为返回一个就可以了,忘了确认。
 楼主| ft3085273 发表于 2017-8-1 01:04:06 | 显示全部楼层
这道题建议大家动手写一写 看似简单 写的时候未必容易 当然也可能我太弱了哈哈哈
回复 支持 反对

使用道具 举报

2011051305 发表于 2017-8-1 01:17:20 | 显示全部楼层
楼主return回去的那个list中所有单词 要保持与之前given words 的相对位置是吗?  我猜大概是建立trie树吧 如果某个单词已经出现过 就在leave加1并记录这个单词在list的位置  整个list的扫一遍之后 遍历trie树的所有terminal ?  是不是太复杂了? 求思路?  
回复 支持 反对

使用道具 举报

say543 发表于 2017-8-1 14:32:27 | 显示全部楼层
最长sequence 不是因该只有一个吗?   turtles
回复 支持 反对

使用道具 举报

cawe 发表于 2017-8-1 16:07:05 | 显示全部楼层
LC #3 类似的题?
回复 支持 反对

使用道具 举报

brn 发表于 2017-8-1 16:13:47 | 显示全部楼层
如果是 subsequence 的话,就直接把所有重复的单词全去掉只留一份就好了啊
回复 支持 反对

使用道具 举报

在浙里 发表于 2017-8-1 19:12:45 | 显示全部楼层
感谢分享,祝楼主拿offer

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| ft3085273 发表于 2017-8-2 00:41:43 | 显示全部楼层
say543 发表于 2017-8-1 14:32
最长sequence 不是因该只有一个吗?   turtles

不是找最长的那个单词,是最长的不重复单词的sequence
回复 支持 反对

使用道具 举报

 楼主| ft3085273 发表于 2017-8-2 00:42:10 | 显示全部楼层
2011051305 发表于 2017-8-1 01:17
楼主return回去的那个list中所有单词 要保持与之前given words 的相对位置是吗?  我猜大概是建立trie树吧  ...

可以用dequeue吧
回复 支持 反对

使用道具 举报

 楼主| ft3085273 发表于 2017-8-2 00:42:46 | 显示全部楼层
cawe 发表于 2017-8-1 16:07. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
LC #3 类似的题?

因为要返回list,而不是长度,所以比那题复杂一些
回复 支持 反对

使用道具 举报

 楼主| ft3085273 发表于 2017-8-2 00:45:24 | 显示全部楼层
brn 发表于 2017-8-1 16:13
如果是 subsequence 的话,就直接把所有重复的单词全去掉只留一份就好了啊

sequence要求是连续的,比如ABACAD,返回的应该是BAC和CAD,按照你说的返回的是BACD?
回复 支持 反对

使用道具 举报

cawe 发表于 2017-8-2 01:37:37 | 显示全部楼层
ft3085273 发表于 2017-8-2 00:42
因为要返回list,而不是长度,所以比那题复杂一些

记录长度和起始的index,最后加到list里,不是这样吗
回复 支持 反对

使用道具 举报

brn 发表于 2017-8-2 01:38:30 | 显示全部楼层
ft3085273 发表于 2017-8-1 11:45
sequence要求是连续的,比如ABACAD,返回的应该是BAC和CAD,按照你说的返回的是BACD?

那你说的就不是 subsequence,而是 subarray
. 鍥磋鎴戜滑@1point 3 acres
不过也不麻烦,用 two pointer 直接做就好了
回复 支持 反对

使用道具 举报

2011051305 发表于 2017-8-2 02:05:58 | 显示全部楼层
这个题目继续求大家的讨论。
题干说到"举个例子 List<String> words: cats, turtles, cats, rats, dogs, rabitts,.... (我假设题主第一个应该是cats, 不是cars哈,是不是typo?). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
返回 List<String> 例子要返回turtles, cats, rats, dogs, rabitts,... 因为第一个单词和第三个单词都是cats,所以要把第一个cats丢掉"

可是后面又说到 如果 “  “A”,"B“,“C”,"A","B","C",那么我返回[“A”,"B“,“C”],["B“,“C”,"A"], [“C”,"A","B"]都可以,都是长度为3 ”  这个我就不懂了: 题干中舍弃了第一个cats(因为cats后面出现了且只保留了最后一个cats),并且要求单词的相对顺序不变, 那么对于  “A”,"B“,“C”,"A","B","C"  我为了只保留最后一次出现的单词,且保存单词的相对顺序,不是应该返回且只返[“A”,"B“,“C”]么?
. From 1point 3acres bbs
(真不是找茬。。。还是我对于题目要求的: “对于重复单词 只返回且所有单词的保持原list的相对顺序”  这个要求我理解错了?)
回复 支持 反对

使用道具 举报

 楼主| ft3085273 发表于 2017-8-2 14:32:49 | 显示全部楼层
cawe 发表于 2017-8-2 01:37. more info on 1point3acres.com
记录长度和起始的index,最后加到list里,不是这样吗

你看我后来补充的 如果是返回List<List<Integer>>呢?

补充内容 (2017-8-2 14:42):
打错了,是String,不是Integer哈:)
回复 支持 反对

使用道具 举报

 楼主| ft3085273 发表于 2017-8-2 14:34:25 | 显示全部楼层
brn 发表于 2017-8-2 01:38
那你说的就不是 subsequence,而是 subarray

不过也不麻烦,用 two pointer 直接做就好了

三哥说是“subsequence” 我跟他还确认了一下 哪种说法不重要啦
回复 支持 反对

使用道具 举报

 楼主| ft3085273 发表于 2017-8-2 14:41:47 | 显示全部楼层
2011051305 发表于 2017-8-2 02:05
这个题目继续求大家的讨论。
题干说到"举个例子 List words: cats, turtles, cats, rats, dogs, rabitts,. ...

嗯嗯 是typo哈哈 我才发现
因为面的时候三哥没有告诉我return type,他让我自己想
所以我就问他是不是返回List<String>,他说“可以”
但是面完以后我发现自己漏考虑一点,就是如果有不止一组符合条件的list呢?那么我是不是要把所有都加到list里?
所以才有了ABCABC这个例子(这里假设每个字母都是一个String,为了方便哈),比如ABCDB那么最长的肯定是ABCD对吧,只有一个答案;但是如果是ABCDABCD,那么ABCD和BCDA和CDBA和DABC都是满足条件的list,这种情况就不止一个答案了。.1point3acres缃
我是刚开始投简历,以前也没面过,所以算法掌握程度还不够,可能哪里理解的不对,欢迎指正哈:)
如果哪里表达的不够清楚,也欢迎指出,我会继续补充的:)
回复 支持 反对

使用道具 举报

say543 发表于 2017-8-2 14:55:43 | 显示全部楼层
ft3085273 发表于 2017-8-2 14:34
三哥说是“subsequence” 我跟他还确认了一下 哪种说法不重要啦


我也觉得因该是two pointer sliding window 就可以 只是要输出list 较麻烦 但是idea 基本上可以work ?
回复 支持 反对

使用道具 举报

 楼主| ft3085273 发表于 2017-8-8 12:09:28 | 显示全部楼层
大米是怎么来的呀 我一直以为是管理员给的 看来不是啊 求大米o( ̄ヘ ̄o#)
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-22 11:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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