SDE - 1

You are given a string ‘str’.

Find the longest prefix in the string which is also a suffix of the string, excluding the string itself.

If there's no such string return an empty string "".

Example:

Input: ‘str’ = ‘ababcdabab’ 

Output: 'abab'

Explanation:
Here the prefix ‘abab’ is equal to the suffix ‘abab’. The length of the prefix is 4. There's no other prefix that has length > 4 and is also present as a suffix. Hence the answer is 'abab'. 

You are given a 2D matrix ‘ARR’ of size ‘N x 3’ having integers, where ‘N’ is the number of rows.

Your task is to find the smallest sum possible while taking one element from each row.

The rules for selecting elements are as follows-

1. In a row, after selecting an element at a given position, you cannot select the element directly below it
2. You can only select elements that are not directly below the previously selected element.

You are given two arrays “initial” and “final”. All the elements in the array “initial” are zero initially. And all the elements of the array “final” are positive integers.

You have to find the minimum number of operations to convert the “initial” array into the “final” array using the following operation:

1. In one operation, you can select any contiguous subsequence of the “initial” array and increment each value by 1.

Note :

A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. If S is {5, 15, -30, 10, -5, 40, 10} then 15, -30, 10 is a contiguous subsequence.

You have been given an array/list ‘ARR’ of integers consisting of ‘N' integers. You need to rearrange ‘ARR’ so that no two adjacent elements are equal. You may return any valid rearrangement and it is guaranteed the answer exists.

Example :

Let’s say you have an array/list ‘ARR = [1,1,2,2]’. 

Then a valid rearrangement can be [1,2,1,2] or [2,1,2,1] such that no two adjacent elements are equal. [2,1,1,2] is an invalid arrangement because two adjacent elements are equal.

You have been given a graph consisting of ‘N’ vertices numbered from 1 to ‘N’. The graph has ‘M’ edges. In an operation, you can shift an edge between two directly connected vertices to between pair of disconnected vertices to make them directly connected. Return the minimum number of operations to make the graph connected. If it is not possible to make graph connected return -1.

Example:

Let’s say ‘N’ is 4 and ‘M' is 3. The 3 edges are (1,2), (2,3) and (1,3). Then our graph will look as follows:-

To make the graph connected we can shift the edge between (1,3) to (1,4). This operation will make the graph connected. There are multiple ways in which we can make graph connected. So, in this case, we can make graph connected in just one operation.

Note:

1. A connected graph is a graph that is connected in the sense of a topological space, i.e., there is a path from any vertex to any other vertex in the graph.

2. There are no repeated edges and self-loops in the graph.

3. You do not need to print anything; it has already been taken care of. Just implement the function.

1- What is the biggest challenge you’ve faced in your current position?
2- How would your coworkers describe you?
3- What skills would you bring to the job?
4- Tell me about yourself?