一亩三分地论坛

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

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

facebook intern,挂了,分享个题

[复制链接] |试试Instant~ |关注本帖
yanxiao135 发表于 2015-3-10 04:24:25 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Fail

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

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

x
facebook intern,面挂了也要来做做贡献,看了很多帖子,对我的面试很有帮助,在此谢谢大家的分享。就这一道题,水平太差,时间完了也没搞定。有做过的同学也麻烦分享下code,谢谢啦。

题目如下:
class IntFileIterator {
  boolean hasNext();
  int next(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}

class FileCompare {
  public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b);

}
// return if the distance between a and b is at most 1.
// Distance: minimum number of modifications to make a=b
// Modification:
//   1. change an int in a
//   2. insert an int to a
//   3. remove an int from a


评分

8

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
LawranceH 发表于 2015-3-10 04:29:12 | 显示全部楼层
这题就是leetcode的 Edit Distance….怎么intern 就考hard 难度的
回复 支持 反对

使用道具 举报

laonawuli 发表于 2015-3-10 04:47:47 | 显示全部楼层
这是Leetcode上 One Edit Distance那题。
回复 支持 反对

使用道具 举报

laonawuli 发表于 2015-3-10 04:48:14 | 显示全部楼层
只不过从数组换成了Iterator
回复 支持 反对

使用道具 举报

readman 发表于 2015-3-10 04:50:07 | 显示全部楼层
LawranceH 发表于 2015-3-10 04:29
这题就是leetcode的 Edit Distance….怎么intern 就考hard 难度的

难道先把int变成string么..
回复 支持 反对

使用道具 举报

protenchen 发表于 2015-3-10 05:05:33 | 显示全部楼层
只是问isDistanceZeroOrOne不算难吧?
回复 支持 反对

使用道具 举报

 楼主| yanxiao135 发表于 2015-3-10 05:16:17 | 显示全部楼层
变成iterator,只能从头走一次,不用extra space的话,没想出怎么做。我是想分三种情况,分别试一下,看看是属于哪种情况,但没写出来。面试官举例说[1 2 1 2 1] 和 [2 1 2 1],在做判断的是时候,就需要走完才知道。leetcode没买,只做了string的那个。
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-10 09:51:23 | 显示全部楼层
LZ什么时候面的啊?多久给的结果?
回复 支持 反对

使用道具 举报

 楼主| yanxiao135 发表于 2015-3-10 11:06:18 | 显示全部楼层
北航小涵 发表于 2015-3-10 09:51
LZ什么时候面的啊?多久给的结果?

今天刚面的,都没做出来,肯定挂了啊
回复 支持 反对

使用道具 举报

yarmyarch 发表于 2015-3-10 15:26:47 | 显示全部楼层
这题实际上已经挂掉不少人了。。。. 鍥磋鎴戜滑@1point 3 acres

初看是one edit distance,实际上有个坑就是这个12121/2121和1212/21212这俩case过不了。
回复 支持 反对

使用道具 举报

cow12331 发表于 2015-3-11 07:37:35 | 显示全部楼层
yarmyarch 发表于 2015-3-10 15:26
这题实际上已经挂掉不少人了。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧

初看是one edit distance,实际上有个坑就是这个12121/2121和1212/21 ...

好像可以过吧. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果遇到不同的就recur三种方法,
删除,第一个next,第二个不动. Waral 鍗氬鏈夋洿澶氭枃绔,
替换,两个都next. 1point3acres.com/bbs
插入,第一个不动,第二个next

比如12121,2121
一开始就a.next != b.next
remove,isDistanceZeroOrOne(a.next, b)
change, isDistanceZeroOrOne(a.next, b.next)
insert, isDistanceZeroOrOne(a, b.next)

public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b, int count){
     if(!a.hasNext && !b.hasNext) return true;.鏈枃鍘熷垱鑷1point3acres璁哄潧
     if(count > 1 || a.hasNext ^ b.hasNext) return false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     if(a != b) return false;
     else return isDistanceZeroOrOne(a.next, b.next, count + 1) || isDistanceZeroOrOne(a, b.next, count + 1) || isDistanceZeroOrOne(a.next, b, count + 1)

}.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2015-3-11 07:39):
判断空的时候搞错了
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-3-11 08:24:31 | 显示全部楼层
因为不知道长度,所以遇到不同的时候就三种情况全部考虑,然后如果有一种情况的distance大于等于2,这种情况就停下,最后遍历完以后如果有一种情况的差距是1, 返回true,否则false
回复 支持 反对

