我是家长,妈妈一枚,突然想写点什么(不太会写)

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 3602|回复: 7
收起左侧

Ebay 电面

[复制链接] |试试Instant~ |关注本帖
averillzheng 发表于 2015-8-19 05:31:22 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类General 硕士 全职@eBay - 内推 - 技术电面  | Fail | 在职跳槽

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

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

x
前一段时间,朋友内推,电面了Ebay Traffic team(bellevue, WA) 的一个社招职位.面完第一轮就挂了。面试就问了个算法题目:在一个词典中,能由元素周期表中元素(一个字母或两个字)组成的最长的单词。.1point3acres缃
当时紧张,写了个backtracking,还有个bug,所以就必须挂了。面完后,重新写了,代码在下面,如果大家有更好的方法,请讨论。-google 1point3acres

    /**. 1point3acres.com/bbs
     * sort all the words in the dictionary,
     * and then validate from the longest word.
     * once find one,.1point3acres缃
     * @param dict.鏈枃鍘熷垱鑷1point3acres璁哄潧
     * @param elements. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     * @return
     */
    private String findLongest(Set<String> dict, Set<String> elements) {-google 1point3acres
        PriorityQueue<String> queue = new PriorityQueue<String>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        });
        while (!queue.isEmpty()) {
            String tmp = queue.poll();
            if (isFormed(0, tmp, elements)) {
                return tmp;
            }
        }
        return null;
    }

鏉ユ簮涓浜.涓夊垎鍦拌鍧.     private boolean isFormed(int i, String word, Set<String> elements) {
        if (i == word.length()) {
            return true;
        }
        if (elements.contains(word.substring(i, i + 1)))
            if (isFormed(i + 1, word, elements))
                return true;
        if (i < word.length() - 1) {
            if (elements.contains(word.substring(i, i + 2)))
                if (isFormed(i + 2, word, elements)). more info on 1point3acres.com
                    return true;
        }
        return false;
    }


由于是朋友内推的,面试流程很快,自己投的那些职位,基本上没啥反应,到时有个朋友已经面了ebay好几个职位了。
另外,Ebay是没有冻结时间的,面挂可以继续投。

评分

1

查看全部评分

psychiatrichwj 发表于 2015-8-19 22:29:50 | 显示全部楼层
LZ 求内推啊 我都找不到人推eBay
回复 支持 反对

使用道具 举报

xytan123 发表于 2015-8-19 23:44:42 | 显示全部楼层
意思是把dict里面的词都写到priority queue里面?
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-8-20 00:04:43 | 显示全部楼层
我在google面过这个类似的,当时的思路也是把字典里面的词按照长度排个序,从最长的单词开始依次往下check能否用规定的元素组成。后来我问他还有啥解法吗,他说差不多就是这个。

补充内容 (2015-8-20 00:08):
BTW,你的priority queue写的有bug,用comparator的constructor还要加上pq的size参数,可以直接用collections来sort
回复 支持 反对

使用道具 举报

 楼主| averillzheng 发表于 2015-8-20 03:32:38 | 显示全部楼层
flyaway25 发表于 2015-8-20 00:04
我在google面过这个类似的,当时的思路也是把字典里面的词按照长度排个序,从最长的单词开始依次往下check ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
是这样的。 用comparator的constructor可以不指定size。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
直接用Collections.sort确实就可以了。
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-8-20 04:05:47 | 显示全部楼层
averillzheng 发表于 2015-8-20 03:32
是这样的。 用comparator的constructor可以不指定size。. 1point 3acres 璁哄潧
直接用Collections.sort确实就可以了。

你用的哪个版本的java,至少我的1.6版本java在这么写priorityqueue的时候如果不加第一个size的参数是直接报错的。

补充内容 (2015-8-20 04:08):
Sorry,刚查了下,1.8版本的java的确可以不加size了。
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2015-8-20 20:27:37 | 显示全部楼层
flyaway25 发表于 2015-8-20 00:04
我在google面过这个类似的,当时的思路也是把字典里面的词按照长度排个序,从最长的单词开始依次往下check ...

请教这样的时间复杂度是O(nk)吗,n单词个数,k单词平均长度。
回复 支持 反对

使用道具 举报

 楼主| averillzheng 发表于 2015-8-21 01:00:57 | 显示全部楼层
flyaway25 发表于 2015-8-20 04:05
你用的哪个版本的java,至少我的1.6版本java在这么写priorityqueue的时候如果不加第一个size的参数是直接 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
是的,我现在用1.8.
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-24 09:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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