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


一亩三分地论坛

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

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

Airbnb 一道面经高频

[复制链接] |试试Instant~ |关注本帖
butterwang 发表于 2015-11-26 00:26:04 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Airbnb - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
[size=14.6666666666667px]实现分页显示。给了以下一些输入数据,要求将以下行分页显示,每页12行,其中每行已经按score排好序,分页显示的时候如果有相同host id的行,则将后面同host id的行移到下一页。
[size=14.6666666666667px][
[size=14.6666666666667px]"host_id,listing_id,score,city",-google 1point3acres
[size=14.6666666666667px]"1,28,300.1,SanFrancisco", 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
[size=14.6666666666667px]"4,5,209.1,SanFrancisco",
[size=14.6666666666667px]"20,7,208.1,SanFrancisco",. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
[size=14.6666666666667px]"23,8,207.1,SanFrancisco",
[size=14.6666666666667px]"16,10,206.1,Oakland",
[size=14.6666666666667px]"1,16,205.1,SanFrancisco",. from: 1point3acres.com/bbs
[size=14.6666666666667px]"6,29,204.1,SanFrancisco",
[size=14.6666666666667px]"7,20,203.1,SanFrancisco",
[size=14.6666666666667px]"8,21,202.1,SanFrancisco",
[size=14.6666666666667px]"2,18,201.1,SanFrancisco",
[size=14.6666666666667px]"2,30,200.1,SanFrancisco",
[size=14.6666666666667px]"15,27,109.1,Oakland",. From 1point 3acres bbs
[size=14.6666666666667px]"10,13,108.1,Oakland",
[size=14.6666666666667px]"11,26,107.1,Oakland",
[size=14.6666666666667px]"12,9,106.1,Oakland",
[size=14.6666666666667px]"13,1,105.1,Oakland",
[size=14.6666666666667px]"22,17,104.1,Oakland",
[size=14.6666666666667px]"1,2,103.1,Oakland",
[size=14.6666666666667px]"28,24,102.1,Oakland",
[size=14.6666666666667px]"18,14,11.1,SanJose",
[size=14.6666666666667px]"6,25,10.1,Oakland",
[size=14.6666666666667px]"19,15,9.1,SanJose",
[size=14.6666666666667px]"3,19,8.1,SanJose",
[size=14.6666666666667px]"3,11,7.1,Oakland",
[size=14.6666666666667px]"27,12,6.1,Oakland",
[size=14.6666666666667px]"1,3,5.1,Oakland",
[size=14.6666666666667px]"25,4,4.1,SanJose",
[size=14.6666666666667px]"5,6,3.1,SanJose",
[size=14.6666666666667px]"29,22,2.1,SanJose",
[size=14.6666666666667px]"30,23,1.1,SanJose"
]


[size=14.6666669845581px]下面是我自己写的答案,能通过测试,就是不知道是否有更好的答案:
[size=14.6666669845581px]
  1. public class Solution {. From 1point 3acres bbs
  2.   public static void displayPages(List<String> input) {
  3.     if (input == null || input.size() == 0) {
  4.       return;
  5.     }
  6.    
  7.     Set<String> visited = new HashSet<>();
  8.     Iterator<String> iterator = input.iterator();
  9.     int pageNum = 1;
  10.    
  11.     System.out.println("Page " + pageNum);
  12.    
  13.     while (iterator.hasNext()) {
  14.       String curr = iterator.next();
  15.       String hostId = curr.split(",")[0];. 鍥磋鎴戜滑@1point 3 acres
  16.       if (!visited.contains(hostId)) {
  17.         System.out.println(curr);
  18.         visited.add(hostId);
  19.         iterator.remove();. from: 1point3acres.com/bbs
  20.       }  
  21.       // New page. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  22.       if (visited.size() == 12 || (!iterator.hasNext())) {
  23.         visited.clear();
  24.         iterator = input.iterator();
  25.         if (!input.isEmpty()) {. 1point3acres.com/bbs
  26.           pageNum++;
  27.           System.out.println("Page " + pageNum);
  28.         }
  29.       }
  30.     }
  31.   }
  32.          
  33.   public static void main(String[] args) {
  34.     String[] strs = new String[]{
  35.       "1,28,300.1,SanFrancisco",
  36.       "4,5,209.1,SanFrancisco",
  37.       "20,7,208.1,SanFrancisco",
  38.       "23,8,207.1,SanFrancisco",
  39.       "16,10,206.1,Oakland",
  40.       "1,16,205.1,SanFrancisco",
  41.       "6,29,204.1,SanFrancisco",
  42.       "7,20,203.1,SanFrancisco",
  43.       "8,21,202.1,SanFrancisco",
  44.       "2,18,201.1,SanFrancisco",
  45.       "2,30,200.1,SanFrancisco",
  46.       "15,27,109.1,Oakland",
  47.       "10,13,108.1,Oakland",
  48.       "11,26,107.1,Oakland",
  49.       "12,9,106.1,Oakland",
  50.       "13,1,105.1,Oakland",
  51.       "22,17,104.1,Oakland",
  52.       "1,2,103.1,Oakland",
  53.       "28,24,102.1,Oakland",
  54.       "18,14,11.1,SanJose",
  55.       "6,25,10.1,Oakland",
  56.       "19,15,9.1,SanJose",
  57.       "3,19,8.1,SanJose",.1point3acres缃
  58.       "3,11,7.1,Oakland",
  59.       "27,12,6.1,Oakland",
  60.       "1,3,5.1,Oakland",
  61.       "25,4,4.1,SanJose",
  62.       "5,6,3.1,SanJose",. 1point3acres.com/bbs
  63.       "29,22,2.1,SanJose",
  64.       "30,23,1.1,SanJose"
  65.     };
  66.     List<String> input = new ArrayList<>(Arrays.asList(strs));
  67.     displayPages(input);
  68.   }      
  69. }
