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.