CareerCup

We are given a list of numbers A= {5,9,12,16,25,30,45} and their fixed probability of occurance P={0.22,0.18,0.20,0.05,0.25,0.02,0.08} where sum(p) =1. The problem is to arrange the numbers in a binary search tree in a way that minimizes the expected total access time. Note: In a binary search tree, number of comparisions needed to access element at depth d is (1+d)

Find the best way to cut a rod of length N units into smaller pieces such that we get maximum benefit. The prices for each smaller pieces of rod is given for cut of length from 1 to N.
Example
Length |1 2 3 4 5 6 7 8
-----------------------------------------
price |1 5 8 9 10 17 17 20

Find the longest Palindromic sub sequence of a given sequence, for example if the sequence is XAYBZBA then length of longest palindromic sub sequence is 5 and it is ABZBA

Write a program to find the longest increasing sub sequence of a given array

How will you perform the preorder and inorder traversal of binary trees without using recursion. Basically he asked first to write a method to perform iterative preorder tree traversal and then iterative inorder tree traversal.

Find the kth smallest element in an array. How can we do it without sorting the array.

Do the post order traversal of a binary search tree in iterative manner. You cannot use recursion. (Hint: You can use stack)