一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2447|回复: 18
收起左侧

Zenefits skype 電面

[复制链接] |试试Instant~ |关注本帖
vassili007 发表于 2015-5-14 03:29:19 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Zenefits - 网上海投 - 技术电面 |Fail在职跳槽

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

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

x
剛才結束skype interview, 只完成一題,sigh
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我遇到的題目:
input 為兩個輸入
1. integer
2. list
計算 list中滿足 三個值的和 小於或等於 integer 的數目

e.q.
integer = 8
list = [1, 2, 3, 4, 6]
則結果有三筆:. 1point 3acres 璁哄潧
1, 2, 3
1, 2, 4
1, 3, 4. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

野人獻曝我的方法:
  1. def triplets(_t, _d):   
  2.     _d = sorted(_d)
  3.    
  4.     d_size = len(_d)
  5.     result_count = 0.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.     for i in range(d_size-2):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  7.     left = i + 1
  8.     right = d_size - 1
  9.     while left < right:
  10.     <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">if _d[i] + _d[left] + _d[right] <= _t:</span>
复制代码
我是用leetcode中3sum那題的思維來做, 改的地方只有在 <= 時, 直接剩下還沒跑的加到結果中.
但是執行時間一直過不了最後兩個test case, 面試官後來說python本來就跑的比較慢, 那可能是因為網站沒有設定python的時間設定
雖然他這樣講 不過花了一小時也只寫了這一題 我想應該是沒機會了
希望能把自己的經驗分享給各位 若有更佳的方法也請不吝指教 謝謝. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

5

查看全部评分

本帖被以下淘专辑推荐:

huahuazhu 发表于 2015-5-18 05:55:37 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
vassili007 发表于 2015-5-18 04:10
不用客氣

你說的例子, i = 0, left, right 分別為1, 5.

这里我更加糊涂了
_d = [1, 2, 3, 4, 4, 4, 6], t = 8
index是
0 1 5
0 1 4
0 1 3
0 1 2
对应的set不是有几个重复么?这四组index我的理解是对应两个set [1,2, 4] 和[ 1, 2, 3].
回复 支持 1 反对 0

使用道具 举报

 楼主| vassili007 发表于 2015-5-14 03:34:27 | 显示全部楼层
关注一亩三分地微博:
Warald
不好意思 不知道為什麼 程式沒顯示正確 我po在這

def triplets(_t, _d):   
    _d = sorted(_d)
   
    d_size = len(_d)
    result_count = 0
鏉ユ簮涓浜.涓夊垎鍦拌鍧.     for i in range(d_size-2):

        left = i + 1
        right = d_size - 1
        while left < right:
            if _d[i] + _d[left] + _d[right] <= _t:
                result_count += right - left. 鍥磋鎴戜滑@1point 3 acres
                left +=1
            else:
                right -= 1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    return result_count
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-14 04:36:59 | 显示全部楼层
小于等于的话去重怎么考虑?或者说是怎么包括所有情况?
比如list 是{1,2,3,4} target = 10
当i = 1, 两个pointer left 和right 分别在 2 和 4, 这时 1+2+4 < 10, 然后你left++, 就是1 ,3, 4 了, 你的答案里面还会包括1,2,3的set么?
回复 支持 反对

使用道具 举报

 楼主| vassili007 发表于 2015-5-14 04:45:50 | 显示全部楼层
wangxinlei 发表于 2015-5-14 04:36
小于等于的话去重怎么考虑?或者说是怎么包括所有情况?
比如list 是{1,2,3,4} target = 10
当i = 1,  ...

會的
當pointer left right 分別在2跟4時 target <= 10的條件
.鐣欏璁哄潧-涓浜-涓夊垎鍦結果會加2 (right - left), 這樣就包含了 1 2 3
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-17 09:45:58 | 显示全部楼层
请问楼主,skype店面是怎么做题? 也是hacerrank, 有test case要运行通过才行么?
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-17 12:15:33 | 显示全部楼层
问一下这个题目的条件, 需要考虑有duplicates的情况么? 看楼主的code似乎是假定没有duplicates的
回复 支持 反对

使用道具 举报

 楼主| vassili007 发表于 2015-5-17 18:05:49 | 显示全部楼层
huahuazhu 发表于 2015-5-17 12:15.1point3acres缃
问一下这个题目的条件, 需要考虑有duplicates的情况么? 看楼主的code似乎是假定没有duplicates的

skype電面的話我自己遇到的情況是,
他們先問我的skype id, 然後也給了一個 codepair hackerrank 連結要我面試前幾分鐘連進去,
等到面試時間到時會用skype撥給你, 但是他沒有加好友, 所以會要求把skpye設定成可以接受非好友的撥電話, 我當初也花了面試時間到後花了點時間才設定好, 建議面試前先設定

