list palindrome

int check_palindrome(node_type *root)
{
int ret_val;
if(root)
{
ret_val=check_palindrome(root->next);
if(root->data != hroot->data)
return FALSE;
hroot=hroot->next;
return ret_val;
}
return TRUE;
}

LCA : lowest common ancestor

tree_node_type *LowestCommonAncestor( tree_node_type *root , tree_node_type *p , tree_node_type *q) { tree_node_type *l , *r , *temp; if(root==NULL) { return NULL; }

if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
return root;
}
else
{
l=LowestCommonAncestor(root->left , p , q);
r=LowestCommonAncestor(root->right , p, q);

if(l!=NULL && r!=NULL)
{
return root;
}
else
{
temp = (l!=NULL)?l:r;
return temp;
}
}
}
====================================================

Good and easy solution

Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side.

Implementation:

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int );

/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
/* If we have reached a leaf node then LCA doesn't exist
If root->data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root->data == n1 || root->data == n2)
return -1;

/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;

if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
return leastCommanAncestor(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return leastCommanAncestor(root->right, n1, n2);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

====================================================
http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

Find Lowest Common Ancestor in Binary Tree

Question:-You have a Binary Tree and Two node p , q.
You have to find the first common parent of p and q.


tree_node_type *LowestCommonAncestor(
tree_node_type *root , tree_node_type *p , tree_node_type *q)
{
tree_node_type *l , *r , *temp;
if(root==NULL)
{
return NULL;
}

if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
return root;
}
else
{
l=LowestCommonAncestor(root->left , p , q);
r=LowestCommonAncestor(root->right , p, q);

if(l!=NULL && r!=NULL)
{
return root;
}
else
{
temp = (l!=NULL)?l:r;
return temp;
}
}
}

hight of binary tree

Height of a Binary Tree
For a tree with just one node, the root node, the height is defined to be 0, if there are 2
levels of nodes the height is 1 and so on. A null tree (no nodes except the null node)
is defined to have a height of –1.
The following height function in pseudocode is defined recursively as discussed in
class. It should be easily to add a C++ version to the program binTree1.cpp.
int height( BinaryTree Node t) {
if t is a null tree
return -1;
hl = height( left subtree of t);
hr = height( right subtree of t);
h = 1 + maximum of hl and hr;
return h;
{

birthday song

linux must read

1. http://tldp.org/LDP/tlk/tlk.html
2. http://tldp.org/LDP/khg/HyperNews/get/khg.html
3. http://tldp.org/LDP/khg/HyperNews/get/memory/linuxmm.html
4. http://tldp.org/LDP/khg/HyperNews/get/tour/tour.html

interview puzzel

Pirates
Five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).

Solution
(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc… )

solution: most of the time i get people who give answers like “the most senior pirate takes half and divides the rest up among the least senior pirates.” um, you missed the whole point to begin with. sorry.

any answer without a specific logic behind it is invalid. if i ask you why pirate 5 gave x coins to pirate 1, please don’t say “because he’s nice”.

now for the real solution. pirate 5 being the most senior knows that he needs to get 2 other people to vote for his solution in order for him not to be executed. so who can he get to vote for him, and why would they choose to vote for him? if you start thinking that pirate 4 will never vote for him, because he would rather have 5 die and then be in charge and take it all for himself, you are on the right track. but it gets more complicated.

lets consider if there were only 1 pirate. obviously he would take it all for himself and no one would complain.

if there were 2 pirates, pirate 2 being the most senior, he would just vote for himself and that would be 50% of the vote, so he’s obviously going to keep all the money for himself.

if there were 3 pirates, pirate 3 has to convince at least one other person to join in his plan. so who can he convince and how? here is the leap that needs to be made to solve this problem. PIRATE 3 REALIZES THAT IF HIS PLAN IS NOT ADOPTED HE WILL BE EXECUTED AND THEY WILL BE LEFT WITH 2 PIRATES. he already knows what happens when there are 2 pirates as we just figured out. pirate 2 takes all the money himself and gives nothing to pirate 1. so pirate 3 proposes that he will take 99 gold coins and give 1 coin to pirate 1. pirate 1 says, well, 1 is better than none, and since i know if i don’t vote for pirate 3, i get nothing, i should vote for this plan.

now we know what happens when there are 3 pirates. so what happens with 4? well pirate 4 has to convince 1 other person to join in his plan. he knows if he walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin. pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote for him, since 2 is better than 1. but as greedy as he is, pirate 4 would rather not part with 2 whole coins. he realizes that if he gets executed, then pirate 3’s scenario happens and pirate 2 gets the shaft in that scenario (he gets zero coins). so pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2 seeing that 1 is better than 0 will obviously vote for this plan.

a common objection is that pirate 2 is not guaranteed to vote for this plan since he might hope for the case when there are only 2 pirates and then he gets all the booty. but that is why i said that the pirates are extremely intelligent. pirate 2 realizes that pirate 3 is smart enough to make the optimal proposal, so he realizes that there will never be 2 pirates left, because 3 doesn’t want to die and we just showed that 3 has a winning proposal.

so lets sum up at this point

Pirate 1 2 3 4 5
5. ? ? ? ? ?
4. 0 1 0 99 -
3. 1 0 99 - -
2. 0 100 - - -
1.100
once you see the pattern it becomes very clear. you have to realize that when a pirate’s plan does not succeed then that means you are in the same situation with one less pirate.
1. pirate 1 needs 0 other people to vote for him. so he votes for himself and takes all the money. 2. pirate 2 needs 0 other people to vote for him. so he votes for himself and takes all the money. pirate 1 gets 0. 3. pirate 3 needs 1 other person to vote for him. he gives 1 coin to pirate 1 for his vote - if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows 1 is better than none. pirate 3 takes 99. pirate 2 gets 0. 4. pirate 4 needs 1 other person to vote for him. he gives 1 coin to pirate 2 - if we reduce to 3 pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes 99. pirate 3 gets 0. pirate 1 gets 0. 5. pirate 5 needs 2 other people to vote for him. its clear now that the 2 people he needs to convince are the 2 who get shafted in the 4 pirate scenario - pirate 3 and pirate 1. so he can give them each 1 coin (which is better than 0 - what they would get otherwise) and keep 98 for himself.

Pirate 1 2 3 4 5
5. 1 0 1 0 98
what happens if there are 15 pirates? pirate 15 needs 7 other people to vote for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps 93 coins himself. those pirates will all vote for him because they know that they get 0 coins if he dies and pirate 14 is in charge.

hope you enjoyed this one. its my favorite interview question of all. it really allows the candidate to ask a lot of interesting questions and its really amazing when they reach the solution all by themselves (as all fogcreek employees have done so far).

array and pointer

Q: Since array references decay into pointers, if arr is an array, what's the difference between arr and &arr?

A: The type.

In Standard C, &arr yields a pointer, of type pointer-to-array-of-T, to the entire array. (In pre-ANSI C, the & in &arr generally elicited a warning, and was generally ignored.) Under all C compilers, a simple reference (without an explicit &) to an array yields a pointer, of type pointer-to-T, to the array's first element.

For a simple array

int a[10];
a reference to a has type ``pointer to int,'' and &a is ``pointer to array of 10 ints.'' For a two-dimensional array like
int array[NROWS][NCOLUMNS];
a reference to array has type ``pointer to array of NCOLUMNS ints,'' while &array has type ``pointer to array of NROWS arrays of NCOLUMNS ints.''
See also questions 6.3, 6.13, and 6.18.

interviewing websites

1. http://www.techinterview.org/
2. http://technical-interview.com/techinterview.aspx

Ayush First Birthday card invite

IP sec

http://www.cromwell-intl.com/tcpip/what-is-ipsec.html

HOW CIDR SIMPLIFING THE WORK OF ROUTING TABLE?

That is a good question and the answer is a CCNP topic called route summarization. Lets say that you have 2 subnets bound on 2 ethernet interfaces. The first 192.168.0.1/24 and on the second eithernet interface, 192.168.1.1/24. Weill instead of advertising 2 seperate routes on your routing table, you would simply just advertise a summary route of 192.168.0.0/23. This would essential advertise both individual subnets as one route and then as the packet arrives at the route via your serial interface, the router would route the packet to the correct ethernet interface based on its binding and the IP address of the packet.

data structure

http://www.brpreiss.com/books/opus4/html/page9.html

http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680No1.html#cis680Ch12.html

Good links

http://www.joyofprogramming.com/

7_Things_Every_Software_Architect_Should_Know

http://97things.oreilly.com/wiki/index.php/97_Things_Every_Software_Architect_Should_Know_-_The_Book

About Flexible Array Members(FAM)

About Flexible Array Members(FAM)
My latest column in LFY is about Flexible Array Members (FAM) - see http://www.lfymag.com/currentissue.asp?id=13 (the article is not available online yet.

For those who dont know that FAM is: FAM is about the C99 feature where the last member of a struct can be an incomplete one. We can allocate memory dynamically for that structure with additional storage for that struct to treat the last element as a flexible lenght array. We remember the size of the allocated array in a member of the struct itself.

So far so good. An LFY reader - Basavaraj Dengi - asked me this intersting question: "when we can use a pointer and keep the things simple,
why use flexible array member?" An interesting question, indeed!

It appears that using FAM member and a pointer are equivalent. For example

struct varlength1 {
int len;
int *data;
};

struct varlength2 {
int len;
int data[];
};

Just think about it - what are the differences here? varlength1 has a *data, and we can allocate the struct statically. Then we need to allocate data with some dynamically allocated memory. What about the struct that is allocate dynamically? We logically do two allocations: one for the struct itself and another for the pointer member inside.

However with varlenght2, we can allocate it statically like this:

struct varlength2 {
int len;
int data[];
} varray { 3, { 1, 2, 3 } };

(This is a GCC feature and I am not sure if its C99), so it is very convenient. Coming to dynamic allocation of varlenght2, we do one dynamic allocation and allocate extra space for the data so that the end of the structure is treated as part of the array. How about doing free of the data? The compiler will obviously give an error, and so we need to do a free once: and that is for the struct.

As we can see, FAM is a convenience feature. Assume that we're writing a program for reading a file which is written according to a simple fileformat (bitmap format comes to my mind, but since I dont remember that format off-my-head, I am not sure if its a very good example for explaining the use of FAM). Now, we read the file header, which is typically a fixed lenght header. The header gives info on the rest of the file, which let us assume, is a simple list of integers. Now, for implementing it, FAM comes handy: as we read the header, we can allocate the struct for that file format once and use that FAM as if we allocated it statically. Freeing that struct is also easy. With a pointer member it is a little more work, but I dont deny it, it will also work.

Get me right: I am not saying using FAM is good and recommended. What I am saying is that FAM is a convenience feature and sometimes we find it as a handy feature to use. Yes, I can hear some of you still murmuring with disapproving my explanation. I see their point: C programmers can live without FAM, just like the K&R C days. But as I said, its just a "convenience" feature. If you want, take it and use it, or you can live with the plain old pointers, and keep going: you make the choice!

cost volatile

volatile long * const timer = 0x0000ABCD;

It reads as follows: the timer is a const pointer to a long volatile variable. In plain English, it means that the timer is a variable that I will not change; it points to a value that can be changed without the knowledge of the compiler!

So in above case..cost is for "timer " but volatile is for "*timer" (value pointed by timer)...so both r not for same variable

but i cam to know that we can set vloatile and cost for same varibale...i think that also true but i don;t know exact example

Demystifying the ‘Volatile’ Keyword in C

http://www.linuxforu.com/teach-me/demystifying-the-volatile-keyword-in-c/

One of my favourite interview questions for novice programmers is: “What is the use of the ‘volatile’ keyword?” For experienced programmers, I ask: “Can we qualify a variable as both ‘const’ and ‘volatile’—if so, what is its meaning?” I bet most of you don’t know the answer, right?
The keyword ‘volatile’ is to do with compiler optimisation. Consider the following code:

long *timer = 0x0000ABCD;
// assume that at location 0x0000ABCD the current time is available
long curr_time = *timer;
// initialize curr_time to value from ‘timer’
// wait in while for 1 sec (i.e. 1000 millisec)
while( (curr_time - *timer) < 1000 )
{
curr_time = *timer; // update current time
}
print_time(curr_time);
// this function prints the current time from the
// passed long variable
Usually, hardware has a timer that can be accessed from a memory location. Here, assume that it’s 0×0000ABCD and is accessed using a long * variable ‘timer’ (in the UNIX tradition, time can be represented as a long variable and increments are done in milliseconds). The loop is meant to wait one second (or 1,000 milliseconds) by repeatedly updating curr_time with the new value from the timer. After a one second delay, the program prints the new time. Looks fine, right?

However, from the compiler point of view, what the loop does is stupid—it repeatedly assigns curr_time with *timer, which is equivalent to doing it once outside the loop. Also, the variable ‘timer’ is de-referenced repeatedly in the loop—when it is enough to do it once. So, to make the code more efficient (i.e., to optimise it), it may modify loop code as follows:

curr_time = *timer; // update current time
long temp_time = *timer;
while( (curr_time - temp_timer) < 1000 )
{ /* do nothing here */
}
As you can see, the result of this transformation is disastrous: the loop will never terminate because neither is curr_time updated nor is the timer de-referenced repeatedly to get new (updated time) values.

