📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: silverwind
跳转到指定楼层
上一主题 下一主题
收起左侧

Google电面被虐成X

 
🔗
LawranceH 2015-2-24 12:38:16 | 只看该作者
全局:
tanis 发表于 2015-2-24 09:39
我也是他,同样题,挺简单的啊。。。就用个ArrayList对比时new一个新的instance,每对一个就remove一个,最 ...

你确定吗??... 你的方法我都说了. 但他还是让我优化.......
回复

使用道具 举报

🔗
LawranceH 2015-2-24 12:39:31 | 只看该作者
全局:
HELLODC 发表于 2015-2-24 12:31
我今天面试也是全程无声,当时没听清名字啥的,现在想来好像就是他...处女面啊...

我处女面也是他....都不知道交流啊..
回复

使用道具 举报

🔗
leyhzm 2015-2-24 13:33:28 | 只看该作者
全局:
那输入字符串的字母的顺序要和字典里一样麻?
比如"TR45" 字典里有 “SORT”,顺序不一样也是算的对吗?

PS:楼主不要难过~赞个人品下次就会有好运~
回复

使用道具 举报

🔗
yarmyarch 2015-2-24 21:13:07 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
KevinFromJail 2015-2-24 23:37:39 | 只看该作者
全局:
trie还是可行的。 每个字典里面的数排序去重 然后放进trie里面。注意更新每个节点以保持最短长度。
一个新的需要判断的词进来,也是排序去重,然后在trie里面查找即可。

补充内容 (2015-2-24 23:39):
啊 不太对。 因为字典里面的词有可能包括我们要查找的词 而不是完全匹配。
回复

使用道具 举报

🔗
mk01 2015-2-25 01:17:22 | 只看该作者
全局:
想了半天发现可以把每个String表示成一个int,然后利用AND判断两个String里字符的交集,这样对已每个字典里的词只需要花O(1)的时间,
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Comparator;
  4. import java.util.List;

  5. public class ShortestDict {
  6.     public static void main(String[] args) {
  7.         String[] words = new String[]{"so99ort", "so1rt", "skype", "so11rt", "apppples"};
  8.         ShortestDict d = new ShortestDict(words);
  9.         
  10.         System.out.println(d.getShortest("SR 456 T"));
  11.         
  12.     }
  13.    
  14.     private List<String> wordList;
  15.     private List<Integer> maskList;

  16.     public ShortestDict(String[] wordArr) {
  17.         wordList = new ArrayList<String>();
  18.         maskList = new ArrayList<Integer>();

  19.         Comparator<String> cmp = new Comparator<String>() {
  20.             public int compare(String s1, String s2) {
  21.                 return s1.length() - s2.length();
  22.             }
  23.         };

  24.         Arrays.sort(wordArr, cmp);

  25.         for (String word : wordArr) {
  26.             wordList.add(word);
  27.             maskList.add(getMask(word));
  28.         }
  29.     }

  30.     public String getShortest(String inputWord) {
  31.         int inputMask = getMask(inputWord);
  32.         for (int i = 0; i < maskList.size(); i++) {
  33.             if (inputMask == (inputMask & maskList.get(i))) {
  34.                 return wordList.get(i);
  35.             }
  36.         }

  37.         return "";
  38.     }

  39.     public static int getMask(String word) {
  40.         int mask = 0;
  41.         word = word.toLowerCase();
  42.         for (char c : word.toCharArray()) {
  43.             if ('a' <= c && c <= 'z') {
  44.                 mask |= (1 << (c - 'a'));
  45.             }
  46.         }
  47.         return mask;
  48.     }


  49. }
复制代码
回复

使用道具 举报

🔗
zengm321 2015-2-25 01:59:01 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
kaimiku 2015-2-25 03:50:28 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
liuliuion1 2015-2-25 04:18:06 | 只看该作者
全局:
tanis 发表于 2015-2-24 11:43
嗯,上学期期末面的,回国签证被check了onsite推迟了,还没面呢。
基本算是brutal force, 我用Java写的 ...

请问图片在哪里啊?
回复

使用道具 举报

🔗
YY大帝 2015-2-25 05:41:46 | 只看该作者
全局:
silverwind 发表于 2015-2-24 11:07
是不是可以详细展开一下叙述呢,恕我愚钝=。=,谢谢了
顺带一提……我一点都不觉得他紧张,也许你和他面 ...

可不可以把所有string都sort了,然后remove dup char,轮次比较,大概是O(n*m)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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