SDE - 1

For a given Singly Linked List of integers, sort the list using the 'Merge Sort' algorithm.

You are given 'N' rectangular buildings in a 2-dimensional city. Your task is to compute the skyline of these buildings, eliminating hidden lines return the skyline formed by these buildings collectively. A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. The geometric information of each building is given in the array of buildings where BUILDINGS[i] = [LEFT_i, RIGHT_i, HEIGHT_i]:

-> LEFT_i is the x coordinate of the left edge of the ith building.

-> RIGHT_i is the x coordinate of the right edge of the ith building.

-> HEIGHT_i is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1, y1], [x2, y2], ...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note:

There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3], [4 5], [7 5], [11 5], [12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output.

As such: [..., [2 3], [4 5], [12 7],...]. 

Also, the buildings are sorted by a non-decreasing order.

For more clarification see sample case 1.

Alex has bought a new machine that does photocopies of photos in batches of minimum size ‘K’. Alex has ‘N’ photos, whose resolution is given in an integer array ‘photos’. The machine has some downsides as well. The error in photocopying a batch is the absolute difference between the highest resolution photo and the lowest resolution photo in the batch.

Now Alex will divide the photos into some groups of size at least ‘K’ and feed it to the machine. The maximum error is the maximum of the errors from each batch. He wants to minimize the maximum error. Can you help him divide the photos into batches efficiently and tell him the minimum maximum error he can achieve?

Example: Let the resolutions be [1, 5, 2] and K = 2. So there is only one way of dividing the array, which is a single group of all three elements. The error is therefore 5 - 1 = 4.

You have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.

Note :

Try to solve the problem in 'Single Scan'. ' Single Scan' refers to iterating over the array/list just once or to put it in other words, you will be visiting each element in the array/list just once.

An alien spaceship arrived at our planet Earth. An alien dropped his dictionary of words on the way back to his planet. Ninja found that dictionary and now wants to create the order of the characters of that language. Help ninja in creating the order of the characters with the help of the list of words given as were found in the Alien’s dictionary.

Example:

Let us assume that we have a list of words found in the dictionary in the same order as given: [“baa”, “abcd”, “abca”, “cab”, “cad”]

Now, ninja needs to find the order of the characters used in these strings.

The order would be: ‘b’, ‘d’, ‘a’, ‘c’, because “baa” comes before “abcd”, hence ‘b’ will come before ‘a’ in the order, similarly because, “abcd” comes before “abca”, ‘d’ will come before ‘a’. And so on.

Note:

A certain list of words might have more than one correct order of characters. In such cases, you need to find the smallest in normal lexicographical order. In the case of INVALID ORDER, simply return an empty string.

Invalid Order:

words = [“aba”, “bba”, “aaa”]. 
In this case, no valid order is possible because, from the first two words, we can deduce ‘a’ should appear before ‘b’, but from the last two words, we can deduce ‘b’ should appear before ‘a’ which is not possible.

More than one correct order:

words = [“ca”, “cb”]. 
In this case, we only know that ‘b’ will come after ‘a’ in the order of characters, but we don't have any knowledge of ‘c’. So, the valid correct orders can be = “abc”, “cab”, “acb”. Out of these, “abc” is lexicographically smallest, hence it will be printed.

Given an array of length N, you need to find and print the sum of all elements of the array.