Suppose you have a 2-d array with integers sorted both horizontally and vertically.
a) Search for the occurrence of a value in the array
b) Sort the array into a single-dimensional array
Jan 21, 2010
Searching and sorting in a 2-d array
Jan 18, 2010
Find the number of negative elements in most efficient way
Given an n X n array with rows sorted and cols sorted, find the number of negative elements in most efficient way.
Dec 31, 2009
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.
Dec 19, 2009
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.
Sep 28, 2009
Sep 8, 2009
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