Insertion of a binary tree involves the following steps:
If the root is null, make this the root.
If the root is a single node with no children and it’s value
is greater than the input, insert the input as the left child of the root.
Otherwise insert as the right child.
If the root has any siblings, traverse right if the root is
smaller than the input, otherwise traverse left. In each case, append the tree
with the input as a leaf. The leaf attaches to the sentinel node just as in the
case of the root above.
Deletion from a binary tree involves the following steps:
Deletion is tricky because the delete of the node requires
several of the following nodes to be written and this is because splicing the
node may be required. The case of deleting the nodes is trivial because the left
child leaf or the right child leaf can be deleted without affecting the rest of
the tree.
There are three cases for the node to be deleted. These cases depends on how many siblings the node has for it to be deleted.
1) the first case is when there are no children , we just remove it.
2) the second case is when there is only one child, we splice out the node.
3) the third case is when there are two children, we splice out the successor which has at most one child and replace z with y.
There are three cases for the node to be deleted. These cases depends on how many siblings the node has for it to be deleted.
1) the first case is when there are no children , we just remove it.
2) the second case is when there is only one child, we splice out the node.
3) the third case is when there are two children, we splice out the successor which has at most one child and replace z with y.
So the steps are as follows:
Walk down the tree to find the node to be deleted. Traverse right
if the node to be deleted has a value greater than the root. Arrive at the node
to be deleted or null if the node is not found .
If the node to be deleted is the root and the root has two
siblings, the tree successor has to be found, spliced and made the root. Otherwise if there is only one sibling, then that sibling is chosen to replace the node. We can call the node to be deleted as z and the one to be spliced as y. y = z when there is only one sibling.
If y has a left sibling, then we will need to update its parent and hence we will call it x.
Otherwise we will choose x as the right sibling.
If x is not null, we update it's parent to point to y's parent.
If y's parent is null, then y is the root, hence x has to be made the root.
Otherwise. if y was the left sibling of its parent then that parent's left sibling should now point to x, otherwise we choose the right sibling.
if y != z, then we transfer y's data to z.
Red Black Tree
The Red black tree must satisfy the following properties:
1. Every node is either red or black.
2. The root is black
3. Every leaf is black
4. If a node is red, then its children are black
5. For each node, all paths to the node contain the same number of black nodes.
Tree Insertions or deletions require rotations.
1. Tree Insertion is very much like the tree insert procedure but involves recoloring and rotation at the end to satisfy the red-black properties. There are three cases to be considered depending on whether the uncle (y) of the node just inserted (z) is red or black and z is a right or left child.
To enumerate these cases:
Case 1: z's uncle y is red : Action - recolor the parent and the uncle, z moved up
Case 2: z's uncle y is black and z is a right child : Action - perform a left rotation
Case 3: z's uncle y is black and z is a left child : Action - perfrom a right rotation
Color of root and leafs to be checked at the end of the procedure :
2. Tree deletions is very much like the tree delete procedure also requires recoloring and rotations. There are four cases to be considered and these are the dependent on whether the node to be fixed (x) has a red or black sibling and whether that node's sibling (w) has red or black children.
To enumerate these cases:
Case 1: x's sibling w is red : Action - exchange the color of the parent and w and perform a left rotation
Case 2: x's sibling w is black, and both of w's children are black : Action - color the sibling to red and move x up the tree
Case 3: x's sibling w is black, w's left child is red, and w's right child is black : Action - exchange the color of w and its left child and perform a right rotation.
Case 4: x's sibling w is black and w's right child is red : Action - remove extra black and perform left rotation.
Graph : This can have nodes similar to a n-ary tree. Graph can also be represented by edges and vertices.
Breadth First Traveral:
Use a queue and insert a node. When the node is removed, it siblings are inserted. Each pop operation results in a step of the breadth first traversal. This continues until the queue is empty.
Depth first traversal is easy to write with a recursive function. Check the parameter, define the terminal condition, recurse down the adjacent nodes, one by one.
Djikstra's algorithm is useful to find a single-source shortest path on a weighted, directed graph. You pick the minimum vertex among the adjacent and then relax the edges for each vertex adjacent to the pick.
B-tree is also popular. Each node has the number of keys currently stored, the node n[x] keys themselves, stored in non-decreasing order and a boolean value to say if it is a leaf or an internal node.
Techniques to use various data structures
Divide and conquer. This performs faster by collapsing linear searches to log n search. Then combining the solutions to sub-problems. Its great for sub problems that are independent
Dynamic Programming: This also combines the solutions to sub-problems except that the sub-problems overlap.
Greedy Algorithms : This makes the choice that looks best at the moment. It will always make the locally optimal choice.
There's top down as well as bottom up approach where the problems are decomposed top down and solutions are built bottom up.
Some examples:
1. Longest Common Subsequence :
Step 1 : Characterize a LCS with the following criteria: say Z is an LCS of X and Y
1. if Xm == Yn, then Zk = Xm = Yn and Zk-1 is an LCS of X and Y
2. If Xm != Yn, then Zk != Xm => Z is an LCS of Xm-1 and Y
3. If Xm != Yn, then Zk != Yn => Z is an LCS of X and Yn-1
Step 2: Define the recursion
C[i, j] = 0 if i = 0, or j = 0
= c[i -1, j - 1] + 1 if i, j > 0 and xi = yi
= max(c[i, j - 1], c[i -1, j ]) if i, j > 0 and xi != yj
Step 3: Computing the length of an LCS
LCS-Length(X, Y) : Use the step 2 and set up a recursion to compute the length.
2. String pattern matching :
Finite state Automata can be used for the following:
Define a finite automaton matcher with right going edges forming the spine of the automaton and numbering as many as the pattern specified. A directed edge shows some state transition. Pattern match length and offset are both captured
In C# language provisions for performing a regex, we have some good design and implementation.
Here it is for a quick recap.
Regex r = new Regex( pattern, options);
int[] gnums = r.GetGroupNumber();
Match m = r.Match(text);
while (m.Success)
{
for ( int i = 0; i < gnums.Length; i++)
{
Group g = m.Groups[gnums[i]];
CaptureCollection cc = g.Captures;
for ( int j = 0; j < cc.Count; j++)
{
capture c = cc[j];
Console.WriteLine( "\t\tCapture{0} = [{1}] Index = {2} and Length = {3}", j, c, c.Index, c.Lenght);
}
}
m = m.NextMatch();
}
Moving to the language based interview questions on C#, here is a quick recap of some questions asked in interviews:
Some questions :
1. [TCS] Desribe the garbage collector in .Net. It's compact generational markdown compactor.
2. [TCS] What is reflection ? How's it used ? Suggested answer : Reflection is a way to manipulate the types based on their metadata. Some uses of reflection are late binding, serialization , remoting, attributes etc.
3. [Starbucks] How do you wrap your MVC methods for error handling. Answer [HandleError] attribute
4. [Starbucks] How do you define your serialization attributes. Why is order useful?
5. [Starbucks] How do you use WCF with SOAP ? What additional items do you specify in the web.config ?
6. [T-Mobile] What attributes are used to define REST APIs in Controller ? HttpGet, HttpPost
7. [Infosys] With use of a single sign on software such as siteminder across various internal applications, a user session is lost between navigations. How do you diagnose and fix the problem ? This could be an issue with javascript, services, siteminder or network.
8. [Infosys] How do you prioritze, keep the team moving, meet the deadlines, and deliver with high quality
9. [Ontela] How would you design a file system ? What are the layers and interface.
There is a lot of considerations for the system programming questions. For example, File System design has to consider organizing files and block level storage, locking, logging, file access security and remoting The layers involve File Organization, File Management. file allocation strategy, file buffering and disk manangement interface.
File allocation strategies have to consider file allocation in large blocks or small file system devices. File Allocation strategies could consider storage in a linked list of alarge blocks, consecutive storage in a single blocks, and storage in a bunch of smal blocks tracked by an index. If random access is important, the linked list might be a poor choice. If fast reads are important, ascertaining the physical location of data would be in constant time for consecutive or indexed storage. If internal and external fragmentation is to be considered, then allocation size will need to be adjusted. If free space needs to be tracked, linked list or bit vector could be used. Operating System like Linux make files systems to be extended or added as plugins with their implementation of Virtual File System.
Virtual File System is an indirection layer which handles all the file system calls and calls the necessary file system functions in the physical file system code to do the I/O. The physical file system may employ one or more buffer cache to interact with device drivers and in turn with device controllers.
File Systems can be mounted and this populates the file descriptors which contains several kinds of information. Information that are common to every file system type.
Talking about files, let's take a look at newer dbs now.
If y has a left sibling, then we will need to update its parent and hence we will call it x.
Otherwise we will choose x as the right sibling.
If x is not null, we update it's parent to point to y's parent.
If y's parent is null, then y is the root, hence x has to be made the root.
Otherwise. if y was the left sibling of its parent then that parent's left sibling should now point to x, otherwise we choose the right sibling.
if y != z, then we transfer y's data to z.
Red Black Tree
The Red black tree must satisfy the following properties:
1. Every node is either red or black.
2. The root is black
3. Every leaf is black
4. If a node is red, then its children are black
5. For each node, all paths to the node contain the same number of black nodes.
Tree Insertions or deletions require rotations.
1. Tree Insertion is very much like the tree insert procedure but involves recoloring and rotation at the end to satisfy the red-black properties. There are three cases to be considered depending on whether the uncle (y) of the node just inserted (z) is red or black and z is a right or left child.
To enumerate these cases:
Case 1: z's uncle y is red : Action - recolor the parent and the uncle, z moved up
Case 2: z's uncle y is black and z is a right child : Action - perform a left rotation
Case 3: z's uncle y is black and z is a left child : Action - perfrom a right rotation
Color of root and leafs to be checked at the end of the procedure :
2. Tree deletions is very much like the tree delete procedure also requires recoloring and rotations. There are four cases to be considered and these are the dependent on whether the node to be fixed (x) has a red or black sibling and whether that node's sibling (w) has red or black children.
To enumerate these cases:
Case 1: x's sibling w is red : Action - exchange the color of the parent and w and perform a left rotation
Case 2: x's sibling w is black, and both of w's children are black : Action - color the sibling to red and move x up the tree
Case 3: x's sibling w is black, w's left child is red, and w's right child is black : Action - exchange the color of w and its left child and perform a right rotation.
Case 4: x's sibling w is black and w's right child is red : Action - remove extra black and perform left rotation.
Graph : This can have nodes similar to a n-ary tree. Graph can also be represented by edges and vertices.
Breadth First Traveral:
Use a queue and insert a node. When the node is removed, it siblings are inserted. Each pop operation results in a step of the breadth first traversal. This continues until the queue is empty.
Depth first traversal is easy to write with a recursive function. Check the parameter, define the terminal condition, recurse down the adjacent nodes, one by one.
Djikstra's algorithm is useful to find a single-source shortest path on a weighted, directed graph. You pick the minimum vertex among the adjacent and then relax the edges for each vertex adjacent to the pick.
B-tree is also popular. Each node has the number of keys currently stored, the node n[x] keys themselves, stored in non-decreasing order and a boolean value to say if it is a leaf or an internal node.
Techniques to use various data structures
Divide and conquer. This performs faster by collapsing linear searches to log n search. Then combining the solutions to sub-problems. Its great for sub problems that are independent
Dynamic Programming: This also combines the solutions to sub-problems except that the sub-problems overlap.
Greedy Algorithms : This makes the choice that looks best at the moment. It will always make the locally optimal choice.
There's top down as well as bottom up approach where the problems are decomposed top down and solutions are built bottom up.
Some examples:
1. Longest Common Subsequence :
Step 1 : Characterize a LCS with the following criteria: say Z is an LCS of X and Y
1. if Xm == Yn, then Zk = Xm = Yn and Zk-1 is an LCS of X and Y
2. If Xm != Yn, then Zk != Xm => Z is an LCS of Xm-1 and Y
3. If Xm != Yn, then Zk != Yn => Z is an LCS of X and Yn-1
Step 2: Define the recursion
C[i, j] = 0 if i = 0, or j = 0
= c[i -1, j - 1] + 1 if i, j > 0 and xi = yi
= max(c[i, j - 1], c[i -1, j ]) if i, j > 0 and xi != yj
Step 3: Computing the length of an LCS
LCS-Length(X, Y) : Use the step 2 and set up a recursion to compute the length.
2. String pattern matching :
Finite state Automata can be used for the following:
Define a finite automaton matcher with right going edges forming the spine of the automaton and numbering as many as the pattern specified. A directed edge shows some state transition. Pattern match length and offset are both captured
In C# language provisions for performing a regex, we have some good design and implementation.
Here it is for a quick recap.
Regex r = new Regex( pattern, options);
int[] gnums = r.GetGroupNumber();
Match m = r.Match(text);
while (m.Success)
{
for ( int i = 0; i < gnums.Length; i++)
{
Group g = m.Groups[gnums[i]];
CaptureCollection cc = g.Captures;
for ( int j = 0; j < cc.Count; j++)
{
capture c = cc[j];
Console.WriteLine( "\t\tCapture{0} = [{1}] Index = {2} and Length = {3}", j, c, c.Index, c.Lenght);
}
}
m = m.NextMatch();
}
Moving to the language based interview questions on C#, here is a quick recap of some questions asked in interviews:
Some questions :
1. [TCS] Desribe the garbage collector in .Net. It's compact generational markdown compactor.
2. [TCS] What is reflection ? How's it used ? Suggested answer : Reflection is a way to manipulate the types based on their metadata. Some uses of reflection are late binding, serialization , remoting, attributes etc.
3. [Starbucks] How do you wrap your MVC methods for error handling. Answer [HandleError] attribute
4. [Starbucks] How do you define your serialization attributes. Why is order useful?
5. [Starbucks] How do you use WCF with SOAP ? What additional items do you specify in the web.config ?
6. [T-Mobile] What attributes are used to define REST APIs in Controller ? HttpGet, HttpPost
7. [Infosys] With use of a single sign on software such as siteminder across various internal applications, a user session is lost between navigations. How do you diagnose and fix the problem ? This could be an issue with javascript, services, siteminder or network.
8. [Infosys] How do you prioritze, keep the team moving, meet the deadlines, and deliver with high quality
9. [Ontela] How would you design a file system ? What are the layers and interface.
There is a lot of considerations for the system programming questions. For example, File System design has to consider organizing files and block level storage, locking, logging, file access security and remoting The layers involve File Organization, File Management. file allocation strategy, file buffering and disk manangement interface.
File allocation strategies have to consider file allocation in large blocks or small file system devices. File Allocation strategies could consider storage in a linked list of alarge blocks, consecutive storage in a single blocks, and storage in a bunch of smal blocks tracked by an index. If random access is important, the linked list might be a poor choice. If fast reads are important, ascertaining the physical location of data would be in constant time for consecutive or indexed storage. If internal and external fragmentation is to be considered, then allocation size will need to be adjusted. If free space needs to be tracked, linked list or bit vector could be used. Operating System like Linux make files systems to be extended or added as plugins with their implementation of Virtual File System.
Virtual File System is an indirection layer which handles all the file system calls and calls the necessary file system functions in the physical file system code to do the I/O. The physical file system may employ one or more buffer cache to interact with device drivers and in turn with device controllers.
File Systems can be mounted and this populates the file descriptors which contains several kinds of information. Information that are common to every file system type.
Talking about files, let's take a look at newer dbs now.
No comments:
Post a Comment