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

Uber一面感觉要跪

全局:

2017(1-3月) 码农类General 硕士 实习@uber - 内推 - 技术电面  | | Other | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

刚刚结束的电面,感觉有点崩的。breakingbad,好像之前面经出现很多次,但是没有详细的介绍,把题想简单了。。

具体介绍一下这个题, input是String[] array(大小写都有), 和
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
这样。

开始太紧张了做了一会才开始急急忙忙的写Trie。

uber是不是一定要跑过才可以啊。。。好想哭。。。



评分

参与人数 7大米 +33 收起 理由
aptaua + 1 给你点个赞!
ARUI35 + 10 很有用的信息!
UC小王子 + 3 给你点个赞!
Booky + 3 别担心!思路是对的应该还好!
松松的鞋带儿 + 3 感谢分享!

查看全部评分


上一篇:Amazon Phone interview 有人接过么
下一篇:BloomBerg 电面
推荐
xmasry 2017-12-7 15:26:46 | 只看该作者
全局:
  1. public String format(String name, String[] array){
  2.                 if(array.length == 0 || name == null || name.length() == 0){
  3.                         return name;
  4.                 }
  5.                 Map<Character, Set<String>> dict = getDict(array);
  6.                 StringBuilder sb = new StringBuilder();
  7.                 for(int i=0; i<name.length(); ){
  8.                         Character c = new Character(name.charAt(i));
  9.                         String str = match(c, i, name, dict);
  10.                         if(str.length()==0){
  11.                                 sb.append(c);
  12.                                 i++ ;
  13.                         }else{
  14.                                 sb.append("[").append(str).append("]");
  15.                                 i+=str.length();
  16.                         }
  17.                 }
  18.                 return sb.toString();
  19.         }
  20.        
  21.         private String match(Character c, int index, String name, Map<Character, Set<String>> dict){
  22.                 String maxMatch = "";
  23.                 if(!dict.containsKey(c)){
  24.                         return maxMatch;
  25.                 }
  26.                 Set<String> set = dict.get(c);
  27.                
  28.                 for(String s: set){
  29.                         if(s.length() <= (name.length() - index)
  30.                                         && name.indexOf(s) == index && s.length()>maxMatch.length()){                       
  31.                                         maxMatch = s;
  32.                         }
  33.                 }
  34.                
  35.                 if(maxMatch.length()!=0){
  36.                         maxMatch = maxMatch.replaceFirst(c.toString(), c.toString().toUpperCase());                       
  37.                 }
  38.                
  39.                 return maxMatch;
  40.         }
  41.        
  42.         private Map<Character, Set<String>> getDict(String[] array){
  43.                 Map<Character, Set<String>> dict =  new HashMap<>();
  44.                 for(String str:array){
  45.                         str = str.toLowerCase();
  46.                         Character c = new Character(str.charAt(0));
  47.                         Set<String> set=dict.get(c);
  48.                         if(set == null){
  49.                                 set = new HashSet<String>();
  50.                                 dict.put(c, set);
  51.                         }
  52.                         set.add(str.toLowerCase());
  53.                 }
  54.                 return dict;
  55.         }
复制代码
回复

使用道具 举报

