SDE - Intern

You are given an array 'ARR' of size 'N' containing positive integers. Consider an undirected graph using the given array with the following conditions:

-> The graph consists of 'N' vertices.
-> The ith vertex has a value 'ARR[i]'.
-> There is an edge between two vertices 'i' and 'j' (where 'i' < 'j'), if and only if GCD('ARR[i]', 'ARR[j]') is greater than 1.

GCD(a, b) is the maximum number x such that both a and b are divisible by x.

Your task is to find the size of the largest component in the graph.

A component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the rest of the graph. The size of a component is the number of vertices in it.

Given a 2-dimensional matrix of size ‘N’ x ‘M’ and an integer K. Find the size of the largest square sub-matrix whose sum is less than or equal to K. The size of a matrix is the product of rows and columns in it.

A sub-matrix is a matrix obtained from the given matrix by deletion of several (possibly, zero or all) rows/columns from the beginning and several (possibly, zero or all) rows/columns from the end. A square matrix is a matrix which has the same number of rows and columns.

For Example

Note

If there is no square sub-matrix with a sum less than or equal to K, then return 0.

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

Given a string ‘strNum’ which represents a number, your task is to find the ways to decode the given string ‘strNum’.

The format of encoding is as follows: ‘A’ - 1, ‘B’ - 2, ‘C’ - 3, ‘D’ - 4, ……………, ‘Z’ - 26.

Encoding is possible in letters from ‘A’ to ‘Z’. There is an encoding between character and number.

Example :

‘n = 226’ so we can decode ‘226’ in such a way-

‘BZ = 2-26’, as B maps to 2 and Z maps to 26.

‘BBF = 2-2-6’

‘VF = 22-6’

‘226; can be decoded in three ‘BZ’, ‘BBF’, ‘VF’ possible ways.

Point to be noticed we can’t decode ‘226’ as ‘226’ because we have no character which can directly map with ‘226’ we can only decode numbers from ‘1’ to ‘26’ only.

You have been given a string 'S' which only consists of lowercase English-Alphabet letters.

Your task is to find the shortest(minimum length) substring of 'S' which contains all the characters of 'S' at least once. If there are many substrings with the shortest length, then find one which appears earlier in the string i.e. substring whose starting index is lowest.

For example-

If the given string is S = "abcba", then the possible substrings are "abc" and "cba". As "abc" starts with a lower index (i.e. 0, "cba" start with index 2), we will print "abc" as our shortest substring that contains all characters of 'S'.

Tell me something not there in your resume.