ABnb 面经总结

输入是

[[‘John’, ‘Smith’, ‘john.smith@gmail.com’, ‘Los Angeles’, ‘1’],.
[‘Jane’, ‘Roberts’, ‘janer@msn.com’, ‘San Francisco, CA’, ‘0’],
[‘Alexandra “Alex”‘, ‘Menendez’, ‘alex.menendez@gmail.com’, ‘Miami’, ‘1’]]

需要返回

John|Smith|john.smith@gmail.com|Los Angeles|1
Jane|Roberts|janer@msn.com|San Francisco, CA|0
Alexandra “Alex”|Menendez|alex.menendez@gmail.com|Miami|1

public String parseCSV(List<List<String>> input) {
  if (input.size() == 0) {
    return "";
  }
  StringBuilder res = new StringBuilder();
  for(List<String> list : input) {
    StringBuilder sb = parseHelper(list);
    if (res.size() == 0) {
      res.append(sb);
    } else {
      res.append('\n');
      res.append(sb);
    }
  }
  return res.toString();
}

private StringBuilder parseHelper(List<String> list) {
  StringBuilder sb = new StringBuilder();
  for (String s : list) {
    s = s.substring(1, s.length()-1); //get ride of single quotes
    if (sb.length() == 0) {
      sb.append(s);
    } else {
      sb.append("|");
      sb.append(s);
    }
  }
  return sb;
}

一个大妈考得,说是一般在店面考,卧轨了。
csv parser
如果有逗号,转化成|
如果有引号,把不考虑引号里逗号,把引号里的内容去引号整体打印。
如果有两重引号,只去掉一重引号。

例子
aa, bb, “aa”,”aa,bb”, “aa””aa”””
输出
aa|bb|aa|aa,bb|aa”aa”

public class Solution {
	public String parseCsv(String s) {
		  StringBuilder sb = new StringBuilder();
		  int quotes = 0;
		  int start = 0;
		  int end = 0;
		  while (end < s.length()) {
		    char c = s.charAt(end);
		    if (c == '"') {
		      quotes++;
		    } else if (c == ',') {
		      if (quotes%2 != 0) { //within a quote
		        end++;
		        continue;
		      } else {
		        String tmp = s.substring(start, end);
		        if (sb.length() != 0) {
		          sb.append('|');
		        }
		        sb.append(processString(tmp)); //remove nested quotes
		        start = end+1;
		        end = start;
		      }
		    }
		    end++;
		  }
		  //last string
		  String tmp = s.substring(start, end);
		  if (sb.length() != 0) {
	          sb.append('|');
	      }
	      sb.append(processString(tmp)); //remove nested quotes
		  return sb.toString();
		}

		private String processString(String s) {
		  int quotes = 0;
		  for(int i=0; i<s.length(); i++) {
		    if (s.charAt(i) == '"') {
		      quotes++;
		    }
		  }
		  if (quotes == 0) {
			  return s;
		  }
		  int start = 0;
		  int end = s.length()-1;
		  StringBuilder tmp = new StringBuilder(s);
		  if (quotes == 2) {
			  while(tmp.charAt(start) != '"') {
				  start++;
			  }
			  while(tmp.charAt(end) != '"') {
				  end--;
			  }
			  tmp.deleteCharAt(end);
			  tmp.deleteCharAt(start);
			  
			  return tmp.toString();
		  }		  
		  while(quotes > 2) {
			  while(tmp.charAt(start) != '"') {
				  start++;
			  }
			  while(tmp.charAt(end) != '"') {
				  end--;
			  }
			  tmp.deleteCharAt(end); 
			  tmp.deleteCharAt(start);  
			  quotes -= 2;
		  }
		  return tmp.toString();
		}

}

实现一个mini parser, 输入是以下格式的string:”324″ or”[123,456,[788,799,833],[[]],10,[]]”
要求输出:324 or [123,456,[788,799,833],[[]],10,[]]
也就是将字符串转换成对应的格式的数据.
其实题不算难,楼主答得不好,面完就知道挂了

这道题如果用java来做的话,因为java 是strict type的,所以不能既return array 又return string的。所以我们建立一个特殊的class, 然后用stack来做。注意处理,的情况

class Node {
  int val;
  bool isArray;
  List<Node> list;
  public Node (int v) {
    this.val = v;
    this.isArray = false;
    this.list = null;
  }
}

