Software Developer

This problem can be solved using hashing. The idea is to traverse the tree in an inorder fashion and insert every node’s value into a set. Also check if, for any node, the difference between the given sum and node’s value is found in the set, then the pair with the given sum exists in the tree.
Time Complexity :O(n).

A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from the list and merge the other into the first interval. Repeat the same steps for remaining intervals after first. This approach cannot be implemented in better than O(n^2) time.

An efficient approach is to first sort the intervals according to the starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i]. 
Algorithm :
1. Sort the intervals based on increasing order of starting time.
2. Push the first interval on to a stack.
3. For each interval do the following
a. If the current interval does not overlap with the stack top, push it.
b. If the current interval overlaps with stack top and ending time of current interval is more than that of stack top, 
update stack top with the ending time of current interval.
4. At the end stack contains the merged intervals.

It works on the principle of Divide and Conquer. Merge sort repeatedly divides the array into several arrays until each array consists of a single element and merging those arrays in a manner that results into a sorted array.

Pseudocode :
MergeSort(A, p, r):
if p > r 
return
q = (p+r)/2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)

Merge function : The task is to merge two subarrays A[p..q] and A[q+1..r] to create a sorted array A[p..r].
Steps :
Create copies of the subarrays L ← A[p..q] and M ← A[q+1..r].
Create three pointers i, j and k
i indicates current index of L, starting at 1
j indicates current index of M, starting at 1
k indicates the current index of A[p..q], starting at p.
Until we reach the end of either L or M, pick the larger among the elements from L and M and place them in the correct position at A[p..q]
When we run out of elements in either L or M, pick up the remaining elements and put in A[p..q]
Time complexity : O(nlogn)

Start from 1 and go to a number whose square is smaller than or equals n. For every number x, we recur for n-x. The recursive formula is: If n = 1 and x*x <= n
The time complexity of the above solution is exponential.
This solution can be optimized using dynamic programming.

1) Create an empty sorted (or result) list
2) Traverse the given list, do following for every node.
......a) Insert current node in sorted way in sorted or result list.
3) Change head of given linked list to head of sorted (or result) list.

Division Method : This is the most simple and easiest method to generate a hash value. The hash function divides the value k by M and then uses the remainder obtained.
Formula: h(K) = k mod M
Here,
k is the key value, and 
M is the size of the hash table.

Mid Square Method : The mid square method is a very good hashing method. It involves two steps to compute the hash value-
Square the value of the key k i.e. k2
Extract the middle r digits as the hash value.
Formula: h(K) = h(k x k)
Here,
k is the key value. 

Folding Method : This method involves two steps:
Divide the key-value k into a number of parts i.e. k1, k2, k3,….,kn, where each part has the same number of digits except for the last part that can have lesser digits than the other parts.
Add the individual parts. The hash value is obtained by ignoring the last carry if any.
Formula: 
k = k1, k2, k3, k4, ….., kn
s = k1+ k2 + k3 + k4 +….+ kn
h(K)= s

Here,
s is obtained by adding the parts of the key k. 

Multiplication Method. This method involves the following steps:
Choose a constant value A such that 0 < A < 1.
Multiply the key value with A.
Extract the fractional part of kA.
Multiply the result of the above step by the size of the hash table i.e. M.
The resulting hash value is obtained by taking the floor of the result obtained in step 4.
Formula: h(K) = floor (M (kA mod 1))
Here,
M is the size of the hash table.
k is the key value.
A is a constant value.