vi.ramanauskas
BAN USERYeah you got me there :D. From information that was provided, I assumed it was an undirected graph. In that case having more than n-1 doesn't increase the amount of vertices you can connect. It is entirely different story ) if it is a directed graph... In that case you have to have additional information provided. E.g. whether it is strongly connected or not.
My graph theory knowledge is very rusty (Wonder what would they say if I asked them to tell me what a graph is, or the rules that define it) so please correct me if I am wrong or missed something.
A good solution, only thing is that, it doesn't handle the case where last point can be considered as a dip (add '60' to the end of an array it wont be detected). Also I think time can be improved by scanning from both ends (although the code will become messier.
Also (seeing the condition that needs to be satisfied) I don't think it handles the case where dip spans for a period of time. E.g.
/\ _ _ _ / \
/ \
But I think this case should be discussed with the person giving an assignment during an interview. Also I think other guys should check their code against this conditions as I don't see their test data including it.
My ugly solution that could be improved many ( MANY ) ways, including the case I've mentioned would be
int[] y = { 0, 10, 20, 10, 30, 40, 50, 40, 30, 20, 10, 20, 30, 40, 50, 60, 50,50,50,50, 60, 70, 60, 60};
List<Integer> list = new LinkedList<Integer>();
List<Integer> tempList = new LinkedList<Integer>();
boolean dipFound = false;
for(int x=0; x <y.length; x++){
if(x+1== y.length){ //handles the last index
if(y[x]<=y[x-1]){
if(!tempList.isEmpty()){
list.addAll(tempList);//this could be improved
tempList.clear();
}
list.add(y[x]);
}
continue;
}
if(y[x]==y[x+1])
tempList.add(y[x]);
if(y[x+1]<y[x]){
dipFound=false;
tempList.clear();
}
if((y[x+1]>y[x]) && !dipFound){
dipFound = true;
if(!tempList.isEmpty()){
list.addAll(tempList); //this could be improved
tempList.clear();
}
list.add(y[x]);
}
}
System.out.println(list);
}
This answer applies only if no two nodes(vertices) can be connected twice, and that no node can be connected to itself.
To connect all the nodes you have in a graph, you have to have a minimum of n-1 edges. So n-1=n, then:
when k=1, then you can connect n vertices
when n>k>1, then you can connect n-k+1 vertices
when k=n, you can connect 0 edges
Here is an idea (using a recursion, but may be rewritten using stack like someone mentioned above). Still uses extra memory though.
Different traverser will return different nodes, if there is more than one pair.
- vi.ramanauskas November 14, 2014