What we need is a way to tell the compiler not to ‘play around’ with such variables by declaring them volatile, as in:

volatile long * timer = 0x0000ABCD;
volatile curr_time = *timer;
Now, the compiler will not do any optimisation on these variables. This, essentially, is the meaning of the ‘volatile’ keyword: It declares the variables as ‘asynchronous’ variables, i.e., variables that are ‘not-modified-sequentially’. Implicitly, all variables that are not declared volatile are ‘synchronous variables’.

How about qualifying a variable as both const and volatile? As we know, when we declare a variable as const, we mean it’s a ‘read-only’ variable—once we initialise it, we will not change it again, and will only read its value. Here is a modified version of the example:

long * const timer = 0x0000ABCD;
// rest of the code as it was before..
We will never change the address of a timer, so we can put it as a const variable. Now, remember what we did to declare the timer as volatile:

volatile long * timer = 0x0000ABCD;
We can now combine const and volatile together:

volatile long * const timer = 0x0000ABCD;
It reads as follows: the timer is a const pointer to a long volatile variable. In plain English, it means that the timer is a variable that I will not change; it points to a value that can be changed without the knowledge of the compiler!

.bss

From Wikipedia, the free encyclopedia

In computer programming, the name .bss or bss is used by many compilers and linkers for a part of the data segment containing statically-allocated variables represented solely by zero-valued bits initially (i.e., when execution begins). It is often referred to as the "bss section" or "bss segment".

