一亩三分地论坛

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

airbnb 一道电面题

[复制链接] |试试Instant~ |关注本帖
yonghu009 发表于 2015-10-15 07:59:27 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Airbnb - 网上海投 - 技术电面 |Pass在职跳槽

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

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

x
农友们已经提到过的, iterator of a 2D array with 2nd dimension are different sizes. three methods: hasNext() Next() Remove().  这种题目没有算法可言,但是很容易爬满虫子。。。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

butterwang 发表于 2015-12-2 07:48:46 | 显示全部楼层
我写了一个,不知道对不对。
  1. import java.io.*;
  2. import java.util.*;

  3. public class Solution {. more info on 1point3acres.com
  4.   private List<List<Integer>> array;
  5.   private int rowId; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  6.   private int colId;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.   private int numRows; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.    
  9.   public Solution(List<List<Integer>> array) {
  10.     this.array = array;
  11.     rowId = 0;
  12.     colId = 0;
  13.     numRows = array.size();. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.   }
  15.    
  16.   public boolean hasNext() {
  17.     if (array == null || array.isEmpty()) {
  18.       return false;
  19.     }
  20.      
  21.     while (rowId < numRows && (array.get(rowId) == null ||
  22.       array.get(rowId).isEmpty())) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.       rowId++;
  24.     }
  25.      
  26.     return rowId < numRows;
  27.   }. 1point 3acres 璁哄潧
  28.    
  29.   public int next() {
  30.     int ret = array.get(rowId).get(colId);
  31.     colId++;
  32.     if (colId == array.get(rowId).size()) {
  33.       rowId++;
  34.       colId = 0;. 1point3acres.com/bbs
  35.     }
  36.      
  37.     return ret;
  38.   }
  39.    
  40.   public void remove() {
  41.     List<Integer> listToRemove;
  42.     int rowToRemove;
  43.     int colToRemove;
  44.      
  45.     // Case 1: if the element to remove is the last element of the row
  46.     if (colId == 0) {
  47.       rowToRemove = rowId - 1;
  48.       listToRemove = array.get(rowToRemove);
  49.       colToRemove = listToRemove.size() - 1;
  50.       
  51.       listToRemove.remove(colToRemove);
  52.     } else { // Case 2: the element to remove is not the last element
  53.       rowToRemove = rowId;. from: 1point3acres.com/bbs
  54.       listToRemove = array.get(rowToRemove);
  55.       colToRemove = colId - 1;
  56.       listToRemove.remove(colToRemove);
  57.     }
  58.      
  59.     // If the list to remove has only one element
  60.     if (listToRemove.isEmpty()) {
  61.       array.remove(listToRemove);
  62.       rowId--;
  63.     }
  64.      .鏈枃鍘熷垱鑷1point3acres璁哄潧
  65.     // Update the colId
  66.     if (colId != 0) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  67.       colId--;. Waral 鍗氬鏈夋洿澶氭枃绔,
  68.     }
  69.   }
  70.    
  71.   public static void main(String[] args) {
  72.     List<List<Integer>> array = new ArrayList<>();
  73.     List<Integer> row1 = new ArrayList<>();
  74.     row1.add(1);
  75.     row1.add(2);
  76.     row1.add(3);. 鍥磋鎴戜滑@1point 3 acres
  77.      
  78.     array.add(row1);
  79.      .鐣欏璁哄潧-涓浜-涓夊垎鍦
  80.     List<Integer> row3 = new ArrayList<>();
  81.     array.add(row3);
  82.      
  83.     List<Integer> row2 = new ArrayList<>();
  84.     row2.add(4);
  85.     row2.add(5);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  86.     array.add(row2);
  87.      . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  88.     Solution sol = new Solution(array);
  89.     while (sol.hasNext()) {
  90.       int result = sol.next();
  91.       System.out.println(result);. 1point 3acres 璁哄潧
  92.       
  93.       if (result == 3) {
  94.         sol.remove();
  95.       }
  96.     }
  97.      
  98.     System.out.println();
  99.      
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  100.     for (List<Integer> row : array) {
  101.       for (Integer elem : row) {. 1point3acres.com/bbs
  102.         System.out.println(elem);
  103.       }
  104.     }
  105.   }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  106.    . 鍥磋鎴戜滑@1point 3 acres
  107. }
复制代码
回复 支持 1 反对 0

使用道具 举报

LifeGoesOn 发表于 2015-11-29 08:53:36 | 显示全部楼层
爬满虫子这个term 我还用了几秒反应是什么意思。。。
回复 支持 反对

使用道具 举报

fsi206914 发表于 2015-12-1 15:06:34 | 显示全部楼层
remove 直接 调用next(),可以么?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-2 13:11:20 | 显示全部楼层
butterwang 发表于 2015-12-2 07:48
我写了一个,不知道对不对。

如果是List<List<Integer>>这样的数据结构,可以用List的iterator,wrap一下就成了iterator of iterator。代码不超过30行
回复 支持 反对

使用道具 举报

joseph5wu 发表于 2016-2-12 11:28:29 | 显示全部楼层
yjfox 发表于 2015-12-2 13:11
如果是List这样的数据结构,可以用List的iterator,wrap一下就成了iterator of iterator。代码不超过30行 ...

这样子就不太好删除元素了
回复 支持 反对

使用道具 举报

yjfox 发表于 2016-2-12 12:51:10 | 显示全部楼层
joseph5wu 发表于 2016-2-12 11:28
这样子就不太好删除元素了

iterator的remove() 一并wrap
回复 支持 反对

使用道具 举报

aifer 发表于 2016-2-12 14:28:38 | 显示全部楼层
降维或者wrap
回复 支持 反对

使用道具 举报

joseph5wu 发表于 2016-2-12 14:31:48 | 显示全部楼层
yjfox 发表于 2016-2-12 12:51
iterator的remove() 一并wrap
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
iterator的话如果上一次next的时候正好换成了下一个原来iterator的开始,这样remove是不是就无法处理了
回复 支持 反对

使用道具 举报

yjfox 发表于 2016-2-12 21:12:11 | 显示全部楼层
joseph5wu 发表于 2016-2-12 14:31
iterator的话如果上一次next的时候正好换成了下一个原来iterator的开始,这样remove是不是就无法处理了

如果你说的是remove一个list中的第一个,那并不影响,删了还是可以next到下一个
如果你说的是remove一个list中的最后一个,那更不影响next到下一个list

不知道是否理解了你说的
回复 支持 反对

使用道具 举报

cytmike 发表于 2016-2-16 06:43:06 | 显示全部楼层
你说的是LC251?
回复 支持 反对

使用道具 举报

Laurinda93 发表于 2016-7-22 07:09:45 | 显示全部楼层
yjfox 发表于 2016-2-12 21:12.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果你说的是remove一个list中的第一个,那并不影响,删了还是可以next到下一个
如果你说的是remove一个 ...

我和层主有着同样的困惑;不知道你的思路有写过代码吗?
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-10-16 19:44:35 | 显示全部楼层
Laurinda93 发表于 2016-7-22 07:09. From 1point 3acres bbs
我和层主有着同样的困惑;不知道你的思路有写过代码吗?

我觉得他的意思是  因为remove只能在next之后调用,而且iterator的更新是在每次调用next的时候更新的, 也就是说调用一次next后,iterator要么指向这一行中间的某个元素,要么指向这一行的end,这时调用remove的话,只要删掉当前iterator的前一个iterator就可以了,当然如果是C++的话,删除的结果应该再赋值给遍历用的iterator
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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