10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1117|回复: 13
收起左侧

Rubrik 挂经

[复制链接] |试试Instant~ |关注本帖
endofunctor 发表于 2017-8-10 07:28:37 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Rubrik - 网上海投 - Onsite |Fail在职跳槽

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

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

x
今天面的,估计已挂。
-google 1point3acres
一轮:
(1) 给一个vector<vector<string>> 输入,求等价类并输出等价类中vector<string>的下标;vector<string>的等价关系定义为,如果两个vector中有相同的string,则它们等价。
举例:对于[['abc', 'def'],['def','ghi'],['abc','ghi','jkl']],输出[0,1,2],因为input[0]中有'abc',input[2]中有'abc',所以[0,2]等价,同理[1,2]等价,故[0,1,2]为一个等价类,输出[[0,1,2]]。.1point3acres缃
(2) 给一堆词和一个document,求一个最小子串,使得子串包含所有词(假设子串之间不会share前缀后缀). 1point3acres.com/bbs
二轮:. 鍥磋鎴戜滑@1point 3 acres
给一个大文件,给一个API,写一个函数要求transfer这个文件到另一个主机。.鏈枃鍘熷垱鑷1point3acres璁哄潧
三轮:
maximum window sum,followup是如果数据存在磁盘上怎么办(假设有个API copyFromDisk可以从磁盘上拷数据到内存),如果copyFromDisk这个API是异步的怎么办

这种小公司的bar果然还是高啊。



