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


一亩三分地论坛

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

UBER电面

[复制链接] |试试Instant~ |关注本帖
catfiona 发表于 2015-7-15 06:43:21 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Other其他

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

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

x
两个月前约过两次电面,都被放鸽子了。昨天recruiter又联系我,约的今天电面。. more info on 1point3acres.com
两道题:
1. 给一个string list, 例如:['a', 'b', 'b', 'c', 'c', 'e', 'e', 'e'],返回出次次数是中位数的字符。例如本题,应该返回[b, c]

2. def crawling()
         pass
   def getcrawlingurl():
         a = []
         for x in (1, 100):
              a.append('google.com'+str(x))
         return a. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

    listsOfURL = getcrwalingurl(). 鍥磋鎴戜滑@1point 3 acres
    def crawlingMax5(listsOfURL)
问题是如何在crawlingMax5()中调用crawling(),使得一次最多抓取5次url。.1point3acres缃

. From 1point 3acres bbs
我没太明白第2题的题意,开始我以为是多线程问题,后面面试官说和多线性无关,根据解析来做。大家有谁看懂了这道题的,欢迎一起讨论~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. more info on 1point3acres.com
补充内容 (2015-7-15 07:29):
补充一下,是同时最多抓取5个url。
yhfyhf 发表于 2015-7-15 10:50:35 | 显示全部楼层
想了一下,貌似没必要用闭包,直接用yield和generator就行了...
  1. def crawling(url):
  2.     print("crawling %s" % url). more info on 1point3acres.com
  3. .鏈枃鍘熷垱鑷1point3acres璁哄潧

  4. def get_crawling_url():
  5.     a = []
  6.     for x in xrange(100):
  7.         a.append('google.com/'+str(x))
  8.     return a


  9. def crawling_max_k(list_of_url, k=5):
  10.     iter_of_url = iter(list_of_url).1point3acres缃

  11.     def _crawling_k():
  12.         for i in xrange(k):
  13.             try:
  14.                 crawling(iter_of_url.next()).1point3acres缃
  15.             except StopIteration:
  16.                 return

  17.     return _crawling_k


  18. def crawling_max_k_using_generator(list_of_url, k=5):
  19.     for idx, url in enumerate(list_of_url):
  20.         crawling(url)
  21.         if idx % k == k - 1:
  22.             yield


  23. if __name__ == '__main__':
  24.     list_of_url = get_crawling_url()
  25.     c5 = crawling_max_k(list_of_url)
  26.     c5(). 鍥磋鎴戜滑@1point 3 acres
  27.     c5()

  28.     print '*' * 30
  29.     c5_gen = crawling_max_k_using_generator(list_of_url)
  30.     c5_gen.next(). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.     c5_gen.next()
复制代码
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2015-7-15 07:13:52 | 显示全部楼层
根据什么的解析? 最多抓取5次 5次还是5个..?
回复 支持 反对

使用道具 举报

 楼主| catfiona 发表于 2015-7-15 07:26:08 | 显示全部楼层
readman 发表于 2015-7-15 07:13
根据什么的解析? 最多抓取5次 5次还是5个..?

是同时最多解析5个url,次数是直到解析完。
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-7-15 07:34:53 | 显示全部楼层
第一题怎么做呢?
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-15 07:47:27 | 显示全部楼层
mkcing 发表于 2015-7-15 07:34
第一题怎么做呢?

one pass 记下每个string的次数,用char[].
. from: 1point3acres.com/bbs 然后quickselect
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-15 07:49:25 | 显示全部楼层
mkcing 发表于 2015-7-15 07:34
第一题怎么做呢?

Median of medians
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-15 09:13:27 | 显示全部楼层
第二题楼主在面试的时候应该再问得详细一点,比如:

crawling的作用是什么?参数和返回值应该是什么?真正的crawling肯定不会是只有一个pass在里面。只看这个函数定义似乎没有什么帮助。

crawlingMax5的输出又应该是什么?比如是不是一个“包含5个抓取的URL的list”?然后listsOfURL将会怎么变化?是否应该将被取出的5个URL删去?

“抓取5个”的意思是从listsOfURL中随机取出5个,还是必须顺次取前5个,或者有其他的取URL规则?

crawlingMax5将会怎样被调用?是不是在同一个listsOfURL上被连续调用很多次,直至listsOfURL不再有未被抓取的URL?

我觉得,这些是要解决这个问题的基本信息。面试时一定要问得清清楚楚再开始下手做。
回复 支持 反对

使用道具 举报