題目沒有說會有duplication, 不過我的方法是可以處理有duplication的, 假設今天題目如下:
e.q. 1.鏈枃鍘熷垱鑷1point3acres璁哄潧
_d = [1, 2, 3, 4, 4, 6], t = 8. more info on 1point3acres.com
i = 0時, 在left right的index分別是 1,  4 時 得到了三數相加為 8,
這時會直接將結果加 3 ([1 2 3], [1 2 4], [1 2 4])

e.q. 2
_d = [1, 1, 2, 3, 4, 6], t = 8
i = 0時, 在left right的index分別是 1,  5 時 得到了三數相加為 8,
這時會直接將結果加 4 ([1 1 2], [1 1  3], [1 1 4], [1 1 6]), . 1point 3acres 璁哄潧
接下來就不贅述了, 這題答案為10, 結果跑出來也是10
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-18 00:00:37 | 显示全部楼层
vassili007 发表于 2015-5-17 18:05
skype電面的話我自己遇到的情況是,
他們先問我的skype id, 然後也給了一個 codepair hackerrank 連結要 ...

多谢你分享这么详细的经验,我会好好看看skype怎么设置,我以前都没用过skype

我再好好想一下duplicate是怎么处理进去的,我本来以为还需要特殊处理一下。我现在还没想通的是,譬如.1point3acres缃
_d = [1, 2, 3, 4, 4, 4, 6], t = 8
. 1point3acres.com/bbsi = 0時, 在left right的index分別是 1,  5 時 得到了三數相加《= 8, . From 1point 3acres bbs
這時返回4,但是我能想到的组合是 ([1 2 3], [1 2 4], [1 3 4]) 感觉还是之前那几组,想不出第四组时什么
回复 支持 反对

使用道具 举报

 楼主| vassili007 发表于 2015-5-18 04:10:35 | 显示全部楼层
huahuazhu 发表于 2015-5-18 00:00
. from: 1point3acres.com/bbs 多谢你分享这么详细的经验,我会好好看看skype怎么设置,我以前都没用过skype

我再好好想一下duplica ...

不用客氣

你說的例子, i = 0, left, right 分別為1, 5.

這時得到的結果為4, 分別是right從 2~5的可能
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
四個結果如下(數字皆代表index)
0 1 5. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
0 1 4
0 1 3
0 1 2. 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

 楼主| vassili007 发表于 2015-5-18 11:20:03 | 显示全部楼层
huahuazhu 发表于 2015-5-18 05:55
这里我更加糊涂了
_d = [1, 2, 3, 4, 4, 4, 6], t = 8
index是

不好意思, 我懂你的意思了, 我的方法確實沒有辦法避開duplication, 若題目有的話, 在前面加上set()可以去除list中的duplication.
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-18 23:17:42 | 显示全部楼层
vassili007 发表于 2015-5-18 11:20
不好意思, 我懂你的意思了, 我的方法確實沒有辦法避開duplication, 若題目有的話, 在前面加上set()可以去 ...

多谢楼主答疑。 我明白大致的要求了,如果真遇到这个题目,只能跟面试官讨论具体的要求了。 我写了一个允许duplicates的, 请大家一起参详一下。我写的时候按照lc那个要求输出set的内容做的。

  public static ArrayList<ArrayList<Integer>> threeSumEqualOrLess(int[] data, int target) {
    ArrayList<ArrayList<Integer>> output = new ArrayList<>();. 鍥磋鎴戜滑@1point 3 acres
    if(data == null || data.length == 0) {
      return output;
    }
    Arrays.sort(data);
    for(int i = 0; i < data.length - 2; i++) {
      if(i == 0 || data != data[i - 1]) {
        int sum = target - data;. 1point3acres.com/bbs
        int start = i + 1;
        int end = data.length - 1;
        while(start < end) {
          if(data[start] + data[end] <= sum) {
            //need to dedup with merge backWords
            ArrayList<ArrayList<Integer>> temp = mergeAllEndBackwardsResult(data, i, start, end);
            output.addAll(temp);

            start++;. from: 1point3acres.com/bbs
            while (start < end && data[start] == data[start - 1]). 1point3acres.com/bbs
              start++;
          } else {
            end--;.鏈枃鍘熷垱鑷1point3acres璁哄潧
          }
        }
      }
    }
    return output;
  }

  private static ArrayList<ArrayList<Integer>> mergePossibleStartForwardResults(int[] data, int target, int i, int start, int end) {
    ArrayList<ArrayList<Integer>> output = new ArrayList<>();
    while(start <= end - 1 && data[start] != data[start - 1]) {
      if(data + data[start] + data[end] <= target) {
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.add(data);
        temp.add(data[start]);
        temp.add(data[end]);
        output.add(temp);
      }. visit 1point3acres.com for more.
      start++;
    }
    return output;
  }

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-5-19 00:12):
贴错了,上面那个mergePossibleStartForwardResults 没用的。 应该是下面这个method
  public static ArrayList<ArrayList<Integer>> mergeAllEndBackwardsResult(int[] data, int i, int j, int k) {
    ArrayL....鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2015-5-19 00:13):