.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · Rubrik|主题: 14, 订阅: 1
aureus 发表于 2017-8-12 06:18:31 | 显示全部楼层
写了一个,只做了一个test case.. 1point3acres.com/bbs
基本思路是先用hashmap把每个string在哪个list出现的index算好。 接下来就是把所有含有相同index的list并起来--这个可以用bfs做。
  1. public class EqualListOfString {
  2.     private Map<String, List<Integer>> map;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3. . 鍥磋鎴戜滑@1point 3 acres
  4.     private static class Graph {.1point3acres缃
  5.         int V;
  6.         LinkedList<Integer>[] adj;
  7.         Graph (int V) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.             this.V = V;
  9.             adj = new LinkedList[V];.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.             for (int i=0; i<V; i++) {
  11.                 adj[i] = new LinkedList<>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.             } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.         }

  14.         void addEdges(List<Integer> list) {
  15.             if (list.size() <=1) return;
  16.             for (int i=0; i<list.size()-1; i++) {
  17.                 addEdge(list.get(i), list.get(i+1));
  18.             }
  19.         }

  20.         void addEdge(int u, int v) {
  21.             adj[u].add(v);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.             adj[v].add(u);
  23.         }

  24.         List<List<Integer>> findConnected() {
  25. //            System.out.println("/nprint graph");
  26. //            for (LinkedList<Integer> l:adj) System.out.print(l+"--");
  27. //            System.out.println();

  28.             boolean[] visited = new boolean[V];    // bfs to find and combine linked lists. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.             Queue<Integer> q = new LinkedList<>();
  30.             List<List<Integer>> res = new ArrayList<>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.             for (int i = 0; i < V; i++) {
  32.                 if (!visited[i]) {
  33.                     List<Integer> temp = new ArrayList<>();
  34.                     q.add(i);. from: 1point3acres.com/bbs
  35.                     visited[i]=true;
  36.                     while (!q.isEmpty()) {
  37.                         int cur = q.poll();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  38.                         temp.add(cur);
  39.                         for (int neigh:adj[cur]) {
  40.                             if (!visited[neigh]) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  41.                                 q.add(neigh);
  42.                                 visited[neigh]=true;
  43.                             }
  44.                         }
  45.                     }
  46.                     res.add(temp);
  47.                 }
  48.             }
  49.             return res;-google 1point3acres
  50.         }
  51.     }

  52.     public List<List<Integer>> equalList(String[][] arr) {
  53.         map = new HashMap<>();
  54.         int numLists = arr.length;
  55.         for (int i=0; i<arr.length; i++) {
  56.             for (String s:arr[i]) {
  57.                 if (!map.containsKey(s)) map.put(s, new ArrayList<>());. more info on 1point3acres.com
  58.                 map.get(s).add(i);
  59.             }
  60.         }
  61.         //System.out.println(map);
  62.         List<List<Integer>> list = new ArrayList<List<Integer>>(map.values());. From 1point 3acres bbs
  63.         Graph g = new Graph(numLists);
  64.         for (int i=0; i<list.size(); i++) {
  65.             g.addEdges(list.get(i));
  66.         }
  67.         List<List<Integer>> res = g.findConnected();
  68.         // System.out.println(list);
  69.         return res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  70.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  71.     public static void main(String[] args) {
  72.         String[][] arr = {{"abc", "def"},{"def","ghi"},{"abc","ghi","jkl"}, {"abd", "deg"}};
  73. //        List<List<String>> list = new ArrayList<>();
  74. //        for (String[] a:arr) {
  75. //            list.add(new ArrayList<String>(Arrays.asList(a)));
  76. //        }
  77.         EqualListOfString o = new EqualListOfString();
  78.         List<List<Integer>> res = o.equalList(arr);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  79.         //System.out.println(res);
  80.     }
  81. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| endofunctor 发表于 2017-8-12 11:34:15 | 显示全部楼层
aureus 发表于 2017-8-12 06:18
写了一个,只做了一个test case.
基本思路是先用hashmap把每个string在哪个list出现的index算好。 接下来 ...

嗯,也可以先build inverted index,再用union find merge indices,因为是等价关系
回复 支持 反对

使用道具 举报

shuoshuo 发表于 2017-8-15 12:38:11 | 显示全部楼层
看着都好难
回复 支持 反对

使用道具 举报

lcq123 发表于 2017-8-15 14:36:08 | 显示全部楼层
这些题目确实有点难!请问第一题有啥好方法吗?
回复 支持 反对

使用道具 举报

 楼主| endofunctor 发表于 2017-8-15 15:00:16 | 显示全部楼层
lcq123 发表于 2017-8-15 14:36
这些题目确实有点难!请问第一题有啥好方法吗?

第一面第一题当时我就是用二楼的做法做的,只不过把BFS换成了Union find,因为可以证明这个关系是等价关系。
第二题我当时没时间写完了,说了下思路:用字符串匹配算法找到所有substring的起点和终点,因为不会出现"aabc", {"aab", "abc"}这种情况,所以可以把每个字符串想像成一个interval。 这样就可以构造一个interval数组,interval之间没有overlap,而且每个interval的tag就是它对应的string。然后用尺取法可求得最短长度。
回复 支持 反对

使用道具 举报

cawe 发表于 2017-8-15 15:10:49 | 显示全部楼层
第一题是先用unionfind得出每一个的单词的root,再建一个map找出每一个root下的index,这样做吗
回复 支持 反对

使用道具 举报

 楼主| endofunctor 发表于 2017-8-15 15:12:32 | 显示全部楼层
cawe 发表于 2017-8-15 15:10. from: 1point3acres.com/bbs
第一题是先用unionfind得出每一个的单词的root,再建一个map找出每一个root下的index,这样做吗

嗯对的,其实是每行下标的root。
回复 支持 反对

使用道具 举报

tonywen2014 发表于 2017-9-10 10:18:45 | 显示全部楼层
第二题是不是minimum window substring? 只是原题是字母, 这里是单词?
回复 支持 反对

使用道具 举报

 楼主| endofunctor 发表于 2017-9-11 11:28:00 | 显示全部楼层
tonywen2014 发表于 2017-9-10 10:18
第二题是不是minimum window substring? 只是原题是字母, 这里是单词?

嗯是的,字数
回复 支持 反对

使用道具 举报

enjoynet 发表于 2017-9-18 14:21:43 | 显示全部楼层
第二轮到底在考什么,是把文件从一个主机transter到网络上另一主机吗?这要用什么函数,partition file+read+transfer+write不就行了吗?给的API是什么?谢了先!
回复 支持 反对

使用道具 举报

AllenTang123 发表于 2017-10-11 09:57:46 | 显示全部楼层
根据第二题的题意,我的假设是不同的word之间不share字母,所以我用的方法用tire来查找每一个单词。再加上用快慢指针的方法来解决,时间复杂度是O(n^2)
  1. class Node:
  2.         def __init__(self):
  3.                 self.dict = {}. visit 1point3acres.com for more.
  4.                 self.isLeaf = False
  5.                 self.word = ""

  6. class Trie:
  7.         def __init__(self):
  8.                 self.dummy = Node() 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  9.         def addWord(self, word):
  10.                 p = self.dummy. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  11.                 for c in word:
  12.                         if c not in p.dict:
  13.                                 p.dict[c] = Node(). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.                         p = p.dict[c]
  15.                 p.isLeaf = True. From 1point 3acres bbs
  16.                 p.word += word

  17.         def search(self, document, start):
  18.                 temp = start + 1
  19.                 p = self.dummy
  20.                 while start < len(document) and document[start] in p.dict:
  21.                         p = p.dict[document[start]]
  22.                         start += 1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.                 if p.isLeaf:        .1point3acres缃
  24.                         return True, start, p.word
  25.                 return False, temp, None. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  26. class Solution:

  27.         def minSubstring(self, words, document):
  28.                 myTrie = Trie()
  29.                 hashmap = {}. from: 1point3acres.com/bbs
  30.                 cnt = len(words)
  31.                 for word in words:
  32.                         myTrie.addWord(word)
  33.                         hashmap[word] = 1.鐣欏璁哄潧-涓浜-涓夊垎鍦

  34.                 i = j = 0
  35.                 minLen = float("inf")
  36.                 minI, minJ = 0, 0
  37.                 while i < len(document):
  38.                         found, i, word = myTrie.search(document, i)
  39.                         if found:
  40.                                 hashmap[word] -= 1
  41.                                 if hashmap[word] == 0:
  42.                                         cnt -= 1
  43.                                         while cnt == 0:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.                                                 minLen = min(minLen, i - j + 1).鐣欏璁哄潧-涓浜-涓夊垎鍦
  45.                                                 minI, minJ = i, j
  46.                                                 found2, j, word2 = myTrie.search(document, j)
  47.                                                 if found2:
  48.                                                         hashmap[word2] += 1
  49.                                                         if hashmap[word2] == 1:
  50.                                                                 cnt += 1
  51.                 return document[minJ:minI+1]

  52. s = Solution()
  53. words = ["hello", "this", "is"]
  54. document = "hello world, this is Allen, but I am not a good boy, this is hellothisis". 鍥磋鎴戜滑@1point 3 acres
  55. print(s.minSubstring(words, document))



  56. -google 1point3acres
复制代码
回复 支持 反对

使用道具 举报

AllenTang123 发表于 2017-10-11 23:35:08 | 显示全部楼层
楼主说的maximum window sum是指max subarray sum 还是slide window max?谢谢
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-19 17:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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