dumbhead
BAN USERsorry I made a small mistake. it should be NODE* p = reverseTree(n); instead of NODE* p = reverseTree(child); reposting the correct code:
class NODE{
public:
NODE(string d) : data(d) {}
string data;
vector<NODE*> children;
};
vector<NODE*>
reverseTreeandReturnListwithLeafNodes(NODE* n)
{
vector<NODE*> roots;
reverseTree(roots, n);
return roots;
}
NODE*
reverseTree(vector<NODE*>& roots, NODE* n)
{
vector<NODE*>& chldrn = n->children;
if (chldrn.empty()) {
roots.push_back(n);
return n;
}
vector<NODE*> children = chldrn;
chldrn.clear();
vector<NODE*>::iterator iter = children.begin();
for (; iter != children.end(); ++iter) {
NODE* child = *iter;
NODE* p = reverseTree(roots, child);
p->children.push_back(n);
}
return n;
}
- dumbhead April 25, 2012c++ code:
-------------
class NODE{
public:
string Label
vector<NODE*> children;
};
vector<Node*>
reverseTreeandReturnListwithLeafNodes(NODE* n)
{
vector<Node*> roots;
reverseTree(roots, n);
return roots;
}
NODE*
reverseTree(vector<Node*>& roots, NODE* n)
{
vector<NODE*>& chldrn = n->children;
if (chldrn.empty()) {
roots->push_back(n);
return n;
}
vector<NODE*> children = chldrn;
chldrn.clear();
vector<NODE*>::iterator iter = children.begin();
for (; iter != children.end(); ++iter) {
NODE* child = *iter;
NODE* p = reverseTree(child);
p->children.push_back(child);
}
return n;
}
- dumbhead April 25, 2012I guess each seq must have at least one unique element.
void PrintAllSeq(int start,vector<int>& seq)
{
if (start == n) {
PrintSeq(seq);
return;
}
while((!seq.empty()) && (A[seq.back()] > A[start])) {
seq.pop_back();
}
for (int i = start; i <n;++i) {
if (seq.empty() || (A[seq.back()] < A[i])) {
seq.push_back(i);
} else {
vector<int> newSeq = seq;
PrintAllSeq(i, newSeq);
}
}
PrintSeq(seq);
}
// we need to keep track of the uniqueness
void PrintSeq(vector<int>& seq)
{
if (seq.empty()) return;
bool hasUnique = false;
for(int i =0; i<seq.size(); ++i) {
if (!isPrinted[seq[i]]) {
hasUnique = true;
break;
}
}
// this seq already subseq of some other seq
if (!hasUnique) return;
for(int i =0; i<seq.size(); ++i) {
isPrinted[seq[i]] = true;
cout << A[seq[i]] << ", ";
}
cout << endl;
}
consider four state variable protected by lock and two two conditions:
AR: active reader
WR:waiting reader
AW:active writer
WW:waiting writer
Reader() {
lock.Acquired()
while (AW+WW>0) {
WR++
okToRead.Wait(lock);
WR--;
}
AR++
lock.Release()
read file
lock.Acquired()
AR--;
if (AR==0 && WW>0) {
okToWrite.Signal();
}
lock.Release()
}
Writer()
{
lock.Acquired();
while(AW+AR>0) {
WW++
okToWrite.wait(lock)
WW--
}
AW++;
lock.Release();
write to the file
lock.Acquired();
AW--;
if (WW > 0) {
okToWrite.signal(lock);
} else if (WR>0) {
okToRead.signal(lock).
}
lock.Release()
}
}
- dumbhead April 23, 2012code without parent pointer:
call as: CreateThreadedTree(root, 0);
void BST::CreateThreadedTree(NODE* root, NODE* inSucc)
{
NODE* succ = 0;
if (root->_left) {
CreateThreadedTree(root->_left, root);
}
if (root->_right) {
CreateThreadedTree(root->_right, inSucc);
} else {
root->_right = inSucc;
}
}
1. create a queue of triplets (x, y, s), where each element in the queue corresponds to a prefix 'amazon'
2. Initialize the queue with all occurrence of 'a' in the matrix.
3. Then, the algorithm proceeds as follows:
for i=2 to 6 // mazon
c = next letter of "mazon"
create a temporary newqueue
While the oldqueue is not empty:
Dequeue a triple (x, y, s) from oldqueue
For each square (x', y') with letter c adjacent to (x, y):
insert (x', y', s+c) into the newqueue
oldqueue = newqueue
Although this works, it doesn't remember the letter it has already used. To fix that, you'd have to add an extra field to each queue datum, a list of all the visited locations, and then check that list before adding the next character.
- dumbhead April 17, 2012level order traversal:
const int d=depth(root);
for (int i = 0; i <d;++i) {
PrintLevel(root, i);
std::cout << std::endl;
}
PrintLevel(NODE* root, int d) {
if (!root) return;
if (d==0) {
std::cout << root->data;
return;
}
PrintLevel(root->left, d-1);
PrintLevel(root->right, d-1);
}
1. For each line in input file create a hashset (of integers) i.e a vector of hashsets.
2. For each integer in input string:
i) check each of the hash_set. If all integer found in a single hash_set , print it. Otherwise keep a count of max_count and hash_set index. Print at the end.
m->no of line in input file
n->max no of integer in a single line
p->no of integer in input
Time complexity: O(m*n + p*m) {m*n=for creating hash_set,p*m for checking}
Space complexity: O(m*n)
a[i]<a[j]<a[k] s.t i<j<k
From the original array build two arrays.
i) LMin[i] contains index of the min element seen so far from the left including a[i].
ii) RMax[i] contains index of the max element seen so far from the right including a[i].
consider the following array:
a=4,7,5,1,3,8,9,6,2
LMin=0,0,0,3,3,3,3,3,3
RMax=6,6,6,6,6,6,6,7,8
Now for i=1 to n if a[LMin[i]] < a[i] < a[RMax[i] print LMin[i],a[i],RMax[i]
Time complexity: O(n)
Space Complexity: O(n)
yes it is. the call should be as IsPalindrome(head,head);
- dumbhead May 10, 2012