2
$\begingroup$

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 where mat[i][j] corresponds to some coordinate (x=i, y=j) and mat[i][j] represents the ID at that coordinate. But mat is 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 mat in 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ This problem looks like it can be solved using some data structure like a quadtree. Not exactly sure, though. $\endgroup$
    – Abdullah Ali Sivas
    Aug 23, 2021 at 3:01
  • $\begingroup$ @AbdullahAliSivas Would you be able to expand on the quadtree idea? I'm not sure how it applies in this scenario. $\endgroup$
    – user5965026
    Aug 23, 2021 at 3:17
  • $\begingroup$ You can read the region quadtree article on wikipedia (I linked in my answer). But TL;DR: the root is the whole matrix; you check if all entries are the same, the moment you find two entries with different IDs create 4 leaves, repeat the procedure for each leaf. If a leaf has no children, then store the region ID in that leaf. For leaves with children, put the region ID = NULL because they contain multiple regions. $\endgroup$
    – Abdullah Ali Sivas
    Aug 23, 2021 at 3:47
  • $\begingroup$ If it doesn't fit into memory, it might still fit onto a harddrive. Algorithms can then only work on parts of the data structure at a time. These are called "out of core" algorithms. $\endgroup$
    – Wolfgang Bangerth
    Aug 23, 2021 at 15:39

1 Answer 1

Reset to default
4
$\begingroup$

After doing some quick research, I am convinced that the interviewer was looking for an answer related to one of the data trees. Depending on the application, one might be better than the others, but all of them are suitable for this general description.

mat[i][j] might be available on a hard disk -which are capable of storing 16TBs of data nowadays- but may not be possible to read into the memory -the best consumer-level motherboard I could find supports only upto 256 GBs-. In this case, you would read the matrix in chunks and process incrementally.

I would probably answer with quadtrees (region quadtrees), because that is a structure I am familiar with. But there are many like R-trees, Kd-trees, ... See wikipedia.

Querying to which leaf a point belongs (which would correspond to finding the ID it belongs to) costs $O(N)$ assuming the matrix mat is $2^N$-by-$2^N$. See this image, where an image is compressed using quadtrees. To find the color of a pixel, you would query the tree and retrieve color information stored at the corresponding leaf.

Improve this answer
$\endgroup$
14
  • 2
    $\begingroup$ Honestly, the question you were asked is a little ambiguous. This is not surprising to me, as I went through some amount of technical interviews this year. In my experience, this is not intentional, in their context the question is clear because they have been working on a related project for a while. Same as the "obvious" trap grad students (even some experienced academics) commonly fall into, the terminology and techniques are obvious to them but not to other people (I know because I was a grad student too). $\endgroup$
    – Abdullah Ali Sivas
    Aug 23, 2021 at 4:07
  • 1
    $\begingroup$ In this case, maybe you could do something with binary search. Though I don't know how that would work, because given i and j if you could access mat[i][j] easily, then you wouldn't have to search. And I don't know how you would do binary search on a bunch of differently sized rectangles. But that is not the point. There is a correct answer to this question (in their mind, it may even be unique) and they probably are looking for someone who can give that (or at least get to) that answer (with/out some help from the interviewer). I think the answer was quadtrees in this case. $\endgroup$
    – Abdullah Ali Sivas
    Aug 23, 2021 at 4:08
  • 1
    $\begingroup$ Nevertheless, even though the binary search could be applicable here, it is your responsibility to convince them that it is a solution and a good one. That is a lesson I learned during my interviews, together with "If it is ambiguous to you, ask for clarification", "Don't be shy to ask 'can I refer to a source I know that contains the answer?'", "If you don't know, don't be afraid to say 'I do not know but I think...'" and "The interviewer is there to measure not only your capabilities but also your growth potential". $\endgroup$
    – Abdullah Ali Sivas
    Aug 23, 2021 at 4:13
  • 1
    $\begingroup$ I guess if you were given the coordinates of the squares, then you could sort them by their $y$-coordinates on top, you can do a binary search to identify the squares which may contain i,j and then sort those matrices by their $x$-coordinates a left then do another binary search to find the square you want. Initial sort would cost $O(K\log K)$ where $K$ is the number of the squares, then you are going to binary search on that which is $O(\log K)$, the rest of the operations may be negligible since they are sort and search on a smaller number of squares. The total cost is $O(K\log K)$. $\endgroup$
    – Abdullah Ali Sivas
    Aug 23, 2021 at 4:26
  • 1
    $\begingroup$ I'm going to look into all of this tomorrow morning. My brain is too fried right now to process this. Just letting you know so you don't think I ditched the discussion :) $\endgroup$
    – user5965026
    Aug 23, 2021 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.