帮人发几个面经

cpcs · 发表于 12-5-2014 02:19 PM

亲！马上注册或者登录会查看更多内容！

您需要登录才可以下载或查看，没有帐号？立即注册

x

声明：我是帮人发的，顺便感谢下提供资源的人～～

Google:

Please use this Google docto code during your interview. To free your hands for coding, we recommend thatyou use a headset or a phone with speaker option.

public class Foo {

private final int i;

private final String s;

public Foo (...)

public int hashcode() {

returni * s.length();

}

public booleanequals(Object f) {

returnf != null && f instanceof(Foo) && this.i == ((Foo) f).getI()&& s.equals(((Foo) f).getS());

}

Iterable<String> lines

public List<String>getNonDuplicateLines(List<String> lines) {

Map<String, Integer>map = new HashMap<String, Integer>();

for(String s : lines) {

if(!map.containsKey(s))

map.put(s,1);

else

map.put(s,map.get(s) + 1);

}

Set<String> keySet =map.keySet();

List<String> result =new ArrayList<String>();

for(String key, keySet) {

if(map.get(key)== 1) {

result.add(key);

}

return result;

}

Find the number of occurrences of a value ina sorted array of ints.

1,1,2,2,2,3,4,5,5

public int findOccurrences(int[] arr, target){

int left = -1;

int right = -1;

int low = 0, high =arr.length - 1;

int pivot = -1;

while(low <= high) {

intmid = low + (high - low) / 2;

if(arr[mid]== target) {

pivot= mid;

break;

}

elseif(arr[mid] < target)

low= mid + 1;

else

high= mid - 1;

}

if(pivot == -1)

return0;

left = right = pivot;

low = 0, high = pivot - 1;

while(low <= high) {

if(arr[high]< target)

break;

intmid = low + (high - low) / 2;

if(target<= arr[mid]) {

if(target== arr[mid]) {

left= mid;

}

high= mid - 1;

}

else{

low= mid + 1;

}

low = pivot + 1;

high = arr.length - 1;

while(low <= high) {

if(arr[low]> target)

break;

intmid = low + (high - low) / 2;

if(target>= arr[mid]) {

if(target== arr[mid])

right= mid;

low= mid + 1;

}

else

high= mid - 1;

}

return right - left + 1;

}

Google：

llease use thisGoogle doc to code during your interview. To make hands free coding a littleeasier, we recommend that you use a headset or a phone with speaker option.

Best,
Google Staffing

Leaderboard

1 A 50000

2 B 45000

3 C 3000

Player {

Name;

score

}

getByRank();

updateByName();

//a^b

public double pow(int a, int b) {

if(b== 0) {

return1;

} else if(a == 0){

return 0;

} else {

if(b < 0) {

if(b >Integer.MIN_VALUE) {

} else {

return (double)1 / pow(a, -b); // (1<< 31) - 1; (1 << 31)

return(double)1 / pow(a, Integer.MAX_VALUE) / a;

}

}else {

double half = pow(a, b / 2);

double res = half * half;

if(b % 2 == 1) {

res *= a;

}

returnres;

}

time : O(lg b)

[0, 3, 1, 2, 0, 0, 5] -> [3, 1, 2, 5, 0,0, 0]

private void swap(int[] num, int p, int q) {

if(p!= q) {

inttmp = num[p];

num[p]= num[q];

num[q]= tmp;

}

public void solve(int[] num) {

if(num== null || num.length == 0) {

return;

}

int cur = 0;

int end = 0;

while(cur <num.length) {

if(num[cur] != 0) { // 0, 3, 1, 2,0,0, 5

swap(num, cur ++, end++) // cur, end: 2, 1; 3,2; 4, 3; 7, 4

}else {

++ cur; // 1, 5, 6

}

[3, 0, 1]

Facebook:

Phone number combination

Linkedin:

Flip binary tree

Max subarray sum/ product

Linkedin Onsite：

1. Manager: 项目介绍极其详细

2. Design： Amazon Product Webpage

3. Coding： House Painting + followup

Max Points

4. Coding： Minimum Window

Sqrt (Double)

Hulu Phone：

Helo, Xiao!

RANSOM NOTE

- Someone wants to send amessage, but they do not want to give away their handwriting

- So they have a message,and they cut out letters in a magazine to make the message

message: "Give me1000 dollars"

magazine: "My name isgiven to be today 10000 dollar"

Want to write a message,by cutting out letters in a magzine.

- does the magazinecontain enough of the letters from my message

// returns true when thereare enough letters in the magazine to make the message

// assume all uppercase

// ignore punctuation

private voidplusOne(Map<Character, Integer> map, char key) {

map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);

}

private voidreduceOne(Map<Character, Integer> map, char key) {

if(map.get(key) == 1) { map.remove(key); }

else {map.put(key, map.get(key) - 1);

}

public booleancanCreateRansomNote(String message, String magazine) {

Map<Character, Integer> table = newHashMap<Character, Integer>();

for(inti = 0; i < message.length(); ++ i) {

plusOne(table, message.charAt(i));

}

for(inti = 0; i < magazine.length() && !map.isEmpty(); ++ i) {

char c = magazine.charAt(i);

if(map.containsKey(c)) { reduceOne(map, c); }

}

returnmap.isEmpty();

}

CHEMiCAL EQUATION PARSING

H20 - {H: 2, O: 1} -["H", "2", "O"]

NaCl - {Na: 1, Cl: 1} -["Na", "Cl"]

O(H(UO)2)3 - {O: 7, H: 3} -["O", "(", "H", "(", "O","2", ")", "3"]

O(H(C)) - {O: 1, H: 1,C:1} - ["O", "(", "H", "(","C", ")", ")"]

- Always well-formed input

- Tokens will be one of:

-Element

-Number

- Leftparen "("

- Rightparen "("

private voidadd(Map<String, Integer> map, String key, int val) {

if(!map.containsKey(key)) { map.put(key, val); }

else {map.put(key, map.get(key) + val);

}

private booleanisInteger(String s) {

try {

Integer.parseInt(s);

}catch(NumberFormatException e) {

return false;

}

returntrue;

}

H20

i = 0

res: {H: 2}

Map<String, Integer>parseEquation(String[] eq) {

Map<String, Integer> res = new HashMap<String, Integer>();

Stack<Map<String,Integer>> mapStack = new Stack<Map<String, Integer>>();

mapStack.push(res);

for(inti = 0; i < eq.length; ++ i) {

String cur = eq【i】;

if(cur.equals("(")) {

mapStack.push(new HashMap<String, Integer>());

} else if(cur.equals(")")) {

int k = 1;

if(i < eq.length - 1 && isInteger(eq[i + 1])) {

k = Integer.valueOf(eq[i + 1]);

++ i;

}

Map<String, Integer> currMap = mapStack.pop();

Map<String, Integer> prevMap = mapStack.peek();

for(Map.Entry<String, Integer> entry : currMap.entrySet()) {

add(prevMap, entry.getKey(), entry.getValue() * k);

}

} else if(i < eq.length - 1 && isInteger(eq[i + 1])) {

add(mapStack.peek(), cur, Integer.parseInt(eq[i + 1]));

++ i;

} else {

add(mapStack.peek(), cur, 1);

}

returnres;

}

Linkedin 加面：

public final class MapPruner

{

/**

* Prune a map byremoving entries corresponding to the given paths.

* Example:

* input:

* {

* "key1": "bar",

* "key2": "baz"

* "key3":

* {

* "key4": "bar"

* }

*

* pathsToPrune:["key2", "key3/key4"]

*

* output:

* {

* "key1": "bar",

* "key3":

* {

* }

*/

// pathsToPrune = ["" ]

private static voidhelper(String[] strs, int i, Map<String, Object> map) { // i = 1; Map:{key4 : bar}

if(!map.containsKey(strs【i】)) { return; }

Object val =map.get(strs【i】); // baz; {key4: bar}; bar

if(i ==strs.length - 1) { map.remove(strs【i】); } // remove baz

else if(valinstanceof Map) { // true

helper(strs,i + 1, (Map)val);

}

public staticMap<String, Object> pruneByPaths(

finalMap<String, Object> input,

finalCollection<String> pathsToPrune)

{

if(input == null|| pathsToPrune == null) {

throw newIllegalArgumentException("Error Msg");

}

for(String path: pathsToPrune) { // key2 ; key3/key4

if(path !=null && !path.equals("")) {

String[]strs = path.split("/"); // {key2}; [key3, key4]

if(strs.length > 0) { // 2

helper(strs, 0, input);

}

return input;

}

FB：
Facebook onsite一周，HR说明天约电话，好紧张。面经：
1. Word Break.
2. Merge K sorted list
3. Word Search(可以斜着走)

Youtube：

1. 视屏推荐的方式；算法：wildcard match（Leetcode）

2. 一些数据结构概念

算法：

给一个String 可以包含数字或者字母找出里面的是否存在一个substring全是数字而且这个substring表示的数字可以被36整除，并且不能是0。

e.g.: 360ab: True

0ab: False

3. 给一堆range（未order有重叠）然后给一个数判断这个数是否在range里面

（1， 5）（0，8）（4，6）

9： false

2: true

可以用bitset做

然后衍生出merge interval算法coding，再用bynarysearch找target是否在range中

4. Pascal Triangle

HULU onsite：

1. Recover dictionary order

2. ATM Database system design （Withdraw,deposit and check balance）

3. Minimum window

4. Sliding window for one function only call atmost 3 times in 5 minutes.

xmpy · 发表于 12-7-2014 08:54 AM

ym caobosi~~~

freshwind · 发表于 12-7-2014 12:06 PM

太赞了！！！

		自动登录	找回密码
密码			立即注册

[米群网大牛独家面经总结] 帮人发几个面经

亲！马上注册或者登录会查看更多内容！

本帖被以下淘专辑推荐:

相关帖子

推广达人

突出贡献

优秀版主

最佳新人

热心会员

精华帖之王

论坛元老

宣传达人

活跃会员