推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

Rubrik 挂经

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

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

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

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

x
今天面的,估计已挂。. 1point 3acres 璁哄潧

一轮:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
(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是异步的怎么办
. Waral 鍗氬鏈夋洿澶氭枃绔,
这种小公司的bar果然还是高啊。


. from: 1point3acres.com/bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Rubrik|主题: 12, 订阅: 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;

  3.     private static class Graph {
  4.         int V;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.         LinkedList<Integer>[] adj;
  6.         Graph (int V) {. more info on 1point3acres.com
  7.             this.V = V;
  8.             adj = new LinkedList[V];
  9.             for (int i=0; i<V; i++) {
  10.                 adj[i] = new LinkedList<>(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11.             }
  12.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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);
    .1point3acres缃
  23.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  24.         List<List<Integer>> findConnected() {
  25. //            System.out.println("/nprint graph");
  26. //            for (LinkedList<Integer> l:adj) System.out.print(l+"--");.1point3acres缃
  27. //            System.out.println();. 鍥磋鎴戜滑@1point 3 acres

  28.             boolean[] visited = new boolean[V];    // bfs to find and combine linked lists-google 1point3acres
  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);
  35.                     visited[i]=true;
  36.                     while (!q.isEmpty()) {. 1point3acres.com/bbs
  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;. more info on 1point3acres.com
  43.                             }
  44.                         }
  45.                     }
  46.                     res.add(temp);
  47.                 }
  48.             }
  49.             return res;
  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<>());. From 1point 3acres bbs
  58.                 map.get(s).add(i);
  59.             }
  60.         }
  61.         //System.out.println(map);
  62.         List<List<Integer>> list = new ArrayList<List<Integer>>(map.values());
  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;
  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 发表于 7 天前 | 显示全部楼层
看着都好难
回复 支持 反对

使用道具 举报

lcq123 发表于 7 天前 | 显示全部楼层
这些题目确实有点难!请问第一题有啥好方法吗?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

 楼主| endofunctor 发表于 7 天前 | 显示全部楼层
cawe 发表于 2017-8-15 15:10
第一题是先用unionfind得出每一个的单词的root,再建一个map找出每一个root下的index,这样做吗

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-22 23:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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