public List<Node> miniParser(String input) {
  Stack<Node> stack = new Stack<Node>();
  //-1 => [, -2 => ], -3 => ,
  for (int i=0; i<input.length(); i++) {
    char c = input.charAt(i);
    if (Character.isDigit(c)) {
      if (stack.isEmpty() || stack.peek().isArray || stack.peek.val == -1) {
        Node n = new Node((int)(c-'0'));
      } else if (stack.peek().val == -3) {
        n = stack.pop();
        n.val = (int)(c-'0');
      } else {
        n = stack.pop();
        n.val = n.val*10 + (int)(c-'0');
      }
    } else if (c == '[') {
      Node n  = null;
      if (!stack.isEmpty() && stack.peek() == -3) {
        n = stack.pop();
      } else {
        n = new Node(-1);
      }
      n.val = -1;
      stack.push(n);
    } else if (c == ',') {
      Node n = new Node(-3);
      stack.push(-3);
    } else if (c == ']') {//if c == ']'
      Node n = new Node(0);
      n.isArray = true;
      while(!stack.isEmpty() && stack.peek().val != -1) {
        n.list.add(stack.pop());
      }
      stack.pop();
      stack.push(n);
    }
    List<Node> res = new ArrayList<Node>();
    while(!stack.isEmpty()) {
      res.add(0, stack.pop());
    }
    return res;
  }
}

1. text justification, leetcode problem

public List<String> textJustification(List<String> s, int limit) {
  List<StringBuilder> list = new ArrayList<StringBuilder>();
  StringBuilder sb = new StringBuilder();
  for(int i=0; i<s.length(); i++) {
    String tmp = s.get(i);
    if (sb.length() == 0) {
      sb.append(tmp);
    } else if (sb.length() + tmp.length() + 1 < limit) {
      sb.append(" ");
      sb.append(tmp);
    } else {
      list.add(sb);
      sb = new StringBuilder();
      i--;
    }
  }
  List<String> res = new ArrayList<String>();
  for (StringBuilder sbi : list) {
    int space = 0;
    for(int i=0; i<sbi.length(); i++) {
      if (sbi.charAt(i) == " ") {
        space++;
      }
    }
    if (spaces == 0) {
      while(sbi.length() < limit) {
        sbi.append(" ");
      }
    } else {
      while(sbi.length() < limit) {
        int i = 0;
        while(i < sbi.length()) {
          if (sbi.charAt(i) != " " && sbi.charAt(i-1) == " ") {
            sbi.insert(i, " ");
            i++;
          }
          if (sbi.length() >= limit) {
            break;
          }
          i++;
        }
      }
    }
   res.add(sbi.toString());
   }
 return res;
}

2. 比较两个document 是否相似
实际上是edit distance

