Sort a ordered linkedlist

A singly LL is given such that there is alternate ordering between the elements.

Ex: 1->2->13->14->11->5->4->null

Give an efficient O(n) algo to sort such a LL. There can be multiple such orderings in the given LL.

find height of a node in BST

Given a BST T and a node N in T such that all leaf nodes are connected in doubly linkedlist fashion, find height of the node N in T.

Given two strings, find the minimum no. of steps required to covert one to the other?

Birthday Calendar

Implement the birthday diary calendar to keep records of all birthdays of your friends
1) what underlying data structure(s) you will use so that the memory consumption should be optimum [i.e if you have only 12 birthday entries you should not hold memory for all 365 days of the year].

2) You should be able to view the data (birthdays) with closest birthday first [i.e 7th July should come before 11 Aug].

3) How will you keep this data sorted (for question 2), everytime you insert a new birthday entry. This sorting should be as optimum as possible [mergesort etc will not be very beneficial bcoz ideally you won't have thousands or millions of birthday]

4) How will you handle 2 or N number of birthdays on same day

Given a string of n characters, find the longest palindrome in the string.

O(n2) is simple, O(n) is nice

Given an undirected graph G(V,E), design an algo to detect whether there is a triangle in the graph?

Find the minimum substring containing all unique characters atleast once in the given string

Find pairs from the given array

Given an array X, find tuples (xi, xj) such that j>i and xj is the immediate number greater than xi in the given array?

Ex Problem: X: {5, 4, 1, 3, 7}
Solution:
{5, 7}
{4, 7}
{1, 3}
{3, 7}

Random Number Generation - II

Given a function rand5() which generates values between 0-5 with equal probablities, how would you create another function rand7() which generates values between 0-7?

For that matter given a function randM() which generates numbers between 0-M, how would you create another function randN() which generates numbers between 0-N with equal probabilities? Is it possible for every value of M,N?

PS: I'm calling this "Random Number Generation - II" because we already have another version of this problem here.

Think in terms of possible values being generated by the given randX() function and map to all the possible values to be generated by the target randY() function