Walmart Labs Interview Question
Java DevelopersCountry: 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.