谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2297|回复: 13
收起左侧

Rubrik 挂经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
endofunctor 发表于 2017-8-10 07:28:37 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2017(7-9月) 码农类General 硕士 全职@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前缀后缀)
二轮:. Waral 博客有更多文章,
给一个大文件,给一个API,写一个函数要求transfer这个文件到另一个主机。. 围观我们@1point 3 acres
三轮:.留学论坛-一亩-三分地
maximum window sum,followup是如果数据存在磁盘上怎么办(假设有个API copyFromDisk可以从磁盘上拷数据到内存),如果copyFromDisk这个API是异步的怎么办

这种小公司的bar果然还是高啊。
-google 1point3acres



评分

参与人数 5大米 +42 收起 理由
ljclin + 3 很有用的信息!
没有蛀牙 + 3 感谢分享!
noname01 + 3 谢谢你的介绍!
enjoynet + 3 感谢分享!
zzwcsong + 30

查看全部评分


上一篇:IXL learing OA这个第四题是不是有问题
下一篇:亚麻20分钟非coding技术面

本帖被以下淘专辑推荐:

  • · Rubrik|主题: 18, 订阅: 4
我的人缘0
aureus 发表于 2017-8-12 06:18:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
写了一个,只做了一个test case.
基本思路是先用hashmap把每个string在哪个list出现的index算好。 接下来就是把所有含有相同index的list并起来--这个可以用bfs做。
  1. public class EqualListOfString {
  2.     private Map<String, List<Integer>> map;

  3. . 1point3acres
  4.     private static class Graph {
  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) {.本文原创自1point3acres论坛
  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.             }. visit 1point3acres for more.
  19.         }

  20.         void addEdge(int u, int v) {
  21.             adj[u].add(v);
  22.             adj[v].add(u);. visit 1point3acres for more.
  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);
  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);. 1point 3acres 论坛
  42.                                 visited[neigh]=true;
  43.                             }
  44.                         }
  45.                     }
  46.                     res.add(temp);
  47.                 }
  48.             }
  49.             return res;
  50.         }. 围观我们@1point 3 acres
  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<>());
  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));. 围观我们@1point 3 acres
  66.         }
  67.         List<List<Integer>> res = g.findConnected();
  68.         // System.out.println(list);
  69.         return res;. visit 1point3acres for more.
  70.     }

  71.     public static void main(String[] args) {
  72.         String[][] arr = {{"abc", "def"},{"def","ghi"},{"abc","ghi","jkl"}, {"abd", "deg"}};
    . 1point3acres
  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. }
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| endofunctor 发表于 2017-8-12 11:34:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
aureus 发表于 2017-8-12 06:18
写了一个,只做了一个test case.
基本思路是先用hashmap把每个string在哪个list出现的index算好。 接下来 ...

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

使用道具 举报

我的人缘0
shuoshuo 发表于 2017-8-15 12:38:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
看着都好难
回复 支持 反对

使用道具 举报

我的人缘0
lcq123 发表于 2017-8-15 14:36:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这些题目确实有点难!请问第一题有啥好方法吗?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| endofunctor 发表于 2017-8-15 15:00:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
lcq123 发表于 2017-8-15 14:36
这些题目确实有点难!请问第一题有啥好方法吗?

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

使用道具 举报

我的人缘0
cawe 发表于 2017-8-15 15:10:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题是先用unionfind得出每一个的单词的root,再建一个map找出每一个root下的index,这样做吗
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| endofunctor 发表于 2017-8-15 15:12:32 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
cawe 发表于 2017-8-15 15:10
第一题是先用unionfind得出每一个的单词的root,再建一个map找出每一个root下的index,这样做吗

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

使用道具 举报

我的人缘0
tonywen2014 发表于 2017-9-10 10:18:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第二题是不是minimum window substring? 只是原题是字母, 这里是单词?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| endofunctor 发表于 2017-9-11 11:28:00 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
tonywen2014 发表于 2017-9-10 10:18
第二题是不是minimum window substring? 只是原题是字母, 这里是单词?

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

使用道具 举报

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

使用道具 举报

我的人缘0
AllenTang123 发表于 2017-10-11 09:57:46 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
根据第二题的题意,我的假设是不同的word之间不share字母,所以我用的方法用tire来查找每一个单词。再加上用快慢指针的方法来解决,时间复杂度是O(n^2)
  1. class Node:
  2.         def __init__(self):
  3.                 self.dict = {}
  4.                 self.isLeaf = False. From 1point 3acres bbs
  5.                 self.word = ""

  6. class Trie:
  7.         def __init__(self):
  8.                 self.dummy = Node()
  9. .本文原创自1point3acres论坛
  10.         def addWord(self, word):
  11.                 p = self.dummy
  12.                 for c in word:
  13.                         if c not in p.dict:
  14.                                 p.dict[c] = Node(). 一亩-三分-地,独家发布
  15.                         p = p.dict[c]. 1point3acres
  16.                 p.isLeaf = True
  17.                 p.word += word

  18.         def search(self, document, start):
  19.                 temp = start + 1
  20.                 p = self.dummy
  21.                 while start < len(document) and document[start] in p.dict:
  22.                         p = p.dict[document[start]]
  23.                         start += 1
  24.                 if p.isLeaf:       
  25.                         return True, start, p.word. From 1point 3acres bbs
  26.                 return False, temp, None

  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)
  34.                         hashmap[word] = 1. 一亩-三分-地,独家发布

  35.                 i = j = 0
  36.                 minLen = float("inf")
  37.                 minI, minJ = 0, 0
  38.                 while i < len(document):
  39.                         found, i, word = myTrie.search(document, i)
  40.                         if found: 来源一亩.三分地论坛.
  41.                                 hashmap[word] -= 1
  42.                                 if hashmap[word] == 0:
  43.                                         cnt -= 1. 1point 3acres 论坛
  44.                                         while cnt == 0:
    . 1point3acres
  45.                                                 minLen = min(minLen, i - j + 1)
  46.                                                 minI, minJ = i, j
  47.                                                 found2, j, word2 = myTrie.search(document, j)
  48.                                                 if found2:
  49.                                                         hashmap[word2] += 1
  50.                                                         if hashmap[word2] == 1:
  51.                                                                 cnt += 1.本文原创自1point3acres论坛
  52.                 return document[minJ:minI+1]

  53. s = Solution()
  54. words = ["hello", "this", "is"]
  55. document = "hello world, this is Allen, but I am not a good boy, this is hellothisis"
  56. print(s.minSubstring(words, document))

  57. .1point3acres网


复制代码
回复 支持 反对

使用道具 举报

我的人缘0
AllenTang123 发表于 2017-10-11 23:35:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主说的maximum window sum是指max subarray sum 还是slide window max?谢谢
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-6-24 15:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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