zwfreesky
BAN USER
Comments (4)
Reputation 20
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Do you mean to optimize the algorithm to make the complexity less than O(n)?
Also the codes above seems wrong , it should be:
vector<int>::iterator i;
int count;
for (i = elements.begin(); i < elements.end(); i++) {
if ((*i) != 0) {
//count++ should be put here
count++;
if (count == n) {
return (*i);
}
}
}
return -1;
}
Comment hidden because of low score. Click to expand.
0
of 0 vote
Can we change the position of the element?
We can do a quick sort on the link list which is O(n*logn), and then do a traversal from the beginning to end and eleminate the duplicated elements (O(n)).
So the complexity of this algorithm is O(n*logn)
I have a question, how can we quick sort on linklist?
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
This question is similar to the BFS question.
- zwfreesky April 10, 2009Just do a Breadth First Search on the Binary tree. We can get the nodes printed level by level.
The question also asks us to print the nodes level by level. In order to realize this , we can mark each node with a "level" property and check when to print new line.
struct Element {
Node *p;
int nodeLevel;
}
void PrintTree(Node *root )
{
int currentLevel = 0;
if (root == NULL) return;
Queue<Element> Q = new Queue<Element>;
Element e = new element(root, 0);
Q.push(e);
while(!Q.empty())
{
e = Q.pop();
if (e.level!=currentLevel)
{
print new line;
currentLevel = e.level;
}
print (e.p->value);
if (Q.p->left!=NULL)
{
Element left = new Element(Q.p->left, Q.p->level+1);
Q.push(left);
}
if (Q.p->left!=NULL)
{
Element left = new Element(Q.p->left, Q.p->level+1);
Q.push(left);
}
}
}