《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3929|回复: 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 {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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) {. more info on 1point3acres.com
  10.     this.array = array;
  11.     rowId = 0;
  12.     colId = 0;. 鍥磋鎴戜滑@1point 3 acres
  13.     numRows = array.size();
  14.   }
  15.    
  16.   public boolean hasNext() {
  17.     if (array == null || array.isEmpty()) {
  18.       return false;-google 1point3acres
  19.     }
  20.      
  21.     while (rowId < numRows && (array.get(rowId) == null || .鐣欏璁哄潧-涓浜-涓夊垎鍦
  22.       array.get(rowId).isEmpty())) {
  23.       rowId++;
  24.     }
  25.      
    . visit 1point3acres.com for more.
  26.     return rowId < numRows;
  27.   }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.    
  29.   public int next() {
  30.     int ret = array.get(rowId).get(colId);
  31.     colId++;
  32.     if (colId == array.get(rowId).size()) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  33.       rowId++;. 1point3acres.com/bbs
  34.       colId = 0;
  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) {. From 1point 3acres bbs
  47.       rowToRemove = rowId - 1;. visit 1point3acres.com for more.
  48.       listToRemove = array.get(rowToRemove);
  49.       colToRemove = listToRemove.size() - 1;
    . from: 1point3acres.com/bbs
  50.       
  51.       listToRemove.remove(colToRemove);. 1point 3acres 璁哄潧
  52.     } else { // Case 2: the element to remove is not the last element. 1point 3acres 璁哄潧
  53.       rowToRemove = rowId;
  54.       listToRemove = array.get(rowToRemove);
  55.       colToRemove = colId - 1;. From 1point 3acres bbs
  56.       listToRemove.remove(colToRemove);
  57.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  58.      .鐣欏璁哄潧-涓浜-涓夊垎鍦
  59.     // If the list to remove has only one element
  60.     if (listToRemove.isEmpty()) {
  61.       array.remove(listToRemove);
  62.       rowId--;
  63.     }
  64.      
  65.     // Update the colId. Waral 鍗氬鏈夋洿澶氭枃绔,
  66.     if (colId != 0) {
  67.       colId--;
  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);
  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);. more info on 1point3acres.com
  89.     while (sol.hasNext()) {
  90.       int result = sol.next();. 1point 3acres 璁哄潧
  91.       System.out.println(result);.1point3acres缃
  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) {
  102.         System.out.println(elem);
  103.       }
  104.     }
  105.   }
  106.    
  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. more info on 1point3acres.com
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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 07:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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