复制代码
Output:

[size=14.6666669845581px]
  1. Page 1
  2. 1,28,300.1,SanFrancisco
  3. 4,5,209.1,SanFrancisco
  4. 20,7,208.1,SanFrancisco
  5. 23,8,207.1,SanFrancisco. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6. 16,10,206.1,Oakland
  7. 6,29,204.1,SanFrancisco
  8. 7,20,203.1,SanFrancisco
  9. 8,21,202.1,SanFrancisco-google 1point3acres
  10. 2,18,201.1,SanFrancisco
  11. 15,27,109.1,Oakland. 鍥磋鎴戜滑@1point 3 acres
  12. 10,13,108.1,Oakland
  13. 11,26,107.1,Oakland
  14. Page 2
  15. 1,16,205.1,SanFrancisco
  16. 2,30,200.1,SanFrancisco
  17. 12,9,106.1,Oakland
  18. 13,1,105.1,Oakland
  19. 22,17,104.1,Oakland-google 1point3acres
  20. 28,24,102.1,Oakland
  21. 18,14,11.1,SanJose
  22. 6,25,10.1,Oakland
  23. 19,15,9.1,SanJose. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  24. 3,19,8.1,SanJose
  25. 27,12,6.1,Oakland
  26. 25,4,4.1,SanJose
  27. Page 3
  28. 1,2,103.1,Oakland
  29. 3,11,7.1,Oakland. more info on 1point3acres.com
  30. 5,6,3.1,SanJose
  31. 29,22,2.1,SanJose
  32. 30,23,1.1,SanJose.鏈枃鍘熷垱鑷1point3acres璁哄潧
  33. Page 4
  34. 1,3,5.1,Oakland
复制代码

本帖被以下淘专辑推荐:

yl2762 发表于 2015-12-7 08:27:57 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
多谢楼主分享,仔细看了代码觉得很靠谱:)
回复 支持 反对

使用道具 举报

lightmark 发表于 2015-12-7 14:53:17 | 显示全部楼层
关注一亩三分地微博:
Warald
import json
from collections import deque

if __name__ == '__main__':. 1point 3acres 璁哄潧
    input = '''
[. From 1point 3acres bbs
"host_id,listing_id,score,city",-google 1point3acres
"1,28,300.1,SanFrancisco",
"4,5,209.1,SanFrancisco",
"20,7,208.1,SanFrancisco",
"23,8,207.1,SanFrancisco",
"16,10,206.1,Oakland",
"1,16,205.1,SanFrancisco",. 1point3acres.com/bbs
"6,29,204.1,SanFrancisco",
"7,20,203.1,SanFrancisco",
"8,21,202.1,SanFrancisco",
"2,18,201.1,SanFrancisco",
"2,30,200.1,SanFrancisco", 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
"15,27,109.1,Oakland",
"10,13,108.1,Oakland",. from: 1point3acres.com/bbs
"11,26,107.1,Oakland",
"12,9,106.1,Oakland",.1point3acres缃
"13,1,105.1,Oakland",
"22,17,104.1,Oakland",
"1,2,103.1,Oakland",
"28,24,102.1,Oakland",
"18,14,11.1,SanJose",. 1point3acres.com/bbs
"6,25,10.1,Oakland",
"19,15,9.1,SanJose",
"3,19,8.1,SanJose",
"3,11,7.1,Oakland",
"27,12,6.1,Oakland",
"1,3,5.1,Oakland",
"25,4,4.1,SanJose",-google 1point3acres
"5,6,3.1,SanJose",
"29,22,2.1,SanJose",
"30,23,1.1,SanJose"
]
'''
    a = json.loads(input);
    a.pop(0)
    items = [s.split(',') for s in a]
    k = 12
    start = 0
    pages = []
    hashmap = {}
    for item in items:
        if item[0] not in hashmap:.1point3acres缃
            hashmap[item[0]] = start
        if hashmap[item[0]] == len(pages):
            pages.append([])
        pages[hashmap[item[0]]].append(','.join(item)). 1point 3acres 璁哄潧
        hashmap[item[0]] += 1
        if len(pages[start]) == k:
            start += 1
    for page in pages:
        print '--- page ---'
        for line in page:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            print line
回复 支持 反对

使用道具 举报

minniedisney 发表于 2016-9-1 14:23:41 | 显示全部楼层
这个有改输入吧,能这样做吗?
回复 支持 反对

使用道具 举报

kradnangel 发表于 2016-9-22 12:50:33 | 显示全部楼层
lightmark 发表于 2015-12-7 14:53
import json
from collections import deque

如果hashmap[item[0]] 上次记录的位置是2, 而当前,前5页都写满了,当item[0]再次出现的时候,写的位置应该是目前的start =6 而不是2+1 = 3吧。


if item[0] not in hashmap:. visit 1point3acres.com for more.
            hashmap[item[0]] = start
# -- add following lines
else:
            hashmap[iterm[0]] = max(start, hashmap[iterm[0])
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-10-16 02:35:22 | 显示全部楼层
所以在最后不到12个元素但是还是有重复hostid的情况下也是要分页的是吗
回复 支持 反对

使用道具 举报

王饱饱 发表于 2017-1-19 14:37:45 | 显示全部楼层
谢谢楼主分享,努力刷题中
回复 支持 反对

使用道具 举报

shanxq12345 发表于 2017-1-22 12:32:17 | 显示全部楼层
谢谢楼主分享。准备店面中
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-28 04:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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