SDE - 1

You are a data analyst working with a numerical sequence A of length n. A sequence is considered "beautiful" if the greatest common divisor (GCD) of all its elements is greater than 1.

To transform a sequence, you can perform a special operation:

- Choose an index i (where 1 <= i < n).
- Replace the two adjacent elements A[i] and A[i+1] with A[i] - A[i+1] and A[i] + A[i+1], respectively.

Your task is to find the minimum number of operations required to make the sequence A beautiful. If the sequence is already beautiful, no operations are needed.

You are given an undirected graph as an adjacency matrix consisting of 'v' vertices and an integer 'm'.

You need to return 'YES' if you can color the graph using at most 'm' colors so that no two adjacent vertices are the same. Else, return 'NO'.

For example:

Input:
If the given adjacency matrix is:
[0 1 0]
[1 0 1]
[0 1 0] and 'm' = 3.

Output: YES

Explanation:
The given adjacency matrix tells us that 1 is connected to 2 and 2 is connected to 3. We can use three different colors and color all three nodes.
Hence we return true.

The N Queens puzzle is the problem of placing N chess queens on an N * N chessboard such that no two queens attack each other.

Given an integer ‘N’, print all distinct solutions to the ‘N’ queen puzzle.

Two queens on the same chessboard can attack each other if any of the below condition satisfies:  
1. They share a row. 
2. They share a column. 
3. They share a diagonal. 

You are given a string digits containing only the digits '0' through '9', and an integer target. Your task is to find all possible ways to insert the binary operators +, -, or * between the digits to form expressions that evaluate to the target value.

Rules for forming expressions:

1) Operators are placed between digits.
2) Operands (the numbers in the expression) can be formed by concatenating multiple digits. For example, in "123", you can form the operand 12.
3) Operands cannot have leading zeros, unless the number is 0 itself. For example, "105" can form 10, but "05" is invalid.

You need to return a list of all unique strings that represent these valid expressions.

Ninja is stuck in a maze which is in a form of a binary tree. He needs your help in order to get out.

Ninja is presently at the node ‘X’. The only exit points of the maze are the leaf nodes of the tree. You need to tell him the distance to the nearest exit point from his current location. This will help him decide which path he should take in order to escape from the maze.

Example:

Suppose, Ninja is stuck at node 62. The possible exit points in the maze are: 40, 10, and 20. From all the possible exit points the closest ones are 10 and 20 which are at a distance of 1 unit.

You are given two strings ‘s1’ and ‘s2’.

Return the longest common subsequence of these strings.

If there’s no such string, return an empty string. If there are multiple possible answers, return any such string.

Note:

Longest common subsequence of string ‘s1’ and ‘s2’ is the longest subsequence of ‘s1’ that is also a subsequence of ‘s2’. A ‘subsequence’ of ‘s1’ is a string that can be formed by deleting one or more (possibly zero) characters from ‘s1’.

Example:

Input: ‘s1’  = “abcab”, ‘s2’ = “cbab”

Output: “bab”

Explanation:
“bab” is one valid longest subsequence present in both strings ‘s1’ , ‘s2’.

You have given a URL id – 'N' consisting of only digits. Your task is to generate a short URL for the given URL id.

To generate a short URL, you need to convert the given URL id to 62 base number where digits of the number are:[“0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ”] i.e “0” corresponds to 0, “a” corresponds to 10, “Z” corresponds to 61, and “10” corresponds to 62, “11” corresponds to 63, and so on….

Follow Up:

Can you solve this in logarithmic time and space complexity?