. You will be given the number of pairs of parenthesis. Find out the total possible valid unique combinations and there should not be any duplicity. Write code
这个应该有计算公式吧？？？
Saturday, October 25, 2014
Sunday, October 19, 2014
Saturday, October 18, 2014
count number of bits of '1' from 1 to n
Q:
from 1 to n, count the number of bits that were set to 1.
For example,
n == 1, return 1,
n == 2, return 3,
n == 3, return 5
n==4, return 6
A:
solution 1: 一个个数，
Solution 2：把n 从2^j 一个个整除，来计算。
Mistakes:
1: 这里，要除的时候，跟n+1无关，而应该是n / 上一位的power，因此要power2<<1
from 1 to n, count the number of bits that were set to 1.
For example,
n == 1, return 1,
n == 2, return 3,
n == 3, return 5
n==4, return 6
A:
solution 1: 一个个数，
Solution 2：把n 从2^j 一个个整除，来计算。
private static int numberOf1Bits(int n) {
int mask = 0; // set the mask as the left part of nPlusOne
int nBits = 0; // counts the bits from 1 to n in their binary form
for (int i = 30; i >= 0; i--) {
int power2 = 1 << i;
if(n/power2<1) // this two lines can be commented
continue; // can be commented
mask |= (n & power2);
int nRepeatOnes = n / (power2<<1) * power2 ;
int nLeftOnes = ( n>>i & 1) * (n - mask+1);
nBits += nRepeatOnes + nLeftOnes;
}
return nBits;
}
Mistakes:
1: 这里，要除的时候，跟n+1无关，而应该是n / 上一位的power，因此要power2<<1
Thursday, October 16, 2014
Amazon面试题
Question 2: A sorted array has been rotated r times to the left. Find r in least possible time.
Question 1: There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?
Question 1: There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).
Count total set bits in all numbers from 1 to n
Given a positive integer n, count the number of 1 bits.
Question 1: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs.
Question 2: The above question was raised to 3 dimensions.
Question 3: The above question was then raised to k dimensions.
Questions : Then there were many questions asked on compilers and dynamic memory allocation.
estion 1: You are given pairs of numbers. In a pair the first number is smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d), the second set can follow the first set if b<c.So you can form a long chain in the similar fashion. Find the longest chain which can be formed.
Find the longest increasing subsequence in O(nlogn). Proof and full code was required.
Amazon2
Replace each element of an array with its greatest next integer in O(n).
题一:
有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
题一:
有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
Answer: 如果每个node不会发送相同的时间戳的话： hashmap <timestamp, 这个时间
戳收到的数量> 如果相同node会发送相同的时间戳： hashmap <timestamp, 一个set
存储哪些node发送过这个时间戳> 然后应该有个数字代表99%的 node吧 如果hashmap的
value （对于第二种情况就是value的size） 超过了这个数字 就记录这个时间戳。
对于超多数据 根据时间戳进行hash 这样相同时间戳的数据会被分到同一台机器上 就
可以了吧
Saturday, October 11, 2014
facebook面试准备及内推 （转）
update:发给我的基本都给推了，有些已经开始面试了，少量被HR筛掉了。继续提供内
推。
提供内推，社招校招皆可，天朝美帝皆可，如有兴趣，请发简历到fbrefer@163.com
申请码工职位的，请至少保证刷完一遍leetcode，或同等水平
最近一年申请过的，由于公司政策，请不要再申请
如果需要，本人可以提供一次mock interview
关于面试流程
社招的话
电面1-2轮，一般就是coding
onsite一般是4轮，2轮coding，1轮design，1轮behavior+coding
校招的话，那轮design也变成coding了
关于准备
1) algo/coding
建议大家刷一下leetcode，基本上cover到了大多数常见面试题，而且有可能碰到原题
。需要注意的是，仅仅解出来，做到bug free可能是不够的。代码的质量和速度也非常
重要。网上有一些别人给出的答案可以参考，尽量做到代码简洁清晰。速度上leetcode
上所有题都做到10分钟以内写完。
2) design
解这种题是个*交流*的过程，或者说是给出方案然后获取反馈的不断循环的过程。
一般的流程：
首先你要问清楚requirement；
然后可以讲一下high level architecture，就是分成哪几个component，互相之间如果
interact，在白板上画一画；
之后面试官可能会让你深入某个component detail讨论；
也有可能变换requirement让你重新设计
另外，f家还喜欢让你估算机器之类的，做一些back-of-envelopme calculation。所以
最好对一些计算机相关的基本常数，fb的用户量等等有个大概的了解。
准备的时候建议看看fb的design高频题。一方面有可能面试的时候刚好碰到这几个
topic，另一方面其实很多design都是相通的。
之前有个帖子讲这个，原帖已经被删了，这儿有个备份http://blog.csdn.net/sigh1988/article/details/9790337
另外补充一点我收集的材料
a) 首先你可以从整体上了解一下facebook的architecture
http://www.quora.com/Facebook-Engineering/What-is-Facebooks-arc
http://www.ece.lsu.edu/hpca-18/files/HPCA2012_Facebook_Keynote.
http://www.quora.com/Facebook-Engineering/What-have-been-Facebo
除了下面给出的一些资料，fb engineering page里还有很多不错的内容
https://www.facebook.com/Engineering
b) news feed
这里有个talk
http://www.infoq.com/presentations/Facebook-News-Feed
对应的slides
http://readme.skplanet.com/wp-content/uploads/2012/11/0-3_Faceb
还有一些quora上的讨论
http://www.quora.com/Activity-Streams/What-are-the-scaling-issu
http://www.quora.com/What-are-best-practices-for-building-somet
http://www.quora.com/What-is-the-best-storage-solution-for-buil
c) facebook chat
这里有两个notes，其中第二个里面还有相应的tech talk links
https://www.facebook.com/notes/facebook-engineering/facebook-chat/
14218138919
https://www.facebook.com/notes/facebook-engineering/chat-stability-and-
scalability/51412338919
d) typeahead search & graph search
关于typeahead search的tech talk和notes
https://www.facebook.com/video/video.php?v=432864835468
https://www.facebook.com/note.php?note_id=365915113919
https://www.facebook.com/note.php?note_id=389105248919
关于graph search的paper, tech talk, notes。其中paper很值得一看。
http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p871-cur
https://newsroom.fb.com/Photos-and-B-Roll/4362/Graph-Search-Whiteboard
https://www.facebook.com/note.php?note_id=10151240856103920
https://www.facebook.com/note.php?note_id=10151347573598920
https://www.facebook.com/note.php?note_id=10151361720763920
https://www.facebook.com/note.php?note_id=10151432733048920
https://www.facebook.com/note.php?note_id=10151755593228920
e) facebook messages
两个tech talks
http://www.youtube.com/watch?v=XAuwAHWpzPc
http://www.infoq.com/presentations/HBase-at-Facebook
以及eng notes
https://www.facebook.com/note.php?note_id=10150148835363920
https://www.facebook.com/note.php?note_id=10150162742108920
f) photo storage
相关的papers和notes
https://www.usenix.org/conference/osdi10/finding-needle-haystack-facebooks-
photo-storage
https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Beaver.pdf
https://www.usenix.org/legacy/events/osdi10/tech/slides/beaver.pdf
https://www.facebook.com/note.php?note_id=76191543919
g) social graph data store
相关的note, video, paper
https://www.facebook.com/notes/facebook-engineering/tao-the-power-of-the-
graph/10151525983993920
https://www.usenix.org/conference/atc13/technical-sessions/presentation/
bronson
http://www.cs.cmu.edu/~pavlo/courses/fall2013/static/papers/117
h) tiny URL
这里有一些讨论
http://n00tc0d3r.blogspot.com/2013/09/big-data-tinyurl.html
http://stackoverflow.com/questions/742013/how-to-code-a-url-sho
http://stackoverflow.com/questions/3376163/what-are-the-things-
i) POI
参考这里
http://www.slideshare.net/mmalone/scaling-gis-data-in-nonrelati
http://www.mitbbs.ca/article_t/JobHunting/32476139.html
3) behavior，建议大家了解一下fb的culture，准备一下常见的behavior questions，
面试之前rehearsal一下。
最后面试临近的时候，可以再刷刷面经，找找感觉。像glassdoor, mitbbs/jobhunting
, careercup，这些上面就有很多。
如果有其它疑问，欢迎回复或者PM我。
Friday, October 10, 2014
LC不能直接pass的题目，需要多写几遍的 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
strstr()
sqrt()
Substring with of All Words
Permutations II ( 这个以前自己写了三种思路，刚刚竟然一种都没想起来，艹）
Wildcard Matching
N-Queens II
Largest Rectangle in Histogram
Permutation Sequence
Valid Number
sqrt()
Sunday, October 5, 2014
152. Maximum Product Subarray ~~~~~~~~~~~最终看了别人的代码
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
A:
----------------------自己的代码-------略---------------
就是先 用0 把所有的A[i]分开， 然后，只算有正负的。这样，每次相乘的结果，绝对值都变大了。因此，可以直接maxPosProduct 和minNegProduct互相转换。
但其实，这样是没有必要的-----------------
------------------------参考了别人的geeksforgeeks的代码--------------------
public class Solution {
public int maxProduct(int[] A) {
assert(A!=null && A.length >0);
if(A.length == 1)
return A[0];
int result = Integer.MIN_VALUE, maxEndHere = 1;// max positive product ending at the current position
int minEndHere = 1;// min negative product ending at the current position
for (int i = 0; i < A.length; i++) {
if (A[i] > 0) {
maxEndHere = maxEndHere * A[i];
minEndHere = Math.min(minEndHere * A[i],1);
result = Math.max(result,maxEndHere);
} else if(A[i]==0) {
maxEndHere = 1;
minEndHere = 1;
result = Math.max(result,0);// 0 can also be a product result
}else{ // A[i]<0
result = Math.max(minEndHere*A[i],result);
int tmp = maxEndHere;
maxEndHere = Math.max( minEndHere*A[i],1);
minEndHere = tmp*A[i];
}
}
return result;
}
}
Mistakes: 1: 就是上面的这个思路了。 每次用maxEndHere 等，每次初始值都设为1
2： when A[i]< 0 , we need calculate the result at the beginning, 因此， 我们不能简单地把result = Math.max( ) 放到if 条件的外面。
3: 切记： A.length ==1的时候要单独列出来。
Learned: ----------
1: java中， given
int a =3;
int A = {1,2,3};
运行语句： A[a/2]是正确的
2：函数要求的返回值是double， 我们可以return一个int类型。语法是正确的
3
Subscribe to:
Posts (Atom)