Yaya
BAN USER- 0of 0 votes
AnswersHow to print the outside frame of a binary tree.
1. the order is top to down, left to right, then down to top
2. print all leftest node and rightest nodes
3. print all leaf nodes
4. print all nodes which only have 1 leaf100 50 150 24 57 130 12 30 60 132
e.g:
- Yaya in United States
the output should be
100, 50, 24, 12, 30, 57, 60, 130, 132, 150| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersQ: print out all leaf node path with non recursive method
The structure of node is *NOT* binary tree, is just a normal tree.// print out all leaf node path // 12 // 4 8 22 //1 2 3 9 18 24
the output is like:
- Yaya in United States
12, 4, 1,
12, 4, 2,
12, 4, 3,
12, 4, 8, 9,
12, 4, 8, 22, 18,
12, 4, 8, 22, 24,| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
How about using bool array instead of int array, it will save a lot of space, e.g.
(p.s. not good at JAVA)
public void FirstNonRepeatedCharacter(string s)
{
int i;
bool[] asc = new bool[95000];
char[] ca = s.ToCharArray();
for (i = 0; i < ca.Length; i++)
{
asc[ca[i]] = 1;
}
for (i = 0; i < ca.Length; i++)
{
if (asc[ca[i]] == 1)
{
Console.WriteLine("first non repeating char is: " + ca[i]);
break;
}
}
}
The implementation of solving the problem is a little complex.My idea is
1. according to L, permutation and concat all the strings, e.g.
L: "fooo", "barr", "wing" => L: A="fooo", B="barr", C="wing"
generate: (if the number of strings in L is m, words length is l, the time in this step is O(m!)
ABC = "fooobarrwing"
ACB = "fooowingbarr"
......
then generate "next array" for every string (which will be used to KMP find)
the time is O(m*l)
2. use KMP algo the search every string above in S. (the length of S is n)
kmp time complex is O(m*l + n)
so the whole time complex is O(m! + m*l + n)
C++ code,
// Find the nth non-repeating number given a streams of characters in the range of A-Z
char FindnthNonRepeatNum(char *str, int k)
{
if (!str || 0 == k) return '\0';
char *p = str;
std::map<char, int> numMap;
std::map<char, int>::iterator it;
std::vector<char> numV; // use the vector to save the order of char occurance
std::vector<char>::iterator itc;
while (*p != '\0')
{
it = numMap.find(*p);
if (numMap.end() != it) // current char has been added to map;
{
(*it).second += 1; // count > 1 mean, the number repeats.
}
else
{
numMap[*p] = 1;
numV.push_back(*p); // not found in map, so add it to vecotr.
}
++p;
}
int kth = 0;
for (itc = numV.begin(); itc != numV.end(); ++itc)
{
if (kth != k && 1 == numMap[*itc]) // the char only occur once
{
kth++;
if (kth == k) break;
}
}
if (k != kth)
return '\0';
else
return (*itc);
}
I think you should use min heap of size 100, NOT max heap.
1. add first 100 data into the heap
2. pick up a data and compare it with the top one of heap, if the data is greater than the top data of the heap, use it replace the top one and adjust the heap. if the data is less than the top data of heap, ignore it.
My idea is to divide the reverse work into 2 steps
1. reverse "next" node,
2. reverse "random" node
RLinkedNode* ReverseRLinkedNode(struct RLinkedNode* node)
{
// pre->p->next
if (!node)
return NULL;
// Divide the reverse work into 2 steps
// First step, reverse the linked list normally
RLinkedNode* p = node->next;
RLinkedNode* pre = node;
pre->next = NULL;
while(p)
{
RLinkedNode* n = p->next;
p->next = pre;
pre = p;
p = n;
}
RLinkedNode* head = pre;
// Second step, reverse random node
// use a set to contain the nodes which have been accessed/reversed in "random"
std::set<RLinkedNode*> accessNodes;
p = head; // get the head
while(p)
{
// if random is null,
// or the current node has been accessed
// then go to next node
if (!p->random || accessNodes.find(p) != accessNodes.end())
{
p = p->next;
}
else
{
// random != null, and the node has not been accessed.
// reverse random node
RLinkedNode* r = p->random;
pre = p;
pre->random = NULL;
// because pre->random is set to null, and (another node)->random may point to this node.
// so don't add this node to accessNodes.
// NOTE: and one of the condition is that there are no 2 nodes which will point to (random) the same node.
while(r)
{
RLinkedNode* n = r->random;
r->random = pre;
pre = r;
r = n;
accessNodes.insert(r);
}
}
}
return head;
}
Does the problem want a subarray or just sum of the subarray?
- Yaya September 09, 2013