sojourner6
BAN USERsuggestion:
idea: in a tree, there is only one path from the root to a leaf.
use BFS to get the maximum number of edges in a path from the root to any leaf. => O(n) time
now from all the leaves (degree 1) obtain the two longest (longest and 2nd longest, both may have same length) leaves in the tree. => O(n)
sum their distances to get the result => O(1)
Overall: Linear time
in O(n), read the linked list in reverse order
public String getKElementsReverse(int n, int k){
String ret = ",";
boolean extra = false;
int seek= 0;
while((seek + k) <= n){
seek += k;
if(seek != n){
seek++;
extra = true;
}
else{
extra = false;
}
}
if(extra){
seek--;
}
Node temp = this;
for(int i= seek; i<=n; i++){
temp = temp.prev;
}
while(temp != null){
//temp = temp.prev;
for(int i=k; i>0; i--){
ret += temp.getContent() + ",";
temp = temp.prev;
}
if(temp != null){
temp = temp.prev;
}
ret += ";";
}
return ret;
}
then display nodes from front, with blocks of size k extracted from the end of "ret"
static String printKPartsReversed(Node temp, String[] kParts, int n, int k){
//temp= temp.getNext();
String full = "";
int count = 0;
int seek = 0;
int l = kParts.length;
while(seek < n){
full += kParts[l -1 - count++];
for(int i=0; i<k; i++){
temp = temp.getNext();
}
if(temp.getNext() == null){
//indicates tail reached
break;
}
seek += k+1;
full += temp.getContent() + ", ";
temp = temp.getNext();
}
return full;
}
Overall time complexity= O(n)
tests on cases that i considered ... but test it no your input before using
RepI am Ricky from the USA. I am 29 year old. I am doing a job. I am doing a ...
Repmarywwaldrop7, Computer Scientist at Chelsio Communications
I am Mary ,working in the field of training and development coordinator for three years, focusing on teaching English as ...
Worst Case: O(k + log n) => where k is the number of occurrences of a number in the list
- sojourner6 December 09, 2015