Meta Interview Prep
Preparing for an upcoming meta interview.
I'm going to use this post for resources and other useful things I want to remember for my upcoming interview.
7 steps to success in your coding interview:
- Do not jump straight into coding, take a few mins to understand the problem and ask any clarifying questions (but not too long!).
- Describe your solution to your interviewer and get their thoughts on your solution.
- Think about your algorithm(s) including the complexity and runtime. Ask the interviewer if it’s ok or if you should think about something more optimized. Then figure out your data structure and implement.
- Run through your code verbally with your interviewer. This is really important at this point. Does it really do what you think it does? Make sure to read what is there, not what you think is there.
- Test your code, put in an input to see what happens. We’re looking for you to find the bugs yourself and fix anything that comes up
- Restate the complexity. Is it the same, or different to your initial thinking based on what you have actually coded up? Make sure you’re thinking about both space and time
- Optimize. Proactively suggest ways to optimize to the interviewer and get their feedback to ensure what you’re trying to do is not overly complex and is correct then code it up.
Neetcode
I found this roadmap through a youtube video about doing Leetcode problems in a structured and better way. I'm using it to guide my study for the next few weeks.
03/11/2024 Update
I've been working through the roadmap and I've had two breakthroughs so far:
- I'm coming to terms with these sorts of problems as a sort of puzzle. I enjoy metal puzzles and those too have a certain trick that, once discovered, makes the puzzle trivial. Finding that trick is difficult, but becomes easier the more you do.
- I'm more confident in just brute-force solving the problem first. Originally, I'd get caught up thinking that the solution was obvious from the description, and I just needed to find that first. But these are designed to be difficult and I can't imagine the sort of person you would have to be to intuit the solution easily. People work on these algorithms for a long time in Universities and such. Expecting to intuit the most ideal solution is crazy.
My second breakthrough came when I saw this problem on Leetcode: 3Sum. I still got frustrated at it being such a strange and contrived problem, but I got over that fairly quickly and decided to just brute-force it right away. Below is that:
function threeSum(nums: number[]): number[][] {
const possibilities = new Set();
for(let left = 0; left < nums.length - 2; left += 1) {
const one = nums[left];
for(let middle = left + 1; middle < nums.length - 1; middle += 1) {
const two = nums[middle];
for(let right = middle + 1; right < nums.length; right += 1) {
const three = nums[right];
if(one + two + three === 0) {
possibilities.add(JSON.stringify([one, two, three].sort()))
}
}
}
}
return Array.from(possibilities).map((stringifiedArray) => {
return JSON.parse(stringifiedArray as string) as [number, number, number];
})
};Now I couldn't think of a better way to ensure uniqueness than just to sort the 3 item array, Stringify it with JSON, put it in a Set, and then rebuild a solutions Array from the set. But it worked! And I did it in reasonable time. It didn't pass all tests in the alloted time, but it was a working solution. I allowed myself to peak at the solutions, and then implemented the better one:
function twoSums(nums, target) {
const results = [];
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
results.push([nums[left], nums[right]]);
left += 1;
} else if (sum < target) {
left += 1;
} else {
right -= 1;
}
}
return results;
}
function threeSum(nums: number[]): Array<[number, number, number]> {
const tried = new Set();
const possibilities = new Set();
nums.sort((a, b) => {
return a - b;
})
for (let index = 0; index < nums.length; index += 1) {
const current = nums[index];
if (tried.has(current)) {
continue;
} else {
tried.add(current);
const target = 0 - current;
const withoutCurrent = nums.slice(0, index).concat(nums.slice(index + 1));
const mates = twoSums(withoutCurrent, target);
mates.forEach((mate) => {
possibilities.add(JSON.stringify([current, ...mate].sort()));
});
}
}
return Array.from(possibilities).map((stringifiedArray) => {
return JSON.parse(stringifiedArray as string) as [number, number, number];
})
}Turns out, the twoSum problem from before was a good and time-efficient way to find all the possibilities needed. That helps me to understand how and why to break the problem into smaller parts. I hope this "sharpens that tool" for me going forward in to the harder problems.
03/12/2024 Update
Did a hard problem in about an hour and a half, though I thought through a brute force solution in maybe 20-25 minutes and could at least articulate it even if I didn't get the code going for the next hour or so. I tried to write my thoughts down as I was thinking in comments.
My first intuition was to go by each row and find the space water could sit in, then track that height and offset future calculations. I realized about halfway through the solution I'd be doing it in something like O(logN) time, but I persevered and got it working.
// simplest [1, 0, 1];
// 1st row potential - first row space takers
// length of array - space
// higher later...
// find container for every level? subtract space?
// Find all containers, add later?
// ohhhh
// find left side
// find right side
// subtract heights in between from area
// max of Min(height) per index in between
// [5, 3, 2, 3, 5]
// 5 * 4 = 20
// 20 - 3 - 2 - 3 = 12
// is that right?
// x _ _ _ x
// x _ _ _ x
// x x _ x x
// x x x x x
// x x x x x
// no it's 7?... height - 3 = 2
// height - 2 = 3, height - 3 = 2
// 2, 3, 2 = 7
// hmmm maybe add as I go using that method
// feels good enough to try
// Had to run out but thought about it, I think first solution is best. Find valid open space per row, and go inwards to find higher spaces.
function findContainerArea(heights, offset = 0, limit = 0): number {
const emptySpaces = heights.reduce((emptySpaceCount, height) => {
const offsetHeight = Math.max(height, offset);
const empties = Math.max(limit - offsetHeight, 0);
return emptySpaceCount + Math.max(empties, 0);
}, 0);
return emptySpaces;
}
function trap(height: number[]): number {
let left = 0;
let right = height.length - 1;
let potential = 0;
let currentHeight = 0
while (left < right) {
const leftWall = height[left];
const rightWall = height[right];
const nextHeight = Math.min(leftWall, rightWall);
if (nextHeight > currentHeight) {
potential += findContainerArea(
height.slice(left + 1, right),
currentHeight,
nextHeight
);
currentHeight = nextHeight;
}
if (leftWall < rightWall) {
left += 1;
} else {
right -= 1;
}
}
return potential;
};Since I got a working solution, I let myself look at the "right" solution from that neetcode guy. And ya know what? I feel like I wasn't far off from that one. I had seen "rows" in my head and so I went that way, but it was better to think in "columns." I like to believe that if I saw the "columns" first, I would have arrived at the more optimal solution.
Overall, I had an idea that I could articulate within the time window of the interview—and for a hard problem. That's some good progress for me.
03/13/2024 Update
Oh man I have to write about this one it was exactly like those metal puzzles. I was scratching my head for a while on it. I was hoping I could just keep a min variable that I could update as I go with the smallest, but what about when the stack gets popped?? If the value that gets popped is the smallest value, then now I have to go back through everything to find the smallest one again.
Well I have to admit I cheated and checked the solutions. It was obvious though once I saw it, you just keep an array of the current minimum at the index (level?) of the stack alongside it, and you pop then both when you pop. Then, you just get the "top" of the min stack to get the current minimum. It reminded me of the one about finding the product of all numbers except the current index one, without dividing. Basically, you make another helper array (or two) that help you track of something.
03/15/2024 Update
Doing Binary Search now and just want to record the implementation I made. I never actually wrote one before so I will continue to write them each time I need it in the problems, but I wanna keep this for reference.
function binarySearch(target: number, arr: number[]): boolean {
let left = 0;
let right = arr.length - 1;
if (target < arr[left] || target > arr[right]) {
return false;
} else if (arr[left] === target || arr[right] === target) {
return true;
} else {
while (left <= right) {
const middle = left + Math.round((right - left) / 2);
if (arr[middle] === target) {
return true;
} else if (arr[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return false;
}
}03/26/2024 Final Update
I had my interview and I was super nervous. I didn't perform very well and they said they wouldn't continue with me. I didn't have working code for my algorithms. I think I focused too much on explaining my solution and I got lost coding it up. I should probably practice doing both at once.. The second one I was totally lost it was some ordering of a tree. I'm sure it would've obvious if I had more experience working with trees.
So I will continue my practice until it's all second nature. They may not be very useful to my everyday coding, but they're good tools to have in my tool belt.