呵呵，今天的菠菜挺折磨人 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

呵呵，今天的菠菜挺折磨人

呵呵，今天的菠菜挺折磨人# Stock

T*e2010-03-02 08:03

1 楼

如题。
比如用Dynamic Programming做Longest Common Subsequence，top down approach（
recursion），需要一个2d array存状态。
如果是在main中declare 一个2d array，然后在recursive function中当参数传递，开
销微增（pass by reference），但貌似更能体现出recursion的精神。
如果是定义成class instance variable，开销更小，code更简洁，也更能体现出OO的
思想。
请问是否面试官更欣赏第二种风格？
如果是的话，再推进一步，一切向OO风格看齐：一个problem当一个class来设计，所有
instance variable和methods该加private的都加。在解题的同时体现出良好的OO
class design素养，相比仿C风格所有method一路public static过去，是否会更受面试
官青睐？
多谢各大牛指点。

b*f2010-03-02 08:03

2 楼

http://www.iavcusa.com/a/1441096288862.html
网上也有直播，有兴趣的请赏光 :-)

w*i2010-03-02 08:03

3 楼

T*e2010-03-02 08:03

4 楼

自己小顶一下......

s*e2010-03-02 08:03

5 楼

haha ~~~~ 网上有看的吗？

【在 b*f 的大作中提到】

: http://www.iavcusa.com/a/1441096288862.html
: 网上也有直播，有兴趣的请赏光 :-)

v*m2010-03-02 08:03

6 楼

哈哈，赢钱了。

s*m2010-03-02 08:03

7 楼

在下以为面试时候一般就写个裸奔的method。。那有心思管这些。不过也无不可。如果
面试官觉得没必要他会叫停的

e*32010-03-02 08:03

8 楼

当然要了，因为时间限制，你不需要具体写实现，但是跟面试官说清楚这是可以改进的
地方，只不过你因为时间紧迫就先take shortcut了，别人不是看你具体的代码如何，
主要看你的思路，知识面，以及是否仔细认真。

【在 T*******e 的大作中提到】

: 如题。
: 比如用Dynamic Programming做Longest Common Subsequence，top down approach（
: recursion），需要一个2d array存状态。
: 如果是在main中declare 一个2d array，然后在recursive function中当参数传递，开
: 销微增（pass by reference），但貌似更能体现出recursion的精神。
: 如果是定义成class instance variable，开销更小，code更简洁，也更能体现出OO的
: 思想。
: 请问是否面试官更欣赏第二种风格？
: 如果是的话，再推进一步，一切向OO风格看齐：一个problem当一个class来设计，所有
: instance variable和methods该加private的都加。在解题的同时体现出良好的OO

T*e2010-03-02 08:03

9 楼

非常感谢楼上各位的指点。我会根据自身coding速度做调整。
euclid2003在另一帖中的code就是个很好的参考。
http://www.mitbbs.com/article_t/JobHunting/32611137.html
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static Map cache = new HashMapInteger>();

static class CacheKey{
public int x, y;
public CacheKey(int x, int y){
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object obj){
CacheKey key = (CacheKey) obj;
return this.x == key.x && this.y == key.y;
}

@Override
public int hashCode(){
return ((Integer) (this.x+this.y)).hashCode();
}
}

public static int[][] createMatrix(int width, int height){
int[][] matrix = new int[height][width];
for (int i=0; ifor (int j=0; jmatrix[i][j] = rand.nextInt(50);
if (rand.nextBoolean()){
matrix[i][j] *= -1;
}
}
}
return matrix;
}

public static void printMatrix(int[][] matrix){
for (int i=0; iint j = 0;
for (; jSystem.out.print(matrix[i][j] + ", ");
}
System.out.println(matrix[i][j]);
}
}

public static int minimumStrength(int x, int y){
int strength = 0;
if (x == matrix[0].length-1 && y == matrix.length-1){
if (matrix[y][x] < 0){
strength = -1 * matrix[y][x];
}
} else if (x == matrix[0].length-1){

int nextStrength = cachedStrength(x, y+1);
strength = calcStrength(nextStrength, x, y);
} else if (y == matrix[0].length-1){
int nextStrength = cachedStrength(x+1, y);
strength = calcStrength(nextStrength, x, y);
} else {
int nextStrength = Math.min(cachedStrength(x, y+1),
cachedStrength(x+1, y));
strength = calcStrength(nextStrength, x, y);
}
System.out.println(x + ", " + y + " needs minimum strength of " +
strength);
return strength;
}

public static int cachedStrength(int x, int y){
CacheKey key = new CacheKey(x, y);
if (cache.containsKey(key)){
return cache.get(key);
} else {
int strength = minimumStrength(x, y);
cache.put(key, strength);
return strength;
}
}

private static int calcStrength(int nextStrength, int x, int y){
int strength = 0;
if (nextStrength == 0){
if (matrix[y][x] < 0) strength = -1 * matrix[y][x];
} else {
if (matrix[y][x] - nextStrength >= 0){
strength = 0;
} else {
strength = nextStrength - matrix[y][x];
}
}
return strength;
}
public static void main(String []args){
int size = 5;
matrix = createMatrix(size,size);
printMatrix(matrix);
cachedStrength(0,0);
}
}

e*32010-03-02 08:03

10 楼

实际写代码还需要写comment，还要写getter，setter，如果比较复杂的话还要考虑
Interface和Abstract Class,最后还要写Unit Test,好几个模块还要写Integration
Test, 不过这些我都忽略了，但是一定要跟面试官说，表示你知道，不过因为时间紧迫
就只能忽略了，实际工作中一定会补上的。

【在 T*******e 的大作中提到】

: 非常感谢楼上各位的指点。我会根据自身coding速度做调整。
: euclid2003在另一帖中的code就是个很好的参考。
: http://www.mitbbs.com/article_t/JobHunting/32611137.html
: import java.util.*;
: public class HarryPotter{
: private static Random rand = new Random();
: private static int[][] matrix;
: private static Map cache = new HashMap: Integer>();
:

T*e2010-03-02 08:03

11 楼

非常详尽到位。再次感谢。

【在 e********3 的大作中提到】

: 实际写代码还需要写comment，还要写getter，setter，如果比较复杂的话还要考虑
: Interface和Abstract Class,最后还要写Unit Test,好几个模块还要写Integration
: Test, 不过这些我都忽略了，但是一定要跟面试官说，表示你知道，不过因为时间紧迫
: 就只能忽略了，实际工作中一定会补上的。

l*a2010-03-02 08:03

12 楼

mark

w*y2010-03-02 08:03

13 楼

改版的leetcode是不是不显示testcase 的运行结果了？
只给这个
Submission Result: Accepted

y*u2010-03-02 08:03

14 楼

平时面试官都在半睡半醒的过程中
你这种漂亮style要是做得慢了，人早不耐烦了

【在 T*******e 的大作中提到】