SDE - Intern

You are given N number of intervals, where each interval contains two integers denoting the start time and the end time for the interval.

The task is to merge all the overlapping intervals and return the list of merged intervals sorted by increasing order of their start time.

Two intervals [A,B] and [C,D] are said to be overlapping with each other if there is at least one integer that is covered by both of them.

For example:

For the given 5 intervals - [1, 4], [3, 5], [6, 8], [10, 12], [8, 9].

Since intervals [1, 4] and [3, 5] overlap with each other, we will merge them into a single interval as [1, 5].

Similarly, [6, 8] and [8, 9] overlap, merge them into [6,9].

Interval [10, 12] does not overlap with any interval.

Final List after merging overlapping intervals: [1, 5], [6, 9], [10, 12].

You are given an array ‘arr’ that contains an equal number of positive and negative elements. Rearrange the given array such that positive and negative numbers are arranged alternatively. Also, the respective relative order of positive and negative should be maintained.

For example:

For the given arr[ ] = { -1, 3, 5, 0, -2, -5 } 
arr[ ] = {3, -1, 5, -2, 0, -5 } is valid rearrangement.
arr[ ] = {3, -1, 0, -2, 5, -5 } is invalid rearrangement; order of 0 and 5 is changed. 
arr[ ] = {3, -1, 5, 0, -2, -5 } is invalid rearrangement; positive and negative elements are not alternative.

Note:

Make changes in the same array and no returning or printing is needed.
Consider zero(0) as a positive element for this question.
It is guaranteed that an answer always exists.

He asked me to write the structure of the Node class for the Linked List first. Then I gave him an iterative approach. He told me to code it. As I started writing the code, I thought recursive would be cleaner, I said the same to him, and he told me to code whatever approach I want. I coded the recursive implementation. Once I was done, I told him that the code is done, just let me dry run it once. He said, let us do it together, he gave me input, and I took him through every line of the code, what value was being stored in each variable after each line, I wrote all of this down in the comments, he was satisfied with it and moved on to the next question.

You are given an array ‘ARR’ of size ‘N’. Your task is to determine whether a subset of ‘ARR’ exists such that you can obtain 1 by multiplying all the elements in the subset by any arbitrary integer (can be different for different elements) and adding all of them.

Subset of an array 'ARR' is a tuple that can be obtained from 'ARR' by removing some (possibly all) elements of 'ARR'.

For example:

Consider the array [2,7,14] and the subset [2,7]. Here, we can multiply 2 with 4 and 7 with -1, and we can add the modified elements present in the subset to obtain 1. Hence, the answer is 1 in this case.