全局:
  1. class Main {
  2.   static class TrieNode {
  3.       char key;
  4.       TrieNode[] children;
  5.       boolean hasword;
  6.       TrieNode(Character key) {
  7.          
  8.           children = new TrieNode[26];
  9.           this.key = key;
  10.           hasword = false;
  11.       }
  12.       TrieNode() {
  13.           this.key = ' ';
  14.           children = new TrieNode[26];
  15.           hasword = false;
  16.       }
  17.   }
  18.   
  19.   static class TrieTree {
  20.       TrieNode root;
  21.       TrieTree() {
  22.           root = new TrieNode();
  23.       }
  24.       public void insert(String word) {
  25.           TrieNode cur = root;
  26.           for (int i = 0; i < word.length(); i++) {
  27.               if (cur.children[word.charAt(i) - 'a'] == null)
  28.                   cur.children[word.charAt(i) - 'a'] = new TrieNode(word.charAt(i));
  29.               cur = cur.children[word.charAt(i) - 'a'];
  30.           }
  31.           cur.hasword = true;
  32.       }
  33.   }
  34.   private static String searchWords(String[] dict, String str) {
  35.       TrieTree trietree = new TrieTree();
  36.       for (int i = 0; i < dict.length; i++) {
  37.           trietree.insert(dict[i]);
  38.       }
  39.       StringBuilder sb = new StringBuilder();
  40.       int slow = 0, fast = 0;
  41.       while (fast < str.length()) {
  42.           TrieNode cur = trietree.root;
  43.           int counter = 0;
  44.           while (fast < str.length() && cur.children[str.charAt(fast) - 'a'] != null) {
  45.               cur = cur.children[str.charAt(fast) - 'a'];
  46.               counter++;
  47.               fast++;
  48.           }
  49.           if (counter > 0) {//wrong: 忘记回退了.
  50.               fast--;
  51.               counter = 0;
  52.           }
  53.           if (cur.hasword) {//hasword 用于区分ddt是个词,但是不是个完整的词这个情况
  54.               int i = slow;
  55.               sb.append("[").append(Character.toUpperCase(str.charAt(i++)));
  56.               while (i < fast) {
  57.                   sb.append(str.charAt(i++));
  58.               }
  59.               sb.append("]");
  60.           } else {
  61.               sb.append(str.substring(slow, fast + 1));
  62.           }
  63.           fast++;
  64.           slow = fast;
  65.          
  66.       }
  67.       return sb.toString();
  68.   }
  69.   
  70.   public static void main(String[] args) {
  71.     String[] dict = {"b", "bc","cde", "e","tt","ertt","ddr"};
  72.     String str = "abcdeddertte";
  73.     System.out.println(searchWords(dict, str));
  74.   }
  75. }
复制代码
回复

使用道具 举报

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

使用道具 举报

🔗
adrianliu729 2017-2-28 04:46:02 | 只看该作者
全局:
你写完Trie了应该没问题了吧?主程序应该就是一个loop了。
回复

使用道具 举报

🔗
 楼主| yevita 2017-2-28 05:01:49 | 只看该作者
全局:
adrianliu729 发表于 2017-2-28 04:46
你写完Trie了应该没问题了吧?主程序应该就是一个loop了。

不知道bugfree重不重要。。哎
回复

使用道具 举报

🔗
zws1818918 2017-3-19 03:43:10 | 只看该作者
全局:
请问下楼主,这题就叫breakingbad吗?
回复

使用道具 举报

🔗
UC小王子 2017-11-14 11:40:30 | 只看该作者
全局:
请问怎么匹配bc呢。。。。字典里面不是只有Bc么
回复

使用道具 举报

🔗
 楼主| yevita 2017-11-14 12:18:33 | 只看该作者
全局:
sherlockzzq 发表于 2017-11-14 11:40
请问怎么匹配bc呢。。。。字典里面不是只有Bc么

记忆有点模糊,应该是匹配的时候可以不考虑大小写
回复

使用道具 举报

🔗
UC小王子 2017-11-14 12:32:32 | 只看该作者
全局:
yevita 发表于 2017-11-14 12:18
记忆有点模糊,应该是匹配的时候可以不考虑大小写

好的 谢谢!!!
回复

使用道具 举报

🔗
ARUI35 2017-11-18 05:47:06 | 只看该作者
全局:
请问系楼主如果array是{“mn”}, 而name是“m”,output是[M]还是空?
问题就是“m”的substring只有“m”和“”。然后“m”是不是不算出现在了array中,只有“mn”才能算出现在了array中?
回复

使用道具 举报

🔗
 楼主| yevita 2017-11-20 13:31:47 | 只看该作者
全局:
ARUI35 发表于 2017-11-18 05:47
请问系楼主如果array是{“mn”}, 而name是“m”,output是[M]还是空?
问题就是“m”的substring只有“m” ...

output是m,mn出现在array中,m找不到匹配
回复

使用道具 举报

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

本版积分规则

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