一亩三分地论坛

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

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

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",. more info on 1point3acres.com
[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",. 鍥磋鎴戜滑@1point 3 acres
[size=14.6666666666667px]"12,9,106.1,Oakland",
[size=14.6666666666667px]"13,1,105.1,Oakland",. Waral 鍗氬鏈夋洿澶氭枃绔,
[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",. Waral 鍗氬鏈夋洿澶氭枃绔,
[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 {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2.   public static void displayPages(List<String> input) {. 鍥磋鎴戜滑@1point 3 acres
  3.     if (input == null || input.size() == 0) {
  4.       return;
  5.     }
  6.    
  7.     Set<String> visited = new HashSet<>();. 鍥磋鎴戜滑@1point 3 acres
  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++;. 1point3acres.com/bbs
  27.           System.out.println("Page " + pageNum);
  28.         }
  29.       }
  30.     }
  31.   }
  32.          
  33.   public static void main(String[] args) {
  34.     String[] strs = new String[]{.1point3acres缃
  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",.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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",
  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",
  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:
. Waral 鍗氬鏈夋洿澶氭枃绔,
[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. From 1point 3acres bbs
  6. 16,10,206.1,Oakland
  7. 6,29,204.1,SanFrancisco
  8. 7,20,203.1,SanFrancisco
  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
  31. 29,22,2.1,SanJose.鐣欏璁哄潧-涓浜-涓夊垎鍦
  32. 30,23,1.1,SanJose
  33. Page 4
  34. 1,3,5.1,Oakland
复制代码
. 1point 3acres 璁哄潧

本帖被以下淘专辑推荐:

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

使用道具 举报

lightmark 发表于 2015-12-7 14:53:17 | 显示全部楼层
import json
from collections import deque. From 1point 3acres bbs
. from: 1point3acres.com/bbs
if __name__ == '__main__':
    input = '''
[
"host_id,listing_id,score,city",
"1,28,300.1,SanFrancisco",
"4,5,209.1,SanFrancisco",
"20,7,208.1,SanFrancisco",
"23,8,207.1,SanFrancisco",. From 1point 3acres bbs
"16,10,206.1,Oakland",. from: 1point3acres.com/bbs
"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",
"15,27,109.1,Oakland",
"10,13,108.1,Oakland",
"11,26,107.1,Oakland",
"12,9,106.1,Oakland",
"13,1,105.1,Oakland",
"22,17,104.1,Oakland",
. 1point3acres.com/bbs"1,2,103.1,Oakland",
. 鍥磋鎴戜滑@1point 3 acres"28,24,102.1,Oakland",
"18,14,11.1,SanJose",
"6,25,10.1,Oakland",
"19,15,9.1,SanJose",
"3,19,8.1,SanJose",. visit 1point3acres.com for more.
"3,11,7.1,Oakland",
"27,12,6.1,Oakland",
"1,3,5.1,Oakland",
"25,4,4.1,SanJose",
"5,6,3.1,SanJose",
"29,22,2.1,SanJose",
"30,23,1.1,SanJose"
]. 1point3acres.com/bbs
'''
    a = json.loads(input);.鏈枃鍘熷垱鑷1point3acres璁哄潧
    a.pop(0)
    items = [s.split(',') for s in a]
    k = 12
    start = 0
    pages = []
    hashmap = {}
    for item in items:. from: 1point3acres.com/bbs
        if item[0] not in hashmap:
            hashmap[item[0]] = start. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        if hashmap[item[0]] == len(pages):
            pages.append([])
        pages[hashmap[item[0]]].append(','.join(item)). Waral 鍗氬鏈夋洿澶氭枃绔,
        hashmap[item[0]] += 1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        if len(pages[start]) == k:. visit 1point3acres.com for more.
            start += 1. 1point3acres.com/bbs
    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.1point3acres缃
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
# -- add following lines. visit 1point3acres.com for more.
else:
            hashmap[iterm[0]] = max(start, hashmap[iterm[0])
回复 支持 反对

使用道具 举报

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

使用道具 举报

王饱饱 发表于 3 天前 | 显示全部楼层
谢谢楼主分享,努力刷题中
回复 支持 反对

使用道具 举报

shanxq12345 发表于 6 小时前 | 显示全部楼层
谢谢楼主分享。准备店面中
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-22 18:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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