Data Structures
http://www.geeksforgeeks.org/archives/22677
Linked List
1. Reverse a linked List - in Place Recursive
2. Check if a LL is a palindrome in place
Reverse 2nd half, compare elt by elt.
3. Middle of a LL
4. Check for a loop in a LL
Binary Tree
5. Print all nodes at a given level
6. Max ht. of a binary tree
7. No. of nodes in a Binary Tree
8. What is a spanning Tree?
A spanning tree is a tree associated with a network. All the nodes of the graph appear
on the tree exactly once. A minimum spanning tree is a spanning tree organized so
that the total edge weight between nodes is minimized.
9. Does the minimum spanning tree of a graph give the shortest distance between any 2
specified nodes?
No. The Minimal spanning tree assures that the total weight of the tree is kept at its
minimum. But it doesn't mean that the distance between any two nodes involved in
the minimum-spanning tree is minimum.
General
10.Find duplicates, no. of duplicates in an array in linear time.
11.Given an array of integers, return the first integer which occurs only once
in O(n).
Same thing, first one with no duplicates.
12.There are 'n' vertices and 0 edges of an undirected graph. What is the
maximum number of
edges that you can draw such that the graph remains disconnected.
Just exclude one vertice and then connect all the n-1 vertices, it will be (n-
1)C2 i.e. (n-1)(n-2)/2.
13.Reverse words : "I love to play" becomes "play to love I".
done in place. -> DONE
14.pre-order, in-order, and post-order tree traversal are ___ type of search
DFS
15.LL nth node from end
16.Rev. a dbly linked list
17.An array has duplicate elements each elements occurs even number of
time except one occurs odd number of times. Print that number. Better
complexity = better.
XOR all the no.s , the no. remaining = ans.
18.Find merge node in 2 LLs
first we need to find the length of both the lists, then move ahead the
difference in bigger list and then match nodes in parallel.
19.Find merge node in 2 LLs without calculating length.
Reverse both the LLs, compare parallel.
20.Recursively Merge 2 sorted LLs
1.
rev(root)
{
if(!root || !(root->next))
newroot=root;
else
{
rev(root->next);
if(root->next)
{ root->next->next=root;
root->next=NULL;
}
}
return newroot;
}
3.
void getTheMiddle(mynode *head)
{
mynode *p = head;
mynode *q = head;
if(q!=NULL)
{
while((q->next)!=NULL && (q->next->next)!=NULL)
{
p = (p!=(mynode *)NULL?p->next:(mynode *)NULL);
q = (q!=(mynode *)NULL?q->next:(mynode *)NULL);
q = (q!=(mynode *)NULL?q->next:(mynode *)NULL);
}
printf("The middle element is [%d]",p->value);
} }
4.
mynode * find_loop(NODE * head)
{
mynode *current = head;
while(current->next != NULL)
{
mynode *temp = current->next;
while(temp->next != NULL && temp != current)
{
if(temp->next == current)
{
printf("\nFound a loop.");
return current;
}
temp = temp->next;
}
current = current->next;
}
return NULL;
}
5.
void print_at_level(Node *node, int desired, int current)
{
if (node)
{
if (desired == current)
print(node);
else
{
print_at_level(node->right, desired, current + 1);
print_at_level(node->left, desired, current + 1);
}
}
}
6.
int maxHeight(BinaryTree *p)
{
if (!p) return 0;
int left_height = maxHeight(p->left);
int right_height = maxHeight(p->right);
return (left_height > right_height) ? left_height + 1 : right_height + 1;
}
7.
public int numNodes(TreeNode t){
if (t == null) return 0;
return (1 + numNodes(t.leftChild) + numNodes(t.rightChild); }
10.
Suppose the array has numbers ranging from a to b. Declare an array of size
(b a+1) = 180 and initialize all values to 0. Let's call this array
duplicates.
Loop through arr. For every arr[i] increment duplicates[arr[i] - a].
After the loop is complete, duplicates[i] will hold the number of times (i
+ a) occurred in arr.
15.
public Node getNthNodeFromEnd(Node head, int nth) {
Node nthNode = head;
Node pointer = nthNode;
int i = 0;
while (nthNode != null && i != nth) {
pointer = pointer.getNext();
i++;
}
while (pointer != null) {
pointer = pointer.getNext();
nthNode = nthNode.getNext();
}
return nthNode;
}
20.
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
if (a == NULL) /* Base cases */
return(b);
else if (b==NULL)
return(a);
if (a->data <= b->data)
{ result = a;
result->next = SortedMerge(a->next, b);
}
else
{ result = b;
result->next = SortedMerge(a, b->next);
}
return(result);}
