[Reverse a linked list (Function Program)]

Given pointer to the head node of a linked list, the task is to reverse the linked list.

Input:
You need to complete a method reverse() that takes head as argument and returns new head.
There are multiple test cases. For each test case, this method will be called individually.  The first line of input contains number of test cases.  Every test case has two lines, number of nodes first line and data values in next line.

Output:
Reverse the linked list and return head of the modified list.
Example:
Input:
1
6
1 2 3 4 5 6

Output:
6 5 4 3 2 1

**For More Examples Use Expected Output**

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

[Bubble Sort (Function Program)]

The task is to complete bubble function which is used to implement Bubble Sort.

Input:
First line of the input denotes number of test cases ‘T’. First line of the test case is the size of array and second line consists of array elements.
Output:
Sorted array in increasing order is displayed to the user.
Constraints:
1 <=T<= 100
1 <=N<= 1000
1 <=arr[i]<= 1000
Example:

Input:
2
5
4 1 3 9 7
10
10 9 8 7 6 5 4 3 2 1

Output:
1 3 4 7 9
1 2 3 4 5 6 7 8 9 10

**For More Examples Use Expected Output**

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Reverse words in a given string

Given a String of length N reverse the words in it. Words are separated by dots.

Input:
The first line contains T denoting the number of testcases. Then follows description of testcases. Each case contains a string containing spaces and characters.
Output:
For each test case, output a single line containing the reversed String.

Constraints:
1<=T<=20
1<=Lenght of String<=2000
Example:
Input:
2
i.like.this.program.very.much
pqr.mno

Output:
much.very.program.this.like.i
mno.pqr

**For More Examples Use Expected Output**

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Kth largest element in a stream

Given an input stream of n integers the task is to insert integers to stream and print the kth largest element in the stream at each insertion.

Example:

Input:
stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}
k = 3

Output:    {-1,   -1, 10, 11, 20, 40, 50,  50, ...}

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line of each test case contains two space separated integers k and n . Then in the next line are n space separated values of the array.

Output:
For each test case in a new line print the space separated values denoting the kth largest element at each insertion, if the kth largest element at a particular insertion in the stream doesn’t exist print -1.

Constraints:
1<=T<=100
1<=n,k<=1000
1<=stream[]<=100000

Example:
Input:

2
4 6
1 2 3 4 5 6
1 2
3 4

Output:
-1 -1 -1 1 2 3
3 4

**For More Examples Use Expected Output**

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Thief trying to escape

A thief trying to escape from a jail has to cross N walls each with varying heights. He climbs X feet every time. But, due to the slippery nature of those walls, every times he slips back by Y feet.  Now the task is to calculate the total number of jumps required to cross all walls and escape from the jail.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two space separated integers X, Y, N. Then in the next line are N space separated values denoting the heights ( Ht[] ) of the walls.

Output:
For each test case in a new line print the total number of jumps.

Constraints:
1<=T<=100
1<= N, X, Y <=100
1<= Ht[] <=1000

Example:
Input:

2
10 1 1
5
4 1 5
6 9 11 4 5

Output:
1
12

**For More Examples Use Expected Output**

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Does array represent Heap

Given an array, the task is to check if the given array represents a Binary Max-Heap.

Examples:

Input:  A[] = {90, 15, 10, 7, 12, 2}
Output: 1
The given array represents below tree
       90
     /    \
   15      10
  /  \     /
 7    12  2
The tree follows max-heap property as every
node is greater than all of its descendants.

Input:  A[] = {9, 15, 10, 7, 12, 11}
Output: 0
The given array represents below tree
       9
     /    \
   15      10
  /  \     /
 7    12  11
The tree doesn't follows max-heap property 9 is
smaller than 15 and 10, and 10 is smaller than 11.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line of input contains an integer N denoting the size of the array. Then in the next line are N space separated values of the array.

Output:
For each test case in a new line print 1 if the array could represent the max heap else print a 0.

Constraints:
1<=T<=100
1<=N<=1000
1<=A[]<=1000

Example:
Input:

2
6
90 15 10 7 12 2
6
9 15 10 7 12 11

Output:
1
0

**For More Examples Use Expected Output**

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Merge two sorted lists (in-place)

Given two sorted lists, merge them so as to produce a combined sorted list (without using extra space).

Examples:

Input : head1: 5->7->9
        head2: 4->6->8
Output : 4->5->6->7->8->9

Input : head1: 1->3->5->7
        head2: 2->4
Output : 1->2->3->4->5->7

 

