An interview question

之前去NetApp onsite的时候遇到的一个问题,因为当时面我的三哥迟到了,时间就被压缩到不到20分钟,加上前面还有一点behavior就导致coding的时间很短,最后也没做出来,但是三哥哥表示这个不是我的错,而且我当时的思路direction是对的,只是需要更多的时间就应该能做出来了。所以回来以后仔细想了想,发现确实,其实如果脑子再快一点应该也能解出来的。刚刚实验了一下发现确实搞出来了,就记录一下。

问题:
给一个Array of Non-negative integers,假设其每一个element都表示从这个element所能走的index上的最远距离,写一个方法bool CanReachEnd(int[] arr),判断给定的array是否能够从第一个element走到最后一个element。

Example1:

1
2
input: [3, 2, 1, 0, 14, 5]
output: False

这里第一个元素是3,所以范围内可以走到arr[1],arr[2],arr[3]。从arr[1] 可以走到arr[2],arr[3];从arr[2] 可以走到arr[3];从arr[3]就哪都去不了了。所以false。

Example2:

1
2
input: [3, 2, 1, 14, 5]
output: True

参考第一个例子,从arr[0]可以走到arr[3],从arr[3]最远index可以走到17,然而arr的长度只有5,所以true。

思路:
当时因为已经过了两轮了,上午在eclipse上写了三个小时的java,下午第一轮又被葡萄牙人虐了polymorphism的基本概念和设计模式,所以第二轮我当时的脑子是相当空的。三哥给我出完题我确实是懵的,但是直觉告诉我这东西要么和树有关,要么和dp有关,所以无论如何是要从最后一个元素开始搞的。然而当时没反应过来,三哥虽然亲切地提示我从后往前搞是对的并问我要keep track of what,我却一脸懵逼。。。现在想来,其实就是个树,从最后一个元素开始往前找,凡是满足arr[i] + i >= currentIndex 这个关系的 i 都是children node,然后进行DFS就好了,反正我只需要能找到 0 就算true了。

Answer:(in C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool CanReachEnd(int[] arr){
if (arr == null || arr.Length == 0) return false;
if (arr.Length == 1) return arr[0] > 0;
int lastIndex = arr.Length - 1;
Stack<int> indexStack = new Stack<int>();
indexStack.Push(lastIndex);
while(indexStack.Count > 0){
int ending = indexStack.Pop();
if (ending == 0)
{
return true;
}
else
{
for(int i = ending - 1; i > -1; i--)
{
if(arr[i] + i >= ending)
{
indexStack.Push(i);
}
}
}
}
return false;
}

考察:
这种通过各种奇怪的东西来构建树还真是挺常见的,得亏去之前多看了看树相关的东西。然而当时并没有反应过来,所以只能写下来泽被后人当作攒人品了。。。

17-05-30
@Sturbridge