In C, statically-allocated variables without an explicit initializer are initialized to zero (for arithmetic types) or a null pointer (for pointer types). Implementations of C typically represent zero values and null pointer values using a bit pattern consisting solely of zero-valued bits (though this is not required by the C standard). Hence, the bss section typically includes all uninitialized variables declared at the file level (i.e., outside of any function) as well as uninitialized local variables declared with the static keyword. An implementation may also assign statically-allocated variables initialized with a value consisting solely of zero-valued bits to the bss section.

Typically, the program loader initializes the memory allocated for the bss section when it loads the program. Operating systems may use a technique called zero-fill-on-demand to efficiently implement the bss segment (McKusick & Karels 1986). In embedded software, the bss segment is mapped into memory that is initialized to zero by the C run-time system before main() is entered.

Some application binary interfaces also support an sbss segment for "small data". Typically, these data items can be accessed by leaner code using instructions that can only access a certain range of addresses.

Historically, BSS (from Block Started by Symbol) was a pseudo-operation in UA-SAP (United Aircraft Symbolic Assembly Program), theassembler developed in the mid-1950s for the IBM 704 by Roy Nutt, Walter Ramshaw, and others at United Aircraft Corporation^{[citation needed]}. The BSS keyword was later incorporated into FAP (FORTRAN Assembly Program), IBM's standard assembler for its 709 and 7090/94 computers. It defined a label (i.e. symbol) and reserved a block of uninitialized space for a given number of words (Timar 1996).

redix tree routing table

1. we should read chapetr in book TCP/IP illusterated vol 2 chapter 18

2.

Where do two linked lists merge? intersection point of circular link list singly

http://www.velocityreviews.com/forums/t587346-where-do-two-linked-lists-merge.html

Where do two linked lists merge?

---

(followups set to comp.programming)

Where do two linked lists merge?

The following question was raised in comp.lang.c: Is there any
efficient way of finding the intersection point of two singly
linked lists? That is, given two singly linked lists that meet
at some point, find the node where they meet.

It turns out that the question as stated conceals two
assumptions. The first is that the two lists terminate with a
common null link. If they do they will have a single merge
point; the two merging lists form a Y structure. However there
are two ways a linked list can terminate, either by a null link
or by a cycle.

When the two lists terminate in a cycle each list can join the
cycle at different nodes. Each is a legitimate merge node, i.e.,

we can follow A until it reaches B's merge point or we can follow

B until it reaches A's merge point. There is no single "the
merge point".

We can remove the ambiguity by adopting some criterion for the
"best" merge point, e.g., the one that minimizes the combined
lengths to the merge point, although this fails if the two merge
points are on exact opposite sides of the cycle.

The second assumption is that the two lists have any nodes in
common, i.e., that they actually merge. Algorithms that fail if
the lists are terminated by cycles are unsafe for cycles.
Algorithms that fail if the lists have no nodes in common are
unsafe for failure to merge.

