Smallest window in a string containing all the characters of another string

Given a string and text output the smallest window in the string which covers all the characters present in the text. Both the string and text contains small case letters.
If such window doesn`t exist or this task can not be done then print -1.

Input:
First line contains T , the number of test cases and each test contains 2 lines having a string each  and  ( n is the main string and x is the text )

Output:
Output the smallest window of the string containing all the characters of the text.

Constraints:
1<=T<=100
1<=N,X<=1000

Example:
Input:
2

timetopractice
toc
zoomlazapzo
oza

Output:
toprac
apzo

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

[Phone directory]

Given a list of contacts which exist in a phone directory. The task is to implement search query for the phone directory. The search query on a string ‘str’ displays all the contacts which prefix as ‘str’. One special property of the search function is that, when a user searches for a contact from the contact list then suggestions (Contacts with prefix as the string entered so for) are shown after user enters each character.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains three lines. First line of each test case contains N i.e., number of contacts. Second line contains space separated all the contacts in the form of string. And third line contains query string.

Output
For each test case, print the query results in new line. If there is no match between query and contacts, print “0”.

Constraints:
1<=T<=100
1<=N<=50
1<=|contact[i].length|<=50
1<=|query length|<=6

Example:
Input:
1
3
geeikistest geeksforgeeks geeksfortest
geeips

Output:

geeikistest geeksforgeeks geeksfortest
geeikistest geeksforgeeks geeksfortest
geeikistest geeksforgeeks geeksfortest
geeikistest
0
0
Explanation:

By running the query on contact list, we get,
Suggestions based on "g" are:
geeikistest geeksforgeeks geeksfortest
Suggestions based on "ge" are:
geeikistest geeksforgeeks geeksfortest
Suggestions based on "gee" are:
geeikistest geeksforgeeks geeksfortest
Suggestions based on "geei" are:
geeikistest
No Results Found for "geeip", So print "0".
No Results Found for "geeips", So print "0".

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

Check whether right angled triangle is valid or not for large sides

Given three integers a, b and c as triplets. Check if it is possible to make right angled triangle or not. Print Yes if possible, else No. 10-18 <= a, b, c <= 1018

Input: 3 4 5
Output: Yes
Explanation:
Since 3*3 + 4*4 = 5*5
Hence print "Yes"

Input: 8 5 13
Since 8 + 5 < 13 which violates the property of
triangle. Hence print "No"

For a right angled triangle to be valid it must satisfies the following criteria:-

  1. a, b and c should be greater then 0.
  2. Sum of any two sides of triangle must be greater than the third side.
  3. Pythagorean Theorem i.e., a2 + b2 = c2.

First two conditions can be easily checked but for third condition we have to take care of overflow. Since a, b and c can be large so we can’t compare them directly unless we use python or BigInteger library in Java. For languages like C and C++, we have to reduce the expression in fraction form.
 \implies a^2 + b^2 = c^2  \implies a^2 = c^2 - b^2  \implies \dfrac{a}{c-b}=\dfrac{c+b}{a}
Before comparing the fraction we need convert them in simplified form by dividing the numerator and denominator by gcd of both of them. Now compare both numerator and denominator of both the fractions of LHS and RHS such that if both would be same then it signifies the valid right angled triangle otherwise not.

// C++ program to check validity of triplets
#include <bits/stdc++.h>
using namespace std;
// Function to check pythagorean triplets
bool Triplets(long long a, long long b, long long c)
{
    if (a <= 0 || b <= 0 || c <= 0)
        return false;
    vector<long long> vec{ a, b, c };
    sort(vec.begin(), vec.end());
    // Re-initialize a, b, c in ascending order
    a = vec[0], b = vec[1], c = vec[2];
    // Check validation of sides of triangle
    if (a + b <= c)
        return false;
    long long p1 = a, p2 = c - b;
    // Reduce fraction to simplified form
    long long div = __gcd(p1, p2);
    p1 /= div, p2 /= div;
    long long q1 = c + b, q2 = a;
    // Reduce fraction to simplified form
    div = __gcd(q1, q2);
    q1 /= div, q2 /= div;
    // If fraction are equal return
    // 'true' else 'false'
    return (p1 == q1 && p2 == q2);
}
// Function that will return 'Yes' or 'No'
// according to the correction of triplets
string checkTriplet(long long a, long long b, long long c)
{
    if (Triplets(a, b, c))
        return "Yes";
    else
        return "No";
}
// Driver code
int main()
{
    long long a = 4, b = 3, c = 5;
    cout << checkTriplet(a, b, c) << endl;
    a = 8, b = 13, c = 5;
    cout << checkTriplet(a, b, c) << endl;
    a = 1200000000000, b = 1600000000000,
    c = 2000000000000;
    cout << checkTriplet(a, b, c) << endl;
    return 0;
}
Output:
Yes
No
Yes

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

Mail System Design

Hattori is very much inspired by the way GMAIL works. He decides to build his own simple version of GMAIL. He divides the mails into 3 categories ,namely : UNREAD , READ and TRASH.
UNREAD:the messages that haven’t been read.
READ:The messages that is read by the user.
TRASH: The messages deleted by the user.
Now, At any point of time, The user can READ an UNREAD message , Move an UNREAD message to TRASH , Move a READ message to TRASH or restore a deleted message back to READ category. Now , Hattori requires your help in determining the messages left in all the categories aligned in the order of their arrival in that category.
Formally: You are given N messages , with ID from 1 to N. Initially all the messages are in the UNREAD section of the mail.Now, Q queries are given in the form as shown below:
1 X : Move the message with ID X from UNREAD to READ.
2 X : Move the message with ID X from READ to TRASH.
3 X : Move the message with ID X from UNREAD to TRASH.
4 X : Move the message with ID X from TRASH to READ.
Given that all the queries are valid, Help Hattori in Determining the messages in all the 3 sections.

Input:
First line contains the number of test cases. First line of each test case contains two space separated values N and Q respectively. Second line contains 2*Q integers each either of the form as described above.

Output:
First line contains all the space seperated message ID’S left in the UNREAD section.
Second line contains all the space seperated message ID’S left in the READ section.
Third line contains all the space seperated message ID’S left in the TRASH section.
NOTE: In case, any section is empty , print “EMPTY” for that section without double quotes.

Constraints:
1<=T<=20
1<=N<=5000
1<=Q<=10^6

Example:
Input:

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

Explaination:
Initial UNREAD section: 1->2->3->4->5->6->7->8->9->10
READ section : EMPTY
TRASH section : Empty
Query 1 : 1 2
UNREAD section: 1->3->4->5->6->7->8->9->10
READ section : 2
TRASH section : Empty
Query 2 : 1 5
UNREAD section: 1->3->4->6->7->8->9->10
READ section : 2->5
TRASH section : Empty
Query 3 : 1 7
UNREAD section: 1->3->4->6->8->9->10
READ section : 2->5->7
TRASH section : Empty
Query 4 : 1 9
UNREAD section: 1->3->4->6->8->10
READ section : 2->5->7->9
TRASH section : Empty
Query 5 : 2 5
UNREAD section: 1->3->4->6->8->10
READ section : 2->7->9
TRASH section : 5
Query 6 : 2 7
UNREAD section: 1->3->4->6->8->10
READ section : 2->9
TRASH section : 5->7
Query 7 : 4 5
UNREAD section: 1->3->4->6->8->10
READ section : 2->9->5
TRASH section : 7

**For More Examples Use Expected Output**

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

Primitive Typing

Given a screen containing alphabets from a-z, we can go from one character to another character using a remote. The remote contains left, right, top and bottom keys.

Remote :
Control buttons

Find the shortest possible path to type all characters of given string using the remote. The initial position is top left and all characters of input string should be printed in order. Print the total number of moves in such a path(Move UP, DOWN, LEFT, RIGHT). Pressing OK also accounts for one move.

Screen:

a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z

Input:
The first line contains an integer T which is the number of test cases. Each test case contains a string s.

Output:
Print the number of minimum moves required to print the string s.

Constraints:
1<=T<=100
1<=|s|<=100

Example:
Input:

2
cozy
a

Output:
24
9

**For More Examples Use Expected Output**

Firing employees

Mr. Alfred is the founder of FooLand Constructions. He always maintains a ‘Black list’ of potential employees which can be fired at any moment without any prior notice.

This company has N employees (including Mr. Alfred), and each employee is assigned a rank (1 <= rank <= N) at the time of joining the company. Any person can have any rank from 1 to N. No two persons have the same rank. The company has a hierarchically organized management. Each employee has one immediate senior but can have any number of seniors. If a person A is the senior of B and B is senior of C, this implies that A is also a senior of C. Note that Mr. Alfred has no senior to him.

Mr. Alfred has a strange and unfair way of evaluating an employee’s performance. Those employees the sum of whose rank and the number of his/her seniors is a prime number is put up on the ‘Black list’.

You are required to find out the number of ‘Black listed’ employees.

Note: The list won’t contain Mr. Alfred’s name as he is the founder of the company and the list is managed by him!

 

Input:

The first line of input consists of a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. The first line contains a single integer N as described in the problem statement. The next line contains N integers. The ith integer (1 <= i <= N) represents the rank of the immediate senior of the ith employee (i.e. the employee with rank = i). If the ith integer is 0, it represents that employee with rank = i is Mr. Alfred as he has no superior.
Output:

For each test case, print in a new line the number of ‘Black listed’ employees.
Constraints:

1 <= T <= 10^3

1 <= N <= 10^5

 

Example:

Input:

2

4

0 1 1 2

3

2 3 0

Output:

1

2

Explanation:

For 1st case:

The employee with rank 1 is Mr. Alfred.

The employee with rank 2 and rank 3 have Mr. Alfred as their senior.

2 + 1 = 3 is a prime and 3 + 1 = 4 is not a prime.

The employee with rank 4 has Employee 2 as its immediate senior. Hence, number of seniors of Employee 4 = 2 (i.e. employee 2 and Mr. Alfred)

4 + 2 = 6 is not a prime.

Hence, the result is 1.

For 2nd case:

Employee 3 is Mr. Alfred.

Employee 2 is Mr. Alfred’s immediate subordinate. His level is 1.

2 + 1 = 3 is a prime.

Employee 1 is Employee 2’s immediate subordinate. His level is 2.

1 + 2 = 3 is a prime.

Hence, the result is 2.

**For More Examples Use Expected Output**

Page Faults in LRU

In operating systems that use paging for memory management, page replacement algorithm are needed to decide which page needs to be replaced when new page comes in. Whenever a new page is referred and is not present in memory, page fault occurs and Operating System replaces one of the existing pages with newly needed page.
Given a sequence of pages and memory capacity, your task is to find the number of page faluts using Least Recently Used (LRU) Algorithm .

Input:
The first line of input contains an integer T denoting the number of test cases. Each test case contains number of pages n and next line contains space seaprated sequence of pages. The following line consist of the capacity of the memory.

Output:
Output the number of page faults.

Constraints:
1<=T<=100
1<=n<=1000
4<=capacity<=100

Example:
Input:
2
9
5 0 1 3 2 4 1 0 5
4
8
3 1 0 2 5 4 1 2
4
Output:
8
7

**For More Examples Use Expected Output**

K’th smallest element

Given an array and a number k where k is smaller than size of array, the task is to find the k’th smallest element in the given array. It is given that all array elements are distinct.

Input:

First Line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of three lines. First line of each test case contains an integer N denoting size of the array. Second line contains N space separated integer denoting elements of the array. Third line of the test case contains an integer K.

Output:

Corresponding to each test case, print the desired output in a new line.

Constraints:

1<=T<=200
1<=N<=1000
K

Expected Time Complexity: O(n)

Example:

INPUT
2
6
7 10 4 3 20 15
3
5
7 10 4 20 15
4

Output:

7
15

**For More Examples Use Expected Output**

Minimum insertions to sort an array

Given an array of integer numbers, we need to sort this array in a minimum number of steps where in one step we can insert any array element from its position to any other position.

 

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer N denoting the size of array A.

The second line of each test case contains N space separated integers denoting elements of the array A[ ].
Output:

Output the minimum steps needed to sort the array. Print the answer for each test case in a new line.
Constraints:

1<= T <=100

1<= N <=1000

1<= A[ ] <=1000
Example:

Input:

1

7

2 3 5 1 4 7 6

Output:

3

**For More Examples Use Expected Output**

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

In First But Second

Given two arrays, the task is that we find numbers which are present in the first array, but not present in the second array.

Input:
The first line of input contains an integer T denoting the number of test cases. Each test case contains space separated integers n and m which denotes the number of elements in the array a[] and b[]. Next two line contains space separated n and m elements in the array a[] and b[] respectively.

Output:
Print space separated numbers present in the first array but not in the second.

Constraints:
1<=T<=100
1<=n,m<=1000
1<=a[i],b[i]<=1000​

Example:
Input:

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

Output:
4 10
5

**For More Examples Use Expected Output**

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