May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

925 Zenefits 电面

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

2015(7-9月) 码农类 硕士 全职@Zenefits - 内推 - 技术电面 |Failfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
上周五面的,直接上题

. Waral 鍗氬鏈夋洿澶氭枃绔,
arr = [1,2, 3, 1, 2]
Prefixes of the array: [1], [1, 2], [1,2, 3], [1,2,3,1], [1,2,3,1,2]. from: 1point3acres.com/bbs
Suffixes of the array: [2], [1, 2], [3,1,2], [2,3,1,2], [1,2,3,1,2]. From 1point 3acres bbs
. from: 1point3acres.com/bbs
prefix [1,2, 3, 1] == {1, 2, 3}
suffix [1, 2, 3, 1, 2] == {1,2,3}

[1, 2, 3, 1] == [1, 2, 3, 1, 2]

Q.How many prefix-suffix pairs (P, S) are there such that set(P) == set(S)?
.1point3acres缃
input: arr
output: int

感觉写的比较慢,估计还有一题来不及写,这周收到邮件已跪

评分

3

查看全部评分

lcysjw 发表于 2015-10-14 20:04:03 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
ymne06 发表于 2015-10-14 19:09
楼主能否解释下这道题题意呢?我对题中的prefix [1,2, 3, 1] == {1, 2, 3} suffix [1, 2, 3, 1, 2] == {1,2 ...

[1,2,3,1]=={1,2,3} 指的是数组转换成集合
回复 支持 1 反对 0

使用道具 举报

lengyu 发表于 2015-10-12 04:38:35 | 显示全部楼层
关注一亩三分地微博:
Warald
请问楼主用的什么方法解这道题呀~~
回复 支持 反对

使用道具 举报

lcysjw 发表于 2015-10-14 15:16:36 | 显示全部楼层
请问楼主是怎么做的呢,希望交流下~
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我觉得这道题目可以这么做: 时间复杂度O(n) 空间复杂度 O(n)
左右同时扫描,比较prefix和suffix的集合是否相等,如果相等求出相等的数量res += m*n
比如 11211 左边集合为1的数量为2 右边也是2 那么这里肯定就有4种 然后包含2的时候 左边有三种 右边也是三种9种 答案就是4+9=13
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不知道是不是这样
回复 支持 反对

使用道具 举报

ymne06 发表于 2015-10-14 19:09:43 | 显示全部楼层
楼主能否解释下这道题题意呢?我对题中的prefix [1,2, 3, 1] == {1, 2, 3} suffix [1, 2, 3, 1, 2] == {1,2,3}  [1, 2, 3, 1] == [1, 2, 3, 1, 2]不太了解,下周电面zenefit,楼主好人帮帮忙
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-15 00:29:38 | 显示全部楼层
lcysjw 发表于 2015-10-14 15:16
请问楼主是怎么做的呢,希望交流下~

我觉得这道题目可以这么做: 时间复杂度O(n) 空间复杂度 O(n)

如何efficient的比较两个集合是否相等?
回复 支持 反对

使用道具 举报

 楼主| ImGoingSSJ 发表于 2015-10-15 06:14:02 | 显示全部楼层
ymne06 发表于 2015-10-14 19:09
楼主能否解释下这道题题意呢?我对题中的prefix [1,2, 3, 1] == {1, 2, 3} suffix [1, 2, 3, 1, 2] == {1,2 ...

[1, 2, 3, 1] 和 [1, 2, 3, 1, 2] 变成set一样都是{1, 2, 3},所以它们相等
回复 支持 反对

使用道具 举报

 楼主| ImGoingSSJ 发表于 2015-10-15 06:15:41 | 显示全部楼层
lengyu 发表于 2015-10-12 04:38
请问楼主用的什么方法解这道题呀~~

当时好像用的hashset,具体怎么样有点忘了,好像不是最优解,面试官说用hashmap
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-15 08:52:36 | 显示全部楼层
lcysjw 发表于 2015-10-14 15:16
请问楼主是怎么做的呢,希望交流下~

我觉得这道题目可以这么做: 时间复杂度O(n) 空间复杂度 O(n)

"左边集合为1的数量为2" 这里还是要用hashmap做记录吧?
回复 支持 反对

使用道具 举报

lcysjw 发表于 2015-10-15 09:43:18 | 显示全部楼层
darkwowgamer 发表于 2015-10-15 08:52. 鍥磋鎴戜滑@1point 3 acres
"左边集合为1的数量为2" 这里还是要用hashmap做记录吧?
. 1point 3acres 璁哄潧
不需要 直接就可以用一个集合来做
回复 支持 反对

使用道具 举报

lcysjw 发表于 2015-10-15 09:46:14 | 显示全部楼层
aiuou 发表于 2015-10-15 00:29
如何efficient的比较两个集合是否相等?

我没考虑到这个点,貌似也没有特别好的方法,不知楼主是怎么做的
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-15 12:03:46 | 显示全部楼层
我想了个方法,同时从左右两边走,用两个set分别记录prefix set和surfix set。同时maintain一个diffset。如果prefix或surfix有一个新的element, 现查看是否diffset里是否有这个值,如果没有就把这个新elment加入,如果有就把这个值从diffset里剪掉。如果diffset为空,说明目前的prefix set 和 surfix set相同,把这时的prefix/surfix set的长度记录下来放在一个set里,叫pairSet。我还用了两个array分别记录 长度为i的prefixset出现的次数,比如{1,1,1} prefix set就是[1]那么义工出现了3次{1},{1,1},{1,1,1}. visit 1point3acres.com for more.
最后过一遍pairSet,然后把相应的prefix set出现的次数 * surfix set 出现的次数就可以了。
整个算法复杂度应该是O(n)
  1. package zenefits;
  2. import java.util.*;
  3. public class PrefixSurfixArray {
  4. . more info on 1point3acres.com
  5.         public static long getPrefixSurfixPair(int [] a){
  6.                 if(a==null||a.length==0) return 0;
  7.                 int[] leftSetCount = new int[a.length];
  8.                 int[] rightSetCount = new int[a.length];
  9.                 int left=0,right=0;
  10.                 long result=0;. 鍥磋鎴戜滑@1point 3 acres
  11.                 HashSet<Integer> diff = new HashSet<Integer> ();
  12.                 HashSet<Integer> leftSet = new HashSet<Integer> ();. more info on 1point3acres.com
  13.                 HashSet<Integer> rightSet = new HashSet<Integer> ();
  14.                 HashSet<Integer> pairIndex = new HashSet<Integer> ();
  15.                 while(left<a.length||right<a.length){
  16.                         int temp=0;
  17.                         if(leftSet.size()<=rightSet.size()&&left<a.length){
  18.                                 temp=a[left];
  19.                                 if(!leftSet.contains(temp)){
  20.                                         leftSet.add(temp);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.                                         leftSetCount[leftSet.size()-1]=1;-google 1point3acres
  22.                                         if(diff.contains(temp)){
  23.                                                 diff.remove(temp);
  24.                                         }else{. from: 1point3acres.com/bbs
  25.                                                 diff.add(temp);
  26.                                         }                       
  27.                                 }else{
  28.                                         leftSetCount[leftSet.size()-1]++;        .鐣欏璁哄潧-涓浜-涓夊垎鍦
  29.                                 }                       
  30.                                 left++;
  31.                         }else {
  32.                                 temp=a[a.length-1-right];
  33.                                 if(!rightSet.contains(temp)){
  34.                                         rightSet.add(temp);
  35.                                         rightSetCount[leftSet.size()-1]=1;
  36.                                         if(diff.contains(temp)){
  37.                                                 diff.remove(temp);
  38.                                         }else{
  39.                                                 diff.add(temp);. 1point3acres.com/bbs
  40.                                         }. visit 1point3acres.com for more.
  41.                                 }else{
  42.                                         rightSetCount[rightSet.size()-1]++;
  43.                                 }                                . from: 1point3acres.com/bbs
  44.                                 right++;
  45.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  46.                         if(diff.isEmpty()&&!pairIndex.contains(leftSet.size())){. from: 1point3acres.com/bbs
  47.                                 pairIndex.add(leftSet.size());
  48.                         }
  49.                 }        . Waral 鍗氬鏈夋洿澶氭枃绔,
  50.                 for(Integer i: pairIndex){
  51.                         result+=leftSetCount[i-1]*rightSetCount[i-1];
  52.                 }
  53.                 return result;
  54.         }
  55.         public static void main(String[] args) {
  56.                 // TODO Auto-generated method stub
  57.                 int[][] tests={
  58.                                 {1,1,1},
  59.                                 {1,2, 3, 1, 2},
  60.                                 {1,2,3,4,5}
  61.                 };.1point3acres缃
  62.                 for(int[] test:tests){. 1point3acres.com/bbs
  63.                         System.out.println("The number of prefix-surfix pair for array " +Arrays.toString(test)+" is "+getPrefixSurfixPair(test));
  64.                 }
  65.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  66. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  67. }
复制代码
回复 支持 反对

使用道具 举报

ymne06 发表于 2015-10-15 12:57:40 | 显示全部楼层
darkwowgamer 发表于 2015-10-15 08:52
"左边集合为1的数量为2" 这里还是要用hashmap做记录吧?

如果用hashmap怎么做呢?是定义map<set<int>, int>吗?能用set<int>作为map的key吗?
回复 支持 反对

使用道具 举报

lcysjw 发表于 2015-10-15 22:18:40 | 显示全部楼层
aiuou 发表于 2015-10-15 12:03
我想了个方法,同时从左右两边走,用两个set分别记录prefix set和surfix set。同时maintain一个diffset。如 ...
. visit 1point3acres.com for more.
感谢set的对比思路,在你基础优化改进了一下,删去了pair这个存储结构,直接在循环的过程中求得答案
  1. def function(arry):
  2.     leftSetDiff = {}. 1point 3acres 璁哄潧
  3.     rightSetDiff = {}. 1point3acres.com/bbs
  4.     leftSet = {}
  5.     rightSet = {}
  6.     l = len(arry)
  7.     result = 0
  8.     leftIndex, rightIndex = 0, l - 1
  9.     while True:
  10.         m = 0
  11.         leftSet[arry[leftIndex]] = 1
  12.         while leftIndex < l and arry[leftIndex] in leftSet:
  13.             leftIndex += 1
  14.             m += 1
  15.         if arry[leftIndex-1] in rightSetDiff:
  16.             del rightSetDiff[arry[leftIndex-1]]
  17.         else:
  18.             leftSetDiff[arry[leftIndex-1]] = 1
  19.         n = 0
  20.         rightSet[arry[rightIndex]] = 1
  21.         while rightIndex >= 0 and arry[rightIndex] in rightSet:
  22.             rightIndex -= 1
  23.             n += 1
  24.         if arry[rightIndex+1] in leftSetDiff:
  25.             del leftSetDiff[arry[rightIndex+1]]
  26.         else:
  27.             rightSetDiff[arry[rightIndex+1]] = 1
  28.         if len(leftSetDiff) == 0 and len(rightSetDiff) == 0:
  29.             result += m*n
  30.         if rightIndex < 0 or leftIndex >= l:
  31.             break
  32.     return result
复制代码
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-15 23:31:42 | 显示全部楼层
ymne06 发表于 2015-10-15 12:57
. From 1point 3acres bbs如果用hashmap怎么做呢?是定义map吗?能用set作为map的key吗?

在eclipse上试了一下,好像可以。那这道题简单多了
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-16 00:19:13 | 显示全部楼层
这题不是KMP的经典应用么。。。
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-16 00:39:58 | 显示全部楼层
和POJ 2752类似.鏈枃鍘熷垱鑷1point3acres璁哄潧

题意是给你一字符串,找你找到一个子串。使得子串即是原串的前辍,又是原串的后辍。

这和我们这道题就是一模一样了。

代码如下:
  1. #include <cstdio>
  2. #include <cstdlib>. From 1point 3acres bbs
  3. #include <cstring>
  4. #include <string>
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <vector>

  8. using namespace std;

  9. #define print(x) cout << x << endl
  10. #define input(x) cin >> x

  11. void get_next(const string& str, vector<int>& next) {
  12.     int n = str.size();
  13.     next = vector<int>(n + 1, -1);

  14.     for (int pre = -1, suf = 0; pre < n && suf < n; /* pass */) {
  15.         if (pre == -1 || str[pre] == str[suf]) {
  16.             pre++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.             suf++;. visit 1point3acres.com for more.
  18.             next[suf] = pre;
  19.         } else {
  20.             pre = next[pre];
  21.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23. }

  24. int main() { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.     string name;
  26.     vector<int> next;. From 1point 3acres bbs

  27.     while (input(name)) {
  28.         get_next(name, next);
  29.         int n = name.size();
  30.         int u = next[n];
  31.         vector<int> ans;
  32.         ans.push_back(n);
  33.         while (u) {
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  34.             ans.push_back(u);. From 1point 3acres bbs
  35.             u = next[u];
  36.         }
  37.         reverse(ans.begin(), ans.end());
  38.         for (int i = 0; i < ans.size(); i++) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  39.             if (i) {
  40.                 printf(" ");. 鍥磋鎴戜滑@1point 3 acres
  41.             }
  42.             printf("%d", ans[i]);. Waral 鍗氬鏈夋洿澶氭枃绔,
  43.         }
  44.         puts("");. 鍥磋鎴戜滑@1point 3 acres
  45.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.     return 0;
  47. }.鏈枃鍘熷垱鑷1point3acres璁哄潧
复制代码
回复 支持 反对

使用道具 举报

lengyu 发表于 2015-10-16 04:07:44 | 显示全部楼层
ImGoingSSJ 发表于 2015-10-15 06:15
当时好像用的hashset,具体怎么样有点忘了,好像不是最优解,面试官说用hashmap

哦哦,好哒好哒,谢谢楼主,明白啦~
回复 支持 反对

使用道具 举报

ymne06 发表于 2015-10-16 12:24:49 | 显示全部楼层
Wizmann 发表于 2015-10-16 00:39
和POJ 2752类似
. visit 1point3acres.com for more.
题意是给你一字符串,找你找到一个子串。使得子串即是原串的前辍,又是原串的后辍。

此面试题是要前缀字符串构成的集合与后缀字符串构成的集合相等,不是前缀、后缀字符串相等。
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-16 14:12:37 | 显示全部楼层
ymne06 发表于 2015-10-16 12:24
此面试题是要前缀字符串构成的集合与后缀字符串构成的集合相等,不是前缀、后缀字符串相等。

好吧。。。

那Hash就好咯。。。
. 鍥磋鎴戜滑@1point 3 acres
还以为Z家这么变态直接上KMP呢,哈哈
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-30 01:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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