Wednesday, July 31, 2013

Populating Next Right Pointers in Each Node

Problem:
Given a binary tree
struct TreeLinkNode {
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.

Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Solution:

public void connect(TreeLinkNode root) {

    TreeLinkNode leftWall = root;
    while (leftWall != null) {

        TreeLinkNode across = leftWall;
        while (across != null) {
            if (across.left != null) {
                across.left.next = across.right;
            }

            if (across.right != null && across.next != null) {
                across.right.next = across.next.left;
            }

            across = across.next;
        }
        leftWall = leftWall.left;
    }
}

Complexity:
time - O(n)
space - O(1)
Links and credits:
http://discuss.leetcode.com/questions/7/populating-next-right-pointers-in-each-node

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

Problem:
Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
Examples:
  Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
  Output: 6  (j = 7, i = 1)

  Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
  Output: 8 ( j = 8, i = 0)

  Input:  {1, 2, 3, 4, 5, 6}
  Output: 5  (j = 5, i = 0)

  Input:  {6, 5, 4, 3, 2, 1}
  Output: -1

Solution:

/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;
 
    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);
 
   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);
 
    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);
 
    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }
 
    return maxDiff;
}


Complexity:
time - O(n)
space - O(n)
Links and credits:
http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/

Sunday, July 21, 2013

Find the path traversed by a KNIGHT

Problem:
Find the path traversed by a KNIGHT to reach the destination from source in a 8x8 chess broad...
**you will be given the starting position and ending position

Solution:
From any position, a knight can go in 4 different directions. Thus, we do a BFS (using a queue), keeping a set of visited positions. Once we get to the target point, we're done.

Complexity:
time - O(n)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=22345665

Pyramid of glasses

Problem:
There are some glasses with equal volume 1 litre. The glasses kept as follows:
                           1
           2   3
        4    5    6
      7    8    9   10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..
If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd - 1/2 litre

Solution:
In this problem the rates at which glasses get filled in are rational numbers, whose numerators form the binomial coefficients and denominators are powers of 2 - specifically 2 raised to the power of level at which glasses are present.

A litre of water (overflowed from previous level) gets distributed among the glasses at each level as follows:

level 0: 1
level 1: 1/2  1/2
level 2: 1/4  2/4  1/4
level 3: 1/8  3/8  3/8  1/8
level 4: 1/16  4/16  6/16  4/16  1/16

The above distribution pattern provides with a partial progress towards the actual algorithm that finds the amount of water in jth glass of ith row. The algorithm gets tricky because all the glasses at a level might not be completely filled yet, before water starts getting filled up in levels below (albeit, in an inverted triangle fashion).

----------------------------------------------------------------------------
The above observation apart, a DP-like algorithm below(that remembers quantities in glasses of the previous row) to find out the amount of water in jth jug of ith row can solve the problem.

0. For each glass, maintain 2 variables - the amount of water it holds and the amount of water it overflows.
1. For a glass at index i in the given row, look up two glasses in the previous row at index i-1 & i. (Boundary cases of indices need to be checked though)
2. The inflow into the current glass = half of outflow of glass in the previous row at i-1 + half of outflow of glass in the previous row at index i
3. Based on the inflow, volume held in the current glass = min(1, inflow) and the overflow at the current glass = inflow - volume held by the current glass
4. Repeat steps 1 to 3 until we reach the required glass.

An implementation in java goes like the below:

import java.util.Scanner;
import java.util.regex.Pattern;

class GlassStatus {
 float heldVolume;
 float overflownVolume;
}

public class GlassPyramid {

 static int ipRowNum, ipGlassNum, ipVolume;
 public static float computeWaterAt(float volume, int level, GlassStatus[] previousRows) {

  if (volume <= 0)
   return 0;
  
  GlassStatus[] rows = new GlassStatus[level + 1];
  float overflow1 = 0, overflow2 = 0, inflow = 0, tempVol = 0;
  
  for (int i = 0, prev = i-1, next = i; i <= level; i++, prev++, next++) {
   
   rows[i] = new GlassStatus();
   
   if (prev < 0) {
    overflow1 = 0;
   } else {
    overflow1 = previousRows[prev].overflownVolume/2;
   }
   
   if (next >= level) {
    overflow2 = 0;
   } else {
    overflow2 = previousRows[next].overflownVolume/2;
   }
   if (level == 0) {
    inflow = volume;
   } else {
    inflow = overflow1 + overflow2;
   }
   
   tempVol += rows[i].heldVolume = Math.min(1, inflow);
   rows[i].overflownVolume = inflow - rows[i].heldVolume;    
  }
  
  if (level == ipRowNum) {
   return rows[ipGlassNum].heldVolume; 
  } else {
   return computeWaterAt(volume - tempVol, level + 1, rows);
  }
 }

