一亩三分地论坛

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

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

Airbnb 一道面经高频

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

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

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

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

x
[size=14.6666666666667px]实现分页显示。给了以下一些输入数据,要求将以下行分页显示,每页12行,其中每行已经按score排好序,分页显示的时候如果有相同host id的行,则将后面同host id的行移到下一页。
[size=14.6666666666667px][
[size=14.6666666666667px]"host_id,listing_id,score,city",
[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",
[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",
[size=14.6666666666667px]"10,13,108.1,Oakland",
[size=14.6666666666667px]"11,26,107.1,Oakland",. more info on 1point3acres.com
[size=14.6666666666667px]"12,9,106.1,Oakland",
[size=14.6666666666667px]"13,1,105.1,Oakland",
. 1point3acres.com/bbs[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]下面是我自己写的答案,能通过测试,就是不知道是否有更好的答案:. 鍥磋鎴戜滑@1point 3 acres
[size=14.6666669845581px]
  1. public class Solution {. from: 1point3acres.com/bbs
  2.   public static void displayPages(List<String> input) {. 鍥磋鎴戜滑@1point 3 acres
  3.     if (input == null || input.size() == 0) {
  4.       return;
  5.     }
  6.     . From 1point 3acres bbs
  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];
  16.       if (!visited.contains(hostId)) {
  17.         System.out.println(curr);
  18.         visited.add(hostId);
  19.         iterator.remove();
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.       }  
  21.       // New page
  22.       if (visited.size() == 12 || (!iterator.hasNext())) {
  23.         visited.clear();
  24.         iterator = input.iterator();
  25.         if (!input.isEmpty()) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  26.           pageNum++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.           System.out.println("Page " + pageNum); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.         }
  29.       }
  30.     }
  31.   }
  32.          
  33.   public static void main(String[] args) {. 1point3acres.com/bbs
  34.     String[] strs = new String[]{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35.       "1,28,300.1,SanFrancisco",
  36.       "4,5,209.1,SanFrancisco",
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  37.       "20,7,208.1,SanFrancisco",. 1point3acres.com/bbs
  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",. visit 1point3acres.com for more.
  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",-google 1point3acres
  56.       "19,15,9.1,SanJose",
  57.       "3,19,8.1,SanJose",
  58.       "3,11,7.1,Oakland",. 1point 3acres 璁哄潧
  59.       "27,12,6.1,Oakland",
  60.       "1,3,5.1,Oakland",
  61.       "25,4,4.1,SanJose",
  62.       "5,6,3.1,SanJose",
  63.       "29,22,2.1,SanJose",. Waral 鍗氬鏈夋洿澶氭枃绔,
  64.       "30,23,1.1,SanJose"
  65.     };
  66.     List<String> input = new ArrayList<>(Arrays.asList(strs));.1point3acres缃
  67.     displayPages(input);
  68.   }      
  69. }
复制代码
Output:

[size=14.6666669845581px]
  1. Page 1
  2. 1,28,300.1,SanFrancisco. visit 1point3acres.com for more.
  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.1point3acres缃
  9. 8,21,202.1,SanFrancisco
  10. 2,18,201.1,SanFrancisco
  11. 15,27,109.1,Oakland
  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
  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
  30. 5,6,3.1,SanJose. 鍥磋鎴戜滑@1point 3 acres
  31. 29,22,2.1,SanJose
  32. 30,23,1.1,SanJose
  33. Page 4
  34. 1,3,5.1,Oakland
复制代码

本帖被以下淘专辑推荐:

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

使用道具 举报

lightmark 发表于 2015-12-7 14:53:17 | 显示全部楼层
import json 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
from collections import deque. 1point 3acres 璁哄潧

if __name__ == '__main__':
    input = '''
[
"host_id,listing_id,score,city",
"1,28,300.1,SanFrancisco",. visit 1point3acres.com for more.
"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",
"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",.1point3acres缃
"15,27,109.1,Oakland",. 1point3acres.com/bbs
"10,13,108.1,Oakland",
"11,26,107.1,Oakland",. 1point3acres.com/bbs
"12,9,106.1,Oakland",. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
"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",. From 1point 3acres 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",. visit 1point3acres.com for more.
"25,4,4.1,SanJose",
"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:.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if item[0] not in hashmap:
. 鍥磋鎴戜滑@1point 3 acres            hashmap[item[0]] = start
        if hashmap[item[0]] == len(pages):
            pages.append([])
        pages[hashmap[item[0]]].append(','.join(item))
        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:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            hashmap[item[0]] = start-google 1point3acres
# -- add following lines
else:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            hashmap[iterm[0]] = max(start, hashmap[iterm[0])
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 18:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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