SDE - 1

You are given an array 'arr' of length 'n', consisting of integers.

A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning and 0 or more integers from the end of an array.

Find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.

The sum of an empty subarray is 0.

Example :

Input: 'arr' = [1, 2, 7, -4, 3, 2, -10, 9, 1]

Output: 11

Explanation: The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].

You have been given two strings “str1” and “str2”. You have to find the length of the longest common substring.

A string “s1” is a substring of another string “s2” if “s2” contains the same characters as in “s1”, in the same order and in continuous fashion also.

For example :

If “str1” = “abcjklp” and “str2” = “acjkp”  then the output will be 3.

Explanation : The longest common substring is “cjk” which is of length 3.

A thief is robbing a store and can carry a maximum weight of ‘W’ into his knapsack. There are 'N' items available in the store and the weight and value of each item is known to the thief. Considering the constraints of the maximum weight that a knapsack can carry, you have to find the maximum profit that a thief can generate by stealing items.

Note: The thief is not allowed to break the items.

For example, N = 4, W = 10 and the weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. Then the best way to fill the knapsack is to choose items with weight 6, 1 and 3. The total value of knapsack = 3 + 6 + 4 = 13.

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

You are given a connected, undirected and acyclic graph with some of the nodes as marked and a positive number 'K'. You need to return the count of all such nodes which have a distance from all marked nodes less than 'K', which means every node whose distance from all marked nodes is less than 'K', should be counted in the result.

A graph is said to be connected if there is a path between every pair of vertex, i.e., from every vertex to any other vertex, there should be some path to traverse and acyclic means that the graph does not contain cycle and undirected means that the edge is bidirectional and one can move in both directions.

Example:

Marked Nodes are Circled with red colour.

Now consider this example of the graph. Here nodes 1,2, and 4 are marked, and let us take the value of K as 3, i.e., we have to find all the nodes at a distance less than 3 from all the marked nodes. We can see that nodes with index 5,9,8,2,0,7 have distances less than 3 from all marked nodes; therefore, the total count of nodes will be 6.

What are your strengths and weaknesses?

Explain your project.

What is the biggest threat to your career?