I recently had a software engineering interview and was asked a series of questions that was a bit outside of knowledge realm, and I feel like there's some scientific computing principles here (I took some scicomp courses many years ago, and I got some scicomp vibes when these questions were asked). I am wondering if anyone know what kind of problem this is? I suspect it's some kind of classical problem under guise.
You're given a large rectangle that has length = n and width = m. The rectangle is divided into many disjoint areas and the areas comes in all shapes (not necessarily convex) and sizes. Each disjoint area is assigned a distinct ID. Assume there are approximately 200 of such disjoint areas/IDs. In addition, suppose you some giant matrix
mat[i][j]corresponds to some coordinate
mat[i][j]represents the ID at that coordinate. But
matis so large you can't store it in memory. (I was a bit confused here because he said you're given this matrix but it's not stored in memory, so I don't quite see how you're "given" the matrix)
The first question I was asked:
How would you turn
matin to an easy to store and more efficient memory structure? The idea the interviewer wanted here is to keep dividing the large rectangle into very small squares repeatedly until the area consists of a single ID (at which point you stop cutting that area into even smaller squares). Then save this square. This sounds straightforward and just like meshing.
The second question I was asked is:
How would you store these squares? What data structure would you use? I think he wanted some kind of sorted way but I have no clue what he was referring to.
Does anyone know what would be a good storage structure here? It seems like it's just a mesh of squares, and I know there's traditional methods of storing structured and unstructured meshes (I highly highly doubt that's what the interviewer wanted though because that's pretty off topic for software engineers).
Then the last question was
You're given a (x,y) coordinate, and you want to quickly query which ID this coordinate belongs to. How would you do this? I said you can use some sort of binary search (at this point, I was just making stuff up...) and the interviewer wanted me to think about "compressing x and y simultaneously." I don't even known what this means.
Does anyone know how you would quickly query the list of squares from the previous question? I suppose the answer to this depends on how its stored.
This third question reminds me of solving the Euler equations at "tracer" coordinates that didn't correspond to the centroids of the mesh elements, but in that situation, I just found the nearest neighbor and outputted the solution there. Don't think that's what was wanted here as an answer for this question however.