1point3acres.com/bbs/forum-28-1.html
What is write-ˇthrough cache? What is write-ˇback (copy-ˇback) cache?
In a write-ˇthrough cache, data is written to main memory at the same time as the
cache is updated.
In a write-ˇback cache, data is only written to main memory when it is forced out
of the cache on line replacement following a cache miss. Otherwise, writes by the
processor only update the cache.
A cache line in a write-ˇback cache that has been modified while it is in the cache
is said to be dirty. A cache line is marked as dirty by setting the dirty bit. If a cache line
is dirty, it must be written to memory on a cache miss because the next level of memory
contains data that has not been updated. The process of writing dirty data to main
memory is called cache cleaning.
http://blog.chinaunix.net/uid-ˇ15014334-ˇid-ˇ4185529.html
Stack vs Heap, which is allocated in run time, which is in compile time
Now Java only stores primitives on the stack. This keeps the stack small and helps
keeping individual stack frames small, thus allowing more nested calls. Objects are
created on the heap, and only references (which in turn are primitives) are passed
around on the stack. Stack values only exist within the scope of the function they are
created in. Once it returns, they are discarded.
process/thread区别
thread和process分别怎么通信。
thread如何安全访问共享内存-ˇ>mutex，semaphone/mutex区别
做一个browser每个tab是用thread还是process? -ˇ-ˇ chrome用process， firefox用
thread 。用process好处是独立memory space一个tab挂掉不影响其他
Java的ArrayList和LinkedList有什么区别
Java的 final, finally, finalize
Java垃圾收集
Java object class里面有什么function，各自是来干什么的
The equals method: by default equals() will behave the same as the “==”
operator and compare object locations.
Java hashCode function什么时候需要改写: if key is self-ˇdefined objects
virtual memory
virtual function
constructor, destructor
a == b. 什么时候++a != ++b:
2. pointer with different size
3. overflow
4. a 和 b 是不同类型的指针的时候
5. multithreading的情况
6. a 是 int ，b 是 long, 且 a== b == Integer.MAX_VALUE
缺页，TLB。换页的过程，换页算法，地址翻译的过程
Tree
Same Tree https://leetcode.com/problems/same-ˇtree/
Symmetric Tree https://leetcode.com/problems/symmetric-ˇtree/
Invert Binary Tree https://leetcode.com/problems/invert-ˇbinary-ˇtree/
mirror image tree: 给一个tree，build一个他的镜像树
Find whether a given binary tree is mirror image of the other one
http://blog.csdn.net/craiglin1992/article/details/44779133
Lowest Common Ancestors With Parent Pointer (same as intersection of linked list!)
http://articles.leetcode.com/2011/07/lowest-ˇcommon-ˇancestor-ˇof-ˇa-ˇbinary-ˇtree-ˇ
part-ˇii.html
Lowest Common Ancestor of a Binary Search Tree
https://leetcode.com/problems/lowest-ˇcommon-ˇancestor-ˇof-ˇa-ˇbinary-ˇsearch-ˇtree/
Lowest Common Ancestor of a Binary Tree https://leetcode.com/problems/lowest-ˇ
common-ˇancestor-ˇof-ˇa-ˇbinary-ˇtree/
Binary Tree Level Order Traversal https://leetcode.com/problems/binary-ˇtree-ˇlevel-ˇ
order-ˇtraversal/
Binary Tree Zigzag Level Order Traversal https://leetcode.com/problems/binary-ˇ
tree-ˇzigzag-ˇlevel-ˇorder-ˇtraversal/
Serialize and Deserialize Binary Tree https://leetcode.com/problems/serialize-ˇand-ˇ
deserialize-ˇbinary-ˇtree/
List
Merge Two Sorted Lists https://leetcode.com/problems/merge-ˇtwo-ˇsorted-ˇlists/
Merge k Sorted Lists https://leetcode.com/problems/merge-ˇk-ˇsorted-ˇlists/
Merge K Sorted Iterators http://buttercola.blogspot.com/2015/11/linkedin-ˇmerge-ˇk-ˇ
sorted-ˇiterators.html
http://blog.csdn.net/craiglin1992/article/details/44770751
Array
Search in Rotated Sorted Array https://leetcode.com/problems/search-ˇin-ˇrotated-ˇ
sorted-ˇarray/
Search in Rotated Sorted Array II https://leetcode.com/problems/search-ˇin-ˇrotated-ˇ
sorted-ˇarray-ˇii/
Find Minimum in Rotated Sorted Array https://leetcode.com/problems/find-ˇminimum-ˇ
in-ˇrotated-ˇsorted-ˇarray/
Find Minimum in Rotated Sorted Array II https://leetcode.com/problems/find-ˇminimum-ˇ
in-ˇrotated-ˇsorted-ˇarray-ˇii/
Maximum Subarray https://leetcode.com/problems/maximum-ˇsubarray/
Maximum Product Subarray https://leetcode.com/problems/maximum-ˇproduct-ˇ
subarray/
Find A Balance Point In An Array
http://www.geeksforgeeks.org/equilibrium-ˇindex-ˇof-ˇan-ˇarray/
http://blog.csdn.net/craiglin1992/article/details/44771655
Merge Sorted Array https://leetcode.com/problems/merge-ˇsorted-ˇarray/
Intersection of Two Sorted Arrays
Solution:
Brute force: O(m * n) time
Binary Search: O(m * lg(n)) time (Faster then two pointers when m << n)
Hash Table: O(m + n) time, O(n) space (if n is big, then too much space and
crashes)
Two Pointers: O(m + n)
http://articles.leetcode.com/2010/03/here-ˇis-ˇphone-ˇscreening-ˇquestion-ˇfrom.html
http://blog.csdn.net/craiglin1992/article/details/44771405
Input is iterator
http://instant.1point3acres.com/thread/141317
String
Isomorphic Strings https://leetcode.com/problems/isomorphic-ˇstrings/
(两个hashmap展现two way mapping。如果input是三个string怎么判断)
Longest Palindromic Substring https://leetcode.com/problems/longest-ˇpalindromic-ˇ
substring/
Valid Number https://leetcode.com/problems/valid-ˇnumber/
(考虑正负号和小数点，不用考虑指数的情况。处理 "-ˇ." 这种情况)
Repeated DNA Sequences https://leetcode.com/problems/repeated-ˇdna-ˇsequences/
(一定要最优解法，也就是必须encoding，并且是1-ˇA, 2-ˇC, 3-ˇG, 4-ˇT这样，顺便考了下bit
操作。为什么要用HashMap不用array，HashMap会不会blow up，以及一些基本概念比
如Java int的范围)
Others
Shortest Word Distance I
Shortest Word Distance II
Shortest Word Distance III http://www.cnblogs.com/easonliu/p/4784826.html
http://segmentfault.com/a/1190000003906667
Paint House http://www.cnblogs.com/easonliu/p/4784858.html
Paint House II http://www.cnblogs.com/yrbbest/p/5020937.html
Find Triangle
Find three values that can be the lengths of the sides of a triangle. Three segments of
lengths A, B, C can form a triangle if and only if: A + B > C, B + C > A, A + C > B. e.g.
6, 4, 5 can form a triangle, 10, 2, 7 can't.
@param segmentLengths the lengths of segments that might form a triangle.
@return three values that can be the lengths of the sides of a triangle, or an empty
array if there are no such values in segmentLengths.
sample input: segmentLengths = [10, 5, 7, 4, 3]
Solution: http://www.geeksforgeeks.org/find-ˇnumber-ˇof-ˇtriangles-ˇpossible/
Brute force: nested for loops: O(n^3) (optimization: break loop when i + j <= k)
Sort and for loops: O(n^2)
Lintcode Triangle Count https://codesolutiony.wordpress.com/2015/05/21/lintcode-ˇ
triangle-ˇcount/
Nested Integer Weighted Sum
Given a nested list of integers, returns the sum of all integers in the list weighted by their
depth.
For example, given the list {{1,1}, 2, {1,1}} the function should return 10 (four 1's at
depth 2, one 2 at depth 1)
Given the list {1, {4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth
2, one 6 at depth2)
class NestedInteger {
public boolean isInteger();;
public boolean getInteger();;
public boolean getList();;
}
Follow up: Reversed Weighted Sum, one pass
Example: {1, {2, {3, 4}} return 1*3 + 2*2 + 3*1 + 4*1
Solution: http://yuanhsh.iteye.com/blog/2192549
private int depth(List input){
int d = 0;;
for( auto nestedInt : input){
if (!nestedInt.isInteger()) d = max(d, depth(nestInteger.getList());;
}
return d + 1;;
}
给一堆点和一个点，求这一堆点里离那个点最近的Top K个点。PriorityQueue
(改写以下comparator让PriorityQueue按照距离倒序建堆，然后遍历一遍所有point，先加
入queue，如果queue的size超过了K，就把队首元素poll出来。最后还留在队里的元素就
是topK)
(维护一个size k的max heap即可)
minHeap和maxHeap区别
Nearest N Points on a Plane: 之前面经出现过，Point就给了xy坐标，然后开始我说
sort，是nlogn。面试官说能不能能够提高，我就说如果这n个不要sorted的话，就quick-ˇ
select。面试官说可以然后没让实现Quick-ˇSelect，然后装傻问我你现在有了第n个的
index，怎么着前n-ˇ1个呢，我愣了半天，结果他就是要靠我是不是不懂装懂，最后我说前
n-ˇ1个经过Select之后就都是比第n个小的，面试官很满意。然后还让写了要穿进去当参数
的Comparator。
http://www.careercup.com/question?id=4758558331633664
http://blog.csdn.net/craiglin1992/article/details/44780401
Two Sum https://leetcode.com/problems/two-ˇsum/
Two Sum II -ˇ Input array is sorted http://blog.csdn.net/xudli/article/details/42290269
Two Sum III -ˇ Data structure design
http://blog.csdn.net/u013325815/article/details/42167849
http://www.cnblogs.com/lichen782/p/4348567.html
public interface TwoSum {
/** * Stores @param input in an internal data structure. */
void store(int input);;
/** * Returns true if there is any pair of numbers in the internal data structure
* which have sum @param val, and false otherwise*/
boolean test(int val);;
}
Follow up: Speed test and能够满足反复调用
Solution:
public class searchSum implements TwoSum {
List<Integer> data = new ArrayList<Integer> ();;
void store(int input) {
data.add(intput);;
}
boolean test(int val) {
int len = data.size();;
Set mem = new HashSet();;
for(int i = 0;; i < len;; i++) {
if ( mem.contains(val -ˇ data.get(i)) return true;;
else mem.add(data.get(i));;
}
return false;;
}
}
public class searchSumFaster implements TwoSum {
Set<Integer> sum = new HashSet<Integer>();;
List<Integer> data = new ArrayList<Integer>();;
void store(int input) {
for(int i = 0;; i < data.size();; i++) {
sum.add(data.get(i) + input);;
}
data.add(intput);;
}
boolean test(int val) {
return sum.contains(val);;
}
}
Insert Interval https://leetcode.com/problems/insert-ˇinterval/
计算interval cover range(和insert interval/merge interval很像) insert 和 getRange 的复杂
度
给一个java interface, 实现两个method，一个是void add interval(int from, int to), 另一个
是int getTotalLength()返回已有interval的总时间，当然，要考虑overlapping。比如(1,5),
(2, 6)的total length 是5
Add Interval
followup如何remove Interval
http://www.careercup.com/question?id=5711223014293504
http://blog.csdn.net/craiglin1992/article/details/44909017
http://blog.csdn.net/craiglin1992/article/details/44759403
输入排好序的int数组和target，求target在数组中出现的次数
mid stack。 例如push 1，3，6，5，4. 返回6。返回index的中值
用双链表做，maintain一个pointer指向中间
follow up是写popMid()函数
Solution: http://www.geeksforgeeks.org/design-ˇa-ˇstack-ˇwith-ˇfind-ˇmiddle-ˇoperation/
Design a data structure that supports add (T val), remove(T val) and
removeRandomElement() all in O(1) time
Solution: hashmap + ArrayList的方法。
用一个Map加一个ArrayList。remove(T t)的时候用map找到t的index，去array里把最后一
个T e挪到index的地方，map里删掉t，map里put(e, index)。removeRandom就在0到
array.size()之间generate一个数，然后用刚才的办法删掉就可以了。
No thread safe, 三个method都synchronized。
http://www.careercup.com/question?id=11353907
http://buttercola.blogspot.com/2015/11/linkedin-ˇdesign-ˇdata-ˇstructure-ˇto.html?m=1
http://blog.csdn.net/craiglin1992/article/details/44902111
Celebrity Problem http://yuanhsh.iteye.com/blog/2183929
tournament tree http://www.1point3acres.com/bbs/thread-ˇ141428-ˇ1-ˇ1.html
Hop Iterator, 类似于这个: http://instant.1point3acres.com/thread/148239
类似climbing stairs， recursion -ˇ> dp 优化
Text Justification
https://leetcode.com/problems/text-ˇjustification/
DelayedSchduled(用一个priorityQueue 以执行时间排序， 然后不断得查询系统时间，
一到时间就pop并且执行?)
Reverse polish notation
Top k most frequent elements
Top k Integer
give a string containing 'a' to 'z', sort lexicographically. Example " bbdda" -ˇ > "abbdd"
get influencer(celebrity)
给multidimensional array，给一个function， 输入这个array以及各个dimension上的
index，可以output这个位置上的数字。
写一个function，input是multidimensional array，以及array的dimensions，只能调用上
面给的那个function，输出这个array里面所有的数字的和
convert bst to doubly linked list
Careercup Linkedin Interview Questions
http://www.careercup.com/page?pid=linkedin-ˇinterview-ˇquestions&n=1
ML
