## Walmart Labs Interview Question for Java Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.
Also, pascals(x, y) == pascals(x, x-y) once you calculate one of these, set the other one in the cache as well.

Comment hidden because of low score. Click to expand.
0

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];

}

Comment hidden because of low score. Click to expand.
0

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];

}

Comment hidden because of low score. Click to expand.
0

``````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];``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0

Could you elaborate?

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can calculate values of pascals triangle using combinatorics

Yth (zero-indexed) value at Xth level can be calculated as (X-1) choose Y

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int pascal(int x, int y){
if(y == 0 || x == y) return 1;
else return pascal(x -1 , y - 1) + pascal(x - 1, y);``````

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.