All About Knowledge

Wednesday, 2 December 2015

Tree: Postorder Traversal

Problem Statement

You are given a pointer to the root of a binary tree; print the values in post-order traversal.

You only have to complete the function.

Input Format
You are given a function,

void Postorder(node *root) {

}

Output Format
Print the values on a single line separated by space.

Sample Input

Sample Output

1 4 5 6 2 3

/* you only have to complete the function given below.
Node is defined as

struct node
{
int data;
node* left;
node* right;
};

*/

void Postorder(node *root) {
if(root == NULL){
return;
}
Postorder(root->left);
Postorder(root->right);
cout<<root->data<<" ";

}

Tree: Preorder Traversal

Problem Statement

You are given a pointer to the root of a binary tree; print the values in preorder traversal.

You only have to complete the function.

Input Format
You are given a function,

void Preorder(node *root) {

}

Output Format
Print the values on a single line separated by space.

Sample Input

Sample Output

3 5 1 4 2 6

/* you only have to complete the function given below.
Node is defined as

struct node
{
int data;
node* left;
node* right;
};

*/

void Preorder(node *root) {
if(root == NULL){
return;
}
cout<<root->data<<" ";
Preorder(root->left);
Preorder(root->right);
}

Print contents of an array in reverse order

Problem Statement

An array is a series of elements of the same type placed in contiguous memory locations that can be individually referenced by adding an index to a unique identifier.

You'll be given an array of

N integers, and you have to print the integers in reverse order.

Note: If you have already solved the problem "Arrays Introduction" in the Introduction chapter of the C++ domain, you may skip this challenge.

Input Format

The first line of input contains

N, the number of integers. The next line contains

N integers separated by a space.

Constraints

1<=N<=1000

1<=Ai<=10000, where

Ai is the

ith integer in the array.

Output Format

Print the

N integers of the array in the reverse order on a single line separated by single spaces.

Sample Input

4
1 4 3 2

Sample Output

2 3 4 1

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int N;
cin>>N;
int* A = (int*)malloc(sizeof(int)*N);
for(int i=0;i<N;i++){
cin>>A[i];
}
while(N>0){
cout<<A[N-1]<<" ";
N--;
}
return 0;
}

Insert a node into a sorted doubly linked list

Problem Statement

You’re given the pointer to the head node of a sorted doubly linked list and an integer to insert into the list. Create a node and insert it into the appropriate position in the list. The head node might be NULL to indicate that the list is empty.

Input Format
You have to complete the Node* SortedInsert(Node* head, int data) method which takes two arguments - the head of the sorted, doubly linked list and the value to insert. You should NOT read any input from stdin/console.

Output Format
Create a node with the given data and insert it into the given list, making sure that the new list is also sorted. Then return the head node of the updated list. Do NOT print anything to stdout/console.

Sample Input

NULL , data = 2
NULL <-- 2 <--> 4 <--> 6 --> NULL , data = 5

Sample Output

NULL <-- 2 --> NULL
NULL <-- 2 <--> 4 <--> 5 <--> 6 --> NULL

Explanation
1. We have an empty list, 2 is inserted.
2. Data 5 is inserted such as list remains sorted.

/*
Insert Node in a doubly sorted linked list
After each insertion, the list should be sorted
Node is defined as
struct Node
{
int data;
Node *next;
Node *prev;
}
*/
Node* SortedInsert(Node *head,int data)
{
// Complete this function
// Do not write the main method.
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->prev = NULL;
node->next = NULL;
if(head == NULL){
head = node;
return head;
}
if(head->next == NULL){
if(head->data > data){
node->next = head;
head->prev = node;
head = node;
return head;
}
}
Node *current = head;
while(current->next != NULL && current->next->data < data){
current = current->next;
}
if(current->next == NULL){
current->next = node;
node->prev = current;
}else{
node->prev = current;
node->next = current->next;
current->next->prev = node;
current->next = node;
}

return head;
}

Tuesday, 1 December 2015

Find Merge Point of Two Linked Lists

Problem Statement

You’re given the pointer to the head nodes of two linked lists that merge together at some node. Find the node at which this merger happens. The two head nodes will be different and neither will be NULL.

[List #1] a--->b--->c
                     \
                      x--->y--->z--->NULL
                     /
     [List #2] p--->q

In the above figure, both list merges at node x.

Input Format
You have to complete the int FindMergeNode(Node* headA, Node* headB) method which takes two arguments - the heads of the linked lists. You should NOT read any input from stdin/console.

Output Format
Find the node at which both lists merge and return the data of that node. Do NOT print anything to stdout/console.

Sample Input

 1
  \
   2--->3--->NULL
  /
 1


1--->2
      \
       3--->Null
      /
     1

Sample Output

2
3

Explanation
1. As shown in the Input, 2 is the merge point.
2. Similarly 3 is merging point

/*
Find merge point of two linked lists
Node is defined as
struct Node
{
int data;
Node* next;
}
*/
int FindMergeNode(Node *headA, Node *headB)
{
// Complete this function
// Do not write the main method.
Node* tempA = headA;
Node* tempB = headB;
if(headA == NULL || headB == NULL){
return 0;
}
int countA = 0;
int countB = 0;
while(tempA != NULL){
countA += 1;
tempA = tempA->next;
}
while(tempB != NULL){
countB += 1;
tempB = tempB->next;
}

tempA = headA;
tempB = headB;
if(countA > countB){
int diff = countA - countB;
while(diff > 0){
tempA = tempA->next;
diff--;
}
while(tempA != tempB){
tempA = tempA->next;
tempB = tempB->next;
}
return tempA->data;
}else if(countA == countB){
while(tempA != tempB){
tempA = tempA->next;
tempB = tempB->next;
}
return tempA->data;
}else{
int diff = countB - countA;
while(diff > 0){
tempB = tempB->next;
diff--;
}
while(tempA != tempB){
tempA = tempA->next;
tempB = tempB->next;
}
return tempB->data;
}
}