public int editDist(String s, String t) {
  int[][] dist = new int[s.length()+1][t.length()+1];
  for (int i=0; i<=s.length(); i++) {
    for (int j=0; j<=t.length(); j++) {
      if (i==0 && j==0) {
        dist[i][j] = 1;
      } else if (i==0) {
        dist[i][j] = j;
      } else if (j==0) {
        dist[i][j] = i;
      } else {
        if (s.charAt(i-1) == t.charAt(j-1)) {
          dist[i][j] = dist[i-1][j-1];
        } else {
          dist[i][j] = Math.min(dist[i-1][j], dist[i][j-1], dist[i-1][j-1]) + 1;
        }
     }
  }
  return dist[s.length()][t.length()];
} 

3. 如何做国际化.
4. Google reader design

实现function:
1. subscribe / unsubscribe feeds
2. mark 整个feed topic as read / unreader

table schema :
user table:
id name … join_date

Feed table:
id name created_date

Post table: ( 1 feed includ many posts)
id feedId created_date

Post_status table:
id userId, postId, status (read/unread) created_time

Regular Expression Matching

//assume there is no continuous “*”s

public boolean regExpMatch(String s, String p) {
  boolean [][] isMatch = new boolean[s.length()+1][p.length()+1];
  for(int i=0; i<s.length(); i++) {
    for(int j=0; j<p.length(); j++) {
      if (i==0 && j==0) {
        isMatch[i][j] = true;
      } else if (i==0) {
        char c = p.charAt(j-1);
        if (c == *) {
          isMatch[i][j] = isMatch[i][j-2];
        } else {
          isMatch[i][j] = false;
        }
      } else if (j == 0) {
        isMatch[i][j] = false;
      } else {
        char c1 = s.charAt(i-1);
        char c2 = p.charAt(j-1);
        if (c2 == "*") {
          char c = p.charAt(j-1);
          if (c == c1) {
            isMatch[i][j] == isMatch[i-1][j];
          } else {
            isMatch[i][j] == isMatch[i][j-2];
          }
        } else if (c2 == '.') {
          isMatch[i][j] = isMatch[i-1][j-1];
        } else {
          isMatch[i][j] = c1 == c2 ? isMatch[i-1][j-1] : false;
        }
     }
     return isMatch[s.length()][p.length()];
   }

一个数组,选出不相邻子序列,要求子序列和最大,
[4,9,6]=10
[4,10,3,1,5]=15

public int findIntervalMax(int [] input) {
  int [] max = new int[input.length];
  for(int i=0; i&lt;input.length; i++) {
    if (i==0) {
      max[i] = input[i];
    } else if (i==1) {
      max[i] = input[i];
    } else {
      max[i] = Math.max(max[i-2] + input[i], max[i-1]);
    }
  }
  return max[input.length-1];
}

find maximum square with all 1's 

public int maxSquare(int [][] matrix) {
  if (matrix.length == 0) {
    return 0;
  }
  int max = 0;
  int [][] maxArea = new int[matrix.length][matrix[0].length];
  for (int i=0; i&lt;matrix.length; i++) {
    for (int j=0; j&lt;matrix[0].length; j++) {
      if (matrix[i][j] == 0) {
        maxArea[i][j] = 0;
      } else {
        maxArea[i][j] = Math.min(maxArea[i-1][j-1], Math.min(maxArea[i-1][j], maxArea[i][j-1]) + 1;
      }
      max = Math.max(max, maxArea[i][j]);
    }
  }
  return max;
}

题目是给定一个word list 和一个target word,要求输出在word list 里跟target
word的edit distance 相差不大于k的所有words。我写了一个基于edit distance的解
法(见下面),程序是要从头到尾都要写,包括main函数和test数据。写完后他问有没有
更好的解法,我说可以用trie,但是我不觉得我能在剩余时间里写得出来基于trie的解
法,就大致说了一下我认为的思路。在此也求大牛给一个基于trie解法的code。

简单的解法就是用edit distance一个一个扫。

如果用trie的话,可以用trie来预处理dictionary,如果发现一个prefix相对于target的edit distance 是m,而他下面的所有的长度小于n的数只要符合m+n < k的话都可以直接放进结果里,这样可以省掉一些计算。

另外还有一种办法就是先找出所有与target edit distance 是1的string,然后每次比较,将match的放进result里。

Given a method decode(testEncStr) which will return the decoded int id if testEncStr is decodeable or will throw an exception (or return null) if not, implement a new method decodeFind(String badEncStr) which takes a string and returns the decoded int id

给一个2d array,要求写一个顺序访问这个2d array的Iterator,包括hasNext()与next()。注意2d array的每行中元素的个数可能不一样,也可能为空。跪在这最后一面上了。
二面的时候他忘了问culture, 所以加了一面。最后跪在最后一面上了,估计是culture不fit

class Iterator {
int col;
int row;
List<List<Integer>> array;
public Iterator(List<List<Integer>> init) {
int col = 0;
int row = 0;
this.array = init;
}

public boolean hasNext() {
if (this.array == null || this.array.size() == 0) {
return false;
}
if ((col + 1) < this.array.get(row).size()) {
return true;
} else {
int r = row + 1;
while(r < this.array.size()){
if (this.array.get(r).size() > 0) {
return true;
}
r++;
}
return false;
}
}

public int getNext() {
if (col + 1 < this.array.get(row).size()) {
col++;
return this.array.get(row).get(col);
}
row++;
while(row < this.array.size()) {
if (this.array.get(row).size() > 0 ) {
col = 0;
return array.get(row).get(col);
}
row++;
}
return null;
}

Often, we want to encode raw IDs in our database by hiding them behind some
2-way decodeable hash. So, a URL which would have at one time been:

https://www.airbnb.com/rooms/848662
becomes

https://www.airbnb.com/rooms/kljJJ324hjkS

We decode the ID kljJJ324hjkS_ to 848662 on our backend and serve the
relevant content. at some point, we start getting 404 errors from clients
requesting a certain URL of the form

https://www.airbnb.com/rooms/kljjj324hjks_

This can happen if certain clients, email services, or url shorteners "
sanitize" the url. Unfortunately, this change breaks decoding and the
resource cannot be found.
To assess how big of a deal this is, we may want to recover the IDs of the
targets that were 404ing.

Your task:
Given a method decode(testEncStr) which will return the decoded int id if
testEncStr is decodeable or will throw an exception or return null.
depending on the language) if not, implement a new method decodeFind(String
badEncStr) which takes a string and returns the decoded int id.

其实就是找出所有可能的大小写组合。

public int decodeFind(String badEncStr) {
List list = recursivelyGetAllPossibleStr(badEncStr);
for (String s : list) {
if (decode(s) != null) {
return decode(s);
}
}
return null;
}

private List recursivelyGetAllPossibleStr(String s) {
List res = new List ();
if (s.length() == 0) {
res.add(“”);
return res;
}
char c = s.charAt(0);
List next = recursivelyGetAllPossibleStr(s.substring(1));
if (Character.isLetter(c) {
char tmp = Character.toLowerCase(c);
for (String n : next) {
res.add(tmp + n);
}
tmp = Character.toUpperCase(c);
for (String n :next) {
res.add(tmp + n);
}
} else {
for (String n : next) {
res.add(c + n);
}
}
return res;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s