lupuslupus
BAN USERPhD student
I can't understand how you can maintain both insertion order info as well as min_value info, using only one heap.
Can you please elaborate how you do each of the three operations?
That logical fallacy would definitely NOT land you the job :)
- lupuslupus September 15, 2010That logical fallacy would definitely NOT land you the job :)
- lupuslupus September 15, 2010<number of zeros> <number of non-zeros> abc ... <number of zeros> etc.
For example:
abc000defg00
becomes
0 3 abc 3 4 defg 2
A tree can not have two roots. Is there an implicit root, which ABC and XYZ are children of?
- lupuslupus September 07, 2010You are right. Let me try to rephrase it so it becomes clearer:
In the "worst case" j is never decremented, and we need n iterations to finish. Perhaps this is an impossible run, but it is definitely impossible for a run to be any worse.
In the "best case" j is always decremented, and we need n/2 iterations to finish. Perhaps this is an impossible run, but it is definitely impossible for a run to be any better.
Hence O(n).
Thank you S.
When int a[] = { 5, 7, 9, 11, 12 };
max = 5 min = 7
Wrong.
In theory it looks right, but will the anagram code fit into a long int?
- lupuslupus September 04, 2010Num. input words: N
Maximum word length: M
OP's soultion:
1. Sort each word: O(M*logM*N).
2. Compare with each anagram group: O(M*N^2)
Total complexity, assuming that logM < N: O(M*N^2)
ibnipun10's solution:
1. Count occurance of each character: O(M*N)
2. Compare with each anagram group: O(N^2)
Total complexity, assuming that M < N: O(N^2)
However, if we assume that word lengths will be "reasonable" (say, always less than C characters)? If so, the complexity of the first solution becomes O(N^2). So I don't think it is clear which solution is the better. Thoughts, anyone?
". create a hashtable where the hashcode is generated using the characters in the string..I got the hash of each string by doing an Exclusive OR of each charcater in the string although i had the dbt if the Ex-OR of non anagrams can be same"
Imagine that the alphabet only has two letters: 1 and 0,
Char representation: a bit for each character
Two words given:
10
100
Hash value:
1 XOR 0 = 1
1 XOR 0 XOR 0 = 1
The two words has the same hash value, but are not anagrams.
Sorting the array has complexity O(nlogn).
Here is a O(n) solution:
Maintain a priority queue (PQ) that never grows beyond size 3, and where the order is ascending, i.e. the element in front is the lowest of the 3 elements. Step through the array. Whenever a value is greater than the front of the PQ, remove the front element from the PQ, and put the new value in its right place in the PQ. When finished, the 3rd largest integer will be in front of the PQ.
Complexity:
Scanning the array: O(n)
Replacing an element in the PQ: O(1) (since the size is a constant k=3)
Totally: O(n)
Often a heap is used for PQ, but in this case the PQ is so small that an array will do fine.
#define NULL -1;
#include <iostream>
using namespace std;
struct BinaryNode
{
// remove definition to save space
};
typedef BinaryNode BinaryTree;
void BinaryTree::printEdges(bool isLeftEdge, bool isRightEdge)
{
if(isLeftEdge || (left==NULL && right==NULL))
cout << value << " ";
if(left!=NULL)
left->printEdges(isLeftEdge, right!=NULL ? false : isRightEdge);
if(right!=NULL)
right->printEdges(left!=NULL ? false : isLeftEdge, isRightEdge);
if(isRightEdge && !isLeftEdge && !(left==NULL && right==NULL))
cout << value << " ";
}
int main()
{
int A[] = {0,1,NULL,2,3,NULL,NULL,4,5,6,7,NULL,NULL,NULL,NULL};
BinaryTree tree(A, 0, sizeof(A)/sizeof(int), A[0]);
tree.printEdges(true, true);
return 0;
}
Ah, its called Levenshtein distance. Wikipedia's article on it has the algorithm.
But if the vocabulary is in order of a million, comparing each pair would certainly be too complex, even if done in advance. Wonder how Word, etc., does it on their spell checker.
Tries works fine for words whose prefix is same. But what about "foo" and "loo"? Counting insertions, deletions and substitutions is common in speech recognition for measuring accuracy (on word level, not letter level). "foo" and "loo" has a difference of 1, since 1 substitution is necessary to make the words identical. Not sure if this can be computed efficiently, though.
- lupuslupus September 02, 2010How is similarity measured? Or is that part of the problem?
- lupuslupus September 02, 2010You mean you traversed the tree twice for the main task, or once for the main task and once for the variant?
- lupuslupus September 01, 2010Hash table seems a bit overkill when the range is only 1-50. An array of size 50 does the job fine.
- lupuslupus September 01, 2010Why sort the numbers first? Is it more efficient?
- lupuslupus August 31, 2010Input: n ranges.
Sort ranges after lowest boundary. O(nlogn)
Foreach range: merge with previous if overlapping, else keep separate. O(n)
Total complexity: O(nlogn)
Can it be done in O(n)?
<pre lang="c++" line="1" title="CodeMonkey22137" class="run-this">#include <iostream>
using namespace std;
struct Node {
int val;
Node * next;
Node(int vals[], int size, int offset=0) {
val = vals[offset];
offset++;
if(offset<size) {
next = new Node(vals, size, offset);
}
}
void print() {
cout << val;
if(next!=NULL) {
cout << " ";
next->print();
}
}
};
typedef Node LinkedList;
void merge(LinkedList& a, LinkedList& b) {
Node * pa = &a;
Node * pb = &b;
while(true) {
if(pb->val < pa->val) { // swap
Node temp = *pa;
*pa = *pb;
*pb = temp;
}
if(pa->next!=NULL)
pa=pa->next;
else
{
pa->next = pb;
break;
}
}
}
int main() {
int a_vals[] = {2,3,6,8};
int b_vals[] = {1,4,5,7};
LinkedList a(a_vals, sizeof(a_vals)/sizeof(int));
LinkedList b(b_vals, sizeof(b_vals)/sizeof(int));
merge(a, b);
a.print(); // a contains merged list, b is irrelevant
return 0;
}</pre><pre title="CodeMonkey22137" input="yes">
</pre>
Rotation is equal to a transpose, followed by a "flop" around the horizontal axis:
A[i][j] => A[j][i] => A[M-j-1][i]
provided the first set of brackets correspond to the column number and the indexes starts at 0
> 1->2->3->4->5->1(this is circular one)
Is the 1 at the beginning and the end the same node?
In the array, store the node address together with the value. Doesn't change complexity.
- lupuslupus August 30, 2010Data objects:
Priority queue (PQ) implemented as heap, each element contains a value.
Stack implemented as array, stores pointers, which points to elements in the PQ.
Push():
1.Insert new value in PQ: O(log n)
2.Push pointer to new value on Stack: O(1)
Pop():
1. Pop pointer of Stack: O(1)
2. Remove value from PQ: O(log n)
FindMin():
1. Look it up in PQ: O(1)
Average operation time: O(log n)
However, the number of elements will probably not grow very large, so for practical purposes, a naive implementation might suffice:
A stack implemented by array, keep track of Min and linear search through the array each time you Pop a Min.
Average operation time: O(n)
My thought was to maintain both a stack (array) and a PQ (heap). Thus the stack takes care of the LIFO property, and the PQ of finding the min. But I know realize that Hinax' solution below (two stacks) is the best one.
- lupuslupus October 01, 2010