Queues Assignment
1. Queue Implementation
You are given an array of 'n' elements. Implement these elements in a queue and return
that queue. In Python, you can use from collections import deque.
Input Format:
The first line contains an integer 'n' (1 ≤ n ≤ 10^5), the number of
elements in the array.
The second line contains 'n' space-separated integers (1 ≤ Number to be
pushed ≤ 10^5).
Output Format:
Return the queue with the elements in the same order as they appear in the input
array.
Sample Input 1:
5
1 3 6 9 8
Sample Output 1:
1 3 6 9 8
Explanation:
The elements are enqueued in the same order as they appear in the input array.
Constraints:
1 ≤ n ≤ 10^5
1 ≤ Number to be pushed ≤ 10^5
Note: The function should return the queue.
class Solution {
public Queue<Integer> enqueue(List<Integer> nums) {
//Write your code here;
}
}
2. Queue Functions
You are given an array of integers and another integer 'k'. Your task is to perform the
following operations in the given order:
Implement a queue with integers from the given array.
Remove the first element of the queue.
Print the first element of the queue.
Find if the integer 'k' exists in the queue.
Finally, return the queue.
Input Format:
The first line contains two integers 'n' (the size of the array) and 'k' (the integer
whose existence in the implemented queue has to be checked).
The second line contains 'n' space-separated integers representing the elements of
the array.
Output Format:
Complete the operations and return the output (if it produces an output) of each
operation on a new line.
Sample Input 1:
5 4
1 9 11 3 2
Sample Output 1:
9
No
9 11 3 2
Explanation:
The queue is initialized with the elements [1, 9, 11, 3, 2].
The first element (1) is removed, resulting in the queue [9, 11, 3, 2].
The first element (9) is printed.
The integer '4' is checked for existence in the queue and is not found, so "No" is
printed.
The final state of the queue [9, 11, 3, 2] is returned.
Constraints:
1 ≤ k ≤ 10^6
2 ≤ n ≤ 10^6
1 ≤ ar[i] ≤ 10^6
Note: The function should print the intermediate results and return the final queue as a
list.
class Solution {
public Queue<Integer> solve(Vector<Integer> v, int k) {
//Write your code here
}
}
3. Reverse elements of queue
You are given a queue and an integer 'k'. Your task is to reverse the order of the first 'k'
elements of the queue.
Input Format:
The first line contains two integers 'n' (the size of the array) and 'k' (the number of
elements to be reversed).
The second line contains 'n' space-separated integers representing the elements of
the queue.
Output Format:
Return the updated queue.
Sample Input 1:
5 3
1 2 3 4 5
Sample Output 1:
3 2 1 4 5
Explanation:
The first 3 elements of the queue [1, 2, 3, 4, 5] are reversed to become [3, 2, 1, 4, 5].
Constraints:
1 ≤ k ≤ 10^6
1 ≤ n ≤ 10^6
1 ≤ q[i] ≤ 10^6 (elements of the queue)
Note:The function should return the updated queue.
4. Tour of all Petrol Pump
Suppose there is a circle with N petrol pumps. You will be given two sets of data:
The amount of petrol that each petrol pump has.
The distance from that petrol pump to the next petrol pump.
Find a starting point where the truck can start to get through the complete circle without
exhausting its petrol in between. If no such path exists, return -1.
Note: Assume for 1 liter of petrol, the truck can go 1 unit of distance.
Input Format:
The first line contains an integer 'N' (the number of petrol pumps).
The second line contains 'N' space-separated integers representing the amount of
petrol at each petrol pump.
The third line contains 'N' space-separated integers representing the distance from
each petrol pump to the next petrol pump.
Output Format:
Return the index of the starting petrol pump if a circular tour is possible, otherwise
return -1.
Sample Input 1:
4
4 6 7 4
6 5 3 5
Sample Output 1:
Explanation:
There are 4 petrol pumps with the amount of petrol and distance to the next petrol pump
as follows:
{4, 6}
{6, 5}
{7, 3}
{4, 5}
The first point from where the truck can make a circular tour is the 2nd petrol pump.
Therefore, the output is 1 (index of the 2nd petrol pump).
Sample Input 2:
3
6 3 7
4 6 3
Sample Output 2:
Explanation:
There are 3 petrol pumps with the amount of petrol and distance to the next petrol pump
as follows:
{6, 4}
{3, 6}
{7, 3}
The first point from where the truck can make a circular tour is the 3rd petrol pump.
Therefore, the output is 2 (index of the 3rd petrol pump).
Constraints:
2 ≤ N ≤ 10000
1 ≤ petrol, distance ≤ 1000
Note: The function should return the result.
/*class PetrolPump {
int petrol;
int distance;
PetrolPump(int petrol, int distance) {
[Link] = petrol;
[Link] = distance;
}
}*/
class Solution {
int solve(PetrolPump[] p, int n) {
//Write your code here
}
}
5. First Non Repeating
Given a string str which denotes a stream of characters, your task is to find a new
string output_str. output_str is formed such that we have to find the first non-
repeating character at each instance when a character is inserted into the stream and
append it at the end of output_str. If no such non-repeating character is found, then
append 'X' at the end of output_str.
Input Format:
Only one line which contains a string that needs to be converted to output_str.
Output Format:
Return the updated string.
Sample Input 1:
dabc
Sample Output 1:
dddd
Explanation:
"d" - first non-repeating character 'd'.
"da" - first non-repeating character 'd'.
"dab" - first non-repeating character 'd'.
"dabc" - first non-repeating character 'd'.
Sample Input 2:
bbe
Sample Output 2:
bXe
Explanation:
"b" - first non-repeating character 'b'.
"bb" - no non-repeating character so 'X'.
"bbe" - first non-repeating character 'e'.
Constraints:
(1 <= |str| <= 10^5)
Note: The function should return the result.
class Solution {
public String firstNonRep(String str) {
//Write your code here
}
}