好像补充不能贴大段的,重新贴在下面一楼
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-19 00:13:22 | 显示全部楼层
  public static ArrayList<ArrayList<Integer>> threeSumEqualOrLess(int[] data, int target) {
    ArrayList<ArrayList<Integer>> output = new ArrayList<>();
    if(data == null || data.length == 0) {. From 1point 3acres bbs
      return output;.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }
    Arrays.sort(data);
    for(int i = 0; i < data.length - 2; i++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      if(i == 0 || data[i] != data[i - 1]) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        int sum = target - data[i];
        int start = i + 1;
        int end = data.length - 1;
        while(start < end) {
          if(data[start] + data[end] <= sum) {
            //need to dedup with merge backWords
            ArrayList<ArrayList<Integer>> temp = mergeAllEndBackwardsResult(data, i, start, end);
            output.addAll(temp);

            start++;
            while (start < end && data[start] == data[start - 1])
              start++;
          } else {
            end--;
          }
        }
      }
    }
    return output;
  }

  public static ArrayList<ArrayList<Integer>> mergeAllEndBackwardsResult(int[] data, int i, int j, int k) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
    ArrayList<ArrayList<Integer>> output = new ArrayList<>(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    while(j < k) {. from: 1point3acres.com/bbs
      ArrayList<Integer> temp = new ArrayList<Integer>();
      temp.add(data[i]);
      temp.add(data[j]);
      temp.add(data[k]);
      output.add(temp);
      System.out.println("mergeToAResult" + Arrays.toString(temp.toArray()));.鐣欏璁哄潧-涓浜-涓夊垎鍦
. more info on 1point3acres.com
      k--;
      //avoid duplicate solutions
      while (j < k && data[k] == data[k + 1])
        k--;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

    }
    return output;
  }
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2015-5-19 02:55:07 | 显示全部楼层
lz 面试官有提这个时间复杂度多少吗
回复 支持 反对

使用道具 举报

 楼主| vassili007 发表于 2015-5-19 07:36:21 | 显示全部楼层
面試官的要求是 O(n), 我的方法中的list sort可以不用, 題目給的似乎都是已經sort好的list
回复 支持 反对

使用道具 举报

volcano 发表于 2015-7-3 03:25:19 | 显示全部楼层
vassili007 发表于 2015-5-19 07:36
面試官的要求是 O(n), 我的方法中的list sort可以不用, 題目給的似乎都是已經sort好的list

没理解错题意的话,好像O(N)不太可能,LZ你确定不是O(N^2)?
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-8-19 03:35:24 | 显示全部楼层
对啊,楼主,这个题你确定O(n)时间复杂度内能做出来??
回复 支持 反对

使用道具 举报

yyboyz 发表于 2016-1-28 01:40:17 | 显示全部楼层
有重复的例子:

1, 2, ,4, 4, 4 要求小于8
当你算到 1+2+4的时候 如果因为小于8而把low++ 那就错了 因为下一个就变成1+4+4=9

这时只需要每次检测
while(low<high&&A[low+1]==A[low]){
//重复加上一个entry
low++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}

while(low<high&&A[high]==A[high--]){
//重复加上一个entry
high--;
}
就可以去重了
回复 支持 反对

使用道具 举报

Cherubic_girl 发表于 2016-2-4 06:35:27 | 显示全部楼层
yyboyz 发表于 2016-1-27 09:40
有重复的例子:

1, 2, ,4, 4, 4 要求小于8

没太看懂lz举的例子。到底duplicates算一个还是多个?如果算一个,那么层主你举的例子里就应该只有一个1,2,4
但如果要算多个就应该有3个1,2,4
彻底晕了。。。. 鍥磋鎴戜滑@1point 3 acres
如果不能算重复的,那么两个while去重也不可取。。。比如[1,1,2,2,3,4,4,4],i=0,j=1,k=7.去重k变到5,但是这时候count就会加上 k-j = 4.但是如果不要重复的,应该只有[1,1,4],[1,2,4],[1,3,4]一共三个。不应该有两个[1,2,4]。。
所以到底怎么去掉重复的呢。。。求指点。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-30 07:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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