Angry Professor

Problem Statement

The professor is conducting a course on Discrete Mathematics to a class of N students. He is angry at the lack of their discipline, and he decides to cancel the class if there are fewer than K students present after the class starts.

Given the arrival time of each student, your task is to find out if the class gets cancelled or not.

Input Format

The first line of the input contains T, the number of test cases. Each test case contains two lines. The first line of each test case contains two space-separated integers, N and K. The next line contains N space-separated integers, a1,a2,…,aN, representing the arrival time of each student.

If the arrival time of a given student is a non-positive integer (ai≤0), then the student enters before the class starts. If the arrival time of a given student is a positive integer (ai>0), the student enters after the class has started.

Output Format

For each testcase, print "YES" (without quotes) if the class gets cancelled and "NO" (without quotes) otherwise.

Constraints •1≤T≤10 •1≤N≤1000 •1≤K≤N •−100≤ai≤100,where i∈[1,N]

Note If a student enters the class exactly when it starts (ai=0), the student is considered to have entered before the class has started.

Sample Input

2 4 3 -1 -3 4 2 4 2 0 -1 2 1

Sample Output

YES NO

Explanation

For the first test case, K=3, i.e., the professor wants at least 3 students to be in class but there are only 2 who have arrived on time (−3 and −1), hence the class gets cancelled.

For the second test case, K=2, i.e, the professor wants at least 2 students to be in class and there are 2 who have arrived on time (0 and −1), hence the class does not get cancelled.

Extra long factorials

Problem Statement

You are given an integer N. Print the factorial of this number.

N!=N×(N−1)×(N−2)×⋯×3×2×1

Note: Factorials of N>20 can't be stored even in a 64−bit long long variable. Big integers must be used for such calculations. Languages like Java, Python, Ruby etc. can handle big integers but we need to write additional code in C/C++ to handle such large values.

We recommend solving this challenge using BigIntegers.

Input Format Input consists of a single integer N.

Constraints 1≤N≤100

Output Format Output the factorial of N.

Sample Input 25

Sample Output 15511210043330985984000000

Reverse a doubly linked list

Problem Statement

You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head node might be NULL to indicate that the list is empty.

Input Format You have to complete the Node* Reverse(Node* head) method which takes one argument - the head of the doubly linked list. You should NOT read any input from stdin/console.

Output Format Change the next and prev pointers of all the nodes so that the direction of the list is reversed. Then return the head node of the reversed list. Do NOT print anything to stdout/console.

Sample Input

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

Sample Output NULL NULL <-- 6 <--> 4 <--> 2 --> NULL

Explanation 1. Empty list, so nothing to do. 2. 2,4,6 become 6,4,2 o reversing in the given doubly linked list.

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.

Find Merge Point of Two 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-->x-->y-->z

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.

Detect Cycle

Problem Statement

You’re given the pointer to the head node of a linked list. Find whether the list contains any cycle (or loop). A linked list is said to contain cycle if any node is re-visited while traversing the list. The head pointer given may be null meaning that the list is empty.

