最近、電話インタビューを行いました。プロセスの一部として問題のコーディングが含まれていました。
問題は のバリエーションでしたFind the most closest common ancestor of a treeが、ひねりがありました。ツリーはグラフによく似ていました。つまり、子ノードを接続できました。例：
A
/
B
| \
C E
| |
D F
\ /
G
この場合、このツリーとノードが与えられF、D結果として得られる最も近い共通の祖先は になりますB。2 番目のひねりは、ツリーが配列として提示されたことです。実装
するメソッドには次の入力があり
public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, String targetNode2)
ました。
正直なところ、私は完全にパニックに陥り（すでにかなり緊張していました）、答えを見つけるのに本当に長い時間がかかりました.nodes{"G", "F", "E", "D", "C", "B", "A"}parentNodes{{"F","D"},{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, null}nodes[i]parentNodes[i]
これは再帰的に解決されると思いますが、私が知る限り、うまくいく反復的な解決策を思いつきました.ノードをキューにプッシュし、最初のターゲットノード、次に2番目のノードのパスを上に移動します。すでに遭遇したノードを見つけたら、それを解決策と見なします (問題を解決するためにコメントを追加しました)。
public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, String targetNode2) {
if(nodes == null || parentNodes == null){
throw new IllegalArgumentException();
}
Map<String, String[]> map = new HashMap<String, String[]>();
for(int i = 0; i < nodes.length; i++){
map.put(nodes[i], parentNodes[i]);
}
//These are the parents visited as we go up
Set<String> parentsSeen = new HashSet<String>();
parentsSeen.add(targetNode1);
Queue<String> path = new LinkedList<String>();
String[] parents = map.get(targetNode1);
//The root is the common parent
if(parents == null){
return targetNode1;
}
//Build the path up
for(String parent:parents){
path.add(parent);
}
while(!path.isEmpty()){
String currentParent = path.remove();
parentsSeen.add(currentParent);
parents = map.get(currentParent);
if(parents == null){
continue;
}
for(String parent:parents){
path.add(parent);
}
}
parents = map.get(targetNode2);
//It is the root, so it is the common parent
if(parents == null){
return targetNode2;
}
//Start going up for the targetNode2. The first parent that we have already visited is the common parent
for(String parent:parents){
if(parentsSeen.contains(parent)){
return parent;
}
path.add(parent);
}
while(!path.isEmpty()){
String currentParent = path.remove();
if(parentsSeen.contains(currentParent)){
return currentParent;
}
parents = map.get(currentParent);
if(parents == null){
continue;
}
for(String parent:parents){
path.add(parent);
}
}
return null;
}
前進の電話がかかってきませんでした。私は「独学」であるため、ここでどのように失敗したかを理解したいと思います。これは技術的な問題であるため、主観的な問題ではないと思います。ここで経験豊富な人々から助けを得ることができれば幸いです。
では、同僚のプログラマーとして、この問題をどのように処理し、私のソリューションをどのように評価しますか? スキルを向上させるために何をする必要がありますか?
できるだけ率直に話すことができます。何がうまくいかなかったのかを理解し、学ぶことができる限り、私は満足しています