Massive Algorithms: Snap Interview Misc

1。meeting room的题目，
给一串meeting room 时间，问是否能够schedule，
【1，2】，【3，4】，【5，6】

2. followup
给一串meeting room 时间，需要多少个meeting room

http://www.1point3acres.com/bbs/thread-282977-1-1.html

题目是离口73. 先让我用两个矩阵来写。然后说time space complexity。然后优化成了in－space。秒杀。

问楼主有没有用过snapchat，楼主我工作都10年了，没有其他盆友用它啊，所以我说没有ative用过。整个过程感觉小哥都很冷淡，然后也实在没有什么可以聊的了。一个小时的面提前了大概10分钟。

今天居然被拒了。实在不理解

如果跑出来的程序有bug，肯定会被拒

第一题很简单一bug自己改了，第二题没bug，面试官还是国人，还是挂了。唯一可能让他觉得不爽的可能是，中间第一题写完了后我的手机没电了，然后过了一会才连上

http://www.1point3acres.com/bbs/thread-190847-1-1.html

电面： LeetCode原题 Jump Game 1和2
onsite:
第一轮是个外国小哥，算术式Evaluation, 要求支持+-*/()。
第二轮是个国人大哥，一个2D平面有一堆雷达（雷达有x, y坐标，以及能探测到的范围r半径）
然后又一辆小车要从y=0和y=1的区间里面通过并且不能被雷达探测到。让写一个function看小车能不能通过。

雷达那题是这样的：一个tunnel，范围是[0，1]中间有各种尺寸的雷达，(x, y, r)，一个小车只有不被雷达监测的地方可以通过，问给定一个List<Radar>判断小车能不能过去。这轮最成功，一点点和大哥分析出需求，做出来的。最后做完题，边走还边和大哥聊天，指出了在snapchat使用中有个小bug，大哥表示会反映一下

第三轮是个印度小哥，Game of Life原题
第四轮是个外国大叔，基本上纯behavior，最后问了一个很简单的题目，就是Leetcode Unique Path ii.
他家聊天会聊很久，大家要注意点聊天技巧。聊得开心就好

http://www.1point3acres.com/bbs/thread-286096-1-1.html

seattle电面，已跪。遇到了一道题，在提示下提出了一种错误的解法。上来分享一下。题目是给出一个数组，输出符合a^2+b^2=c^2 的(a,b,c)组合。
brute force很简单，三个for循环, O(n^3). 要求优化，提出了用3sum的想法去解，然后让写code。写完了之后，讨论了一些edge case, 然后挂了。
问题在于，3sum 的思想不适用于这里，这个问题是a^2+b^2 －c^2 ＝0, 而不是a^2+b^2 ＋c^2 ＝0。
譬如（x, y, z, t) 选中 x, 然后 x^2 + y^2 < t^2, 这时既可以选择x^2 +z^2 和 t^2比较，也可以选择x^2 + y^2 和 z^2比较。假如是3sum, x + y +t <0, 只能是选择x + z+t 进行判断。
所以这个解法是错的。不知道大家有什么想法。但很显然，面试官没有发现这个错，否则在写之前就应该否定

public static List<List<Integer>> getCompleteSquares(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length < 3) return res;

Arrays.sort(nums);
//[1,2,3,4,5,6,7,8,9,10];
//a^ + b^ = c^
for(int i = nums.length - 1; i >= 2; i--) {
if(i != nums.length - 1 && nums[i] == nums[i+1]) continue;
int left = 0, right = i - 1;
while(left < right) {
int sum = nums[left] * nums[left] + nums[right] * nums[right];
if(sum < nums[i] * nums[i]) {
left++;
}else if(sum > nums[i] * nums[i]) {
right--;
}else{
List<Integer> path = new ArrayList<>();
path.add(nums[left]);
path.add(nums[right]);
path.add(nums[i]);
res.add(path);
left++;
right--;
while(nums[left] == nums[left-1]) left++;
while(nums[right] == nums[right+1]) right--;
}
}
}

return res;
}

http://www.1point3acres.com/bbs/thread-168446-1-1.html

29号snapchat电面

第一题

给一个矩阵，对角线打印数字比如

1 2 34 5

6 7 89 10

1112 13 14 15

输出

1

26

37 11

48 12

59 13

1014

直接将元素matrix(i, j), Then按顺序存到第i+j行
*/
public static List<List<Integer>> printMatrix(int[][] nums) {

      List<List<Integer>> res = new ArrayList<>();
      if (nums == null || nums.length == 0)
         return res;

      int rows = nums.length + nums[0].length - 1;

      for (int i = 0; i < rows; i++)
         res.add(new ArrayList<>());

      for (int i = 0; i < nums.length; i++) {
         for (int j = 0; j < nums[0].length; j++) {

            res.get(i + j).add(nums[i][j]);
         }
      }

      return res;
}

两个string一长T 一短S

find anagramsubstring of S in T in linear time

有史以来最简单店面。。。。。1。如何给一个字符串去重后按字母表顺序排列输出。
2. 按反字母表顺序排列
http://www.1point3acres.com/bbs/thread-213778-1-1.html
之后写的很顺，改了几个syntax error，跑了一下一遍就过了。我当时还在庆幸自己运气好没漏写什么步骤。
之后又问了follow up怎么提速，我说有对称，小哥很满意，然后就结束了，还说让我等待next step。结果今天早上收到拒信，还不给feeback。我哪里可能有问题么？

刚跟recuriter 反馈过，拿到了加面机会。之前被弄错面的是nyc 新office，bar非常高，culturefit那块挂了。加面la

问了很多当前的项目问题，他们比较偏前端，javascript
算法题问了word ladder的变体，如果能发现就返回真，不能发现就返回假
例子：{“abc”,"acd","abd","acc"}
from: abc
to: acc

然后又问了一些domain knowledge，bfs，dfs。。。

Snap Interview Misc

Labels

Popular Posts