SDE - 1

You are given the head node of a singly linked list 'head'. Your task is to modify the linked list in such a way that all the even valued nodes appear before the all odd valued node and order of nodes remain the same.

Example :-

The given singly linked list is  6 -> 5 -> 3 -> 4 -> 7 -> 1 -> 2 

The modified linked list should have all even values in starting and odd values in the end.

Given an adjacency list representation of a directed graph with ‘n’ vertices and ‘m’ edges. Your task is to return a list consisting of Breadth-First Traversal (BFS) starting from vertex 0.

In this traversal, one can move from vertex 'u' to vertex 'v' only if there is an edge from 'u' to 'v'. The BFS traversal should include all nodes directly or indirectly connected to vertex 0.

Note:

The traversal should proceed from left to right according to the input adjacency list.

Example:

Adjacency list: { {1,2,3},{4}, {5}, {},{},{}}

The interpretation of this adjacency list is as follows:
Vertex 0 has directed edges towards vertices 1, 2, and 3.
Vertex 1 has a directed edge towards vertex 4.
Vertex 2 has a directed edge towards vertex 5.
Vertices 3, 4, and 5 have no outgoing edges.

We can also see this in the diagram below.

BFS traversal: 0 1 2 3 4 5

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

You are given an undirected graph with N nodes in the form of an adjacency matrix. You are also given an integer M.

Your task is to find if you can color the vertices of the graph using at most M colors such that no two adjacent vertices are of the same color.

For example:

If the given adjacency matrix is:
[0 1 0]
[1 0 1]
[0 1 0] and M = 3.

The given adjacency matrix tells us that node 1 is connected to node 2 and node 2 is connected to node 3. 

So if we color vertex 1 with ‘red’, vertex 2 with ‘blue’, and vertex 3 with ‘red’, it is possible to color the given graph with two colors which is less than or equal to M.

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

 HR told to introduce myself and then asked about my internship experience and projects.