 public static void readInput() {
  Scanner scanner = new Scanner(System.in);
  scanner.useDelimiter(System.getProperty("line.separator"));
  Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
  scanner.useDelimiter(delimiters);
  
  System.out.println("Input row#:");
  ipRowNum = scanner.nextInt();
  
  System.out.println("Input glass#:");
  ipGlassNum = scanner.nextInt();
  
  System.out.println("Input volume:");
  ipVolume = scanner.nextInt();
    
 }
 
 public static void main(String[] args) {
  readInput();
  System.out.println("Volume in the glass=" + computeWaterAt(ipVolume, 0, new GlassStatus[] {}));
 }

}


Complexity:
time - O(n)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=22191662

Saturday, July 20, 2013

Construct a binary tree from inorder and preorder traversals

Problem:
Construct a BST from inorder and preorder traversal string

Solution:
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.
                 A
               /   \
             /       \
           D B E     F C
We recursively follow above steps and get the following tree.
         A
       /   \
     /       \
    B         C
   / \        /
 /     \    /
D       E  F

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
  static int preIndex = 0;
 
  if(inStrt > inEnd)
     return NULL;
 
  /* Pick current node from Preorder traversal using preIndex
    and increment preIndex */
  struct node *tNode = newNode(pre[preIndex++]);
 
  /* If this node has no children then return */
  if(inStrt == inEnd)
    return tNode;
 
  /* Else find the index of this node in Inorder traversal */
  int inIndex = search(in, inStrt, inEnd, tNode->data);
 
  /* Using index in Inorder traversal, construct left and
     right subtress */
  tNode->left = buildTree(in, pre, inStrt, inIndex-1);
  tNode->right = buildTree(in, pre, inIndex+1, inEnd);
 
  return tNode;
}


Complexity:
time - O(n^2)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=21296665
http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
http://discuss.leetcode.com/questions/148/construct-binary-tree-from-preorder-and-inorder-traversal

Sunday, July 14, 2013

Find all combinations summing up to a given target

Problem:
In a given array a = {1, 7, 3, 4, 5, 6, 2} Print the indices of all the combinations which lead to a given sum called target. For e.g. if the method is
Void PrintAllSumCombos(int[] arr, int target) - and the array shown above is passed with sum target = 7, then the output should be:

0, 3, 6
0, 5
1
2, 3
4, 6

Note: For simplicity, You may assume the array does not contain any negative numbers and also consider same set of indices with a different order as identical - for e.g. if 2, 3 is already printed, ignore 3, 2 as they are one and the same.

Solution:
A simple  and straightforward solution is to examine all possible combinations recursively, and print those that sum up to the target:

void PrintAllSumCombos(int arr[], int target,int start,int taken[],int count) {
   if (target==0) {
      for (int i =0;i<count;i++) {
         cout << taken[i] << " ";
      }
      cout << "\n";
      return ;
   }
   if (target ==-1 || start > 7) {
      return ;
   }
   for(int i=start; i < 7 ;i++) {
      taken[count]=i;
   }
}
int main() {
   int a[7]={1, 7, 3, 4, 5, 6, 2};
   int b[7];
   PrintAllSumCombos(a, 7,0,b,0) ;

   return 0;
}

