Given two integers m and n , n>=m. Find total number of structurally correct BSTs possible with all numbers between m and n (inclusive).
For example, m=3, n=5 then answer is 5.
Daily Archives: October 15, 2015
Quicksort – inplace O(nlgn) sorting
From wiki, Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, with his work published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.
C++ Class Hierarchy Pointer Assigments
Implicit Conversion of Classes: The address of an object of a derived class can be assigned to a pointer declared to the base class, but the base class pointer can be used only to invoke member functions of the base class
Profit Maximization – Maximum Single-Sell Profit problem
Given an array of stock prices, where the increasing indexes of the array signify the increase in time. Return a good time to buy and sell such that profit is maximized.
Reverse Linked List – single pointer – in group of K
Reverse a link list using one/single pointer.
We first try to device straightforward solution to reverse a linked list recursively. For example, given a linked list 1->2->3->4->5->null, how we can reverse this? Let’s start with straightforward solution using two temp pointers. We will basically keep a new pointer to append nodes from the list into the front of new pointer. Below is both recursive and iterative solution in O(n) time.
Merge Sort
Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.