SDE - Intern

You are given an array/list ‘ARR’ of ‘N’ positive integers’. Your task is to find out the size of the smallest subset with the maximum OR possible. That means that among all subsets that have OR of its elements maximum, you need to report the size of the smallest such subset.

For Example :

Input : arr[] = {5, 1, 3, 4, 2}   
Output : 2
7 is the maximum value possible of OR, 
5|2 = 7 and 5|3 = 7

You are given a dictionary ‘D’ consisting of ‘N’ words. Each word of the dictionary is of fixed size ‘L’ and contains only lowercase English alphabets.

Now you have to answer ‘Q’ queries, in each query you are given a word ‘W’ of fixed size ‘L’ but this word can consist of either lowercase English alphabets or ‘?’ (wildcard characters). Where ‘?’ can be matched by any lowercase English alphabet.

For each query find how many words in the dictionary can be matched by the query word ‘W’ by replacing ‘?’(if present) with some lowercase English alphabet.

Example :

If the dictionary is: {"cat", "rat", "bat", "hat"}

And query words are "?at" and "b?t", then:

"?at" => can be matched by all the 4 dictionary words by replacing '?' with 'c', 'r', 'b' or 'h'.

"b?t" => can only be matched by the dictionary word "bat" by replacing '?' with 'a'.  

You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a square matrix of order 'N' * 'N' where the cells with value 0 represent the maze’s blocked locations while value 1 is the open/available path that the rat can take to reach its destination. The rat's destination is at ('N' - 1, 'N' - 1). Your task is to find all the possible paths that the rat can take to reach from source to destination in the maze. The possible directions that it can take to move in the maze are 'U'(up) i.e. (x, y - 1) , 'D'(down) i.e. (x, y + 1) , 'L' (left) i.e. (x - 1, y), 'R' (right) i.e. (x + 1, y).

Note:

Here, sorted paths mean that the expected output should be in alphabetical order.

For Example:

Given a square matrix of size 4*4 (i.e. here 'N' = 4):
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1 
Expected Output:
DDRDRR DRDDRR 
i.e. Path-1: DDRDRR and Path-2: DRDDRR

The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.

Given an adjacency list representation of a directed graph with ‘n’ vertices and ‘m’ edges. Your task is to return a list consisting of Breadth-First Traversal (BFS) starting from vertex 0.

In this traversal, one can move from vertex 'u' to vertex 'v' only if there is an edge from 'u' to 'v'. The BFS traversal should include all nodes directly or indirectly connected to vertex 0.

Note:

The traversal should proceed from left to right according to the input adjacency list.

Example:

Adjacency list: { {1,2,3},{4}, {5}, {},{},{}}

The interpretation of this adjacency list is as follows:
Vertex 0 has directed edges towards vertices 1, 2, and 3.
Vertex 1 has a directed edge towards vertex 4.
Vertex 2 has a directed edge towards vertex 5.
Vertices 3, 4, and 5 have no outgoing edges.

We can also see this in the diagram below.

BFS traversal: 0 1 2 3 4 5