SDE - Intern

Given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges . Your task is to check whether the graph is bipartite or not.

A bipartite graph is a graph whose vertices can be divided into two sets such that each edge of the graph connects one vertex from the first set and another vertex from the second set.
We can also define a bipartite graph as a graph which can be colored using two colors such that no two adjacent vertices have the same color. 

For example: 
Input: 
4 4
0 1
0 2
1 3
2 3

An undirected graph to the above input is shown below:

In the given input, the number of vertices is 4, and the number of edges is 4.
In the input, following the number of vertices and edges, a list of pairs of numbers is given where each pair (u, v) denotes an edge between vertex u and v.
As per the input, there is an edge between vertex 0 and vertex 1.
The vertices 0 and 2 have an edge between them.

The vertices 1 and 3 have an edge between them.
The vertices 2 and 3 have an edge between them.

As the graph can be colored using two colors, and no adjacent vertices share the same color, the graph is bipartite. 

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 are given an array 'ARR' of integers having 'N' elements. Your task is to convert the input array into a min-Binary Heap.

A min-Binary heap is a complete binary tree in which the value of each internal node is smaller than or equal to the values of the children of that node.

Note :

1. Input array follows 0 - based indexing. 

2. After constructing the min-heap, the Left child of the 'i-th' node should be present at the (2*i + 1)-th index if it exists.

3. After constructing the min-heap, the Right child of the 'i-th' node should be present at the (2*i + 2)-th index if it exists.

4. Note that you do not need to create a tree, just update the array.

Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if the wildcard pattern is matched with the text. The matching should cover the entire text not partial text.

The wildcard pattern can include the characters ‘?’ and ‘*’

 ‘?’ – matches any single character 
 ‘*’ – Matches any sequence of characters(sequence can be of length 0 or more)

You have been given a Binary Tree of 'n' nodes, where the nodes have integer values

Print the left view of the binary tree.

Example :

If the input tree is as depicted in the picture: 

The Left View of the tree will be:  2 35 2 

- 3 way handshake
- Socket
- OOS -> thread / parallel execution