## Walmart Labs Interview Question

Java Developers**Country:**United States

**Interview Type:**In-Person

public static int pascal(int x, int y) {

int[] currentrow;

int[] previosrow = { 1 };

printArray(previosrow);

for (int i = 2; i <= x; i++) {

currentrow = new int[i];

currentrow[0] = 1;

currentrow[i - 1] = 1;

for (int j = 0; j < i - 2; j++) {

currentrow[j + 1] = previosrow[j] + previosrow[j + 1];

}

printArray(currentrow);

previosrow = currentrow;

}

return previosrow[y];

}

public static int pascal(int x, int y) {

int[] currentrow;

int[] previosrow = { 1 };

printArray(previosrow);

for (int i = 2; i <= x; i++) {

currentrow = new int[i];

currentrow[0] = 1;

currentrow[i - 1] = 1;

for (int j = 0; j < i - 2; j++) {

currentrow[j + 1] = previosrow[j] + previosrow[j + 1];

}

printArray(currentrow);

previosrow = currentrow;

}

return previosrow[y];

}

```
public static int pascal(int x, int y) {
int[] currentrow;
int[] previosrow = { 1 };
printArray(previosrow);
for (int i = 2; i <= x; i++) {
currentrow = new int[i];
currentrow[0] = 1;
currentrow[i - 1] = 1;
for (int j = 0; j < i - 2; j++) {
currentrow[j + 1] = previosrow[j] + previosrow[j + 1];
}
printArray(currentrow);
previosrow = currentrow;
}
return previosrow[y];
```

}

Here is O(x) solution

```
def pascal(x, y):
assert x <= y
x = min(x, y - x)
result = 1
for i in xrange(x):
result = (result * (y - i)) / (i + 1)
return result
```

top down dynamic programming.

```
static int getPascalValue(int i, int j, HashMap<String, Integer> map, int[] cnt) {
//base cases: left col or diagonal
if( j == 0 || i == j)
return 1;
if(map.containsKey(i + " " + j))
return map.get(i + " " + j);
int res = getPascalValue(i -1,j, map, cnt) + getPascalValue(i-1,j-1, map,cnt);
map.put(i + " " + j, res);
cnt[0]++;
return res;
}
public static void main(String[] args) {
int cnt[] = new int[1];
HashMap<String, Integer> map = new HashMap<>();
out.println(getPascalValue(40, 20, map, cnt) + " cnt: " + cnt[0]);
}
```

407575348 cnt: 400

If you are allowed to use extra memory, you can improve the solution by caching calculated value so that the second recursion branch becomes more efficient.

- victor.stratan October 11, 2015Also, pascals(x, y) == pascals(x, x-y) once you calculate one of these, set the other one in the cache as well.