SDE - 1

Problem: Number of triangles in a graph

Given an undirected graph, find how many triangles it can have where a triangle is a cyclic path of length three which begins and end at the same vertex.

An undirected graph is a graph in which if you can go from a vertex, say, ‘A’ to ‘B,’ you can come back to ‘A’ from ‘B.’

For example: In this graph, we can visit from vertex 1 to 2, then we can also visit from vertex 2 to 1. This is true for all vertices.

Take the length(L) and breadth(B) of the rectangle as input and find its area.

Note:

Length and breadth must be an integer value and the area will always be in the range of integers.

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 long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Example:

Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

There are 25 horses among which you need to find out the fastest 3 horses. You can conduct a race among at most 5 to find out their relative speed. At no point, you can find out the actual speed of the horse in a race. Find out the minimum no. of races that are required to get the top 3 horses.

Design a system to generate tombola game tickets following design principles, ticket is a matrix of 5X9 with some constrained, system to generate such kind of ticket.

Given an input string 'S' and a pattern 'P', implement a regular expression matching with the support of two special characters ‘.’ (dot) and ‘*’(asterisk) where

1. ‘.’ matches to any single character.
2. ‘*’ matches to zero or more of the preceding element.

If the input string 'S' matches the pattern 'P', then return true else, return false.

Note:

1. You have to match the entire string with the pattern given.

2. Both the strings, 'S' and 'P' contain only lower-case alphabets.

3. Only the pattern will contain additional characters ‘*’ and ‘.’ along with alphabets.

What are multi-threading and concurrency?