一亩三分地论坛

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

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

谷歌电面 02/22/2016

[复制链接] |试试Instant~ |关注本帖
mzli1989 发表于 2016-2-23 08:23:55 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

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

x
新人发帖回馈社会

面试官一美国小哥,简单闲聊后甩题:. From 1point 3acres bbs

给一个 array of words,和favorite letters, 让重新排序array,使得按照favorite letters的priority 排列。 没有包含 favorite letters 的 words 则继续按照原本字母表排序

举个栗子:array:['animal','duck','snake','zebra','horse','mouse'], favorite letter:'zh',  output--->['zebra','horse','animal','duck','mouse','snake']
array:['aab','baa','caa','aaa','aaaa'], favorite letter:'ab',  output--->['aaa','aaaa','aab','baa','caa']


算是半个水题。用随便一种sorting自己定义一个 comparator就ok。也可以用类似radix sort 来逐层比较每一个位置的letter。
但是本人脑抽,一紧张把quicksort的pivot index搞错被interviewer发现了。估计难逃一死了。

发个贴给大家看一看本人的死相多难看之余,希望大家别犯同样的傻叉错误。。


补充内容 (2016-2-24 07:39):
刚接到电话,居然过了。。美国小哥人好啊,放生积德啊!!继续准备onsite去了。大家也都加油好运!

评分

1

查看全部评分

yanggao1119 发表于 2016-2-25 12:51:11 | 显示全部楼层
overwrite comparator-google 1point3acres

  public void sortByFavorite(String[] words, String favorite) {
    // TODO: corner cases
    Map<Character, Integer> favToInd = new HashMap<>();
    for (int i = 0; i < favorite.length(); i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
      favToInd.put(favorite.charAt(i), i);
    }
    Arrays.sort(words, new Comparator<String>(){
      @Override
      public int compare(String s1, String s2) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        // case 1: both contain fav letter
        int p = 0;
        while (p < s1.length() && p < s2.length()) {
          char c1 = s1.charAt(p);.鏈枃鍘熷垱鑷1point3acres璁哄潧
          char c2 = s2.charAt(p);
          if (favToInd.containsKey(c1) && !favToInd.containsKey(c2)) {
            return -1;
          } else if (!favToInd.containsKey(c1) && favToInd.containsKey(c2)) {. 鍥磋鎴戜滑@1point 3 acres
            return 1;
          } else if (favToInd.containsKey(c1) && favToInd.containsKey(c2)) {. visit 1point3acres.com for more.
            if (favToInd.get(c1) < favToInd.get(c2)) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
              return -1;
            } else if (favToInd.get(c1) > favToInd.get(c2)) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
              return 1;
            }. from: 1point3acres.com/bbs
          }
          p++;. more info on 1point3acres.com
        }.1point3acres缃
        return s1.compareTo(s2);
      }. visit 1point3acres.com for more.
    });
  }
回复 支持 2 反对 0

使用道具 举报

iscream258 发表于 2016-2-23 09:24:46 | 显示全部楼层
居然要自己实现sort啊。。。
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-2-23 09:30:22 | 显示全部楼层
iscream258 发表于 2016-2-23 09:24. visit 1point3acres.com for more.
居然要自己实现sort啊。。。

. From 1point 3acres bbs嗯应该让自己写sorting algorithm还是挺常见的吧。
我自己脑残整出了个bug。本来应该秒的题目。
继续努力继续努力
回复 支持 反对

使用道具 举报

夹心lee 发表于 2016-2-23 09:35:06 | 显示全部楼层
请问你只面了这一道题吗?
回复 支持 反对

使用道具 举报

flashpacker 发表于 2016-2-23 09:42:14 | 显示全部楼层
祝楼主好运!有个问题呀,为什么aaa在aaaa的前面,有点疑惑呀这里
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-2-23 10:02:46 | 显示全部楼层
夹心lee 发表于 2016-2-23 09:35
请问你只面了这一道题吗?

对只问了一道。之前和之后杂七杂八聊了些有的没的。然后小哥一看时间差不多了,就不问了
所以估计要跪了
回复 支持 反对

使用道具 举报

夹心lee 发表于 2016-2-23 10:04:27 | 显示全部楼层
mzli1989 发表于 2016-2-22 21:02
对只问了一道。之前和之后杂七杂八聊了些有的没的。然后小哥一看时间差不多了,就不问了. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
所以估计要跪了

明天要面谷歌,lz不要灰心,基本都会加面的,先move on!good luck
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-2-23 10:05:18 | 显示全部楼层
flashpacker 发表于 2016-2-23 09:42
祝楼主好运!有个问题呀,为什么aaa在aaaa的前面,有点疑惑呀这里

应该比较前面三位都一样,到第四位是 ‘’ 对‘a’, 而 ‘’<‘a’.
就跟正常的字符串排序一样的规矩吧
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-2-23 10:13:08 | 显示全部楼层
夹心lee 发表于 2016-2-23 10:04
明天要面谷歌,lz不要灰心,基本都会加面的,先move on!good luck

