一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1555|回复: 13
收起左侧

Rubrik 挂经

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

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

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

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

x
今天面的,估计已挂。

一轮: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
(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]]。
(2) 给一堆词和一个document,求一个最小子串,使得子串包含所有词(假设子串之间不会share前缀后缀)
二轮:
给一个大文件,给一个API,写一个函数要求transfer这个文件到另一个主机。
三轮:
maximum window sum,followup是如果数据存在磁盘上怎么办(假设有个API copyFromDisk可以从磁盘上拷数据到内存),如果copyFromDisk这个API是异步的怎么办

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




评分

5

查看全部评分

本帖被以下淘专辑推荐:

  • · Rubrik|主题: 17, 订阅: 2
aureus 发表于 2017-8-12 06:18:31 | 显示全部楼层
写了一个,只做了一个test case.
基本思路是先用hashmap把每个string在哪个list出现的index算好。 接下来就是把所有含有相同index的list并起来--这个可以用bfs做。
  1. public class EqualListOfString {
  2.     private Map<String, List<Integer>> map;
    . more info on 1point3acres.com

  3.     private static class Graph {
  4.         int V;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.         LinkedList<Integer>[] adj;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  6.         Graph (int V) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.             this.V = V;
  8.             adj = new LinkedList[V];
  9.             for (int i=0; i<V; i++) {
  10.                 adj[i] = new LinkedList<>();
  11.             }
  12.         }

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

  19. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.         void addEdge(int u, int v) {. 鍥磋鎴戜滑@1point 3 acres
  21.             adj[u].add(v);
  22.             adj[v].add(u);. visit 1point3acres.com for more.
  23.         }

  24.         List<List<Integer>> findConnected() {. 1point 3acres 璁哄潧
  25. //            System.out.println("/nprint graph");
  26. //            for (LinkedList<Integer> l:adj) System.out.print(l+"--");
  27. //            System.out.println();
  28. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  29.             boolean[] visited = new boolean[V];    // bfs to find and combine linked lists
  30.             Queue<Integer> q = new LinkedList<>();
  31.             List<List<Integer>> res = new ArrayList<>();
  32.             for (int i = 0; i < V; i++) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  33.                 if (!visited[i]) {
  34.                     List<Integer> temp = new ArrayList<>();
  35.                     q.add(i);
  36.                     visited[i]=true;
  37.                     while (!q.isEmpty()) {
  38.                         int cur = q.poll();. 1point 3acres 璁哄潧
  39.                         temp.add(cur);
  40.                         for (int neigh:adj[cur]) {
  41.                             if (!visited[neigh]) {
  42.                                 q.add(neigh);
  43.                                 visited[neigh]=true;
  44.                             }
  45.                         }
  46.                     }
  47.                     res.add(temp);
  48.                 }
  49.             }
  50.             return res;
  51.         }
  52.     }
  53. . more info on 1point3acres.com
  54.     public List<List<Integer>> equalList(String[][] arr) {
  55.         map = new HashMap<>();
  56.         int numLists = arr.length;
  57.         for (int i=0; i<arr.length; i++) {
  58.             for (String s:arr[i]) {
  59.                 if (!map.containsKey(s)) map.put(s, new ArrayList<>());
  60.                 map.get(s).add(i);
  61.             }
  62.         }
  63.         //System.out.println(map);
  64.         List<List<Integer>> list = new ArrayList<List<Integer>>(map.values());
  65.         Graph g = new Graph(numLists);
  66.         for (int i=0; i<list.size(); i++) {
  67.             g.addEdges(list.get(i));. 1point3acres.com/bbs
  68.         }
  69.         List<List<Integer>> res = g.findConnected();
  70.         // System.out.println(list);
  71.         return res;
  72.     }

  73.     public static void main(String[] args) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  74.         String[][] arr = {{"abc", "def"},{"def","ghi"},{"abc","ghi","jkl"}, {"abd", "deg"}};
  75. //        List<List<String>> list = new ArrayList<>();
  76. //        for (String[] a:arr) {
  77. //            list.add(new ArrayList<String>(Arrays.asList(a)));
  78. //        }
  79.         EqualListOfString o = new EqualListOfString();
  80.         List<List<Integer>> res = o.equalList(arr);
  81.         //System.out.println(res);
  82.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  83. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| endofunctor 发表于 2017-8-12 11:34:15 | 显示全部楼层
aureus 发表于 2017-8-12 06:18. 鍥磋鎴戜滑@1point 3 acres
写了一个,只做了一个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
第一题是先用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 = {}
  4.                 self.isLeaf = False
  5.                 self.word = ""

  6. class Trie:. 鍥磋鎴戜滑@1point 3 acres
  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:. from: 1point3acres.com/bbs
  13.                                 p.dict[c] = Node()
  14.                         p = p.dict[c]
  15.                 p.isLeaf = True
  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:       
  24.                         return True, start, p.word
  25.                 return False, temp, None
  26. . From 1point 3acres bbs
  27. class Solution:

  28.         def minSubstring(self, words, document):
  29.                 myTrie = Trie()
  30.                 hashmap = {}
  31.                 cnt = len(words)
  32.                 for word in words:
  33.                         myTrie.addWord(word). 1point3acres.com/bbs
  34.                         hashmap[word] = 1
  35. . 鍥磋鎴戜滑@1point 3 acres
  36.                 i = j = 0
  37.                 minLen = float("inf")
  38.                 minI, minJ = 0, 0
  39.                 while i < len(document):
  40.                         found, i, word = myTrie.search(document, i)
  41.                         if found:
  42.                                 hashmap[word] -= 1
  43.                                 if hashmap[word] == 0:
  44.                                         cnt -= 1
  45.                                         while cnt == 0:
  46.                                                 minLen = min(minLen, i - j + 1).1point3acres缃
  47.                                                 minI, minJ = i, j. Waral 鍗氬鏈夋洿澶氭枃绔,
  48.                                                 found2, j, word2 = myTrie.search(document, j). 1point 3acres 璁哄潧
  49.                                                 if found2:
  50.                                                         hashmap[word2] += 1
  51.                                                         if hashmap[word2] == 1:
  52.                                                                 cnt += 1
  53.                 return document[minJ:minI+1]. 鍥磋鎴戜滑@1point 3 acres
  54. . Waral 鍗氬鏈夋洿澶氭枃绔,
  55. s = Solution(). more info on 1point3acres.com
  56. words = ["hello", "this", "is"]
  57. document = "hello world, this is Allen, but I am not a good boy, this is hellothisis"
  58. print(s.minSubstring(words, document))




复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-13 04:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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