SDE - 1

You have been given an Encrypted String where repetitions of substrings are represented as substring followed by the count of substrings.

Example: String "aabbbcdcdcd" will be encrypted as "a2b3cd3".

You need to find the 'K'th character of Decrypted String. Decrypted String would have 1-based indexing.

Note :

Input string will always be lowercase characters without any spaces.

If the count of a substring is 1 then also it will be followed by Integer '1'.
Example: "aabcdee" will be Encrypted as "a2bcd1e2"
This means it's guaranteed that each substring is followed by some Integer.

Also, the frequency of encrypted substring can be of more than one digit. For example, in "ab12c3", ab is repeated 12 times. No leading 0 is present in the frequency of substring.

The frequency of a repeated substring can also be in parts.
Example: "aaaabbbb" can also have "a2a2b3b1" as Encrypted String.

You have been given an undirected graph with 'N' vertices and 'M' edges. The vertices are labelled from 1 to 'N'.

Your task is to find if the graph contains a cycle or not.

A path that starts from a given vertex and ends at the same vertex traversing the edges only once is called a cycle.

Example :

In the below graph, there exists a cycle between vertex 1, 2 and 3. 

Note:

1. There are no parallel edges between two vertices.

2. There are no self-loops(an edge connecting the vertex to itself) in the graph.

3. The graph can be disconnected.

For Example :

Input: N = 3 , Edges =  [[1, 2], [2, 3], [1, 3]].
Output: Yes

Explanation : There are a total of 3 vertices in the graph. There is an edge between vertex 1 and 2, vertex 2 and 3 and vertex 1 and 3. So, there exists a cycle in the graph. 

You are given an array/list ‘ARR’ consisting of ‘N’ distinct integers arranged in ascending order. You are also given an integer ‘TARGET’. Your task is to count all the distinct pairs in ‘ARR’ such that their sum is equal to ‘TARGET’.

Note:

1. Pair (x,y) and Pair(y,x) are considered as the same pair. 

2. If there exists no such pair with sum equals to 'TARGET', then return -1.

Example:

Let ‘ARR’ = [1 2 3] and ‘TARGET’ = 4. Then, there exists only one pair in ‘ARR’ with a sum of 4 which is (1, 3). (1, 3) and (3, 1) are counted as only one pair.

You are given a number 'N' in the form of a string 'S', which is a palindrome. You need to find the greatest number strictly less than 'N' which is also a palindrome.

Note:

1. A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as madam, racecar, 1234321, etc.
2. The numerical value of the given string S will be greater than 0.
3. A single-digit number is also considered a palindrome.
4. The answer number should not contain any leading zeros, except for the case when the answer is 0.
5. Note that the length of the string is nothing but the number of digits in N.

You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters. A common subsequence of two Strings is a subsequence that is common to both Strings.

You have been given a binary tree of integers. Your task is to print the boundary nodes of this binary tree in an Anti-Clockwise direction starting from the root node.

NOTE: The boundary nodes of a binary tree include nodes from the left boundary, right boundary and the leaf nodes without duplicate nodes. However, the values from the nodes may contain duplicates.

For Example:

You have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.

Note :

Try to solve the problem in 'Single Scan'. ' Single Scan' refers to iterating over the array/list just once or to put it in other words, you will be visiting each element in the array/list just once.

Where do you see yourself in 5 years?

What are your weaknesses?