Thx
祝好运!!!
千万要沉着。我就是一激动脑抽才整出了个低级bug
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-23 10:32:14 | 显示全部楼层
我觉得这个题有点像alien dictionary
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-2-23 11:19:05 | 显示全部楼层
kinggarden2001 发表于 2016-2-23 10:32
我觉得这个题有点像alien dictionary

对啊这样一说还真挺像。。不过刚好是反过来的,先告诉你order rule,让你排序。.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉还是alien dict更难些
回复 支持 反对

使用道具 举报

farm 发表于 2016-2-23 12:01:15 | 显示全部楼层
用随便一种sorting自己定义一个 comparator就ok

那为啥还要自己实现quick sort呢?
回复 支持 反对

使用道具 举报

ludi5522 发表于 2016-2-23 12:17:55 | 显示全部楼层
感谢楼主分享经验!
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-2-23 12:20:30 | 显示全部楼层
farm 发表于 2016-2-23 12:01
用随便一种sorting自己定义一个 comparator就ok

那为啥还要自己实现quick sort呢?

因为不从底层做,直接用现成的怕面试官不买账。。说到底就是自己作死。。
回复 支持 反对

使用道具 举报

farm 发表于 2016-2-23 12:46:30 | 显示全部楼层
mzli1989 发表于 2016-2-23 12:20
因为不从底层做,直接用现成的怕面试官不买账。。说到底就是自己作死。。

patpat 。。。 这种似乎应该先问一下面试官可不可以直接改写?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-23 14:06:14 | 显示全部楼层
mzli1989 发表于 2016-2-23 11:19
对啊这样一说还真挺像。。不过刚好是反过来的,先告诉你order rule,让你排序。
感觉还是alien dict更难 ...

恩 因为这个基本省略了build adjacent list 过程。 正确解法是 topological sort, 具体用bfs dfs 应该都行。 bfs应该更好。
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-2-23 14:37:57 | 显示全部楼层
又臭又长。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧

#include <iostream>
#include <string>. 1point 3acres 璁哄潧
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

string favLetter;
set<char> s;
extern bool myCmpHelper(string a, string b, int i, int j);
static bool myCmp(string a, string b) //比较a和b的优先级
{
        //if(a==b)return true;
        return myCmpHelper(a, b, 0, 0);
}
bool myCmpHelper(string a, string b, int i, int j)
{
        if(i < (int)a.size() && j < (int)b.size())
        {
                if(s.find(a[i]) != s.end() && s.find(b[j]) != s.end())
                {
                        if(favLetter.find_first_of(a[i]) < favLetter.find_first_of(b[j]))
                        {
                                return true;
                        }
                        else if(favLetter.find_first_of(a[i]) > favLetter.find_first_of(b[j]))
                        {. from: 1point3acres.com/bbs
                                return false;
                        }
                        return myCmpHelper(a, b, i + 1, j + 1);
                }
                else if(s.find(a[i]) == s.end() && s.find(b[j]) != s.end()). 1point3acres.com/bbs
                {
                        return false;
                }. visit 1point3acres.com for more.
                else if(s.find(a[i]) != s.end() && s.find(b[j]) == s.end())
                {
                        return true;
                }
                else
                {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        if(a[i] < b[j])
                        {
                                return true;
                        }.1point3acres缃
                        else if(a[i] > b[j]). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        {
                                return false;
                        }
                        return myCmpHelper(a, b, i + 1, j + 1);. from: 1point3acres.com/bbs
                }
        }
        if(i == a.size())return true;
        if(j == b.size())return false;
        return true;
}

void main()
{
        favLetter = "ab";
        for(int i = 0; i < (int)favLetter.size(); i++)
        { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                s.insert(favLetter[i]);
        }
        vector<string> v;. 鍥磋鎴戜滑@1point 3 acres
        v.push_back("aab");. from: 1point3acres.com/bbs
        v.push_back("baa");
        v.push_back("caa");. 1point 3acres 璁哄潧
        v.push_back("aaa");
        v.push_back("aaaa");
        sort(v.begin(), v.end(), myCmp);
        for(int i = 0; i < (int)v.size(); i++) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        {
                cout << v[i].c_str() << " ";
        }
}
回复 支持 反对

使用道具 举报

echo33 发表于 2016-2-24 02:22:58 | 显示全部楼层
想问一下,这题如果用radix sort的话,单词长度短的怎么安排?
我的意思是,比如从后位往首位sort
''aaaa'本来在'baa'前面,但是继续的话就会反过来

感觉不是很合适用radix sort
回复 支持 反对

使用道具 举报

echo33 发表于 2016-2-24 02:33:37 | 显示全部楼层
另外,quick sort并非stable sort啊,这里要求保留relative order....
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 02:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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