yhfyhf 发表于 2015-7-15 10:14:13 | 显示全部楼层
我猜这题是考闭包?

  1. def crawling(url): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2.     print("crawling %s" % url). more info on 1point3acres.com

  3. . From 1point 3acres bbs
  4. def get_crawling_url():
  5.     a = []. Waral 鍗氬鏈夋洿澶氭枃绔,
  6.     for x in xrange(100):
  7.         a.append('google.com/'+str(x))
  8.     return a
  9. .鐣欏璁哄潧-涓浜-涓夊垎鍦

  10. def crawling_max_k(list_of_url, k=5):
  11.     iter_of_url = iter(list_of_url)

  12.     def _crawling_k():
  13.         for i in xrange(k):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.             try:
  15.                 crawling(iter_of_url.next()).1point3acres缃
  16.             except StopIteration:
  17.                 return

  18.     return _crawling_k


  19. if __name__ == '__main__':
  20.     list_of_url = get_crawling_url()
  21.     c5 = crawling_max_k(list_of_url)
  22.     c5()
  23.     c5()
复制代码
回复 支持 反对

使用道具 举报

 楼主| catfiona 发表于 2015-7-16 04:18:21 | 显示全部楼层
yhfyhf 发表于 2015-7-15 10:50
想了一下,貌似没必要用闭包,直接用yield和generator就行了...

赞!我先学习一下!
回复 支持 反对

使用道具 举报

limingli1991 发表于 2015-9-15 10:11:21 | 显示全部楼层

你好楼主请问一下Median of medians不是只能估计出median么?  这道题不需要算出准确的吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-10 12:59:52 | 显示全部楼层
readman 发表于 2015-7-15 07:47 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
one pass 记下每个string的次数,用char[].
然后quickselect

应该是这样的,快排找出个数,然后还得扫一遍median
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-2-10 13:00):
扫一遍hashmap, 如果个数和median一样,就得加入结果
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-14 05:05:15 | 显示全部楼层
写了下第一题
  1. public class MedianOccurence {

  2.         static class Ele {
  3.                 char c ;
  4.                 int times;
  5.                 public Ele(char c, int t) {
  6.                         this.c = c;-google 1point3acres
  7.                         times = t;
  8.                 }
  9.         }
  10.        
  11.         public static List<Character> getMedianOccurenceCharactr(char[] chars) {
  12.                 List<Character> res = new ArrayList<Character>();
  13.                 if (chars == null || chars.length == 0) {
  14.                         return res;
  15.                 }
    . from: 1point3acres.com/bbs
  16.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  17.                 for (char c : chars) {
  18.                         if (map.containsKey(c)) {
  19.                                 map.put(c, map.get(c) + 1);
  20.                         } else {
  21.                                 map.put(c, 1);
  22.                         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  24.                 Ele[] eles = new Ele[map.size()];
  25.                 int index = 0;
  26.                 for (Entry<Character, Integer> entry : map.entrySet()) {
  27.                         eles[index++] = new Ele(entry.getKey(), entry.getValue());
  28.                 }
  29.                 int median = getMedian(eles, 0, eles.length - 1);
  30.                 for (Ele ele : eles) {
  31.                         if (ele.times == median) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  32.                                 res.add(ele.c);
  33.                         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  34.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  35.                
  36.                 return res;
  37.         }
  38.         private static int getMedian(Ele[] eles, int start, int end) {
  39.                 int k = (eles.length - 1) / 2;
  40.                 int index = parition(eles, start, end);
  41.                 if (index == k) {
  42.                         return eles[index].times;
  43.                 } else if (index > k) {
  44.                         return getMedian(eles, start, index - 1);
  45.                 } else {
  46.                         return getMedian(eles, index + 1, end);
  47.                 }
  48.         }
  49.         private static int parition(Ele[] eles, int start, int end) {
  50.                 int pivot = start;
  51.                 int i = start;
  52.                 int j = start + 1;
  53.                 while (j <= end) {
  54.                         if (eles[j].times < eles[pivot].times) {
  55.                                 i++;
  56.                                 swap(eles, i, j);
  57.                         }
  58.                         j++;
  59.                 }
  60.                 swap(eles, i, pivot);
  61.                 return i;
  62.         }
  63.         private static void swap(Ele[] eles, int i, int j) {
  64.                 Ele tmp = eles[i];
  65.                 eles[i] = eles[j];
  66.                 eles[j] = tmp;
  67.         }
  68.        
  69.         public static void main(String[] args) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  70.                 char[] chars = {'a', 'b', 'b','c', 'c', 'c', 'e', 'e', 'e', 'd', 'd', 'd', 'd'};
  71.                 List<Character> res = getMedianOccurenceCharactr(chars);
  72.                 for (char c : res) {
  73.                         System.out.println(c);
  74.                 }. more info on 1point3acres.com
  75.         }
  76.        
  77. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-25 00:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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