传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1385|回复: 12
收起左侧

Uber 电面+onsite

[复制链接] |试试Instant~ |关注本帖
ThinkDeeper2 发表于 2017-7-28 22:38:42 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 本科 全职@Uber - 内推 - 技术电面 Onsite |Fail在职跳槽

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

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

x
电面是 insert_into_cycle_linked_list.html: https://moonlightsd.gitbooks.io/ ... le_linked_list.html

onsite:
1. 给出 [“1999-02-13”, “2001-03-14"] 打印出中间所有的月份 [“1999-02-13”, “1999-02-28"],[“1999-03-01”, “1999-03-31"] ...  ["2001-03-01", “2001-03-14"]. 鍥磋鎴戜滑@1point 3 acres
当然input可以是任意年月日。要求当场能运行,中间有问题不回答, 让自己查 google 和 stackoverflow. 最后code都没有写完,更别提其它的了。我写的时候也没有什么技巧,就是各种判断和打印, 但边界条件过多,相同的年份,月份,起始月份,结束月份。。。在这里请教高手指点clean 的程序。
2.  https://leetcode.com/problems/ma ... -k/tabs/description
3. design typehead, 实现trienode 和 trie 类 还有buildTrie 和 searchTrieLeafNode方法
4. hc聊一下 why uber, why leave your current job.
5. design pokemonGo. pokemonGo有三个要求,显示pokemonStop, spinpokeMonstop, catchPokemon. 在提到要把pokemonStop信息存储的时候,卡住了。因为pokemonstop的数目很多要多台DB, 如何sharding成了问题。如果按照id sharding,用坐标查询附近的stop就很麻烦。如果按城市存储,查询的坐标正好落在城市边缘就要去另外一个数据库查询。如果DB存一些周围城市stop 的duplication, consistence 就成了问题。请高手指点如何存储stop 的信息并且方便按cutomer的位置进行快速的查询。

评分

1

查看全部评分

luobo 发表于 2017-7-29 14:31:18 | 显示全部楼层
        LocalDate end = LocalDate.of(2001, 03, 14);
        LocalDate start = LocalDate.of(1999, 02, 13); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        LocalDate nextDay = start;
        while (nextDay.isBefore(end) || nextDay.equals(end)) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                System.out.print(nextDay);
                nextDay = nextDay.with(lastDayOfMonth());
                if (nextDay.isBefore(end)) {
                        System.out.print("--" + nextDay);
                        System.out.println();
                }
                nextDay = nextDay.plusDays(1);
        }. From 1point 3acres bbs
        if (nextDay.isAfter(end)) System.out.print("--" + end);.鐣欏璁哄潧-涓浜-涓夊垎鍦
        System.out.println();
回复 支持 1 反对 0

使用道具 举报

jingshihao 发表于 2017-7-28 22:48:35 | 显示全部楼层
感觉system design好像很难的样子,请问楼主如果是new grad会考这么难的system design吗?
回复 支持 反对

使用道具 举报

 楼主| ThinkDeeper2 发表于 2017-7-29 07:05:36 | 显示全部楼层
第一题应该用 import java.time.LocalDate;
回复 支持 反对

使用道具 举报

风华义气 发表于 2017-7-29 09:02:39 | 显示全部楼层
为啥感觉面试的时候好难啊
回复 支持 反对

使用道具 举报

saklyn 发表于 2017-7-29 11:52:07 | 显示全部楼层
第一题有个方法:提前做好每年每个月的表格,就用自带的函数,比如python的datetime。出来[“1999-01-01“, “1999-01-31“]...["2001-12-01", "2001-12-31"],然后直接滤掉时间结尾在在[“1999-02-13“]之前和开头在["2001-03-14"]之后的。剩下了[“1999-02-01“, “1999-02-28“]...["2001-03-01", "2001-03-31"]。然后比较[“1999-02-13“]和第一个的开始,即[“1999-02-01“],因为不相等,故代替。再比较["2001-03-14"]和最后一个的结束,即["2001-03-31"],因为不想等,故代替。
回复 支持 反对

使用道具 举报

sterne 发表于 2017-7-30 12:48:29 | 显示全部楼层
请问楼主面的哪个组?感觉偏难
回复 支持 反对

使用道具 举报

sterne 发表于 2017-7-30 13:09:23 | 显示全部楼层
sterne 发表于 2017-7-30 12:48
请问楼主面的哪个组?感觉偏难

最后一题, PokemonGo sharding 问题,跟facebook shard friendship graph类似。 如何把朋友关系放到不同的machine上,FB的解决方案是TAO + Dragon(Social Hash)。sharding key我觉得可以用geohash. https://code.facebook.com/posts/ ... graph-query-engine/
回复 支持 反对

使用道具 举报

endofunctor 发表于 2017-7-30 14:33:20 | 显示全部楼层
最后一题可以用Geohashing存stop + quad tree存地形吗?render的时候同时读stop geolocation和地形。.1point3acres缃
一个想法不一定对
回复 支持 反对

使用道具 举报

