Sudhindra.A
BAN USERYou are right ... Count Sort will make the sorting efficient but Search/Space time will not be so efficient.
- Sudhindra.A April 25, 2013METHOD 1 :: Time - O(n^2), Space - O(1) [SIMPLE AND INEFFICIENT]
Name :: Brute Force Approach
Use 2 for loops.
For every element in 1st loop, try to find another element matching the sum in 2nd loop.
METHOD 2 :: Time - O(nlogn), Space - O(1) [TRICKY]
Name :: Sort and find approach
1. Sort the elements
2. Use 2 indexes from both ends and find the 2 elements matching the sum
METHOD 3 :: Time - O(n), Space - O(n) [EFFICIENT]
Name :: Hash and search approach
1. Insert all the elements into a hashmap
2. For every element x, check if there is (sum-x) element in the hashmap.
I didnt find a type called "Dynamic Recursion" under Recursion Types.
Can you give me the link for the same?
I didnt find a type called "Dynamic Recursion" under Recursion Types.
Can you give me the link for the same?
I find a type called "Dynamic Recursion" under Recursion Types.
Can you give me the link for its definition?
Found it out from GeeksForGeeks
#include <iostream>
using namespace std;
template<int N>
class PrintOneToN
{
public:
static void print()
{
PrintOneToN<N-1>::print(); // Note that this is not recursion
cout << N << endl;
}
};
template<>
class PrintOneToN<1>
{
public:
static void print()
{
cout << 1 << endl;
}
};
int main()
{
const int N = 100;
PrintOneToN<N>::print();
return 0;
}
Use a TRIE datastructure. It is also called prefix trees or digital search trees.
This will be the optimized datastructure when many words are inserted and indexed across.
Insertion/Retrieval/Deletion Time : O(k), where k is the length of the string
Reverse every word individually
Consider entire string as one word and reverse it.
Step 1 : knaht uoy rof rouy pleh
Step 2 : help your for you Thank
I am not sure whether it satisfies the memory constraint specified.
Agreed.
Step1 : Sorting elements - O(nlogn)
Step2 : Looping through the elements - O(nlogn)
Target is not given to you. You have to find for all numbers and arrive at the solution.
- Sudhindra.A April 19, 2013If both occurences of the number are adjacent, then it would result O(n^2) algorithm.
- Sudhindra.A April 18, 2013If array size is N and all elements are in the range 1 to N, then we can design an algorithm with below complexities :
Time complexity - O(N)
Space complexity - O(1)
Are the elements within the range 1 to N?
Rotation to maintain the balance, creation of nodes etc.,
- Sudhindra.A April 18, 2013Use a Self-Balanced Binary Search Tree. Let each node have 2 fields - start_index and end_index.
Insert elements into the BST along with the below operations.
If the element is not found in BST, create a node in BST using a[i]. Let start_index=end_index=i
If element is already found, then end_index=i
After inserting all the elements, traverse the BST to find the node with maximum distance.
Time Complexity Analysis
------------------------
Insert Operation= O(logN)
Inserting N elements = O(NlogN)
Other operations = O(1)
Time Complexity - O(NlogN)
Space Complexity - O(N)
I agree with Anonymous above.
You are supposed to store the state of the originator rather than entire originator object. When i say state, it is the data inside originator not the originator itself.
Your example is relevant to Memento Pattern.
I think he was expecting few completely-defined, like :
- Memento will be a class, having methods - Save & Restore
- Caretaker will be having a collection of Mementos
GetMaxDepth(root)
{
if(root is null)
return 0;
return Maximum( GetMaxDepth(root->left) , GetMaxDepth(root->right) ) + 1;
}
Recursion actually needs to switch/restore back the states correctly. This restoration can happen effectively through pointers as they are address-based.
Hence, linked lists are preferred.
Let given number be x.
x's compliment = (power( 2, sizeof(int) -1) - x
For example, if given number is 13 and size of integer is 8. then,
13's compliment = (power(2,8)-1) - 13
= 255 - 13 = 242
If given number is 9, then one's complement in 8-Bit Integer machine would be 246.
As per your algorithm, it will return 6 which is incorrect.
I would strongly agree with Red-Black trees or Balanced BST. Priority queue may give max/min but will fail in giving a range of results efficiently.
- Sudhindra.A December 25, 2014Using a balanced BST,
Insertion - O(n logn)
Querying based on given date - O(log n).
Sorting the queried results in Inorder - O(logn)