However, there must exist a more efficient dynamic programming solution. Basic idea: examine each element of the array. Drop those that are greater than the target (because all the elements are non-negative). Also drop all elements equal to the target and print their indexes (tricky part if we should account for zeroes, but this is doable - just don't drop the elements that are equal to the target then). Now we're left with items that are less than the target. We must now produce all possible pairs, remembering the indexes of the pair elements, calculate their sum and perform the same procedure as for single elements (dropping/printing the pairs as necessary). So we end up with a list of pairs with sums less than the target. Continue this until the list is empty. The worst case time complexity of this algorithm is still O(n ^ 2), however, in average case it must be more efficient because we examine less and less elements on each step due to dropping those that are too large.

Complexity:
time - O(n ^ 2)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=21383667

Check if a binary tree is symmetric

Problem:
Check if a given binary tree is symmetric.

Solution:

public boolean recurseSymmetry(Node<AnyType> left, Node<AnyType> right ){
   if(left == null || right == null) return left==right;
   else 
      return left.value == right.value &&
             recurseSymmetry(left.left, right.right) &&
             recurseSymmetry(left.right, right.left);
}


Complexity:
time - O(n)
space - O(n) (for recursion stack)
Links and credits:
http://www.careercup.com/question?id=20884671

Rank of a permutation

Problem:
Given a word consisting of letters, different words can be formed using all the letters in the word. Find the rank of input word in sorted list of all possible words.

Eg.
ABAB = 2
QUESTION = 24572

Program should use no more than 1GB memory and run within 500 milliseconds. Maximum input length = 25 and input word will contain atleast 2 different letters.

Solution:
From http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation :
A particular ranking of a permutation associates an integer with a particular ordering of all the permutations of a set of distinct items. For our purposes the ranking will assign integers 0..(n! − 1) to an ordering of all the permutations of the integers 0..(n − 1).
For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank:
  PERMUTATION      RANK
  (0, 1, 2, 3) ->  0
  (0, 1, 3, 2) ->  1
  (0, 2, 1, 3) ->  2
  (0, 2, 3, 1) ->  3
  (0, 3, 1, 2) ->  4
  (0, 3, 2, 1) ->  5
  (1, 0, 2, 3) ->  6
  (1, 0, 3, 2) ->  7
  (1, 2, 0, 3) ->  8
  (1, 2, 3, 0) ->  9
  (1, 3, 0, 2) -> 10
  (1, 3, 2, 0) -> 11
  (2, 0, 1, 3) -> 12
  (2, 0, 3, 1) -> 13
  (2, 1, 0, 3) -> 14
  (2, 1, 3, 0) -> 15
  (2, 3, 0, 1) -> 16
  (2, 3, 1, 0) -> 17
  (3, 0, 1, 2) -> 18
  (3, 0, 2, 1) -> 19
  (3, 1, 0, 2) -> 20
  (3, 1, 2, 0) -> 21
  (3, 2, 0, 1) -> 22
  (3, 2, 1, 0) -> 23
Algorithms exist that can generate a rank from a permutation for some particular ordering of permutations, and that can generate the same rank from the given individual permutation (i.e. given a rank of 17 produce (2, 3, 1, 0) in the example above).
One use of such algorithms could be in generating a small, random, sample of permutations of n items without duplicates when the total number of permutations is large. Remember that the total number of permutations of n items is given by n! which grows large very quickly: A 32 bit integer can only hold 12!, a 64 bit integer only 20!. It becomes difficult to take the straight-forward approach of generating all permutations then taking a random sample of them.
Code in Java:

  public static BigInteger getRank(int[] permutation)
  {
    int n = permutation.length;
    BitSet usedDigits = new BitSet();
    BigInteger rank = BigInteger.ZERO;
    for (int i = 0; i < n; i++)
    {
      rank = rank.multiply(BigInteger.valueOf(n - i));
      int digit = 0;
      int v = -1;
      while ((v = usedDigits.nextClearBit(v + 1)) < permutation[i])
        digit++;
      usedDigits.set(v);
      rank = rank.add(BigInteger.valueOf(digit));
    }
    return rank;
  }
 
  public static int[] getPermutation(int n, BigInteger rank)
  {
    int[] digits = new int[n];
    for (int digit = 2; digit <= n; digit++)
    {
      BigInteger divisor = BigInteger.valueOf(digit);
      digits[n - digit] = rank.mod(divisor).intValue();
      if (digit < n)
        rank = rank.divide(divisor);
    }
    BitSet usedDigits = new BitSet();
    int[] permutation = new int[n];
    for (int i = 0; i < n; i++)
    {
      int v = usedDigits.nextClearBit(0);
      for (int j = 0; j < digits[i]; j++)
        v = usedDigits.nextClearBit(v + 1);
      permutation[i] = v;
      usedDigits.set(v);
    }
    return permutation;
  }


Complexity:
time - O(n)
space - O(1)
Links and credits:
http://www.careercup.com/question?id=21500666
http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation
http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms/1506337#1506337

Saturday, July 13, 2013

Find increasing 3-tuple (sub-sequence)

Problem:
You given an array:
3, 2, 1, 6, 5, 4, 9, 8, 7
you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array.
Answer can have multiple tuples, you have to find any one.
In this array, answer will be 3, 6, 9

Solution:

  1. Simple. Time complexity = O(n ^ 2)
    • Create an array of indexes, and sort the original array keeping track of the indexes in the second array. Now go through the sorted array and for each element try to find a pair of grater elements whose indexes are increasing. Complexity: time = O(n log n) + O(n ^ 2) = O(n ^ 2), space = O(n)
    • Alternatively, traverse the original array starting from the second element and consider it to be the middle of the 3-tuple. Try to find a smaller element at indexes [0..i) and a greater element at (i..n]. Complexity: time = O(n ^ 2), space = O(1)
    • As suggested in a comment, the following BST solution won't work for "3, 1, 2, 4".
      Or, build a BST from the original array. Then find an element having two consecutive right children. They are grater than one another due to the BST property, and they are located one after another in the original array because we added them in this order in the BST. Complexity: time = O(n ^ 2) [worst] + O(n) = O(n ^ 2), space = O(n)
  2. Advanced.
    Search for Longest Increasing Subsequence and stop after finding three elements of the tuple. Time complexity = O(n log n), space = O(n)

From Wikipedia:
Denote the sequence values as X[1], X[2], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:
M[j] — stores the position k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range k ≤ i (note we have j ≤ k ≤ i here, because j represents the length of the increasing subsequence, and k represents the position of its termination. Obviously, we can never have an increasing subsequence of length 13 ending at position 11. k ≤ i by definition).
P[k] — stores the position of the predecessor of X[k] in the longest increasing subsequence ending at X[k].
In addition the algorithm stores a variable L representing the length of the longest increasing subsequence found so far.
Note that, at any point in the algorithm, the sequence
X[M[1]], X[M[2]], ..., X[M[L]]
is nondecreasing. For, if there is an increasing subsequence of length i ending at X[M[i]], then there is also a subsequence of length i-1 ending at a smaller value: namely the one ending at X[P[M[i]]]. Thus, we may do binary searches in this sequence in logarithmic time.
The algorithm, then, proceeds as follows.
L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L
     such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)