I. THE SIMPLE APPROACH FOR NULL TERMINATED LISTS

What we want to find is the first node the two lists have in
common. Let A.m and B.m be the number of nodes respectively
between the start of A and the merge node and B and the merge
node. Let m be the difference between A.m and B.m. If we skip
the first m nodes of the longer list than we can compare the two
lists node by node until we get to a match, the merge node.

Thus we can find the merge point if we can find m. Since the two

lists have the same nodes in common after the merge point we have



m = A.length - B.length.

The advantage of this approach is its simplicity. However it
does require knowing the list lengths. If this information is
not available in advance, the lists must be traversed in their
entirety.

The simple algorithm is unsafe for cycles (traversing the lists
to find end points goes into an infinite loop) but it is safe for

failure to merge (the comparison loop reaches the terminating
null node.)

II. FINDING THE ENTRY POINT INTO A TERMINATING CYCLE

Finding a cycle in a linked list is a classic algorithm. Let A
be the list. Let p1 and p2 be two pointers into A. Initialize
each to point to the start of the list. In each iteration of a
loop advance p1 by one node and p2 by two nodes; escape from the
loop when p1 and p2 both point to the same node. Call the node
x; it is a node within the list cycle.

The next step is to find the length of the cycle. In each
iteration of a second loop advance p1 by one node until again
points to x. The number of iterations is the length of the
cycle. Let k be the length of the cycle.

Now initialize p1 and p2 to the start of the list. Advance p2 by

k nodes. In a loop advance p1 and p2 by one node in each
iteration; escape from the loop when p1 and p2 point to the same
node. Call the node y. Then y is the entry point into the list
cycle.

If it is not known whether the lists are terminated by a cycle or

by a null node, we can add a test in the first loop to see if p2
detects a null node.

III. AN ALGORITHM BASED ON CYCLE DETECTION

When there is a terminating cycle there are three possibilities -

(a) A and B merge before they reach the cycle, (b) they merge at
a common entry point, or (c) they enter at different points in
the cycle. To distinguish these cases we need to find the entry
points for A and B. If the entry points are the same treat the
common entry point as a list terminator and apply the simple
algorithm in part I. If they differ we have case (c) - either
entry point is a legitimate answer.

If the two lists are null terminated the cycle detection
algorithm will discover the fact; the basic algorithm of part I
can be used.

In case (c) a complete implementation checks that the two lists
actually share a common cycle. Clearly they don't if the two
cycle lengths are different. If they are the same commonality
can be done by checking that the entry point of A can be reached
from the entry point of B.

This algorithm is O(n) but it is cumbersome and relatively
expensive. However,properly implemented, it is safe against
cycles and against failure to merge.

IV. A METHOD THAT DOESN'T REQUIRE FINDING THE TERMINATOR

The basic algorithm doesn't actually require knowing the list
length; what it needs is the distance between two nodes that
match. Call that distance m. It turns out that m can be found
without searching to the ends of the lists.

To see how that this works let us first suppose that we know a
bound M for m, and that A is the longer list. We compare
the first element of B with the first M elements of A. If we
find a match we've found m (and the merge point.) If no match is
found we go to node M+1 in B and check it against nodes M+1
through 2*M in A; we keep advancing by M nodes until a match is
found. A match will be found when the merge point is passed.
The difference in positions of the match in A and B yields m.

Unfortunately we don't have a bound M for m nor do we know which
list is longer. However we can use M=1 in the first iteration,
M=2 in the second iteration, and so on. We solve the problem of
not knowing which list is longer by alternating which list is the

lead list. With a bit of bookkeeping we get the following
algorithm:

Traverse A by one step. Traverse B by three steps, checking to
see if it there is a match with the last element read from A.
Traverse A by five more steps, checking for a match with the last

element read from B. Continue, alternating lists and increasing
the steps by two each time. When a match is found this way we
know the difference of distances to the merge point, m. This
gives us an O(m^2 +D) method where D is the common distance to
the merge point.

If the lists are null terminated it is possible that one of the
lists is exhausted before the a match is found. In that case we
revert to algorithm I. If the lists are terminated by a common
cycle algorithm IV will find one of the entry points. Algorithm
IV will fail if the two lists are disjoint and are terminated by
separate cycles.

FINAL REMARKS

This problem is more a puzzle than a serious programming problem.

A 'correct' solution depends on the objective and upon context.
If the lists are known to be null terminated algorithm III is not

needed. In principle algorithm IV is more efficient than
algorithm I; however it is more complex and in practice
simplicity may trump computational efficiency. If the lists are
known to be cycle terminated algorithm I will fail. Algorithm
III is guaranteed to work but is cumbersome; algorithm IV will be

considerably more efficient, but will fail if the lists are
disjoint.

Considered as a puzzle, algorithm I is the 'correct' solution.
It is simple and elegant.

Interview at Netapp

Q1. how to find point of intersaction of two list and how to find in circular list

1. http://geeksforgeeks.org/?p=2405

Q2. difference between

char *p="neeraj gupta"

array abcd[]="neeraj gupta"

if these r part of function will that increase size of stack?

Q3. How prectrisia tree work??

Q4. How specific rules get more priority from generic rules?

const and volatile

an a variable be both const and volatile?

Yes. The const modifier means that this code cannot change the value of the variable, but that does not mean that the value cannot be changed by means outside this code. For instance, in the example in FAQ 8, the timer structure was accessed through a volatile const pointer. The function itself did not change the value of the timer, so it was declared const. However, the value was changed by hardware on the computer, so it was declared volatile. If a variable is both const and volatile, the two modifiers can appear in either order. This is possible and mostly used in embedded system.The example is Interrupt Status Register.As it is a status register , in the program we should not modify this variable.So it should be a constant.But this variable can be changed by the processor or hardware based on the interrupt condition.So when in the program ,we want to read the value of this varible , it should read the actual value with out any optimisation.For this reason ,the variable can be declared as volatile too.

tcp state machine

dhcp state machine

