一亩三分地论坛

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

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

airbnb 一道电面题

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

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

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

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

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

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

使用道具 举报

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

  3. public class Solution {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.   private List<List<Integer>> array;
  5.   private int rowId;
  6.   private int colId;
  7.   private int numRows;
  8.    . 鍥磋鎴戜滑@1point 3 acres
  9.   public Solution(List<List<Integer>> array) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.     this.array = array;
  11.     rowId = 0;
  12.     colId = 0;
  13.     numRows = array.size();
  14.   }. from: 1point3acres.com/bbs
  15.    
  16.   public boolean hasNext() {
  17.     if (array == null || array.isEmpty()) {
  18.       return false;
  19.     }
  20.      . 鍥磋鎴戜滑@1point 3 acres
  21.     while (rowId < numRows && (array.get(rowId) == null ||
  22.       array.get(rowId).isEmpty())) {
  23.       rowId++;
  24.     }
  25.      
  26.     return rowId < numRows;
  27.   }. 1point3acres.com/bbs
  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;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35.     }
  36.      
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  37.     return ret;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  38.   }
  39.    
  40.   public void remove() {
  41.     List<Integer> listToRemove;
  42.     int rowToRemove;
  43.     int colToRemove;. 1point3acres.com/bbs
  44.      . Waral 鍗氬鏈夋洿澶氭枃绔,
  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);. visit 1point3acres.com for more.
  49.       colToRemove = listToRemove.size() - 1;
  50.        .1point3acres缃
  51.       listToRemove.remove(colToRemove);
  52.     } else { // Case 2: the element to remove is not the last element
  53.       rowToRemove = rowId;
  54.       listToRemove = array.get(rowToRemove);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  55.       colToRemove = colId - 1;. more info on 1point3acres.com
  56.       listToRemove.remove(colToRemove);
  57.     }
  58.      . Waral 鍗氬鏈夋洿澶氭枃绔,
  59.     // If the list to remove has only one element
  60.     if (listToRemove.isEmpty()) {. From 1point 3acres bbs
  61.       array.remove(listToRemove);
  62.       rowId--;
  63.     }
  64.      
  65.     // Update the colId
  66.     if (colId != 0) {
  67.       colId--;
  68.     }. From 1point 3acres bbs
  69.   }
  70.    . more info on 1point3acres.com
  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);
  77.      
  78.     array.add(row1);. 鍥磋鎴戜滑@1point 3 acres
  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()) {. 1point3acres.com/bbs
  90.       int result = sol.next();
  91.       System.out.println(result);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  92.       
  93.       if (result == 3) {
  94.         sol.remove();
  95.       }
  96.     }. From 1point 3acres bbs
  97.      
  98.     System.out.println();
  99.      . 1point 3acres 璁哄潧
  100.     for (List<Integer> row : array) {
  101.       for (Integer elem : row) {
  102.         System.out.println(elem);
  103.       }
  104.     }
  105.   }
  106.    . 1point 3acres 璁哄潧
  107. }
复制代码
回复 支持 反对

使用道具 举报

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. Waral 鍗氬鏈夋洿澶氭枃绔,
iterator的remove() 一并wrap
. more info on 1point3acres.com
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
我和层主有着同样的困惑;不知道你的思路有写过代码吗?

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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