一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 5748|回复: 8
收起左侧

Airbnb 一道面经高频

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

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

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

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

x
[size=14.6666666666667px]实现分页显示。给了以下一些输入数据,要求将以下行分页显示,每页12行,其中每行已经按score排好序,分页显示的时候如果有相同host id的行,则将后面同host id的行移到下一页。
[size=14.6666666666667px][
[size=14.6666666666667px]"host_id,listing_id,score,city",.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",
[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",.1point3acres缃
[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",. 鍥磋鎴戜滑@1point 3 acres
[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". from: 1point3acres.com/bbs
]

. 1point 3acres 璁哄潧
[size=14.6666669845581px]下面是我自己写的答案,能通过测试,就是不知道是否有更好的答案:
[size=14.6666669845581px]
  1. public class Solution {
  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<>();. from: 1point3acres.com/bbs
  8.     Iterator<String> iterator = input.iterator();
  9.     int pageNum = 1;. from: 1point3acres.com/bbs
  10.    
  11.     System.out.println("Page " + pageNum);
  12.    
  13.     while (iterator.hasNext()) {
  14.       String curr = iterator.next();
  15.       String hostId = curr.split(",")[0];. 1point3acres.com/bbs
  16.       if (!visited.contains(hostId)) {
    . 1point3acres.com/bbs
  17.         System.out.println(curr);. 1point3acres.com/bbs
  18.         visited.add(hostId);-google 1point3acres
  19.         iterator.remove();
  20.       }  
  21.       // New page. from: 1point3acres.com/bbs
  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);. 鍥磋鎴戜滑@1point 3 acres
  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",. 1point 3acres 璁哄潧
  39.       "16,10,206.1,Oakland",
  40.       "1,16,205.1,SanFrancisco",
  41.       "6,29,204.1,SanFrancisco",
  42.       "7,20,203.1,SanFrancisco",
    . from: 1point3acres.com/bbs
  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",. From 1point 3acres bbs
  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));-google 1point3acres
  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
  10. 2,18,201.1,SanFrancisco
  11. 15,27,109.1,Oakland. From 1point 3acres bbs
  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
复制代码

本帖被以下淘专辑推荐:

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

使用道具 举报

lightmark 发表于 2015-12-7 14:53:17 | 显示全部楼层
import json.鐣欏璁哄潧-涓浜-涓夊垎鍦
from collections import deque

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",-google 1point3acres
"23,8,207.1,SanFrancisco",
"16,10,206.1,Oakland",
"1,16,205.1,SanFrancisco",
"6,29,204.1,SanFrancisco",-google 1point3acres
"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",. From 1point 3acres bbs
"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",
"1,2,103.1,Oakland",
"28,24,102.1,Oakland",
"18,14,11.1,SanJose",
"6,25,10.1,Oakland",. more info on 1point3acres.com
"19,15,9.1,SanJose",
"3,19,8.1,SanJose",
"3,11,7.1,Oakland",
"27,12,6.1,Oakland",.鏈枃鍘熷垱鑷1point3acres璁哄潧
"1,3,5.1,Oakland",
"25,4,4.1,SanJose",
"5,6,3.1,SanJose",
"29,22,2.1,SanJose",.1point3acres缃
"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.com/bbs
        if item[0] not in hashmap:
            hashmap[item[0]] = start
        if hashmap[item[0]] == len(pages):.1point3acres缃
            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吧。. visit 1point3acres.com for more.


if item[0] not in hashmap:
            hashmap[item[0]] = start
# -- add following lines. Waral 鍗氬鏈夋洿澶氭枃绔,
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 | 显示全部楼层
谢谢楼主分享。准备店面中
回复 支持 反对

使用道具 举报

总是忘密码 发表于 2017-10-12 10:34:52 | 显示全部楼层
感觉楼主的代码不太对,如果input是1,2,3,1,1,1,2,2,page size是5的话,楼主的代码输出的就是错误的答案。我不清楚是不是15年oa的题和现在有变化,楼主的代码里并没有考虑到如果page填不满该怎么做。希望大家看代码的时候留意一下
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-23 04:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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