YOE: 5.5
College: Tier-3
Currently SSE @ Walmart
Applied directly at Apple's careers website.
Coderpad Link was shared which had 2 questions (Java based) with 70 min time limit.
- You're given a list of strings representing a 2D grid. The first character of the first string is the upper left side of coordinates(0,0).
The grid always has the same size:
Width = 15 (each string contains 15 characters)
Height = 10 (10 strings in the list)
The grid contains a unique path, made of stars(*) and of lowercase letters.
The path always starts at the coordinates(0,0) and does not contain any forks or loops. It moves in the four directions (up,down,right,left) but not diagonally.
You must follow the path and record the letters in the order as you encounter them (do not record the stars).
At the end of the path, output the string made with the letters.
The path may immediately start with a letter and may end with a letter too.
The path has a minimum length of two characters and contains at least one letter.
public class PathFinder {
public static String followPath(String[] grid) {
int rows = grid.length;
int cols = grid[0].length();
int x = 0, y = 0;
StringBuilder result = new StringBuilder();
boolean[][] visited = new boolean[rows][cols];
int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}}; // right, down, left, up
while (true) {
visited[y][x] = true;
char c = grid[y].charAt(x);
if (Character.isLowerCase(c)) {
result.append(c);
}
// Find next cell in path
boolean moved = false;
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < cols && ny >= 0 && ny < rows && !visited[ny][nx]) {
char nc = grid[ny].charAt(nx);
if (nc == '*' || Character.isLowerCase(nc)) {
x = nx;
y = ny;
moved = true;
break;
}
}
}
if (!moved) break; // End of path
}
return result.toString();
}
}- Finding the maximum combined weight of items that can be packed into two suitcases with given weight limits (w1 and w2)—you need to implement a variation of the 0/1 Knapsack problem, but with two knapsacks (suitcases).
Implement a method maxWeight(weights, w1, w2) which takes as input
- an array of positive integers weights representing the weights of the items.
- two integers w1 and w2 representing the maximum weight that can be put in suitcase 1 and suitcase 2 respectively.
e.gweights=[10,8,3,8] w1=5, w2=17
Answer: 19
public class SuitcaseKnapsack {
public static int maxWeight(int[] weights, int w1, int w2) {
int n = weights.length;
// dp[i][j]: can we achieve weight i in suitcase1 and j in suitcase2
boolean[][] dp = new boolean[w1 + 1][w2 + 1];
dp[0][0] = true;
for (int weight : weights) {
boolean[][] next = new boolean[w1 + 1][w2 + 1];
for (int i = 0; i <= w1; i++) {
for (int j = 0; j <= w2; j++) {
if (dp[i][j]) {
// Option 1: don't take this item
next[i][j] = true;
// Option 2: put in suitcase 1
if (i + weight <= w1) next[i + weight][j] = true;
// Option 3: put in suitcase 2
if (j + weight <= w2) next[i][j + weight] = true;
}
}
}
dp = next;
}
// Find the maximum combined weight possible
int max = 0;
for (int i = 0; i <= w1; i++) {
for (int j = 0; j <= w2; j++) {
if (dp[i][j]) {
max = Math.max(max, i + j);
}
}
}
return max;
}
}