【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3204|回复: 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]. 1point3acres.com/bbs

2. def crawling()
         pass
   def getcrawlingurl():
         a = []-google 1point3acres
         for x in (1, 100):
              a.append('google.com'+str(x))
         return a

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


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


补充内容 (2015-7-15 07:29):
补充一下,是同时最多抓取5个url。
yhfyhf 发表于 2015-7-15 10:50:35 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
想了一下,貌似没必要用闭包,直接用yield和generator就行了...
  1. def crawling(url):
  2.     print("crawling %s" % url)

  3. . From 1point 3acres bbs
  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)

  11.     def _crawling_k():
  12.         for i in xrange(k):
  13.             try:
  14.                 crawling(iter_of_url.next()). 鍥磋鎴戜滑@1point 3 acres
  15.             except StopIteration:
  16.                 return

  17.     return _crawling_k
  18. . 1point3acres.com/bbs
  19. . more info on 1point3acres.com
  20. def crawling_max_k_using_generator(list_of_url, k=5):. from: 1point3acres.com/bbs
  21.     for idx, url in enumerate(list_of_url): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.         crawling(url)
  23.         if idx % k == k - 1:. 1point 3acres 璁哄潧
  24.             yield


  25. if __name__ == '__main__':-google 1point3acres
  26.     list_of_url = get_crawling_url()
  27.     c5 = crawling_max_k(list_of_url)
  28.     c5()
  29.     c5(). From 1point 3acres bbs

  30.     print '*' * 30
  31.     c5_gen = crawling_max_k_using_generator(list_of_url). From 1point 3acres bbs
  32.     c5_gen.next()
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  33.     c5_gen.next()
复制代码
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2015-7-15 07:13:52 | 显示全部楼层
关注一亩三分地微博:
Warald
根据什么的解析? 最多抓取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[].
然后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. . 鍥磋鎴戜滑@1point 3 acres
  2. def crawling(url):. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.     print("crawling %s" % url)


  4. def get_crawling_url():
  5.     a = []
  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):. more info on 1point3acres.com
  11.     iter_of_url = iter(list_of_url)
  12. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.     def _crawling_k():
  14.         for i in xrange(k):
  15.             try:
  16.                 crawling(iter_of_url.next())
  17.             except StopIteration:
  18.                 return

  19.     return _crawling_k


  20. if __name__ == '__main__':. from: 1point3acres.com/bbs
  21.     list_of_url = get_crawling_url()-google 1point3acres
  22.     c5 = crawling_max_k(list_of_url)
  23.     c5()
  24.     c5().1point3acres缃
复制代码
回复 支持 反对

使用道具 举报

 楼主| catfiona 发表于 2015-7-16 04:18:21 | 显示全部楼层
yhfyhf 发表于 2015-7-15 10:50.1point3acres缃
想了一下,貌似没必要用闭包,直接用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
. from: 1point3acres.com/bbs
应该是这样的,快排找出个数,然后还得扫一遍median

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-22 21:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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