SDE - 1

There were a total of 19 MCQs.

Topics: Trees(5), semaphores(3), deadlocks(5) and algorithms(6)

Check if two strings are anagram or not.

Given a number n, find the smallest number that has same set of digits as n and is greater than n. If n is the greatest possible number with its set of digits, then print “not possible”.

Examples:

For simplicity of implementation, we have considered input number as a string.

Input:  n = "218765"

Output: "251678"

Input:  n = "1234"

Output: "1243"

Input: n = "4321"

Output: "Not Possible"

Input: n = "534976"

Output: "536479"

Given a sequence of moves for a robot, check if the sequence is circular or not. A sequence of moves is circular if first and last positions of robot are same. A move can be on of the following.

 G - Go one unit

 L - Turn left

 R - Turn right  

Examples:

Input: path[] = "GLGLGLG"

Output: Given sequence of moves is circular  

Input: path[] = "GLLG"

Output: Given sequence of moves is circular

Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island. For example, the below matrix contains 5 islands

Example:

Input : mat[][] = {{1, 1, 0, 0, 0},

                  {0, 1, 0, 0, 1},

                  {1, 0, 0, 1, 1},

                  {0, 0, 0, 0, 0},

                  {1, 0, 1, 0, 1}  

Output : 5

This is a variation of the standard problem: “Counting the number of connected components in an undirected graph”.

Before we go to the problem, let us understand what is a connected component. A connected component of an undirected graph is a subgraph in which every two vertices are connected to each other by a path(s), and which is connected to no other vertices outside the subgraph.

For example, the graph shown below has three connected components.

Reverse stack using recursion.

Given a Binary Tree, Print the corner nodes at each level. The node at the leftmost and the node at the rightmost.

For example, output for following is 15, 10, 20, 8, 25.