In this post, a new simpler solutions are discussed. The idea is to one by one compare nodes and form the result list.

Method 1 (Recursive)

// C program to merge two sorted linked lists
// in-place.
#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
// Function to create newNode in a linkedlist
Node *newNode(int key)
{
    struct Node *temp = new Node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}
// A utility function to print linked list
void printList(Node *node)
{
    while (node != NULL)
    {
        printf("%d  ", node->data);
        node = node->next;
    }
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node *merge(Node *h1, Node *h2)
{
    if (!h1)
        return h2;
    if (!h2)
        return h1;
    // start with the linked list
    // whose head data is the least
    if (h1->data < h2->data)
    {
        h1->next = merge(h1->next, h2);
        return h1;
    }
    else
    {
        h2->next = merge(h1, h2->next);
        return h2;
    }
}
// Driver program
int main()
{
    Node *head1 = newNode(1);
    head1->next = newNode(3);
    head1->next->next = newNode(5);
    // 1->3->5 LinkedList created
    Node *head2 = newNode(0);
    head2->next = newNode(2);
    head2->next->next = newNode(4);
    // 0->2->4 LinkedList created
    Node *mergedhead = merge(head1, head2);
    printList(mergedhead);
    return 0;
}

Output:

0 1 2 3 4 5

 

Method 2 (Iterative)

// C program to merge two sorted linked lists
// in-place.
#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
// Function to create newNode in a linkedlist
struct Node *newNode(int key)
{
    struct Node *temp = new Node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}
// A utility function to print linked list
void printList(struct Node *node)
{
    while (node != NULL)
    {
        printf("%d  ", node->data);
        node = node->next;
    }
}
// Merges two lists with headers as h1 and h2.
// It assumes that h1's data is smaller than
// or equal to h2's data.
struct Node *mergeUtil(struct Node *h1,
                      struct Node *h2)
{
    // if only one node in first list
    // simply point its head to second list
    if (!h1->next)
    {
        h1->next = h2;
        return h1;
    }
    // Initialize current and next pointers of
    // both lists
    struct Node *curr1 = h1, *next1 = h1->next;
    struct Node *curr2 = h2, *next2 = h2->next;
    while (next1 && next2)
    {
        // if curr2 lies in between curr1 and next1
        // then do curr1->curr2->next1
        if ((curr2->data) > (curr1->data) &&
            (curr2->data) < (next1->data))
        {
            next2 = curr2->next;
            curr1->next = curr2;
            curr2->next = next1;
            // now let curr1 and curr2 to point
            // to their immediate next pointers
            curr1 = curr2;
            curr2 = next2;
        }
        else
        {
            // if more nodes in first list
            if (next1->next)
            {
                next1 = next1->next;
                curr1 = curr1->next;
            }
            // else point the last node of first list
            // to the remaining nodes of second list
            else
            {
                next1->next = curr2;
                return h1;
            }
        }
    }
    return h1;
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
struct Node *merge(struct Node *h1,
                          struct Node *h2)
{
    if (!h1)
        return h2;
    if (!h2)
        return h1;
    // start with the linked list
    // whose head data is the least
    if (h1->data < h2->data)
        return mergeUtil(h1, h2);
    else
        return mergeUtil(h2, h1);
}
// Driver program
int main()
{
    struct Node *head1 = newNode(1);
    head1->next = newNode(3);
    head1->next->next = newNode(5);
    // 1->3->5 LinkedList created
    struct Node *head2 = newNode(0);
    head2->next = newNode(2);
    head2->next->next = newNode(4);
    // 0->2->4 LinkedList created
    struct Node *mergedhead =
    merge(head1, head2);
    printList(mergedhead);
    return 0;
}

Output:

0 1 2 3 4 5

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

pthread_self() in C with Example

Syntax :- pthread_t pthread_self(void);

The pthread_self() function returns the ID of the thread in which it is invoked.

// C program to demonstrate working of pthread_self()
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void* calls(void* ptr)
{
    // using pthread_self() get current thread id
    printf("In funtion \nthread id = %d\n", pthread_self());
    pthread_exit(NULL);
    return NULL;
}
int main()
{
    pthread_t thread; // declare thread
    pthread_create(&thread, NULL, calls, NULL);
    printf("In main \nthread id = %d\n", thread);
    pthread_join(thread, NULL);
    return 0;
}

Output:

In function
thread id = 1
In main
thread id = 1

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Maximum length subsequence with difference between adjacent elements as either 0 or 1

Given an array of n integers. The problem is to find maximum length of the subsequence with difference between adjacent elements as either 0 or 1.

Examples:

Input : arr[] = {2, 5, 6, 3, 7, 6, 5, 8}
Output : 5
The subsequence is {5, 6, 7, 6, 5}.

Input : arr[] = {-2, -1, 5, -1, 4, 0, 3}
Output : 4
The subsequence is {-2, -1, -1, 0}.

The solution to this problem closely resembles the Longest Increasing Subsequence problem. The only difference is that here we have to check whether the absolute difference between the adjacent elements of the subsequence is either 0 or 1.

// C++ implementation to find maximum length
// subsequence with difference between adjacent
// elements as either 0 or 1
#include <bits/stdc++.h>
using namespace std;
// function to find maximum length subsequence
// with difference between adjacent elements as
// either 0 or 1
int maxLenSub(int arr[], int n)
{
    int mls[n], max = 0;
    
    // Initialize mls[] values for all indexes
    for (int i=0; i<n; i++)
        mls[i] = 1;
    
    // Compute optimized maximum length subsequence
    // values in bottom up manner
    for (int i=1; i<n; i++)
        for (int j=0; j<i; j++)
            if (abs(arr[i] - arr[j]) <= 1 &&
                    mls[i] < mls[j] + 1)
                mls[i] = mls[j] + 1;
    
    // Store maximum of all 'mls' values in 'max'   
    for (int i=0; i<n; i++)
        if (max < mls[i])
            max = mls[i];
    
    // required maximum length subsequence
    return max;       
}
// Driver program to test above
int main()
{
    int arr[] = {2, 5, 6, 3, 7, 6, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum length subsequence = "
         << maxLenSub(arr, n);
    return 0;
}

Output:

Maximum length subsequence = 5

Time Complexity: O(n2)
Auxiliary Space: O(n)

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Minimum cells traversed to reach corner where every cell represents jumps

Suppose A is at position (0, 0) of a 2-D grid containing ‘m’ rows and ‘n’ columns. His aim is to reach the bottom right point of this grid traveling through as minimum number of cells as possible.

Each cell of the grid contains a positive integer that defines the number of cells A can jump either in the right or the downward direction when he reaches that cell.

Find the minimum no of cells that need to be touched in order to reach bottom right corner.

Examples:

Input : 2 4 2
        5 3 8
        1 1 1
Output :
So following two paths exist to reach (2, 2) from (0, 0)
(0, 0) => (0, 2) => (2, 2)
(0, 0) => (2, 0) => (2, 1) => (2, 2)

Hence the output for this test case should be 3

Following is a Breadth First Search(BFS) solution of the problem:

  1. Think of this matrix as tree and (0, 0) as root and apply BFS using level order traversal.
  2. Push the coordinates and no of jumps in a queue.
  3. Pop the queue after every level of tree.
  4. Add the value at cell to the coordinates while traversing right and downward direction.
  5. Return no of cells touched while jumping when it reaches bottom right corner.
// C++ program to reach bottom right corner using
// minimum jumps.
#include <bits/stdc++.h>
using namespace std;
#define R 3
#define C 3
// function to check coordinates are in valid range.
bool safe(int x, int y)
{
    if (x < R && y < C && x >= 0 && y >= 0)
        return true;
    return false;
}
// function to return minimum no of cells to reach
// bottom right cell.
int matrixJump(int M[R][C], int R1, int C1)
{
    queue<pair<int, pair<int, int> > > q;
    // push the no of cells and coordinates in a queue.
    q.push(make_pair(1, make_pair(R1, C1)));
    while (!q.empty()) {
        int x = q.front().second.first; // x coordinate
        int y = q.front().second.second; // y coordinate
        int no_of_cells = q.front().first; // no of cells
        q.pop();
        // when it reaches bottom right return no of cells
        if (x == R - 1 && y == C - 1)           
            return no_of_cells;
        int v = M[x][y];
        if (safe(x + v, y))
            q.push(make_pair(no_of_cells + 1, make_pair(x + v, y)));
        if (safe(x, y + v))
            q.push(make_pair(no_of_cells + 1, make_pair(x, y + v)));
    }
    // when destination cannot be reached
    return -1;
}
// driver function
int main()
{
    int M[R][C] = { { 2, 4, 2 },
                    { 5, 3, 8 },
                    { 1, 1, 1 } };
    cout << matrixJump(M, 0, 0);
    return 0;
}

Output:

 3


Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org