The result of this is the length of the longest sequence in L. The actual longest sequence can be found by backtracking through the P array: the last item of the longest sequence is in X[M[L]], the second-to-last item is in X[P[M[L]]], etc. Thus, the sequence has the form
..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].
Another explanation for the above dynamic programming solution:
In general, we have set of active lists of varying length. We are adding an element A[i] to these lists. We scan the lists (for end elements) in decreasing order of their length. We will verify the end elements of all the lists to find a list whose end element is smaller than A[i] (floor value).

Our strategy determined by the following conditions,

1. If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.

2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].

3. If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.

Note that at any instance during our construction of active lists, the following condition is maintained.

“end element of smaller list is smaller than end elements of larger lists”.

It will be clear with an example, let us take example from wiki {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

A[0] = 0. Case 1. There are no active lists, create one.
0.
----------------------------------------------------------
A[1] = 8. Case 2. Clone and extend.
0.
0, 8.
----------------------------------------------------------

A[2] = 4. Case 3. Clone, extend and discard.
0.
0, 4.
0, 8. Discarded
----------------------------------------------------------

A[3] = 12. Case 2. Clone and extend.
0.
0, 4.
0, 4, 12.
----------------------------------------------------------

A[4] = 2. Case 3. Clone, extend and discard.
0.
0, 2.
0, 4. Discarded.
0, 4, 12.
----------------------------------------------------------

A[5] = 10. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 10.
0, 4, 12. Discarded.
----------------------------------------------------------

A[6] = 6. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 6.
0, 2, 10. Discarded.
----------------------------------------------------------

A[7] = 14. Case 2. Clone and extend.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------------------------

A[8] = 1. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2. Discarded.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------------------------

A[9] = 9. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Discarded.
----------------------------------------------------------

A[10] = 5. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 5.
0, 2, 6. Discarded.
0, 2, 6, 9.
----------------------------------------------------------

A[11] = 13. Case 2. Clone and extend.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------------------------

A[12] = 3. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 5. Discarded.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------------------------

A[13] = 11. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Discarded.
----------------------------------------------------------

A[14] = 7. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9. Discarded.
0, 2, 6, 9, 11.
----------------------------------------------------------

A[15] = 15. Case 2. Clone and extend.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <-- LIS List
----------------------------------------------------------


Complexity:
time - O(n log n)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=21602662
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Sunday, July 7, 2013

Find Nth number in x2x3x5 sequence

Problem:
Following sequence is given:
1,2,3,4,5,6,8,9,10,12,15,16,18,20,24
In this sequence, each number is multiple of 2,3 or 5 only.
This sequence does not contain 7 & 14 as these number has sequence 7 as multiple.
So, if you are given N find the Nth number of this sequence.

Solution:
A dynamic programming solution (assume the sequence starts with 2):
  1. Maintain a counter, that is initialized to 1 and start from an initial value v, say 2. 
  2. Keep incrementing the value v and check if it is divisible by 2 or 3 or 5. 
  3. If divisible, check if the corresponding quotient of v/2 or v/3 or v/5 is present in the solutions to subproblems, that are already computed. If yes increment the counter. 
  4. Return value v when the counter becomes N.
void findN(int N) {
    HashMap<Integer, Integer> DPMap = new HashMap<Integer, Integer>();
    int temp = 2, i = 1;
    DPMap.put(1, 1);
    DPMap.put(2, 2);

    while (i < N) {
        temp++;
        if ((temp % 2 == 0 && DPMap.containsKey(temp / 2))
                || (temp % 3 == 0 && DPMap.containsKey(temp / 3))
                || (temp % 5 == 0 && DPMap.containsKey(temp / 5)))
        {
            i++;
            DPMap.put(temp, temp);
        }
    }
    System.out.println("The required number = " + temp);
}


Complexity:
time - O(n)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=20810664

Monday, July 1, 2013

Synchronize two clocks

Problem:
There is a clock at the bottom of the hill and a clock at the top of the hill. The clock at the bottom of the hill works fine but the clock at the top doesn’t. How will you synchronize the two clocks. Obviously, you can’t carry either of the clocks up or down the hill! And you have a horse to help you transport yourself. And, the time required for going up the hill is not equal to the time required to go down the hill.

Solution:
Let h1 be the time required to climb up to the top of the mountain on the horseback and h2 be the time required to climb down to the bottom on the horseback.

Let p1 and p2 be times required for the person to climb up and climb down on foot.

The person has to make four different kinds of round-trips and measure the round trip times.

1. Climb up and climb down on horseback. The round trip time would be: h1 + h2 = t1 (t1 is measured accurately using the clock at the bottom)
2. Climb up and climb down on foot. The round trip time would be: p1 + p2 = t2
3. Climb up on horseback and climb down on foot. The round trip time would be: h1 + p2 = t3
4. Climb up on foot and climb down on horseback. The round trip time would be: p1 + h2 = t4

Now we have four equations and four unknowns:
h1 + h2 = t1
p1 + p2 = t2
h1 + p2 = t3
p1 + h2 = t4

(t1 to t4 are measured values and hence are known). Solving the system of linear equations gives the values of h1, h2, p1 & p2.

Now start from the bottom of the hill, record the time, call it t, using the clock at the bottom and climb up either on horseback or on foot.

Once you reach the top, correct the clock's time at the top to be either t + h1(if you have climbed up the hill on horseback) or t + p1(if you have climbed up the hill on foot).

Links and credits:
http://www.careercup.com/question?id=20676667