0
인터뷰 질문/코딩 과제에서 배열 "arr"을 통해 가장 짧은 양의 "홉"을 만들어야했습니다. 색인 나는 1 -> arr [i]를 뛰어 넘을 수있다.최소한의 홉 수의 배열 탐색 기술 회사 인터뷰에서의 온라인 코딩 과제
하나의 비꼬는 점은 값이 0 인 색인에는 착륙 할 수 없다는 것입니다.
문제를 해결하기 시작했을 때 각 색인이 노드 i이고 자식 노드가 도달 가능한 모든 노드 i + 1-> i + arr [i]로 표시되는 방향 그래프로 배열의 일을 시작했습니다.
이 그래프를 상상할 때 Dijkstra를 사용하는 것이 좋은 접근 방법이라고 생각하면 최상의 경로를 찾기 위해 수 백만 번 반복을 반복하지 않아도됩니다.
이것은 엔지니어에게 적절한 대답이 아니 었습니다. 제 생각은 아닌가요? 아니면 내 구현에서 실행되지 않았다.
import java.util.LinkedList;
import java.util.Scanner;
public class Solution {
public static void main(String args[]) throws Exception {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
// get canyon from standard in
Integer[] canyon = getInput();
// This problem is a twist on the shortest path algorithm (Dijkstras), the array is like a graph
// with the values being used to determine the "edges" to different "nodes" aka other indexes with
// non zero values
// these are used for tracking the necessary details of our "graph"
// we could have make an actual graph or made an array of objects with these fields but given
// the potential size of the input, 3 arrays made most sense
// the current ammount of jumps to reach this space, set to int max for starters
int[] cost = getIntArray(canyon.length, true);
// tracking if the "nodes" are yet "known"/"discovered" by the algorithm
// dragon nodes are set to known so the algorithm will ignore them
boolean[] known = getBoolArray(canyon, canyon.length);
// used to point back ward to the previos step in the shorts path to each node
// can be traversed backwards from destination to get shortest path from root
int[] path = getIntArray(canyon.length, false);
// starting at the beginning, we are assuming the starting place cannot be null
if (canyon[0] == 0){
System.out.println("failure");
return;
}
// start by adding the root to "known" paths
int root = 0;
cost[root] = 0;
known[root] = true;
// do not need to calculate path to root
//now the traverse the canyon, how far can we jump at first?
int maxJump = canyon[root];
//lets find every node we can jump to that's not a dragon
for(int jump = 1; jump <= maxJump; jump++){
int leap;
//we need to handle the case of jumping beyond the canyon, which should map to a sngle "node"
//this is handled in our cost, path, and known arrays
if (root + jump >= canyon.length){
leap = canyon.length;
} else {
leap = root + jump;
}
if (!known[leap]){
// we can jump here! lets set the cost and path to reachable nodes
//our "so far" best path to this node has gone up by one jump
//including root here to show that's its a jump from root
cost[leap]++;
path[leap] = root;
}
// we've already passed the end of the canyon, we're done
if(leap == canyon.length)
break;
}
// now we traverse the canyon until we've discovered every node, and know its shortest path
// one invariant of the algorithm is that once you "know" a node, you know (one of) its shortest paths
while (remainingUnknownNodes(known)){
//find the node with the lowest cost
int minNextNode = getUnknownNodeWithLowestCost(known, cost);
if (minNextNode == -1){
// this means we couldn't find a next place to jump that wasn't a dragon
// we're doomed!
System.out.println("failure");
return;
}
known[minNextNode] = true;
// check if we just discovered the shortest path out
if (minNextNode == canyon.length)
break;
// still searching, lets check where we can jump and see if we can update their paths
maxJump = canyon[minNextNode];
for(int jump = 1; jump <= maxJump; jump++){
int leap;
if (minNextNode + jump >= canyon.length){
leap = canyon.length;
} else {
leap = minNextNode + jump;
}
if (!known[leap]){
int costNow = cost[leap];
int costNew = cost[minNextNode] + 1;
if (costNew < costNow){
cost[leap]++;
path[leap] = minNextNode;
}
}
// we've already passed the end of the canyon, we're done
if(leap == canyon.length)
break;
}
}
// lets print out our path of "nodes"
System.out.println(printPath(path, path.length - 1));
}
// returns an array of ints used for tracking current paths and costs of each node
// depending on the context
private static int[] getIntArray(int length, boolean isCostArray){
int[] arr = new int[length + 1]; // extra index to represent beyond the canyon
for (int i = 0; i < length; i++){
if(isCostArray){
arr[i] = Integer.MAX_VALUE;
} else {
// path array
arr[i] = -1;
}
}
if(isCostArray){
arr[length] = Integer.MAX_VALUE;
} else {
// path array
arr[length] = -1;
}
return arr;
}
// returns a boolean array used for tracing which nodes are "known" to the algorithm
private static boolean[] getBoolArray(Integer[] canyon, int length){
boolean[] arr = new boolean[length + 1]; // extra index to represent beyond the canyon
for (int i = 0; i < length; i++){
if(canyon[i] == 0){
// this spot has a dragon so we don't want to include it in our search
// so we'll just say we "know" it
arr[i] = true;
} else {
arr[i] = false;
}
}
arr[length] = false;
return arr;
}
// helper method to see if there are any remaining nodes that are unknown
private static boolean remainingUnknownNodes(boolean[] known){
for (int i = 0; i < known.length; i ++){
if (known[i] == false)
return true;
}
return false;
}
// helper method used to get the next node in the shortest path algorithm
private static int getUnknownNodeWithLowestCost(boolean[] known, int[] cost){
int minCost = Integer.MAX_VALUE;
int minNode = -1;
for(int i = 0; i < known.length; i++){
if (!known[i] && cost[i] < minCost){
minCost = cost[i];
minNode = i;
}
}
return minNode;
}
// helper method that prints the path
private static String printPath(int[] path, int index){
if (index == 0){
return Integer.toString(index);
} else {
String str = index == path.length - 1 ? "out" : Integer.toString(index);
return printPath(path, path[index]) + ", " + str;
}
}
//helper method that gets input from STDIN
private static Integer[] getInput(){
Scanner in = new Scanner(System.in);
LinkedList<Integer> initialNumbers = new LinkedList<Integer>();
while(in.hasNextInt()) {
initialNumbers.add(in.nextInt());
}
Integer[] canyon = new Integer[initialNumbers.size()];
for (int i = 0; i < canyon.length; i++){
canyon[i] = initialNumbers.get(i);
}
return canyon;
}
}