一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2119|回复: 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. Waral 鍗氬鏈夋洿澶氭枃绔,
計算 list中滿足 三個值的和 小於或等於 integer 的數目

e.q.
integer = 8. Waral 鍗氬鏈夋洿澶氭枃绔,
list = [1, 2, 3, 4, 6]
則結果有三筆:. more info on 1point3acres.com
1, 2, 3
1, 2, 4. visit 1point3acres.com for more.
1, 3, 4

野人獻曝我的方法:
  1. def triplets(_t, _d):   
  2.     _d = sorted(_d)
  3.    
  4.     d_size = len(_d)
  5.     result_count = 0
  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 | 显示全部楼层
vassili007 发表于 2015-5-18 04:10
不用客氣
. more info on 1point3acres.com
你說的例子, 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 | 显示全部楼层
不好意思 不知道為什麼 程式沒顯示正確 我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
                left +=1
            else:
                right -= 1
    return result_count
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-5-14 04:36:59 | 显示全部楼层
小于等于的话去重怎么考虑?或者说是怎么包括所有情况?
比如list 是{1,2,3,4} target = 10. Waral 鍗氬鏈夋洿澶氭枃绔,
当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. From 1point 3acres bbs
小于等于的话去重怎么考虑?或者说是怎么包括所有情况?
比如list 是{1,2,3,4} target = 10
当i = 1,  ...

會的
當pointer left right 分別在2跟4時 target <= 10的條件. Waral 鍗氬鏈夋洿澶氭枃绔,
結果會加2 (right - left), 這樣就包含了 1 2 3
回复 支持 反对

使用道具 举报

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
问一下这个题目的条件, 需要考虑有duplicates的情况么? 看楼主的code似乎是假定没有duplicates的

skype電面的話我自己遇到的情況是,
他們先問我的skype id, 然後也給了一個 codepair hackerrank 連結要我面試前幾分鐘連進去,
等到面試時間到時會用skype撥給你, 但是他沒有加好友, 所以會要求把skpye設定成可以接受非好友的撥電話, 我當初也花了面試時間到後花了點時間才設定好, 建議面試前先設定
. From 1point 3acres bbs
題目沒有說會有duplication, 不過我的方法是可以處理有duplication的, 假設今天題目如下:
e.q. 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
_d = [1, 2, 3, 4, 4, 6], t = 8. 鍥磋鎴戜滑@1point 3 acres
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]),
接下來就不贅述了, 這題答案為10, 結果跑出來也是10
回复 支持 反对

使用道具 举报

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

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

我再好好想一下duplicate是怎么处理进去的,我本来以为还需要特殊处理一下。我现在还没想通的是,譬如
_d = [1, 2, 3, 4, 4, 4, 6], t = 8. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
i = 0時, 在left right的index分別是 1,  5 時 得到了三數相加《= 8,
這時返回4,但是我能想到的组合是 ([1 2 3], [1 2 4], [1 3 4]) 感觉还是之前那几组,想不出第四组时什么
回复 支持 反对

使用道具 举报

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

我再好好想一下duplica ...

不用客氣
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你說的例子, i = 0, left, right 分別為1, 5.

這時得到的結果為4, 分別是right從 2~5的可能

四個結果如下(數字皆代表index)
0 1 5
0 1 4
0 1 3
0 1 2
回复 支持 反对

使用道具 举报

 楼主| 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的内容做的。-google 1point3acres
. 鍥磋鎴戜滑@1point 3 acres
  public static ArrayList<ArrayList<Integer>> threeSumEqualOrLess(int[] data, int target) {
    ArrayList<ArrayList<Integer>> output = new ArrayList<>();.1point3acres缃
    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;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        int start = i + 1;. visit 1point3acres.com for more.
        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++;. more info on 1point3acres.com
            while (start < end && data[start] == data[start - 1]). 1point3acres.com/bbs
              start++;
          } else {
            end--;
. Waral 鍗氬鏈夋洿澶氭枃绔,          }
        }
      }
    }
    return output;
  }-google 1point3acres

  private static ArrayList<ArrayList<Integer>> mergePossibleStartForwardResults(int[] data, int target, int i, int start, int end) {. Waral 鍗氬鏈夋洿澶氭枃绔,
    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);. Waral 鍗氬鏈夋洿澶氭枃绔,
      }
      start++;
    }
    return output;-google 1point3acres
  }


补充内容 (2015-5-19 00:12):
贴错了,上面那个mergePossibleStartForwardResults 没用的。 应该是下面这个method
  public static ArrayList<ArrayList<Integer>> mergeAllEndBackwardsResult(int[] data, int i, int j, int k) {-google 1point3acres
    ArrayL...
. visit 1point3acres.com for more.
补充内容 (2015-5-19 00:13):. Waral 鍗氬鏈夋洿澶氭枃绔,
好像补充不能贴大段的,重新贴在下面一楼
回复 支持 反对

使用道具 举报

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) {. Waral 鍗氬鏈夋洿澶氭枃绔,
      return output;. Waral 鍗氬鏈夋洿澶氭枃绔,
    }
    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--;. 1point 3acres 璁哄潧
          }
. 1point3acres.com/bbs        }
      }
    }
    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) {
      ArrayList<Integer> temp = new ArrayList<Integer>();
      temp.add(data[i]);
      temp.add(data[j]);-google 1point3acres
      temp.add(data[k]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      output.add(temp);
      System.out.println("mergeToAResult" + Arrays.toString(temp.toArray()));

      k--;
      //avoid duplicate solutions
      while (j < k && data[k] == data[k + 1])
        k--;. from: 1point3acres.com/bbs
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    }
    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.1point3acres缃
面試官的要求是 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
. 1point 3acres 璁哄潧
这时只需要每次检测
while(low<high&&A[low+1]==A[low]){
//重复加上一个entry
low++;. more info on 1point3acres.com
}. Waral 鍗氬鏈夋洿澶氭枃绔,

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

使用道具 举报

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
彻底晕了。。。
如果不能算重复的,那么两个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, 2016-12-4 20:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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