Input Format You have to complete the int HasCycle(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console. Number of nodes in a linked list doesn't exceed 100.

Output Format Check whether the linked list has a cycle and return 1 if there is a cycle. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input 1 --> NULL

1 --> 2 --> <--3

Sample Output 0 1

Explanation 1. First list has no cycle, hence return 0 2. Second list is shown to have a cycle, hence return 1.

Note After first solving the problem by yourself, see Floyd's cycle-finding algorithm for an efficient solution which uses O(N) time and O(1) additional memory.

Delete duplicate-value nodes from a sorted linked list

Problem Statement

You're given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete as few nodes as possible so that the list does not contain any value more than once. The given head pointer may be null indicating that the list is empty.

For now do not be concerned with the memory deallocation. In common abstract data structure scenarios, deleting an element might also require deallocating the memory occupied by it. For an initial intro to the topic of dynamic memory please consult: http://www.cplusplus.com/doc/tutorial/dynamic/

Input Format You have to complete the Node* RemoveDuplicates(Node* head) method which takes one argument - the head of the sorted linked list. You should NOT read any input from stdin/console.

Output Format Delete as few nodes as possible to ensure that no two nodes have the same data. Adjust the next pointers to ensure that the remaining nodes form a single sorted linked list. Then return the head of the sorted updated linked list. Do NOT print anything to stdout/console.

Sample Input 1 -> 1 -> 3 -> 3 -> 5 -> 6 -> NULL NULL

Sample Output 1 -> 3 -> 5 -> 6 -> NULL NULL

Explanation 1. 1 and 3 are repeated, and are deleted. 2. Empty list remains empty.

Get Node Value

Problem Statement

You’re given the pointer to the head node of a linked list and a specific position. Counting backwards from the tail node of the linked list, get the value of the node at the given position. A position of 0 corresponds to the tail, 1 corresponds to the node before the tail and so on.

Input Format You have to complete the int GetNode(Node* head, int positionFromTail) method which takes two arguments - the head of the linked list and the position of the node from the tail. positionFromTail will be at least 0 and less than the number of nodes in the list. You should NOT read any input from stdin/console.

Output Format Find the node at the given position counting backwards from the tail. Then return the data contained in this node. Do NOT print anything to stdout/console.

Sample Input 1 -> 3 -> 5 -> 6 -> NULL, positionFromTail = 0 1 -> 3 -> 5 -> 6 -> NULL, positionFromTail = 2

Sample Output 6 3

Merge two sorted linked lists

Problem Statement

You’re given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the corresponding list is empty.

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

Output Format Change the next pointer of individual nodes so that nodes from both lists are merged into a single list. Then return the head of this merged list. Do NOT print anything to stdout/console.

Sample Input 1 -> 3 -> 5 -> 6 -> NULL 2 -> 4 -> 7 -> NULL

15 -> NULL 12 -> NULL

NULL 1 -> 2 -> NULL

Sample Output 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 12 -> 15 -> NULL 1 -> 2 -> NULL

Explanation 1. We merge elements in both list in sorted order and output.

Compare two linked lists

Problem Statement

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. The lists are equal only if they have the same number of nodes and corresponding nodes contain the same data. Either head pointer given may be null meaning that the corresponding list is empty.

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

Output Format Compare the two linked lists and return 1 if the lists are equal. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input

NULL, 1 --> NULL 1 --> 2 --> NULL, 1 --> 2 --> NULL

Sample Output 0 1

Explanation 1. We compare an empty list with a list containing 1. They don't match, hence return 0. 2. We have 2 similar lists. Hence return 1.

Reverse a linked list

Problem Statement

You’re given the pointer to the head node of a linked list. Change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.

Input Format You have to complete the Node* Reverse(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console.

Output Format Change the next pointers of the nodes that their order is reversed and return the head of the reversed linked list. Do NOT print anything to stdout/console.

Sample Input

NULL 2 --> 3 --> NULL

Sample Output NULL 3 --> 2 --> NULL

Explanation 1. Empty list remains empty 2. List is reversed from 2,3 to 3,2

Print in Reverse

Problem Statement

You are given the pointer to the head node of a linked list and you need to print all its elements in reverse order from tail to head, one element per line. The head pointer may be null meaning that the list is empty - in that case, do not print anything!

Input Format You have to complete the void ReversePrint(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console.

Output Format Print the elements of the linked list in reverse order to stdout/console (using printf or cout) , one per line.

Sample Input

1 --> 2 --> NULL 2 --> 1 --> 4 --> 5 --> NULL

Sample Output 2 1 5 4 1 2

Explanation 1. First list is printed from tail to head hence 2,1 2. Similarly second list is also printed from tail to head.

Delete a Node

Problem Statement

You’re given the pointer to the head node of a linked list and the position of a node to delete. Delete the node at the given position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The list may become empty after you delete the node.

Input Format You have to complete the Node* Delete(Node* head, int position) method which takes two arguments - the head of the linked list and the position of the node to delete. You should NOT read any input from stdin/console. position will always be at least 0 and less than the number of the elements in the list.

Output Format Delete the node at the given position and return the head of the updated linked list. Do NOT print anything to stdout/console.

Sample Input

1 --> 2 --> 3 --> NULL, position = 0 1 --> NULL , position = 0

Sample Output 2 --> 3 --> NULL NULL

Explanation 1. 0th position is removed, 1 is deleted from the list. 2. Again 0th position is deleted and we are left with empty list.

Insert a node at a specific position in a linked list

Problem Statement

You’re given the pointer to the head node of a linked list, an integer to add to the list and the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

Input Format You have to complete the Node* Insert(Node* head, int data, int position) method which takes three arguments - the head of the linked list, the integer to insert and the position at which the integer must be inserted. You should NOT read any input from stdin/console. position will always be between 0 and the number of the elements in the list (inclusive).

Output Format Insert the new node at the desired position and return the head of the updated linked list. Do NOT print anything to stdout/console.

Sample Input

NULL, data = 3, position = 0 3 --> NULL, data = 4, position = 0

Sample Output 3 --> NULL 4 --> 3 --> NULL

Explanation 1. we have an empty list and position 0. 3 becomes head. 2. 4 is added to position 0, hence 4 becomes head.

Note For the purpose of evaluation the list has been initialised with a node with data=2. Ignore it, this is done to avoid printing empty lists while comparing output.

Insert at head of linkedlist

Problem Statement

You’re given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer, insert this node at the head of the linked list and return the new head node. The head pointer given may be null meaning that the initial list is empty.

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

Output Format Insert the new node at the head and return the head of the updated linked list. Do NOT print anything to stdout/console.

Sample Input

NULL , data = 1 1 --> NULL , data = 2

Sample Output 1 --> NULL 2 --> 1 --> NULL

Explanation 1. We have an empty list, on inserting 1, 1 becomes new head. 2. We have a list with 1 as head, on inserting 2, 2 becomes the new head.

Insert at end of linkedlist

Problem Statement

You’re given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer, insert this node at the tail of the linked list and return the head node. The head pointer given may be null meaning that the initial list is empty.

Input Format

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

Output Format

Insert the new node at the tail and just return the head of the updated linked list. Do NOT print anything to stdout/console.

Sample Input

NULL, data = 2

2 --> NULL, data = 3

Sample Output

2 -->NULL

2 --> 3 --> NULL

Explanation

1. We have an empty list and we insert 2.

2. We have 2 in the tail, when 3 is inserted 3 becomes the tail.

Print linklist data

Problem Statement

If you’re new to working with linked lists, this is a great exercise to get familiar with them. You’re given the pointer to the head node of a linked list and you need to print all its elements in order, one element per line. The head pointer may be null, i.e., it may be an empty list. In that case, don’t print anything!

Input Format

You have to complete the void Print(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually.

Output Format

Print the elements of the linked list to stdout/console (using printf or cout) , one per line.

Sample Input

NULL

1->2->3->NULL

Sample Output

1

2

3

Explanation

For first case, an empty list is passed to the method. So nothing is printed. For second case, all the elements of the linked list (1, 2 and 3) are printed in separate lines.