http://www.tcpipguide.com/free/t_DHCPGeneralOperationandClientFiniteStateMachine.htm

College ragging

Read Index

1. Linux IP stack Book

a. Socket programming ( Good tutorial link : http://www.tenouk.com/cnlinuxsockettutorials.html)

2. OS concepts

3. RTOS

4. Networking

a. IGMP, Multicast rounting

b. Normal routing

c. DHCP

d. TCP , SACK , Fast retansmit and Fast recovery

e. Throughput, bandwidth

5. Algorothm

a. Hashing

b. Pactrica tree , used for IPv4 address and string manupilation

c. Complexity of Algo

d. Sorting

6. BW arch

7. Multi core

Netlink (for user/kernel communication)

Why do the above features use netlink instead of system calls, ioctls or proc filesystems for communication between user and kernel worlds? It is a nontrivial task to add system calls, ioctls or proc files for new features; we risk polluting the kernel and damaging the stability of the system. Netlink socket is simple, though: only a constant, the protocol type, needs to be added to netlink.h. Then, the kernel module and application can talk using socket-style APIs immediately.

Netlink is asynchronous because, as with any other socket API, it provides a socket queue to smooth the burst of messages. The system call for sending a netlink message queues the message to the receiver's netlink queue and then invokes the receiver's reception handler. The receiver, within the reception handler's context, can decide whether to process the message immediately or leave the message in the queue and process it later in a different context. Unlike netlink, system calls require synchronous processing. Therefore, if we use a system call to pass a message from user space to the kernel, the kernel scheduling granularity may be affected if the time to process that message is long.

The code implementing a system call in the kernel is linked statically to the kernel in compilation time; thus, it is not appropriate to include system call code in a loadable module, which is the case for most device drivers. With netlink socket, no compilation time dependency exists between the netlink core of Linux kernel and the netlink application living in loadable kernel modules.

Netlink socket supports multicast, which is another benefit over system calls, ioctls and proc. One process can multicast a message to a netlink group address, and any number of other processes can listen to that group address. This provides a near-perfect mechanism for event distribution from kernel to user space.

System call and ioctl are simplex IPCs in the sense that a session for these IPCs can be initiated only by user-space applications. But, what if a kernel module has an urgent message for a user-space application? There is no way of doing that directly using these IPCs. Normally, applications periodically need to poll the kernel to get the state changes, although intensive polling is expensive. Netlink solves this problem gracefully by allowing the kernel to initiate sessions too. We call it the duplex characteristic of the netlink socket.

Finally, netlink socket provides a BSD socket-style API that is well understood by the software development community. Therefore, training costs are less as compared to using the rather cryptic system call APIs and ioctls.

Relating to the BSD Routing Socket

In BSD TCP/IP stack implementation, there is a special socket called the routing socket. It has an address family of AF_ROUTE, a protocol family of PF_ROUTE and a socket type of SOCK_RAW. The routing socket in BSD is used by processes to add or delete routes in the kernel routing table.

In Linux, the equivalent function of the routing socket is provided by the netlink socket protocol type NETLINK_ROUTE. Netlink socket provides a functionality superset of BSD's routing socket.

Pthread producer consumer example in C

This code creates two threads then passes data from one to the other in sequence. To compile, save the code as main.c (or whatever you want) and then use the command:

 gcc -lpthread main.c -o main 

or you can create a make file containing the lines:

main: main.c      gcc -lpthread main.c -o main

You can then just use the command “make” to compile the code, this is useful if you want to change the program thus needing to compile it multiple times.

/*pthread example. Copyright (c) 2006-2007 Richard Palethorpe  Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:  The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE  Website: richiejp.wordpress.com email: richiejp@gmail.com*/  #include  #include  #include   void* producer(void*); void* consumer(void*);  /*This data structure contains information that needs to be shared between threads. It is passed to the producer and consumer threads' starter functions. The alternative to this is to use global variables.*/ struct Context{         pthread_cond_t* cond;         pthread_mutex_t* mutex;         /*This is used to hold a character while it is passed from one thread to         another. Only the thread which owns the mutex lock should access it.*/         char holder;         int error; };  int main(){         volatile struct Context context;         context.cond = (pthread_cond_t*)malloc(sizeof(pthread_cond_t));         context.mutex = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t));         context.error = 0;          pthread_cond_init(context.cond, NULL);         pthread_mutex_init(context.mutex, NULL);          pthread_t prod;         pthread_t cons;          puts("createing first thread");         if(pthread_create(&prod, NULL, producer, (void*)&context) != 0){                 puts("Could not create producer thread");                  pthread_mutex_destroy(context.mutex);                 pthread_cond_destroy(context.cond);                  return(EXIT_FAILURE);         }          puts("createing second thread");         if(pthread_create(&cons, NULL, consumer, (void*)&context) != 0){                 puts("Could not create consumer thread");                  pthread_mutex_lock(context.mutex);                 context.error = 1;                 pthread_mutex_unlock(context.mutex);                 pthread_cond_signal(context.cond);                  pthread_join(prod, NULL);                  pthread_mutex_destroy(context.mutex);                 pthread_cond_destroy(context.cond);;                  return(EXIT_FAILURE);         }          pthread_join(prod, NULL);         pthread_join(cons, NULL);          pthread_mutex_destroy(context.mutex);         pthread_cond_destroy(context.cond);          free(context.cond);         free(context.mutex);          return(EXIT_SUCCESS); }  void* producer(void* _context){         puts("in producer");         struct Context* context = (struct Context*)_context;          char data[] = "Some data to send to the consumer\n";          pthread_mutex_lock(context->mutex);         int i;         for(i = 0; i  sizeof data; i++){                 if(!context->error){                         context->holder = data[i];                          pthread_cond_signal(context->cond);                         pthread_cond_wait(context->cond, context->mutex);                 }else{                         pthread_mutex_unlock(context->mutex);                          return NULL;                 }         }          pthread_cond_signal(context->cond);         pthread_mutex_unlock(context->mutex);          return NULL; }  void* consumer(void* _context){         puts("in consumer");         struct Context* context = (struct Context*)_context;          printf("Recieving data: ");           pthread_mutex_lock(context->mutex);         while(context->holder != ''){                 if(!context->error){                         putc((unsigned int)context->holder, stdout);                          pthread_cond_signal(context->cond);                         pthread_cond_wait(context->cond, context->mutex);                 }else{                         pthread_cond_signal(context->cond);                         pthread_mutex_unlock(context->mutex);                          return NULL;                 }         }          pthread_cond_signal(context->cond);         pthread_mutex_unlock(context->mutex);          return NULL; }

Priority Inversion

Priority Inversion

Priority inversion occurs when a low-priority thread holds a mutex, blocking a high-priority thread. Due to its low priority, the mutex owner may hold the mutex for an unbounded duration. As a result, it becomes impossible to guarantee thread deadlines.

The following example illustrates a typical priority inversion. In this example, the case of a uniprocessor system is considered. Priority inversions also occur on multiprocessor systems in a similar way.

In our example, a mutex M is used to protect some common data. Thread A has a priority level of 100 and is scheduled very often. Thread B has a priority level of 20 and is a background thread. Other threads in the process have priority levels near 60. A code fragment from thread A is as follows:

pthread_mutex_lock(&M);             /* 1 */ ... pthread_mutex_unlock(&M);

A code fragment from thread B is as follows:

pthread_mutex_lock(&M);          /* 2 */ ... fprintf(...);                    /* 3 */ ... pthread_mutex_unlock(&M);

Consider the following execution chronology. Thread B is scheduled and executes line 2. While executing line 3, thread B is preempted by thread A. Thread A executes line 1 and is blocked, because the mutex M is held by thread B. Thus, other threads in the process are scheduled. Because thread Bhas a very low priority, it may not be rescheduled for a long period, blocking thread A, although threadA has a very high priority.

Mutex Protocols

To avoid priority inversions, the following mutex protocols are provided by the threads library:

Priority inheritance protocol

Sometimes called basic priority inheritance protocol. In the priority inheritance protocol, the mutex holder inherits the priority of the highest-priority blocked thread. When a thread tries to lock a mutex using this protocol and is blocked, the mutex owner temporarily receives the blocked thread's priority, if that priority is higher than the owner's. It recovers its original priority when it unlocks the mutex.

Priority protection protocol

Sometimes called priority ceiling protocol emulation. In the priority protection protocol, each mutex has a priority ceiling. It is a priority level within the valid range of priorities. When a thread owns a mutex, it temporarily receives the mutex priority ceiling, if the ceiling is higher than its own priority. It recovers its original priority when it unlocks the mutex. The priority ceiling should have the value of the highest priority of all threads that may lock the mutex. Otherwise, priority inversions or even deadlocks may occur, and the protocol would be inefficient.

Choosing a Mutex Protocol

The choice of a mutex protocol is made by setting attributes when creating a mutex. The mutex protocol is controlled through the protocol attribute. This attribute can be set in the mutex attributes object by using the pthread_mutexattr_getprotocol and pthread_mutexattr_setprotocolsubroutines. The protocol attribute can have one of the following values:

PTHREAD_PRIO_NONE	Denotes no protocol. This is the default value.
PTHREAD_PRIO_INHERIT	Denotes the priority inheritance protocol.
PTHREAD_PRIO_PROTECT	Denotes the priority protection protocol.

The priority protection protocol uses one additional attribute: the prioceiling attribute. This attribute contains the priority ceiling of the mutex. The prioceiling attribute can be controlled in the mutex attributes object, by using the pthread_mutexattr_getprioceiling andpthread_mutexattr_setprioceiling subroutines.

The prioceiling attribute of a mutex can also be dynamically controlled by using thepthread_mutex_getprioceiling and pthread_mutex_setprioceiling subroutines. When dynamically changing the priority ceiling of a mutex, the mutex is locked by the library; it should not be held by the thread calling the pthread_mutex_setprioceiling subroutine to avoid a deadlock. Dynamically setting the priority ceiling of a mutex can be useful when increasing the priority of a thread.

The implementation of mutex protocols is optional. Each protocol is a POSIX option. For more information about the priority inheritance and the priority protection POSIX options, see Threads Library Options.

Inheritance or Protection

Both protocols are similar and result in promoting the priority of the thread holding the mutex. If both protocols are available, programmers must choose a protocol. The choice depends on whether the priorities of the threads that will lock the mutex are available to the programmer who is creating the mutex. Typically, mutexes defined by a library and used by application threads will use the inheritance protocol, whereas mutexes created within the application program will use the protection protocol.

In performance-critical programs, performance considerations may also influence the choice. In most implementations, especially in AIX, changing the priority of a thread results in making a system call. Therefore, the two mutex protocols differ in the amount of system calls they generate, as follows:

• Using the inheritance protocol, a system call is made each time a thread is blocked when trying to lock the mutex.
• Using the protection protocol, one system call is always made each time the mutex is locked by a thread.

In most performance-critical programs, the inheritance protocol should be chosen, because mutexes are low contention objects. Mutexes are not held for long periods of time; thus, it is not likely that threads are blocked when trying to lock them.

Thread

1. When several threads compete for a mutex, the losers block at that call - an unblocking call is available with "trylock" instead of the "lock" call.

2. In subroutines that execute to completion normally, you can often dispense with calling pthread_exit() - unless, of course, you want to pass a return code back. However, in main(), there is a definite problem if main() completes before the threads it spawned. If you don't call pthread_exit()explicitly, when main() completes, the process (and all threads) will be terminated. By calling pthread_exit() in main(), the process and all of its threads will be kept alive even though all of the code in main() has been executed

3. pthread_exit is used to explicitly exit a thread. Typically, the pthread_exit() routine is called after a thread has completed its work and is no longer required to exist.

4. If main() finishes before the threads it has created, and exits with pthread_exit(), the other threads will continue to execute. Otherwise, they will be automatically terminated when main() finishes.

5. The attr object is used to establish properties for the mutex object, and must be of type pthread_mutexattr_t if used (may be specified as NULL to accept defaults). The Pthreads standard defines three optional mutex attributes:

• Protocol: Specifies the protocol used to prevent priority inversions for a mutex.
• Prioceiling: Specifies the priority ceiling of a mutex.
• Process-shared: Specifies the process sharing of a mutex.

Idea

1. webpage for TV programs

Interview at sonus

Q1. Difference between OS and RTOS?

Q2. producer consumer ?

Q3. How to send signal in Linux?

Q4. How to calculate Throughput ?

Q5. DHCP send broadcast for some responses? why ?

Kernel Space - User Space Interfaces

http://people.ee.ethz.ch/~arkeller/linux/kernel_user_space_howto.html

This how-to aims to provide an overview over all existing communication mechanisms between Linux user and kernel space. The goal is to present a starting point for a developer who needs to transfer data between Linux kernel modules and user space programs. Each mechanism is described in its own section, with each section further divided into Description, Implementation, and Resources & Further Reading. In the description section we describe the basic mechanism and intended use of the mechanism. The implementation provides an example source code along with a short description. The Resources & Further reading section provides a list of useful articles and book chapters.

cisco interview

1. how to find Intersaction node for two link list

2. how to store one bit data for large number of entries..

Charles de Gaulle Airport (CDG) to Paris by Train | Paris by Train

Charles de Gaulle Airport (CDG) to Paris by Train | Paris by Train: "A�roport Charles de Gaulle 1” station two minutes later, and then reaches Gare du Nord in Paris"

Interview at Cisco

1. How sunetting helps in routing?

2. How to detect memory corruption

Network in freebsd

puzzel

You’re standing in front of a 100 story building with two identical bowling balls. You’ve been tasked with testing the bowling balls’ resilience. The building has a stairwell with a window at each story from which you can (conveniently) drop bowling balls.

To test the bowling balls you need to find the first floor at which they break. It might be the 100th floor or it might be the 50th floor, but if it breaks somewhere in the middle you know it will break at every floor above.

Devise an algorithm which guarantees you’ll find the first floor at which one of your bowling balls will break. You’re graded on your algorithm’s worst-case running time.

How gdb and ioctl works

1. How gdb breakpoint works

(http://www.delorie.com/gnu/docs/gdb/gdbint_toc.html#SEC_Contents : GDB INTERNALS)

The basic theory is that GDB will replace a program instruction with a trap, illegal divide, or some other instruction that will cause an exception, and then when it's encountered, GDB will take the exception and stop the program. When the user says to continue, GDB will restore the original instruction, single-step, re-insert the trap, and continue on.

Since it literally overwrites the program being tested, the program area must be writable, so this technique won't work on programs in ROM. It can also distort the behavior of programs that examine themselves, although such a situation would be highly unusual.

2. How IOCTL works

little endian or bg endian

const int i = 1; #define is_bigendian() ( (*(char*)&i) == 0 )

#define LITTLE_ENDIAN 0 #define BIG_ENDIAN    1  int endian() {     int i = 1;     char *p = (char *)&i;      if (p[0] == 1)         return LITTLE_ENDIAN;     else         return BIG_ENDIAN; }

Interview c question

Interview Questions

Home Interview Questions Interview Tips Puzzles HR Interview FAQs Mass Communication Indian Comics Contact us Your Ad Here

Below is the list of latest technical interview questions: Link List Questions Ques 1: How do you reverse a singly linked list? How do you reverse a doubly linked list? Write a C program to do the same. [Answer] Ques 2: Given only a pointer to a node to be deleted in a singly linked list, how do you delete it. [Answer] Ques 3: How do you sort a linked list? Write a C program to sort a linked list. [Answer] Ques 4: How to declare a structure of a linked list? [Answer] Ques 5: Write a C program to implement a Generic Linked List. [Answer] Ques 6: How do you reverse a linked list without using any C pointers? [Answer] Ques 7:How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list. [Answer] Ques 8:How do you find the middle of a linked list? Write a C program to return the middle of a linked list. [Answer] Ques 9:If you are using C language to implement the heterogeneous linked list, what pointer type will you use? [Answer] Ques 10: How to compare two linked lists? Write a C program to compare two linked lists. [Answer] Ques 11: How to create a copy of a linked list? Write a C program to create a copy of a linked list. [Answer] Ques 12: Write a C program to free the nodes of a linked list. [Answer] Ques 13: Can we do a Binary search on a linked list? [Answer] Ques 14: Write a C program to return the nth node from the end of a linked list. [Answer] Ques 15: How would you find out if one of the pointers in a linked list is corrupted or not? [Answer] Ques 16: Write a C program to insert nodes into a linked list in a sorted fashion. [Answer] Ques 17:Write a C program to remove duplicates from a sorted linked list. [Answer] Ques 18: How to read a singly linked list backwards? [Answer] Ques 19: How can I search for data in a linked list? [Answer] Ques 20: What is the difference between a linked list and Array? Ques 21: Implement a linked list. Why did you pick the method you did? Ques 22: Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time. Ques 23: Given two sorted linked lists, write a function to merge them into one. Ques 24: Delete an element from a doubly linked list. Ques 25: Find the nth node from the end of a singly link list in a single pass. C Functions Implementation Questions Ques 1: Write your own C program to implement the atoi() function. [Answer] Ques 2: Implement the memmove() function. What is the difference between the memmove() and memcpy() function? [Answer] Ques 3: Write C code to implement the strstr() (search for a substring) function. [Answer] Ques 4: Write your own printf() function in C. [Answer] Ques 5: Implement the strcpy() function. [Answer] Ques 6: Implement the strcmp(str1, str2) function. [Answer] Ques 7: Implement the substr() function in C. [Answer] Ques 8: Write your own File copy() function. [Answer] Ques 9: Write C programs to implement the toupper() and the isupper() functions. [Answer] Ques 10: Write a C program to implement your own strdup() function. [Answer] Ques 11: Write a C program to implement the strlen() function. [Answer] Ques 12: Write your own strcat() function. [Answer] C Programming Questions Ques 1: Right a program to implement malloc. Ques 2: Write a C program to swap two variables without using a temporaryvariable . [Answer] Ques 3: What is the 8 queens problem? Write a C program to solve it. [Answer] Ques 4: Write a C program to print a square matrixhelically. [Answer] Ques 5: Write a C program to reverse a string. [Answer] Ques 6: Write a C program to reverse the words in a sentence in place. [Answer] Ques 7: Write a C program generate permutations. [Answer] Ques 8: Write a C program to calculate pow(x,n). [Answer] Ques 9: Write a C program which does wildcard pattern matching algorithm. [Answer] Ques 10: How do you calculate the maximum subarray of a list of numbers? [Answer] Ques 11: How to generate fibonacci numbers? How to find out if a given number is a fibonacci number or not? Write C programs to do both. [Answer] Ques 12: Solve the Rat In A Maze problem usingbacktracking. [Answer] Ques 13: What Little-Endian and Big-Endian? How can I determine whether a machine's byte order is big-endian or little endian? How can we convert from one to another? [Answer] Ques 14: Write C code to solve the Tower of Hanoi problem. [Answer] Ques 15: Write C code to return a string from a function. [Answer] Ques 16: Write a C program which produces its own source code as its output. [Answer] Ques 17: Write a C progam to convert from decimal to any base (binary, hex, oct etc...). [Answer] Ques 18: Write C code to check if an integer is a power of 2 or not in a single line? [Answer] Ques 19: Write a C program to find the GCD of two numbers. [Answer] Ques 20: Finding a duplicated integer problem. [Answer] Ques 21: Write code to remove duplicates in a sorted array. [Answer] Ques 22: How do you initialize a pointer inside a function? [Answer] Ques 23: Write C code to dynamically allocate one, two and three dimensional arrays (using malloc()). [Answer] Ques 24: How would you find the size of structure without using sizeof(). [Answer] Ques 25: Write a C program to multiply two matrices. [Answer] Ques 26: Write a C program to check for palindromes. [Answer] Ques 27: Write C code to implement the Binary Search algorithm. [Answer] Ques 28: Write code to add two polynomials. [Answer] Ques 29: Write a program to add two long positive numbers (each represented by linked lists). [Answer] Ques 30: How do you compare floating point numbers? [Answer] Ques 31: Is there something we can do in C but not in C++? [Answer] Ques 32: How to swap the two nibbles in a byte ? [Answer] Ques 33: How to scan a string till we hit a new line using scanf()? [Answer] Ques 34: How do you get the line numbers in C? [Answer] Ques 35: How to fast multiply a number by 7? [Answer] Ques 36: Write a simple piece of code to split a string at equal intervals. [Answer] Ques 37: Is there a way to multiply matrices in lesser than o(n^3) time complexity? [Answer] Ques 38: How can we sum the digits of a given number in single statement? [Answer] Ques 39: Given two strings A and B, how would you find out if the characters in B were a subset of the characters in A? [Answer] Ques 40: Write a program to check if the stack grows up or down. [Answer] Ques 41: Write a program to print numbers from 1 to 100 without using loops! [Answer] Ques 41: How to generate prime numbers? How to generate the next prime after a given prime? [Answer] Ques 42: How to add two numbers without using the plus operator? [Answer] Ques 43: Write your own trim() or squeeze() function to remove the spaces from a string. [Answer] Ques 44: Write your own random number generator function in C. Tree : (Answers will come soon) Ques 1: Write a C program to find the depth or height of a tree. Ques 2: Write a C program to determine the number of elements (or size) in a tree. Ques 3: Write a C program to delete a tree (i.e, free up its nodes) Ques 4: Write C code to determine if two trees are identical . Ques 5: Write a C program to find the mininum value in a binary search tree. Ques 6: Write a C program to compute the maximum depth in a tree? Ques 7: Write a C program to create a mirror copy of a tree (left nodes become right and right nodes become left)! Ques 8: Write C code to return a pointer to the nth node of an inorder traversal of a BST. Ques 9: Write C code to implement the preorder(), inorder() and postorder() traversals. Whats their time complexities? Ques 10: Write a C program to create a copy of a tree. Ques 11: Write C code to check if a given binary tree is a binary search tree or not? Ques 12: Write C code to implement level order traversal of a tree. Ques 13: Write a C program to delete a node from a Binary Search Tree? Ques 14: Write C code to search for a value in a binary search tree (BST). Ques 15: Write C code to count the number of leaves in a tree. Ques 16: Write C code for iterative preorder, inorder and postorder tree traversals Ques 17: Can you construct a tree using postorder and preorder traversal? Ques 18: Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings. Ques 19: Find the closest ancestor of two nodes in a tree. Ques 20: Given an expression tree, evaluate the expression and obtain a paranthesized form of the expression. Ques 21: How do you convert a tree into an array? What is an AVL tree? Ques 22: How many different trees can be constructed using n nodes? Ques 23: A full N-ary tree has M non-leaf nodes, how many leaf nodes does it have? Ques 24: Implement Breadth First Search (BFS) and Depth First Search (DFS) Updated! Ques 25: Write pseudocode to add a new node to a Binary Search Tree (BST) Updated! Ques 26: What is a threaded binary tree? Sorting Questions: (Answers will be posted soon) Ques 1:What is heap sort? Ques 2:What is the difference between Merge Sort and Quick sort? Ques 3:Give pseudocode for the mergesort algorithm. Ques 4:Implement the bubble sort algorithm. How can it be improved? Ques 5:Write the code for selection sort. Ques 6:Write the code for quick sort. Ques 7:Write the code for insertion sort. Ques 8:How can I sort things that are too large to bring into memory? Ques 9:For very small input which sorting algorithm will work best?