使用道具 举报

wcy1984123 发表于 2015-3-11 14:40:52 | 显示全部楼层
cow12331 发表于 2015-3-11 07:37
好像可以过吧
如果遇到不同的就recur三种方法,
删除,第一个next,第二个不动
. 鍥磋鎴戜滑@1point 3 acres
hasNext每次都会返回新的数字。你这种递归的话没有办法在return以后回溯到以前的数字输出。我不知道是不是能够用两个临时的string保存下来 然后用类似one edit distance的方法判定两个临时的string是否满足条件。
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-3-11 16:08:47 | 显示全部楼层
wcy1984123 发表于 2015-3-11 14:40
hasNext每次都会返回新的数字。你这种递归的话没有办法在return以后回溯到以前的数字输出。我不知道是不 ...

我觉得转成string再比较可能不可以,等于用了extra space. 这题的考点应该就是iterator的操作,一边跑一边比较。
回复 支持 反对

使用道具 举报

cow12331 发表于 2015-3-11 21:57:59 | 显示全部楼层
wcy1984123 发表于 2015-3-11 14:40
hasNext每次都会返回新的数字。你这种递归的话没有办法在return以后回溯到以前的数字输出。我不知道是不 ...

public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b, int count){
     if(!a.hasNext && !b.hasNext) return true;
     if(count > 1) return false;
if(a == b) return isDistanceZeroOrOne(a.next, b.next, count);
     return isDistanceZeroOrOne(a.next, b.next, count + 1) || isDistanceZeroOrOne(a, b.next, count + 1) || isDistanceZeroOrOne(a.next, b, count + 1)
相当于两个指针一直移动, 都为空的时候为真,如果修改大于1位false
}
回复 支持 反对

使用道具 举报

cow12331 发表于 2015-3-11 21:59:19 | 显示全部楼层
cow12331 发表于 2015-3-11 21:57
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b, int count){
     if(!a.h ...

把a.next和b.next先存下来就可以回溯了
回复 支持 反对

使用道具 举报

cow12331 发表于 2015-3-11 21:59:38 | 显示全部楼层
cow12331 发表于 2015-3-11 21:57
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b, int count){
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴     if(!a.h ...

把a.next和b.next先存下来就可以回溯了
回复 支持 反对

使用道具 举报

wyni18 发表于 2015-3-12 02:09:42 | 显示全部楼层
cow12331 发表于 2015-3-11 21:59-google 1point3acres
把a.next和b.next先存下来就可以回溯了

是啊,感觉这里的next比较tricky,call a.next的时候a就已经指向下一个了,能把IntFileIterator a保存下来吗
回复 支持 反对

使用道具 举报

mtq 发表于 2015-3-12 05:54:58 | 显示全部楼层
没出结果呢,等等看,Iterator考得好多啊
回复 支持 反对

使用道具 举报

bchen2008 发表于 2015-3-13 07:44:15 | 显示全部楼层
class FileCompare {
  public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b) {
    boolean checkSame = true, checkChange = true, checkAddRemove = false;
    boolean isSame = true, isChange = false, isAdd = false, isRemove = false;
    boolean isFirstLoop = true;   
    int prevA, prevB, curA = 0, curB = 0;
    while (a.hasNext() && b.hasNext()) {
      prevA = curA;
      prevB = curB;
      curA = a.next();
      curB = b.next();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
      
      if (curA != curB) {. 1point 3acres 璁哄潧
        if (checkSame) {
          isSame = false;
          checkSame = false;
        }
        if (checkChange) {
          if (!isChange) {
            isChange = true;
          }
          else {. from: 1point3acres.com/bbs
            isChange = false;
            checkChange = false;.1point3acres缃
          }
        }
        if (!checkAddRemove) {
          checkAddRemove = true;
          isAdd = true;
          isRemove = true;
          continue;
        }-google 1point3acres
      }. From 1point 3acres bbs
      
      if (checkAddRemove) {
        isAdd = isAdd && (curA == prevB);
        isRemove = isRemove && (curB == prevA);
      }
      
      if (!(isSame || isChange || isAdd || isRemove))
        return false;
    }
   
    if (a.hasNext()) {
      a.next();
      return ((isSame || isAdd) && !a.hasNext());
    }   
    if (b.hasNext()) {.1point3acres缃
      b.next();
      return ((isSame || isRemove) && !b.hasNext());
    }. visit 1point3acres.com for more.
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    return (isSame || isChange || isAdd || isRemove);
  }
}. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 18:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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