推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3218|回复: 12
收起左侧

UBER电面

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

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

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

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

x
两个月前约过两次电面,都被放鸽子了。昨天recruiter又联系我,约的今天电面。
两道题:
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)). 鍥磋鎴戜滑@1point 3 acres
         return a

    listsOfURL = getcrwalingurl()
    def crawlingMax5(listsOfURL). from: 1point3acres.com/bbs
问题是如何在crawlingMax5()中调用crawling(),使得一次最多抓取5次url。


我没太明白第2题的题意,开始我以为是多线程问题,后面面试官说和多线性无关,根据解析来做。大家有谁看懂了这道题的,欢迎一起讨论~
.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (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)
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3. . more info on 1point3acres.com

  4. def get_crawling_url():
  5.     a = [].鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.     for x in xrange(100):
  7.         a.append('google.com/'+str(x)). from: 1point3acres.com/bbs
  8.     return a


  9. def crawling_max_k(list_of_url, k=5):. From 1point 3acres bbs
  10.     iter_of_url = iter(list_of_url)

  11.     def _crawling_k():
  12.         for i in xrange(k):
  13.             try:
  14.                 crawling(iter_of_url.next())
  15.             except StopIteration:
  16.                 return
  17. . from: 1point3acres.com/bbs
  18.     return _crawling_k


  19. def crawling_max_k_using_generator(list_of_url, k=5):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.     for idx, url in enumerate(list_of_url):
  21.         crawling(url)
  22.         if idx % k == k - 1:
  23.             yield.鐣欏璁哄潧-涓浜-涓夊垎鍦

  24. . 1point 3acres 璁哄潧
  25. if __name__ == '__main__':
  26.     list_of_url = get_crawling_url().鐣欏璁哄潧-涓浜-涓夊垎鍦
  27.     c5 = crawling_max_k(list_of_url)
  28.     c5()
  29.     c5()

  30.     print '*' * 30-google 1point3acres
  31.     c5_gen = crawling_max_k_using_generator(list_of_url)
  32.     c5_gen.next()
  33.     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. from: 1point3acres.com/bbs
根据什么的解析? 最多抓取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[].
然后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规则?. 1point3acres.com/bbs
. 鍥磋鎴戜滑@1point 3 acres
crawlingMax5将会怎样被调用?是不是在同一个listsOfURL上被连续调用很多次,直至listsOfURL不再有未被抓取的URL?

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

使用道具 举报

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

  1. def crawling(url):
  2.     print("crawling %s" % url)
  3. -google 1point3acres

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


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

  11.     def _crawling_k():
  12.         for i in xrange(k):
  13.             try:
  14.                 crawling(iter_of_url.next())
  15.             except StopIteration:
  16.                 return 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  17.     return _crawling_k


  18. if __name__ == '__main__':
  19.     list_of_url = get_crawling_url()
  20.     c5 = crawling_max_k(list_of_url).鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.     c5()
  22.     c5(). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
复制代码
回复 支持 反对

使用道具 举报

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

. Waral 鍗氬鏈夋洿澶氭枃绔,赞!我先学习一下!
回复 支持 反对

使用道具 举报

limingli1991 发表于 2015-9-15 10:11:21 | 显示全部楼层
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你好楼主请问一下Median of medians不是只能估计出median么?  这道题不需要算出准确的吗?
回复 支持 反对

使用道具 举报

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

应该是这样的,快排找出个数,然后还得扫一遍median

. visit 1point3acres.com for more.补充内容 (2016-2-10 13:00):. more info on 1point3acres.com
扫一遍hashmap, 如果个数和median一样,就得加入结果
回复 支持 反对

使用道具 举报

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

  2.         static class Ele {
  3.                 char c ;
  4.                 int times;. more info on 1point3acres.com
  5.                 public Ele(char c, int t) {
  6.                         this.c = c;
  7.                         times = t;. from: 1point3acres.com/bbs
  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;. 鍥磋鎴戜滑@1point 3 acres
  15.                 }
  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.                         }
  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.                 }. 鍥磋鎴戜滑@1point 3 acres
  29.                 int median = getMedian(eles, 0, eles.length - 1);
  30.                 for (Ele ele : eles) {
  31.                         if (ele.times == median) {
  32.                                 res.add(ele.c);. 1point3acres.com/bbs
  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;
    . 鍥磋鎴戜滑@1point 3 acres
  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;-google 1point3acres
  51.                 int i = start;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.         }. more info on 1point3acres.com
  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;.1point3acres缃
  67.         }
  68.        
  69.         public static void main(String[] args) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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.                 }
  75.         }
  76.         . 鍥磋鎴戜滑@1point 3 acres
  77. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-19 00:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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