SDE - 1

You are given a Singly Linked List of integers. Sort the Linked List using merge sort.

Merge Sort is a Divide and Conquer algorithm. It divides the input into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, L, M, R) is a key process that assumes that arr[L..M] and arr[M + 1...R] are sorted and merges the two sorted subarrays into one.

Explain different types of Normalization forms in a DBMS.

You are given a binary tree of 'N' nodes.

Your task is to find the path from the leaf node to the root node which has the maximum path sum among all the root to leaf paths.

For Example:

All the possible root to leaf paths are:
3, 4, -2, 4 with sum 9
5, 3, 4 with sum 12
6, 3, 4 with sum 13
Here, the maximum sum is 13. Thus, the output path will be 6, 3, 4.

Note:

There will be only 1 path with max sum.

List tables involved in Online Apps like Uber.