endofunctor 发表于 2017-8-4 16:39:30 | 显示全部楼层
试着写了下第一题(没重构过,写的比较丑)。。。. Waral 鍗氬鏈夋洿澶氭枃绔,
  1. vector<pair<string, string> > getSpan(const string& start, const string& end) {
  2.   int i = 0;
  3.   int year_start;
  4.   int month_start;
  5.   int day_start;
  6.   int year_end;
  7.   int month_end;
    . from: 1point3acres.com/bbs
  8.   int day_end;
  9.   int j = 0;
  10.   
  11.   while (j < start.size() && start[j] != '-')
    . more info on 1point3acres.com
  12.     ++j;. visit 1point3acres.com for more.
  13.   year_start = stoi(start.substr(i, j - i));
  14.   ++j;
  15.   i = j;
  16.   while (j < start.size() && start[j] != '-')
  17.     ++j;
  18.   month_start = stoi(start.substr(i, j - i));
  19.   ++j;. 鍥磋鎴戜滑@1point 3 acres
  20.   i = j;. from: 1point3acres.com/bbs
  21.   while (j < start.size() && start[j] != '-')
  22.     ++j;
  23.   day_start = stoi(start.substr(i, j - i));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  24.   i = 0;
  25.   j = 0;
  26.   while (j < end.size() && end[j] != '-').1point3acres缃
  27.     ++j;
  28.   year_end = stoi(end.substr(i, j - i));
  29.   ++j;
  30.   i = j;
  31.   while (j < end.size() && end[j] != '-')
  32.     ++j;
  33.   month_end = stoi(end.substr(i, j - i));
  34.   ++j;
  35.   i = j;
  36.   while (j < end.size() && end[j] != '-')
  37.     ++j;
  38.   day_end = stoi(end.substr(i, j - i));
  39.   
  40.   if (year_start == year_end && month_start == month_end).鏈枃鍘熷垱鑷1point3acres璁哄潧
  41.     return {{start, end}};
  42. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  43.   int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

  44.   int year = year_start;
  45.   int month = month_start + 1;
  46.   vector<pair<string, string> > res;
  47.   res.push_back({
  48.       start,. 1point3acres.com/bbs
  49.         to_string(year_start) + "-" + to_string(month_start) + "-" +. From 1point 3acres bbs
  50.         to_string(days[month_start - 1] + (month_start == 2 && (year_start % 400 == 0 || (year_start % 100 != 0 && year_start % 4 == 0))))
  51.         });
  52.   while (year != year_end || month != month_end) {
  53.     res.push_back({
  54.         to_string(year) + "-" + to_string(month) + "-1",
  55.           to_string(year) + "-" + to_string(month) + "-" + to_string(days[month - 1] + (month == 2 && (year % 400 == 0 || (year % 100 != 0 && year % 4 == 0))))
  56.       });
  57.     year = year + month / 12;
  58.     month = month % 12 + 1;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  59.   }
  60.   res.push_back({to_string(year_end) + "-" + to_string(month_end) + "-1", end});
  61.   return res;
  62. }
复制代码
回复 支持 反对

使用道具 举报

linixtest 发表于 2017-8-5 05:54:44 | 显示全部楼层
我想,可以用下一个月的第一天减掉60*60*24秒来计算这个月的最后一天。下个月的第一天就是当前日期的年月加1,注意12月翻年,再加上日期1就好了吧。
回复 支持 反对

使用道具 举报

f1371342385 发表于 2017-9-4 09:40:44 | 显示全部楼层
我咋感觉你这个和design uber差不多那种的。。。查询地理信息的
回复 支持 反对

使用道具 举报

wangchengxuan 发表于 2017-9-7 13:59:02 | 显示全部楼层
试着写了一下第一题:
  1. public class DatePrinter {

  2.     static int[][] months = {
  3.         {0, 31,28,31,30,31,30,31,31,30,31,30,31},
  4.         {0, 31,29,31,30,31,30,31,31,30,31,30,31}
  5.     };
  6.     public static void main(String[] args) {
  7.         list(new int[]{2017,3,31}, new int[]{2017, 5, 29}).forEach(System.out::println);
  8.     }
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.     private static String format = "%d/%d/%d-%d/%d/%d";

  10.     private static List<String> list(int[] start, int[] end) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.         // year, month, day
  12.         int year = start[0];. Waral 鍗氬鏈夋洿澶氭枃绔,
  13.         int month = start[1];. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.         int day = start[2]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.         List<String> res = new ArrayList<>();
  16.         res.toArray();
  17.         while (year <= end[0]) {
  18.             while (month < (year == end[0] ? end[1] : 13)) {. From 1point 3acres bbs
  19.                 res.add(String.format(format, month, day, year, month, months[isLeap(year)][month], year));. 鍥磋鎴戜滑@1point 3 acres
  20.                 month++;
  21.                 day = 1;
  22.             }. more info on 1point3acres.com
  23.             if (year == end[0] && month == end[1] && day <= end[2]) {
  24.                 res.add(String.format(format, month, day, year, end[1], end[2], end[0]));
  25.             }
  26.             month = 1;
  27.             year++;

  28.         }. visit 1point3acres.com for more.
  29.         return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.     }

  31.     private static int isLeap(int year) {
  32.         return ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0)) ? 1 : 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.     }
  34. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-23 03:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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