一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1983|回复: 12
收起左侧

UBER电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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):
. from: 1point3acres.com/bbs               a.append('google.com'+str(x))
         return a-google 1point3acres

    listsOfURL = getcrwalingurl()
    def crawlingMax5(listsOfURL).鐣欏璁哄潧-涓浜-涓夊垎鍦
问题是如何在crawlingMax5()中调用crawling(),使得一次最多抓取5次url。. 鍥磋鎴戜滑@1point 3 acres


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

. from: 1point3acres.com/bbs
补充内容 (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). visit 1point3acres.com for more.
  3. -google 1point3acres

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


  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()). more info on 1point3acres.com
  15.             except StopIteration:. visit 1point3acres.com for more.
  16.                 return

  17.     return _crawling_k

  18. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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:.1point3acres缃
  23.             yield
  24. .鏈枃鍘熷垱鑷1point3acres璁哄潧

  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
  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
根据什么的解析? 最多抓取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[].
. more info on 1point3acres.com然后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)


  3. def get_crawling_url():
  4.     a = []. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5.     for x in xrange(100):
  6.         a.append('google.com/'+str(x))
  7.     return a. 1point3acres.com/bbs


  8. def crawling_max_k(list_of_url, k=5):
  9.     iter_of_url = iter(list_of_url)
    .鐣欏璁哄潧-涓浜-涓夊垎鍦

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

  16.     return _crawling_k


  17. if __name__ == '__main__':
  18.     list_of_url = get_crawling_url()
  19.     c5 = crawling_max_k(list_of_url). from: 1point3acres.com/bbs
  20.     c5()
  21.     c5(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

limingli1991 发表于 2015-9-15 10:11:21 | 显示全部楼层
readman 发表于 2015-7-15 07:49 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Median of medians

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

使用道具 举报

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

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

补充内容 (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;. from: 1point3acres.com/bbs
  7.                         times = t;
  8.                 }-google 1point3acres
  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.                 }
  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.                         }. 1point 3acres 璁哄潧
  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);
    . 1point 3acres 璁哄潧
  33.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  34.                 }-google 1point3acres
  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;. From 1point 3acres bbs
  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) {. visit 1point3acres.com for more.
  64.                 Ele tmp = eles[i];
  65.                 eles[i] = eles[j];
  66.                 eles[j] = tmp;. 1point 3acres 璁哄潧
  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);-google 1point3acres
  74.                 }
    . from: 1point3acres.com/bbs
  75.         }
  76.        
  77. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 00:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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