ghost
BAN USERGetting all the overlapping intervals in augmented red-black tree is O(min(n, Klgn)), without modification. You can't delete an element, otherwise next query would would not able to find the particular element. Please check the question where it clearly says that DB can be queried many times.
- ghost June 06, 2012Best Solution:
As usual, the best solution requires you to think from another perspective. In other words, we no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.
Isn’t the bottom-up approach neat? Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.
Below is the code for converting a singly linked list to a balanced BST. Please note that the algorithm requires the list’s length to be passed in as the function’s parameters. The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).
BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow
int mid = start + (end - start) / 2;
BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
BinaryTree *parent = new BinaryTree(list->data);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid+1, end);
return parent;
}
BinaryTree* sortedListToBST(ListNode *head, int n) {
return sortedListToBST(head, 0, n-1);
}
copied from leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
- ghost May 27, 2012You algo is wrong. For you input string max length substring with unique characters is fghaksdljweo , length = 12
Moreover, although you feel that your algo is O(n) but it is actually O(n^2) because you are using strlen(s) in loop, which itself is a O(n) algo. This information is not stored somewhere, it is calculated every time you make a call to strlen.
@Anonymous: Yes partition problem is NP, and you can't find exact solution for NP problems if problem set becomes larger, however, there are subset of NP problems which can be solved in pseudo linear time using DP if space constraint is satisfied, and they are called weak NP problems. Partition problem and subset-sum problem happens to be one of those weak NP problems which can be solved in pseudo linear time using DP
- ghost August 20, 2012