http://www.6test.edu.cn/~lujx/linux_networking/index.html?page=0131777203_ch17lev1sec4.html
http://www.ecsl.cs.sunysb.edu/elibrary/linux/network/LinuxKernel.pdf : good link
http://e-university.wisdomjobs.com/linux/chapter-208-277/receiving-data-in-the-transport-layer-udp-and-tcp.html
http://hsnlab.tmit.bme.hu/twiki/pub/Targyak/Mar11Cikkek/Network_stack.pdf : very good
Monday, January 30, 2012
Friday, January 27, 2012
Tree Algo
Thursday, January 26, 2012
Merge Sort vs. Quick Sort: Overview
Merge Sort vs. Quick Sort: Overview
Merge Sort
Quick Sort
Time complexity (Average): O(n log n) Time complexity (Average): O(n log n)
Time complexity (Worst): O(n log n) Time complexity (Worst): O(n^2)
(Occurs when list is sorted)
Stable sort
Not dependent on any factors
Average case = Worst Case Not a stable sort
Dependent on randomness of list
Memory: O(n)
Additional memory space required Memory: O(log n)
Memory Complexity (Best): O(1)
Little additional memory space required
When to use Merge Sort? When additional memory usage is not a problem and list could be partial sorted
When to use Quick Sort? When additonal memory usage is a problem and the list is randomized.
[Source: Sorting Algorithm]
Merge Sort
Quick Sort
Time complexity (Average): O(n log n) Time complexity (Average): O(n log n)
Time complexity (Worst): O(n log n) Time complexity (Worst): O(n^2)
(Occurs when list is sorted)
Stable sort
Not dependent on any factors
Average case = Worst Case Not a stable sort
Dependent on randomness of list
Memory: O(n)
Additional memory space required Memory: O(log n)
Memory Complexity (Best): O(1)
Little additional memory space required
When to use Merge Sort? When additional memory usage is not a problem and list could be partial sorted
When to use Quick Sort? When additonal memory usage is a problem and the list is randomized.
[Source: Sorting Algorithm]
Wednesday, January 25, 2012
Interview Mcafee
1. Is MSS optional or not
2. how traceroute work
3. implementation of hash funation
4. insert in binary search tree : try to write a program by urself
5. IPC machenism
6. shared memory
7. how kernel pass information to process
8. try to look at linux kernel path
Juniper
1. Mirror image of binary tree
2. How to write state machine using function pointer
3. how to write word alligned data.
4. If data is present in stack then is there any padding
2. how traceroute work
3. implementation of hash funation
4. insert in binary search tree : try to write a program by urself
5. IPC machenism
6. shared memory
7. how kernel pass information to process
8. try to look at linux kernel path
Juniper
1. Mirror image of binary tree
2. How to write state machine using function pointer
3. how to write word alligned data.
4. If data is present in stack then is there any padding
Saturday, January 21, 2012
Patricia tree
Must read : http://books.google.co.in/books?id=ESM3CWY5xRYC&pg=PA562&lpg=PA562&dq=patricia+tree+routing&source=bl&ots=b4pXXGtACY&sig=TISdjQMrPkEPDjorJMQelA9zx7U&hl=en&sa=X&ei=PZAbT9lw0IisB4Pa4eQN&ved=0CDwQ6AEwBDgK#v=onepage&q=patricia%20tree%20routing&f=false
Patricia stands for "Practical algorithm to retrieve information coded in alphanumeric",
Trie : A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes
Node : (1) A unit of reference in a data structure. Also called a vertex in graphs and trees. (2) A collection of information which must be kept at a single memory location.
Child : An item of a tree referred to by a parent item. See the figure at tree. Every item, except the root, is the child of some parent.
A Patricia tree is related to a Trie. The problem with Tries is that when the set of keys is sparse, i.e. when the actual keys form a small subset of the set of potential keys, as is very often the case, many (most) of the internal nodes in the Trie have only one descendant. This causes the Trie to have a high space-complexity.
Patricia tree : Binary digital tree
Specs :
n external nodes with key values
n-1 internal nodes
---------
Tries were invented by E. Fredkin in 1960
Patricia trees Patricia stands for "Practical algorithm to retrieve information coded in alphanumeric", invented by D. R. Morrison, 1968
The idea is to take a trie and get rid of any nodes that only have one child. Instead, each remaining node is labeled with a character position number which would have given that node's depth in the original uncompressed trie. We now have the problem that keys are no longer uniquely specified by the search path, so we have to store the key itself in the appropriate leaf. The storage requirement is now kn pointers, where n is the number of keys and k is the size of the alphabet. This is often significantly less than s(k + 1), particularly if the keys are very long.
A Patricia tree alone is far from efficient.
Patricia stands for "Practical algorithm to retrieve information coded in alphanumeric",
Trie : A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes
Node : (1) A unit of reference in a data structure. Also called a vertex in graphs and trees. (2) A collection of information which must be kept at a single memory location.
Child : An item of a tree referred to by a parent item. See the figure at tree. Every item, except the root, is the child of some parent.
A Patricia tree is related to a Trie. The problem with Tries is that when the set of keys is sparse, i.e. when the actual keys form a small subset of the set of potential keys, as is very often the case, many (most) of the internal nodes in the Trie have only one descendant. This causes the Trie to have a high space-complexity.
Patricia tree : Binary digital tree
Specs :
n external nodes with key values
n-1 internal nodes
---------
Tries were invented by E. Fredkin in 1960
Patricia trees Patricia stands for "Practical algorithm to retrieve information coded in alphanumeric", invented by D. R. Morrison, 1968
The idea is to take a trie and get rid of any nodes that only have one child. Instead, each remaining node is labeled with a character position number which would have given that node's depth in the original uncompressed trie. We now have the problem that keys are no longer uniquely specified by the search path, so we have to store the key itself in the appropriate leaf. The storage requirement is now kn pointers, where n is the number of keys and k is the size of the alphabet. This is often significantly less than s(k + 1), particularly if the keys are very long.
A Patricia tree alone is far from efficient.
Monday, January 16, 2012
multicasting
http://www.h3c.com/portal/Products___Solutions/Technology/Security_and_VPN/Technology_Introduction/200701/195605_57_0.htm
Sunday, January 15, 2012
Atomic operation and spin lock
http://en.wikipedia.org/wiki/Linearizability
spin lock : http://www.csie.dyu.edu.tw/~swang/LDD/ch5_p2.pdf
spin lock : http://www.csie.dyu.edu.tw/~swang/LDD/ch5_p2.pdf
Subscribe to:
Posts (Atom)