How to answer this coding question from a top hedge fund?
I was given this question in the 2nd round of coding interview with a well-known hedge fund. This question cannot be found on leetcode as far as I know. You are given 3 input arrays, A, B and X. At each iteration, you can select any element Xi from X, choose a subarray within A, and transform all elements in that subarray to Xi, only if all elements in that subarray are >= Xi. (i.e. you can only transform downwards) You can only use each element from X once. This means that elements in X can have duplicates if it can be used more than once. Return true if A can be converted to B using such transformations, or false otherwise. Example: A: [3 3 3] B: [2 1 2] X: [2 1] Answer: true 1) Use 2 from X and apply it to the entire A, causing A to become [2 2 2] 2) Use 1 from X to apply to only the middle element in A, becoming [2 1 2] Interviewer says theres an O(n) solution but I couldnt even figure out the O(nlogn) part. Got a rejection as a result :(
Check that for every element in B, the element at the same index in A is greater than or equal to it. This is clearly O(N). For every index such that A[i] != B[i], verify that B[i] is in X’, where X’ is set(X).
Op what's the answer for this - Example: A: [3 3 3] B: [1 2 1] X: [2 1]
Should be false as first we will convert all elements to 2, but we cqn only convert one more element to 1. If X = [2 1 1] then it would be true
Yup this would be false since we don’t have enough 1s
Don't answer it, just give up
start from the left and calculate the sub array where a[i] >b[i] while calculating the subarray we can keep track of the subarray max of B array. We can replace this subarray with the max value from X (also remove this value from X) that is equal to or higher than max from subarray and repeat this again till the array matches or the max condition is not satisfied or X is empty
Just chiming in on the nontechnical aspect -- how do you know o(n) solution was prereq to getting the job? I often ask a question with a very clever o(1) solution but it is not a prereq to getting hired, but rather an invitation for a conversation that can go a little deeper about algorithms.
I guess I will never really know. Interviewer mentioned that there’s a nlgn solution as well but I didn’t even get that one.
O(n) solution is possible using a map and a stack. Create a map of the values in x to their instance count in X. Aka {2:1, 1;1} Initialize empty integer stack Iterate though A & B (should be the same size) If (a[i] < b[i]) return false If (stack.isEmpty() && b[i] < a[i]) {processMapAndStack(); } Else { If (b[i] < stack.peek()) {processMapAndStack()} Else If (b[i] > stack.peek()) { While (!stack.isEmpty() && b[i] != stack.peek()) { stack.pop() } If ((!stack.isEmpty() && a[i] == stack.peek()) || b[i] < a[i] && stack.isEmpty()) { processMapAndStack() } } } Return true; processMapAndStack() { Integer r = xCount.getOrDefault(b[i], 0) If (r <= 0) return false xCount.put(b[i], r - 1) stack.push(b[i]) } Sorry for quality, typing from phone. For reference took me about 5 minutes to reason out and 15 to implement.
Yeah, this isn't 100% correct (e.g. at the very least, at the very first call to stack.peek(), the stack could be empty), but it's very close and on the right track. I think the following are some actual bugs in the logic: 1) Shouldn't the while loop be while (!stack.isEmpty() && b[i] < stack.peek()) {...} I.e. < instead of != 2) Shouldn't the if after the while loop be more like if (stack.isEmpty() || b[i] < stack.peek()) { process() } Though again, it's hard to say for sure until the initial conditions with the stack and a[i] ?= b[i] are nailed down. Good job seeing the stack pattern on this one.
Actually I think this is right and simplifies it all nicely: Iterate through A and B: if (a[i] < b[i]) return false while (!stack.isEmpty() && stack.peek() < b[i]) { stack.pop() } if (stack.isEmpty() || stack.peek() > b[i]) { processMapAndStack() } After iterating through the whole arrays without returning false, you can return true.
Sounds tough. How much time were you given?
About 30 - 45mins