SDE - 1

The gardener wants to water the garden by opening the minimum number of taps. The garden is one-dimensional along the x-axis of length N i.e. the garden starts from point 0 and ends at point N. There are N + 1 tap located at points [0, 1, 2, …, N] in the garden.

You are given an integer N, and an array named “ranges” of size N + 1(0-indexed). The ith tap, if opened, can water the gardener from point (i - ranges[i]) to (i + ranges[i]) including both. The task is to find the minimum number of taps that should be open to water the whole garden, return -1 if the garden can not be watered.

Example :

Follow Up:

Can you solve the problem in O(N) time?

Given an undirected and disconnected graph G(V, E), containing 'V' vertices and 'E' edges, the information about edges is given using 'GRAPH' matrix, where i-th edge is between GRAPH[i][0] and GRAPH[i][1]. print its DFS traversal.

V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 

E is the number of edges present in graph G.

Note :

The Graph may not be connected i.e there may exist multiple components in a graph.

Given an integer array 'ARR' of size 'N' and an integer 'K', return all the subsets of 'ARR' which sum to 'K'.

Subset of an array 'ARR' is a tuple that can be obtained from 'ARR' by removing some (possibly all) elements of 'ARR'.

Note :

The order of subsets is not important. 

The order of elements in a particular subset should be in increasing order of the index.

You are given a string 'S'. Your task is to partition 'S' such that every substring of the partition is a palindrome. You need to return all possible palindrome partitioning of 'S'.

Note: A substring is a contiguous segment of a string.

For Example:

For a given string “BaaB”
3 possible palindrome partitioning of the given string are:
{“B”, “a”, “a”, “B”}
{“B”, “aa”, “B”}
{“BaaB”}
Every substring of all the above partitions of “BaaB” is a palindrome.

Implement a queue data structure which follows FIFO(First In First Out) property, using only the instances of the stack data structure.

Note:

1. To implement means you need to complete some predefined functions, which are supported by a normal queue such that it can efficiently handle the given input queries which are defined below.


2. The implemented queue must support the following operations of a normal queue: 

a. enQueue(data) : This function should take one argument of type integer and place the integer to the back of the queue.

b. deQueue(): This function should remove an integer from the front of the queue and also return that integer. If the queue is empty, it should return -1.

c. peek(): This function returns the element present in the front of the queue. If the queue is empty, it should return -1.

d. isEmpty(): This function should return true if the queue is empty and false otherwise.


3. You will be given q queries of 4 types:

a. 1 val - For this type of query, you need to insert the integer val to the back of the queue.

b. 2 - For this type of query, you need to remove the element from the front of the queue, and also return it.

c. 3 - For this type of query, you need to return the element present at the front of the queue(No need to remove it from the queue).

d. 4 - For this type of query, you need to return true if the queue is empty and false otherwise.


4. For every query of type:

a. 1, you do not need to return anything.

b. 2, return the integer being deQueued from the queue.

c. 3, return the integer present in the front of the queue.

d. 4, return “true” if the queue is empty, “false” otherwise.

Example

Operations: 
1 5
1 10
2
3
4

Enqueue operation 1 5: We insert 5 at the back of the queue.
Queue: [5]

Enqueue operation 1 10: We insert 10 at the back of the queue.
Queue: [5, 10]

Dequeue operation 2: We remove the element from the front of the queue, which is 5, and print it.
Output: 5
Queue: [10]

Peek operation 3: We return the element present at the front of the queue, which is 10, without removing it.
Output: 10
Queue: [10]

IsEmpty operation 4: We check if the queue is empty.
Output: False
Queue: [10]