Snapchat phone interview
1.一开始问了很多暑假实习的内容，coding题目是一个矩阵里某些位置有墙，给一个出发点及目的地，求最短距离。 follwup是现在墙可以打破，没打破一个cost为1，求cost最小的路线
follow up : use min heap to record the cost as proceeding
//test case input:
[
[0,0,0,s,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,e],
[0,0,0,0,0,0],
]
import java.util.*;
public class FindPath {
private int[][] dirt = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};
public static void main(String[] args) {
int[][] matrix = new int[][]{{0,0,1,0,1,0},{0,0,0,0,1,0},{0,0,0,1,0,0},{0,0,0,1,0,0},{0,0,1,0,0,0},{0,0,0,0,0,0}};
int[] start = new int[]{0,3};
int[] end = new int[]{4,5};
FindPath test = new FindPath();
System.out.println(test.findpath1(matrix,start,end));
}
public int findpath1(int[][] matrix, int[] start, int[] end){
if(matrix.length==0||matrix[0].length==0) return -1;
int row = matrix.length;
int col = matrix[0].length;
Queue<int[]> qe = new LinkedList<>();
qe.offer(new int[]{start[0],start[1],0});
matrix[start[0]][start[1]] = 2;
while(!qe.isEmpty()){
int[] crt = qe.poll();
int lvl = crt[2];
if(crt[0]==end[0]&&crt[1]==end[1]) return lvl;
for(int[] ea : dirt){
int x = crt[0] + ea[0];
int y = crt[1] + ea[1];
if(x<0||x>=row||y<0||y>=col) continue;
if(matrix[x][y]!=0) continue;
qe.offer(new int[]{x,y,lvl+1});
matrix[x][y] = 2;
}
}
return -1;
}
}
import java.util.*;
public class Test {
public int minCost(int[][] maze, int start_x, int start_y, int end_x, int end_y){
if(maze==null||maze.length==0||maze[0].length==0) return -1;
int row = maze.length;
int col = maze[0].length;
boolean[][] visited = new boolean[row][col];
PriorityQueue<Position> heap = new PriorityQueue<>(new Comparator<Position>(){
public int compare(Position p1, Position p2){
return p1.cost-p2.cost;
}
});
heap.offer(new Position(start_x,start_y,0,null));
visited[start_x][start_y] = true;
int[][] dirts = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
while(!heap.isEmpty()){
Position crt = heap.poll();
for(int[] dirt : dirts){
int next_x = crt.x + dirt[0];
int next_y = crt.y + dirt[1];
if(next_x<0||next_y<0||next_x>=row||next_y>=col||visited[next_x][next_y]) continue;
if(next_x == end_x && next_y == end_y) return crt.cost;
int cost = crt.cost + (maze[next_x][next_y] == 1 ? 1 : 0);
heap.offer(new Position(next_x,next_y,cost,crt));
}
}
return -1;
}
public class Position {
int x,y;
Position prev;
int cost;
public Position(int x, int y, int cost, Position prev){
this.x = x;
this.y = y;
this.cost = cost;
this.prev = prev;
}
}
public static void main(String[] args) {
Test test = new Test();
int[][] maze = new int[][]{{1,1,1,8,0,1},{1,1,1,1,1,1},{1,1,1,1,1,1},{1,1,1,1,0,1},{1,1,1,1,1,8},{1,1,1,1,1,1}};
// int[][] maze = new int[][]{{8,1,1},{1,1,1},{1,1,8}};
for(int[] row : maze) System.out.println(Arrays.toString(row));
System.out.println(test.minCost(maze,0,3,4,5));
}
}
2.detect cycle in directed graph
import java.util.*;
public class DetectGraphCycle {
public class Node {
int val;
List<Node> next;
public Node(int val){
this.val = val;
next = new ArrayList<>();
}
}
public List<Node> generateGraph(){
List<Node> graph = new ArrayList<>();
Node g1 = new Node(1);
graph.add(g1);
Node g2 = new Node(2);
graph.add(g2);
Node g4 = new Node(4);
graph.add(g4);
Node g5 = new Node(5);
graph.add(g5);
Node g6 = new Node(6);
graph.add(g6);
g1.next.add(g2);
g4.next.add(g1);
g4.next.add(g5);
g5.next.add(g6);
g6.next.add(g4);
return graph;
}
public boolean hasCycle(List<Node> graph){
Set<Node> whiteset = new HashSet<>();
Set<Node> grayset = new HashSet<>();
Set<Node> blackset = new HashSet<>();
for(Node ea : graph){
whiteset.add(ea);
}
while(whiteset.size()>0){
Node crt = whiteset.iterator().next();
if(DFS(crt,whiteset,grayset,blackset)) return true;
}
return false;
}
public boolean DFS(Node crt, Set<Node> whiteset, Set<Node> grayset, Set<Node> blackset){
whiteset.remove(crt);
grayset.add(crt);
for(Node ea : crt.next){
if(blackset.contains(ea)) continue;
if(grayset.contains(ea)) return true;
if(DFS(ea,whiteset,grayset,blackset)) return true;
}
grayset.remove(crt);
blackset.add(crt);
return false;
}
public static void main(String[] args) {
DetectGraphCycle test = new DetectGraphCycle();
System.out.println(test.hasCycle(test.generateGraph()));
}
}
3.Bigint实现加法。题目简单，最好代码一遍过
import java.util.*;
public class BigInt {
public String add(String s1, String s2){
StringBuilder rst = new StringBuilder();
int idx1 = s1.length()-1;
int idx2 = s2.length()-1;
int carry = 0;
while(idx1>=0||idx2>=0){
int sum = carry;
if(idx1>=0) sum += s1.charAt(idx1--)-'0';
if(idx2>=0) sum += s2.charAt(idx2--)-'0';
rst.append(sum%10);
carry = sum/10;
}
if(carry!=0) rst.append(carry);
return rst.reverse().toString();
}
public static void main(String[] args) {
BigInt test = new BigInt();
String s1 = "1231231";
String s2 = "234234";
System.out.println(test.add(s1,s2));
}
}
4.给一个二维数组，对角线打印
1 2 3 4
5 6 7 8
9 10 11 12
打印出
1
2 5
3 6 9
4 7 10
8 11
12
import java.util.*;
public class PrintArray {
public List<List<Integer>> print(int[][] ipt) {
List<List<Integer>> rst = new ArrayList<>();
if(ipt.length==0||ipt[0].length==0) return rst;
int row = ipt.length;
int col = ipt[0].length;
int n = row+col-2;//each line
for(int i=0;i<=n;i++){
rst.add(new ArrayList<>());
for(int j=Math.max(0,i-col+1);j<=Math.min(i,row-1);j++){
rst.get(i).add(ipt[j][i-j]);
}
}
return rst;
}
public static void main(String[] args) {
PrintArray test = new PrintArray();
int[][] ipt = new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
System.out.println(test.print(ipt));
}
}
5.给定字符串A，B， 判断A中是否存在子串是B的anagram
public class Anagram {
public boolean hasAnagram(String s1, String s2){
int[] map = new int[128];
int cnt = s2.length();
for(int i=0;i<s2.length();i++) map[s2.charAt(i)]++;
int L=0,R=0;
while(R < s1.length()){
char c = s1.charAt(R++);
map[c]--;
if(map[c]>=0) cnt--;
if(R>=s2.length()){
if(cnt==0) return true;
char k = s1.charAt(L++);
map[k]++;
if(map[k]>0) cnt++;
}
}
return false;
}
public static void main(String[] args) {
Anagram test = new Anagram();
System.out.println(test.hasAnagram("fsssdweeas","sdf"));
}
}
6.用array实现arraylist
int[] array;
int size;
7.写一个level order traversal
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> rst = new ArrayList<>();
List<Integer> crt = new ArrayList<>();
Queue<TreeNode> qe = new LinkedList<>();
if(root==null) return rst;
qe.offer(root);
TreeNode dummy = new TreeNode(0);
qe.offer(dummy);
while(!qe.isEmpty()){
TreeNode n = qe.poll();
if(n==dummy){
rst.add(new ArrayList<>(crt));
crt.clear();
if(!qe.isEmpty()) qe.offer(dummy);
continue;
}
if(n.left!=null) qe.offer(n.left);
if(n.right!=null) qe.offer(n.right);
crt.add(n.val);
}
return rst;
}
}
8.给你一个integer set和一个target,找出set用所有integer和能组成target的， 数字可以重复，排列可以不一样，比如set 是 1 3 5，target 是5, 那么需要输出 3 1 1， 1 3 1， 1 1 3， 是Leetcode上的变种，想了一下用一个dfs搞定。follow up是数字不重复怎么办，其实就是每次取一个数后将他从set中移除，回朔时在加上去。
import java.util.*;
public class CombinationSum {
private List<List<Integer>> rst = new ArrayList<>();
private List<Integer> crt = new ArrayList<>();
public List<List<Integer>> combination(int[] mem, int tar){
rst.clear();
crt.clear();
backtracking(mem,0,tar);
return rst;
}
public List<List<Integer>> combination2(int[] mem, int tar){
rst.clear();
crt.clear();
backtracking2(mem,0,0,tar);
return rst;
}
public void backtracking(int[] mem, int sum, int tar){
if(sum>tar) return;
if(sum==tar){
rst.add(new ArrayList<>(crt));
return;
}
for(int ea : mem){
crt.add(ea);
backtracking(mem,sum+ea,tar);
crt.remove(crt.size()-1);
}
}
public void backtracking2(int[] mem, int idx, int sum, int tar){
if(sum>tar) return;
if(sum==tar){
rst.add(new ArrayList<>(crt));
return;
}
for(int i=idx;i<mem.length;i++){
crt.add(mem[i]);
backtracking2(mem,i+1,sum+mem[i],tar);
crt.remove(crt.size()-1);
}
}
public static void main(String[] args) {
CombinationSum test = new CombinationSum();
int[] mem = new int[]{1,3,5};
System.out.println(test.combination2(mem,4));
}
}
9.level order travesal, 要求不要用recursive, 用了bfs(See above 7 problem)
10.Implement a BigInt class，Implement the multiply method(See problem summary bigint)
11.LeetCode 原题 Binary Tree Vertical Order Traversal
import java.util.*;
public class VerticalOrderTrav {
public List<List<Integer> verticalorder(TreeNode root){
List<List<Integer>> rst = new ArrayList<>();
if(root==null) return rst;
Map<Integer,List<Intege>> map = new HashMap<>();
Queue<TreeNode> qe = new LinkedList<>();
Queue<Integer> lvl = new LinkedList<>();
qe.offer(root);
lvl.offer(0);
int L=0,R=0;
while(!qe.isEmpty()){
TreeNode crt = qe.poll();
int crt_lvl = lvl.poll();
if(!map.containsKey(crt_lvl)) map.put(crt_lvl, new ArrayList<>());
map.get(crt_lvl).add(crt.val);
if(crt.left!=null){
qe.offer(crt.left);
lvl.offer(crt_lvl-1);
L = Math.min(L,crt_lvl-1);
}
if(crt.right!=null){
qe.offer(crt.right);
lvl.offer(crt_lvl+1);
R = Math.max(R,crt_lvl+1);
}
}
for(int i=L;i<=R;i++) rst.add(map.get(i));
return rst;
}
}
12.给你一些interviews 的起始时间和终止时间，问如何安排interview用的meeting room的数量最短。就是LC meeing room II 的变形。 要输出最后如何安排,先按照起始时间排序。 然后建一个heap， 把终止时间依次加进去。 每次加一个新的回忆， 访问heap的根来看是否有可以用的meeting room,没有就在分配一个。有的话就pop 出来复用这个room,最后跑了几个test case.小哥人不错， 一直给建议说变量名要好好起。。。面了30 分钟左右就结束了。一天了还没消息。。。。。感觉已跪， 求给个onsite的机会， 二面也行。。。。
public class MeetingRoom {
public int minMeetingRoom(Interval[] intervals){
if(intervals==null||intervals.length==0) return 0;
Arrays.sort(intervals, new Comparator<Interval>(){
public int compare(Interval i1, Interval i2){
return i1.start-i2.start;
}
});
//handle end times
PriorityQueue<Integer> endTimes = new PriorityQueue<>();
endTimes.offer(intervals[0].end);
for(int i=1;i<intervals.length;i++){
/*比如第一个时间段我们放入房间1，然后第二个时间段，
如果和房间1的结束时间不冲突，就放入房间1，否则开辟一个房间2。
然后第三个时间段，如果和房间1或者房间2的结束时间不冲突，就放入房间1或者2，
否则开辟一个房间3，依次类推，最后统计开辟了多少房间,所以说房间只增或不变，不会减少
以此来记录总共开辟了多少房间*/
if(intervals[i].start>=endTimes.peek()) endTimes.poll();
endTimes.offer(intervals[i].end);
}
return endTimes.size();
}
public List<List<Interval>> scheduleMeetingRoom(Interval[] intervals){
List<List<Interval>> rst = new ArrayList<>();
if(intervals==null||intervals.length==0) return rst;
Arrays.sort(intervals, new Comparator<Interval>(){
public int compare(Interval i1, Interval i2){
return i1.start-i2.start;
}
});
PriorityQueue<Interval> heap = new PriorityQueue<>(new Comparator<Interval>(){
public int compare(Interval i1, Interval i2){
return i1.end-i2.end;
}
});
Map<Interval,Integer> map = new HashMap<>();
rst.add(new ArrayList<>());
rst.get(0).add(intervals[0]);
heap.offer(intervals[0]);
map.put(intervals[0],0);
for(int i=1;i<intervals.length;i++){
Interval last = heap.peek();
int room;
if(intervals[i].start>=last.end){
heap.poll();
room = map.get(last);
}else{
rst.add(new ArrayList<>());
room = rst.size()-1;
}
rst.get(room).add(intervals[i]);
heap.offer(intervals[i]);
map.put(intervals[i],room);
}
return rst;
}
}
13.第一轮：meeting room 输入时很多对开始时间和结束时间，比如 1:00 ~ 2:00 14:00 ~ 16:00 然后问哪些时间段这个room是被占用的
//merge intervals
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> rst = new ArrayList<>();
if(intervals==null||intervals.size()==0) return rst;
Collections.sort(intervals, new Comparator<Interval>(){
public int compare(Interval obj1, Interval obj2){
return obj1.start-obj2.start;
}
});
int start=intervals.get(0).start;
int end=intervals.get(0).end;
for(Interval itv : intervals){
if(itv.start<=end){
start=Math.min(start,itv.start);
end = Math.max(end,itv.end);
}else{
rst.add(new Interval(start,end));
start=itv.start;
end=itv.end;
}
}
rst.add(new Interval(start,end));
return rst;
}
}
第二轮：big number add 就是两个很大的数相加，要考虑小数. 面试我的人都很好，一直都在看我写代码，时不时的还帮我一下，都很友好。
public String addincludedot(String s1, String s2){
String[] fors1 = s1.split("\\.");
String[] fors2 = s2.split("\\.");
int carry = 0;
String fir = "";
String sec = "";
if(fors1.length==2 && fors1.length==fors2.length){
StringBuilder tail = new StringBuilder();
int idx = Math.max(fors1[1].length()-1,fors2[1].length()-1);
while(idx>=0){
int sum = carry;
if(idx<fors1[1].length()) sum += fors1[1].charAt(idx)-'0';
if(idx<fors2[1].length()) sum += fors2[1].charAt(idx)-'0';
idx--;
tail.append(sum%10);
carry = sum/10;
}
sec = tail.reverse().toString();
}else if(fors1.length!=fors2.length){
if(fors1.length==2){
sec = fors1[1];
}else{
sec = fors2[1];
}
}
StringBuilder head = new StringBuilder();
int idx1 = fors1[0].length()-1;
int idx2 = fors2[0].length()-1;
while(idx1>=0||idx2>=0){
int sum = carry;
if(idx1>=0) sum += s1.charAt(idx1--)-'0';
if(idx2>=0) sum += s2.charAt(idx2--)-'0';
head.append(sum%10);
carry = sum/10;
}
if(carry!=0) head.append(carry);
fir = head.reverse().toString();
if(sec.equals("")) return fir;
else return fir+"."+sec;
}
14.给一串log（function, timestamp，act）, 在single thread的情况下输出各个function执行的时间段
15.valid BST 两种写法
//traverse in-order, should following increasing order
public class Solution {
private Integer lastVal = null;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (lastVal!=null && lastVal >= root.val) {
return false;
}
lastVal = root.val;
if (!isValidBST(root.right)) {
return false;
}
return true;
}
}
//recursive way
public class ValidBST {
public boolean isValidBST(TreeNode root){
long max = Long.MAX_VALUE;
long min = Long.MIN_VALUE;
return isValidBST(root,max,min);
}
public boolean isValidBST(TreeNode root, long max, long min){
if(root==null) return true;
if(root.val>=max||root.val<=min) return false;
return isValidBST(root.left,root.val,min)&&isValidBST(root.right,max,root.val);
}
}
16.给一个List 实现iterator, 支持next(),delete(),hasNext()
public class ListIterator {
private List<Integer> lst;
private int crt,size;
public ListIterator(List<Integer> ipt){
lst = new ArrayList<>(ipt);
crt = 0;
size = lst.size();
}
public boolean hasNext(){
return crt<size;
}
public int next(){
if(!hasNext()) return Integer.MIN_VALUE;
return lst.get(crt++);;
}
public void delete(){
if(crt-1<0||crt-1>=size) return;
lst.remove(--crt);
size = lst.size();
}
}
17.find min in a sorted array稍微变了下形
So in this sorted problem, we don't need to use nums[idx] to show our answer, we could directly use a variable to record the minimum number which avoid the complexity of idx problem.
//Find Minimum in Rotated Sorted Array
public class Solution {
public int findMin(int[] nums) {
int L=0,R=nums.length-1;
int min = Integer.MAX_VALUE;
while(L<=R){
int mid = L+((R-L)>>1);
if(nums[mid]<=nums[R]){
R = mid - 1;
}else{
L = mid + 1;
}
min = Math.min(min,nums[mid]);
}
return min;
}
}
//Find Minimum in Rotated Sorted ArrayII
public class Solution {
public int findMin(int[] nums) {
if(nums==null||nums.length==0) return -1;
int L=0, R=nums.length-1;
int min = Integer.MAX_VALUE;
while(L<=R){
int mid=L+((R-L)>>1);
if(nums[L]<nums[mid]){
min = Math.min(min,nums[L]);
L = mid+1;
}else if(nums[L]>nums[mid]){
min = Math.min(min,nums[mid]);
R = mid-1;
}else{
min = Math.min(min,nums[L]);
L++;
}
}
return min;
}
}
18.search in rotated array && min stack
public class Solution {
public int search(int[] nums, int target) {
int L=0,R=nums.length-1;
while(L<=R){
int mid = L+((R-L)>>1);
if(nums[mid]==target) return mid;
if(nums[L]<=nums[mid]){
if(target<nums[L]||target>nums[mid]){
L = mid+1;
}else{
R = mid-1;
}
continue;
}
if(nums[mid]<=nums[R]){
if(target<nums[mid]||target>nums[R]){
R = mid - 1;
}else{
L = mid + 1;
}
continue;
}
}
return -1;
}
}
19.实现ArrayList。CodePair写的，还要自己写test case。。。
20.一个string, 有空格，需要reverse string中所有的word follow up： 一个char arr， 把里面的词都reverse了
//first reverse each word, then reverse whole char array
public class Solution {
public String reverseWords(String s) {
String aftertrim=s.trim();
char[] words = aftertrim.toCharArray();
int len=words.length;
int L=0,R=-1;
for(int i=0;i<len;i++){
if(words[i]==' '){
if(L!=R) reverse(words,L,R);
L=i+1;
R=i;
continue;
}
R++;
}
reverse(words,L,R);
reverse(words,0,len-1);
return new String(words).replaceAll(" +"," ");
}
public void reverse(char[] words, int L, int R){
while(L<R){
char c = words[L];
words[L] = words[R];
words[R] = c;
L++;
R--;
}
}
}
21.然后问如果给snapchat加一个feature要加什么 coding: construct binary tree from inorder and preorder 要考虑输入invalid的情况
public class ConstructTree {
public TreeNode buildTree(int[] preorder, int[] inorder){
if(preorder==null||inorder==null) return null;
if(preorder.length==0||inorder.length==0) return null;
int rootval = preorder[0];
TreeNode root = new TreeNode(rootval);
Integer rootidx = null;
for(int i=0;i<inorder.length;i++){
if(inorder[i]==rootval){
rootidx=i;
break;
}
}
if(rootidx==null) return null;
int[] preleft = Arrays.copyOfRange(preorder,1,rootidx+1);
int[] preright = Arrays.copyOfRange(preorder,rootidx+1,preorder.length);
int[] inoleft = Arrays.copyOfRange(inorder,0,rootidx);
int[] inoright= Arrays.copyOfRange(inorder,rootidx+1,inorder.length);
root.left = buildTree(preleft,inoleft);
root.right= buildTree(preright,inoright);
return root;
}
}
22.给定一个全是正整数的array， 和一个targe值。 你可以取任意数目的elements from the array，允许有重复，然后使得这些elements的和等于target 问一共多少种solutions？
需要注意的是：只要排列不一样就视为不同的solution， 如 {1,2} 和 {2,1}算两个solutions,而不是一个。
example：
array = {1,2,3}，
target = 4
solutions:
1. {1,1,1,1}
2. {1,1,2}
3. {1,2,1}
4. {2,1,1}
5. {1,3}
6. {3,1}
7. {2,2}
8. Therefore, return 7.
最开始并没有说这个array全是正数，需要你提问，并且去确认。这个时候面试官会问你如果包含非正数， 有没有algorithm能解决这个问题。这些楼主都没有问题。
很明显要用Dynamic Programming去解。楼主一看时间不多了，来不及多想，凭直觉就上了，写了个看似正确其实是错误的解法。 用了2D array。 因为楼主把红色那句给忽视掉了，楼主的解法是针对solutions里不包含duplicate的解法，这样一来其实题目变得更难。。。面试结束之 后才发现解法本身就大错特错了，而面试的时候面试官 也没发现楼主的解法本质上就不对，只是说“看起来没问题，应该是初始的值不对”。有可能是他觉得没时间了， 没有让我去debug我自己的代码。然后他就给我大致说了他自己的解法，用1D array。然后让我把他的解法code出来，楼主很快搞定， 基本一遍就bugfree了。接着问了下他的方法的时间复杂度，和我的方法的时间复杂度。然后就是我提问的环节。随便聊了几句就结束了。
Two Method: Backtracking O(n^(k)): n is array length and k is target number. Or DP O(n*k).
23.Design
// snapchatter send-list
// toggle(string username)
// getSelectedLlist()
// t: a getsl: a
// t: a b c getSl: a b c
// t: a b a c getSl: b c
Design题我给的设计，用了doublelinkedlist，确保了toggle时的时间复 杂度为O(1)
This problem is like LRU, use doublelinkedlist to store one node and hashmap to get string->node. toggle means switch, tap once then appear, tap again then disselect.
24.Three Sum
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> rst = new ArrayList<>();
if(nums==null||nums.length==0) return rst;
Arrays.sort(nums);
int len = nums.length;
for(int i=0;i<len-2;i++){
int L=i+1,R=len-1;
int trg = -nums[i];
while(L<R){
int sum = nums[L]+nums[R];
if(sum==trg){
rst.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[L],nums[R])));
while(++L<len&&nums[L]==nums[L-1]);
while(--R>=0&&nums[R]==nums[R+1]);
}else if(sum<trg){
L++;
}else{
R--;
}
}
while(i+1<len&&nums[i]==nums[i+1]) i++;
}
return rst;
}
}
25.用前序和中序数组重建二叉树，LC 原题。(See above)
26.开始做题目，是game of life。 我虽说准备过这个面经题，我还是很无耻的打开了leetcode。。。（然后还写出了一个bug。。尼玛）面试官只要求写了建新matrix的那种，然后讨论了一下space的问题，说用int表示board还是比较大的，然后我说用boolean就小了32倍，然后提了一下wiki上面的方法，如果board很大可以用一个set只记录live的点，这样更加省。然后就完了，继续聊了一下他们的公司就结束了，总体来说还是比较愉快的。希望能move forward吧。 在谈到Ad的时候问我是否了解Snapchat Geofilter的广告策略，我当时蒙了，本来做了功课好像看过他们推出了广告Geofilter，但是随口答了一个on-demond geofilter。Game of Life，其实挺幸运的，因为面经上有，但是我coding好几个bug，最后有一个bug没调出来，是行列坐标整反了，他说思路可以，我算你对了，然后follow up，真是悔恨没仔细想这个问题：首先问时间空间能不能省，我就说可以存活着的pair
27.一个是计算combinations. 是理论上的计算，计算有多少种组合方式。 大概类似word break，比如#Ilovenyc 有多少种分解方式，此时先不考虑字典。
Permutation and combination: $$C_n^k$$, then k could be 0 to n
28.一个是 word break 2，给个字典，如何break Ilovenyc 问了时间复杂度，worst case是什么时候，为什么solution会比brute force search好，大概说了一下怎么剪枝。 比如word：aaaaa dict= {a, aa, aaa, aaaa, aaaaa}.
//DFS Solution: time: O(2^n), space: O(n)
public class Solution {
private List<String> rst = new ArrayList<>();
private StringBuilder crt = new StringBuilder();
private boolean[] DP;
public List<String> wordBreak(String s, Set<String> wordDict) {
if(s==null||s.length()==0) return rst;
DP = new boolean[s.length()+1];
DP[s.length()]=true;
for(int i=s.length()-1;i>=0;i--){
for(int j=i;j<s.length();j++){
if(DP[j+1]&&wordDict.contains(s.substring(i,j+1))){
DP[i]=true;
break;
}
}
}
backtracking(s,0,wordDict);
return rst;
}
public void backtracking(String s, int index, Set<String> wordDict){
if(index==s.length()){
rst.add(crt.toString().trim());
return;
}
for(int i=index;i<s.length();i++){
String tmp = s.substring(index,i+1);
if(wordDict.contains(tmp)&&DP[i+1]){
int len = crt.length();
crt.append(tmp+" ");
backtracking(s,i+1,wordDict);
crt.setLength(len);
}
}
}
}
//DP solution: time: O(n^2*k), space: O(nk)
public class Solution {
public List<String> wordBreak(String s, Set<String> wordDict) {
// 判断是否能够分解
if (!helper(s, wordDict)) {
return new ArrayList<String>();
}
// 记录字符串s.substring(0, i)对应的解
HashMap<Integer, List<String>> map = new HashMap<Integer, List<String>>();
map.put(0, new ArrayList<>());
map.get(0).add("");
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (map.containsKey(j) && wordDict.contains(s.substring(j, i))) {
if (!map.containsKey(i))
map.put(i, new ArrayList<>());
for (String str : map.get(j)) {
map.get(i).add(str + (str.equals("") ? "" : " ") + s.substring(j, i));
}
}
}
}
return map.get(s.length());
}
private boolean helper(String s, Set<String> wordDict) {
boolean dp[] = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
}
}
}
return dp[s.length()];
}
}
29.上来惯例问为什么来snapchat，然后就是题给一个n+1元素的数组，元素在范围内，至少有一个重复，让你找其中任意一个duplicate 我马上说了hashset和元素变负的两种方法，他没让coding， followup如果数组只读，而且只用constant space的方法。暴力法可以， 然后followup 继续提高时间效率，二分法缩小range 这时候才给code。 以后一个问题的每一个解法都得看看，中间二分那里卡了一会儿，结果导致时间还就不少白人小哥就不再问了，想来也是被放弃了。。。 word ladder 2
//Find the Duplicate Number
public class Solution {
public int findDuplicate(int[] nums) {
int slow=0,fast=0;
while(true){
slow=nums[slow];
fast=nums[nums[fast]];
if(slow==fast) break;
}
slow=0;
while(slow!=fast){
slow=nums[slow];
fast=nums[fast];
}
return slow;
}
}
30.第一题是valid palindrome。判断是不是合法的palindrome。第二题说给一个string,可以add/delete/change，还可以combine几种来使他变为合法的palindrome。比如：ebabc可以先删了中间的a再把c改成e。问最少需要几步。
public class Solution {
public boolean isPalindrome(String s) {
if(s.equals("")) return true;
int head=0,tail=s.length()-1;
while(head<=tail){
char h_s=s.charAt(head);
char t_s=s.charAt(tail);
if(!Character.isLetterOrDigit(h_s)){
head++;
}else if(!Character.isLetterOrDigit(t_s)){
tail--;
}else{
if(Character.toLowerCase(h_s)==Character.toLowerCase(t_s)){
head++;
tail--;
}else{
return false;
}
}
}
return true;
}
}
//edit distance
/*对于矩阵中的i,j位置，他可以有如下三种方式变换：
1、从i-1,j 为T1增加一个字符，获得i，j，这样编辑距离本身就需要+1
2、同理，从i，j-1过来，编辑距离必须+1。
3、从i-1，j-1位置变换过来，那么这个时后，如果T1在i的取值和T2在j的取值一样，那么这个变换，编辑距离不变，如果不一样，那么就需要做替换操作，那么必须+1.
*/
public class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] DP = new int[len1+1][len2+1];
for(int i=0;i<=len1;i++) DP[i][0] = i;
for(int i=0;i<=len2;i++) DP[0][i] = i;
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
DP[i+1][j+1] = Math.min(DP[i][j+1],DP[i+1][j])+1;
DP[i+1][j+1] = Math.min(DP[i+1][j+1], DP[i][j] + (word1.charAt(i)==word2.charAt(j) ? 0 : 1));
}
}
return DP[len1][len2];
}
}
31.题目是设计一个类来存放一个无向图的边和点，我大概用的hashset来存一个点的邻居这样，follow up是问图有多满的情况下用bitmap更加合适。要写main函数和简单testcase跑一下。我是一开始有点编译错误但是编译通过之后结果是对的。感觉只要是能跑通应该就没什么问题。面试小哥是camera组的。
public class Node{
int val;
List<Node> next;
public Node(int val){
this.val = val;
next = new ArrayList<>();
}
}
How to use Bitmap: reference
//bitmap for longest consecutive sequence problem, array nums have to be non-negative
public class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length==0) return 0;
BitSet map = new BitSet();
for(int num : nums) map.set(num);
int max=0,cnt=0;
for(int i=0;i<map.size();i++){
if(map.get(i)){
cnt++;
}else{
if(cnt>max) max = cnt;
cnt=0;
}
}
return max;
}
}
32.word abbreviation (See Snapchat OA)
34.给一个int的matrix，里面只有0和1，matrix表示i和j是朋友，如果是0表示两人不是朋友，是朋友的分成一个组，问能分几组。比如1和2是朋友，3和他们都不是朋友，那么就是2组，return 2就可以。自己写test自己测
int cnt = n;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
Union And Find;
if(matrix[i][j]==1){
//only when they are not in a group, then union and cnt --;
if(getroot(i)!=getroot(j)) cnt--;
}
}
}
35.第一题 ：给一个数组，返回左边之和等于右边之和的那个index， 没有就返回-1，比如{1,2,3,2,1}， 返回2，写了好多testcase，各种情况。。。。10分钟完事 ]
public class EqualSum {
public int equalIdx(int[] nums){
if(nums.length==0) return -1;
int total = 0;
for(int num : nums ) total += num;
int crt = 0;
for(int i=0;i<nums.length;i++){
int subtotal = total-nums[i];
if(crt*2 == subtotal) return i;
crt += nums[i];
}
return -1;
}
public static void main(String[] args) {
EqualSum test = new EqualSum();
int[] nums = new int[]{3,2,2,5,2,1,4};
System.out.println(test.equalIdx(nums));
}
}
第二题 ：给了一个Person class， 有score和nextSnap两个属性，每个Person有一个朋友的list，也就是nextSnap，输入是（Person， maxStep）， 在maxStep步数以内算max score，注意的是下一个Friend可能会指向上一个Person，要注意回溯的问题。。。10分钟写好了， 输出一直不对。。从recursive改到一个乱七八糟的方法，还是不对，然后一行一行的肉眼debug，感觉没问题啊，最后发现她给的构造器有问题，score没赋值。。。。。。我去。。。。。过分了啊。。。。最后也没有follow up，直接问有什么问题么，我问你们现在做什么，下一步有什么计划。。韩国MM说是private company，不能告诉你。。。好吧，I am good, take care。。。。面经都看了，准备的也挺充分，总是一些各种各样的原因，继续努力吧。。。大家还有5月份毕业，没拿到offer的么。。
Using BFS, and Dummy Node, when meeting a dummy node then count++ and insert a new dummy node, when count equals maxstep then stop. And also use hashset to record the person that has already calculated.
36.面经题 basic calculator +-*/和数字 都是一位 没有空格 输入都是valid 所以不用考虑corner case
follow up是 数字变成多位
然后再followup加上空格
follow up: 负数
public class Solution {
public int calculate(String s) {
Stack<Integer> stk = new Stack<>();
char sign = '+';
int num = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c>='0'&&c<='9') num = num*10 + c -'0';
if((c>'9'&&c<'0'&&c!=' ')||i==s.length()-1){
if(sign=='+') stk.push(num);
if(sign=='-') stk.push(-num);
if(sign=='*') stk.push(stk.pop()*num);
if(sign=='/') stk.push(stk.pop()/num);
sign = c;
num=0;
}
}
num=0;
while(!stk.empty()) num += stk.pop();
return num;
}
}
37.面试时间是上午11点，面试官是个亲切的白人小哥。上来自我介绍一下，然后聊了聊家常，得知小哥原来也是在湾区工作。之后小哥问为什么想来Snapchat，楼主说我可是你们的用户，特别喜欢里面的Stories里面的Discover类别。然后小哥问楼主最喜欢哪一个频道，楼主说Tastemade，小哥说我也喜欢啊，特别喜欢几个妹子做饭。之后就开始聊楼主的工作，问了目前干什么，工作中遇到过什么挑战。楼主说自己是做网站的，前端后端都搞。小哥问楼主喜欢什么技术，楼主说AngularJS，这时候小哥又共鸣了，貌似他也是搞网页了，然后又聊了一下。
这些有的没的说完了，然后就是做题。这里还一个小插曲，小哥问我语言是不是用JS，楼主说并不我要用Java。小哥有点愣住了，说Java我不是很熟，估计看到我web的背景所以给我安排了一个用JS的面试官。 问题一个走迷宫问题。给了一个矩阵，"1"代表起点，位于左上角；"9"代表重点，位于右下角；"0"代表通路，"5"代表墙。. 矩阵长得是这样
[
[1, 5, 5, 5, 5, 0],
[0, 5, 0, 5, 5, 0],
[0, 5, 0, 0, 0, 0],
[0, 5, 0, 0, 5, 0],
[0, 0, 0, 5, 0, 9]
]
设计一个算法，看看这个迷宫能不能从起点走到重点。
楼主因为面试经验少，上来突然慌神了，完全不知道从哪里下手，感觉这是一个DP的问但是又不像。楼主突然跟面试官说这个问题用DFS解决，然后小哥说好，那就写代码吧。Snapchat允许查各种资料，Google Hangout也不需要Share Screen，如果运气好貌似查到原题就可以一步登天了，不过楼主并没有去查原题。自己在草稿纸画了画走迷宫的方法，然后确定这个就是DFS问题，而且准备使用递归来实现。之后楼主开始写代码，刚开始跟小哥聊一下思路，小哥没有说话，就说我这边都看得，你自己写就好了，估计小哥是跟楼主一样安静工作的人。代码写完了就是运行，这个时候问题就来了。楼主一直做web而且用leetcode刷题不用自己搭环境，对于Java的运行不是很清楚了，包括各种头文件的引用。由于小哥也不懂Java，楼主只能自己来找错。楼主急中生智打开Eclipse查以前写的代码，发现自己"static"和"length"拼错了，实在是不应该。改了这些拼写错误以后，代码就可以运行了而且结果也正确。然后小哥说能不能打印出来路径，楼主便加入了打印的代码并且输出路径数组。小哥又把迷宫改了改，运行几次说没问题了。.
import java.util.*;
public class Maze {
private int row,col;
public boolean hasPath(int[][] maze){
if(maze.length==0||maze[0].length==0) return false;
row = maze.length;
col = maze[0].length;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(maze[i][j]==1){
maze[i][j]=0;
return DFS(maze,i,j);
}
}
}
return false;
}
private boolean DFS(int[][] maze, int r, int c){
if(r>=row||c>=col||r<0||c<0) return false;
if(maze[r][c]==9) return true;
if(maze[r][c]!=0) return false;
maze[r][c] = 3;
boolean rst = DFS(maze,r-1,c)||DFS(maze,r+1,c)||DFS(maze,r,c-1)||DFS(maze,r,c+1);
maze[r][c] = 0;
return rst;
}
public static void main(String[] args) {
int[][] maze = new int[][]{{1,5,5,5,5,0},{0,5,0,5,5,0},{0,5,0,0,0,0},{0,5,0,0,5,0},{0,0,0,5,0,9}};
Maze test = new Maze();
System.out.println(Arrays.deepToString(maze));
System.out.println(test.hasPath(maze));
}
}
本以为还有一道题，结果小哥说就这样问我还有没有什么问题。楼主问了一下选组和Training的问题，小哥简单介绍了一下。然后楼主说没问题了，小哥说你真的没问题了么，意思再跟我聊聊啊。幸好楼主之前问过一个朋友是Snapchat的资深用户，她说新消息来的时候不知道是照片还是视频，有时候上班的时候想看结果发现是视频，搞得非常尴尬。楼主把这个问题跟小哥说了，小哥说消息之前会有红框或者紫框，一个说明是照片另一个说明是视频，楼主说我不知道啊，小哥说没事这个设计也并不是很清楚，会作为用户反馈的。之后就是小哥说楼主表现还可以，HR会在一周内给消息，简单告别就挂了。面试的第二天下午楼主就收到了HR的邮件约onsite了。
总结一下，Snapchat面试我的问题并不难，楼主感觉自己发挥一般，能给onsite真的是运气不错。感觉面试的心态真的是太重要了，还是要多面才能更加从容。遇到问题以后千万不能慌，如果想不出来算法可以现在纸上画一画，看看自己如何手工实现解法，然后把自己变成机器来思考，这样就把这个解法转换成算了。千万不要把面试当做是一件特别严肃的事情，做题并不是考试，把解题当做一个解决问题的过程就可以了。
37.第一道题是print 2d array diagonally top-down, e.g.. From 1point 3acres bbs [[1,2,3,4], [5,6,7,8], [9,10,11,12]] => 1, 2 5, 3 6 9, 4 7 10, 8 11, 12. 题外话：这道题其实隐隐约约面经里我记得有人写过zigzag打印应该就是这个。。楼主地里电面面经看得到的都自己写了，准备了了洋洋洒洒近两千行的面经代码，唯独那道当时觉得年代久而且觉得现场也能秒就没写。。就那一道。。。然后当时心情就坏了。。开始扣着写吧 一开始竟然还开了一个大小相同的数组存访问过没有，空间复杂度O(n)的。。。果断写完等着被优化，冥想半天从上边和右边开始向左下输出就好了，no space。(See above diagonally print problem)
第二道，先问知不知道anagram，两个string怎么判断是不是anagram，楼主迅速说了开128或者256空间那个，以为要问原题了。。。结果 并不是。。 问题是给一个source string和pattern string，求有没有任意一个source string的substring和pattern string互为anagram，返回true or false。让用O(n)。。当时觉得有点蒙，我擦怎么O(n)啊。。光比较就要n的复杂度了何况还要slice window。。反正是后来苦思冥想半天总算是想到了。。楼主解法是用另外一个diff map存不对应关系，key是frequency不同的characters，value是对应的difference，source多value正，pattern为负，然后slice window，没slice一位，更新diff表，每有一个value变空了从map中删除那个entry，diff map为空则说明找到了一个匹配的window返回true。。。此法时间复杂即O(n)。。空间O(n)
(See problem 5)
38.你觉得snapchat 怎么样，你有用么？ 你喜欢什么功能 doge脸，说阅后即焚好酷啊，我和朋友之间发污污的东西，都用的它（其实前天才专上软件...），各种stories功能好欢乐啊，还教做饭，喜欢的不行. 说说你的经历吧，我没你的简历在手上（怎么写在面试都这样， 周一面Google也是），然后就扯了我的经历，小哥表示你做的东西好有趣啊...
开始编程，题目不难，不过刷了地里大半的电面面经以为会有重复的碰到，结果是新的，还是有点紧张，大致意思就是输入一串的double表示的sort好的timestamps, 然后一个double的windowSize, 请你找出一个起始时间区域，使得以这个范围的起始时间开始的[x, x + windowSize] 内有最多的timestamp;
- 我先给了queue的思路，然后每次碰到新的timestamp, remove所有之前的点，remove的时候更新pre, 然后check现在queue的size, 返回最大sizes时对应的(pre, queue.head]就是answer.
- 码完之后说，你有没有更好的思路，不要用O (n)的extra space, 我说用two pointers, 然后又吭呲吭呲地写，小哥说你其中有个地方又问题，我看了半天没发现，提示说，你有没有觉得windowSize 可能是负数。。。负数。。。
- 你写几个unit test吧，我对java Unit test 不熟，然后愣了几愣，说我平常常做的就是给不同的输入，看输出的结果，小哥无奈。。 ［求助大家，unit test 一般要怎么写啊，google了下，感觉好复杂］
import java.util.*;
public class MaxTimeStamps {
public double[] getRange(double[] timestamps, double window){
double[] rst = new double[2];
if(timestamps.length==0) return rst;
int max = 0;
int L = 0, R = 0;
while(R <= timestamps.length){
if(R==timestamps.length||timestamps[L]+window<timestamps[R]){
if(R-L>max){
max = R-L;
rst[0] = timestamps[L];
rst[1] = timestamps[L]+window;
}
L++;
if(R==timestamps.length) break;
}else{
R++;
}
}
return rst;
}
public static void main(String[] args) {
double[] ipt = new double[]{2,4,5,7,8,9,12,13,15,16};
double win = 4;
MaxTimeStamps test = new MaxTimeStamps();
System.out.println(Arrays.toString(test.getRange(ipt,win)));
}
}
39.就是给了一个Person类，让实现打出这个Person的关系网中的所有朋友，Person有属性id, name和friendList, sample输出是这样子的：
/* * Mike(1) {Mitch, Ryan}
* Mitch(2) {Mike}
* Ryan(3) {Mike, Lila}
* Lila(4) {Ryan}
* Mike.printFriendsGraph() : Mitch, Ryan, Lila */
41.given a number n, how many ways you can create a BST, for eg for n=2, o/p = 2,n = 3 , o/p is 5.
public class Solution {
public int numTrees(int n) {
int[] DP = new int[n+1];
DP[0] = 1;
for(int i=1;i<=n;i++){
int sum = 0;
for(int j=0;j<=i-1;j++){
sum += DP[j]*DP[i-j-1];
}
DP[i] = sum;
}
return DP[n];
}
}
42.Implement LRU.
43.Determine whether a graph is bipartite
Problem Explanation
import java.util.*;
public class Bipartite {
public boolean isBipartite(int[][] graph, int src, int cnt){
int[] colorArr = new int[cnt];
Arrays.fill(colorArr,-1);
colorArr[src] = -1;
Queue<Integer> qe = new LinkedList<>();
qe.offer(src);
while(!qe.isEmpty()){
int crt = qe.poll();
for(int i=0;i<cnt;i++){
if(graph[crt][i]==1 && colorArr[i]==-1){
colorArr[i] = 1-colorArr[crt];
qe.offer(i);
}else if(graph[crt][i]==1 && colorArr[i] == colorArr[crt]){
return false;
}
}
}
return true;
}
}
44.刚面完 是国人大哥 题目 一个板子 一个起点 一个终点 移动按照中国象棋的马 要求输出一条最短移动路径
BFS, there is 8 ways for a node.
45.第一提，给你你个数组，要你返回数组的最小值的平方是否小于最大值。题目很简单，需要注意的就是最小值的平方可能越界。 佛罗阿噗：如果这个数组不满足第一题中的条件，然后允许你执行“删除数组的第一个元素”的操作，让你返回要执行多少次，也就是删除多少个数组前面的元素后才能满足第一题中的条件。如果删完都不满足，返回-1；这一题小哥反复提示才想出来一个O（n）的做法，然后今天看还有个小bug，哎。。 接着佛罗阿噗：如果可以每次都可以选择删除第一个或者最后一个，问最少要删掉几次。。