4 ms·

> But I wanted to appear smart, so I didn’t express any confusion. In fact some interviews are intended to flush out behavior like this. Give a candidate an am

by wging 11y ago

> But I wanted to appear smart, so I didn’t express any confusion. In fact some interviews are intended to flush out behavior like this. Give a candidate an ambiguous problem statement, and see if they ask the necessary clarifying questions. This meta-problem (ambiguous problems/unclear goals) happens all the time in the real world and bringing clarity to situations like this is a good skill to have.

x0x0 11y ago
True story of how an interview exploded for me: I'm asked to code a simple matrix in java. I ask about the fill factor, and get told quite low. The constructor takes the dimension and it's assumed square. I ask the interviewer if a csc matrix is ok, and he kind of says he's not sure what a csc matrix is. I tell him it's column sparse, and proceed to quickly write out, on a whiteboard, a simple csc matrix -- basically, an array of dimension columns of ArrayList of tuple <index, value>. The constructor is pretty much ArrayList<Tuple>[] columns; void SparseCSCMatrix(int dim){ columns = new ArrayList<Tuple>[ dim ]; } The interviewer then starts going at me because having, eg, a million columns requires an array with a million elements in it. I say yes, duh. He says it's quite inefficient -- what if I only use 10 columns out of the million? My response is, well, that's fine -- but what you're describing isn't a matrix. It turns out that what he really wanted was a HashMap from tuple: (x idx, y idx) to value, and that a typical load would be perhaps 1k elements in a space of 1 million by 1 million. We then go at it about whether I should have asked him to clarify, and I basically decide I don't have to play along with stupid gotcha questions so I told him words have meanings and a "matrix" with only 10 non-empty columns is not a matrix. And I don't have time for wankers. At least I learned what they were like fast...
- wging 11y ago
  I think I disagree. What he wanted can certainly be called a matrix. An m-by-n matrix has an entry for every (x, y), 0<=x<m 0<=y<n, but that's not a description of the way to represent a matrix in memory. That is an implementation decision. Of course I wasn't there, and I don't know the fine details that got you mad.
- sharth 11y ago
  It's certainly a matrix if the other elements are 0. If they have no value then a hash-map or what not makes sense.
- jholman 11y ago
  I agree that many words "have meanings", including "matrix" in general, and "CSC matrix" in particular. I think you have the wrong definitions for both. In my experience, "matrix" is a mathematical concept, and is independent of the implementation. As such, an extremely sparse matrix, such as your alleged interviewer described, is absolutely a matrix. And for such a matrix (density 10^-9), such a dictionary-style approach seems fairly reasonable. Next, it seems to me that "CSC matrix" is a particular encoding that works well for sparse matrices, that is not related to the code that you wrote. It contains no index/value tuples, and it consists of three top-level arrays (that, in the general case, are of different lengths). https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_column_.28CSC_or_CCS.29 https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_spars... http://netlib.org/linalg/html_templates/node92.html#SECTION00931200000000000000 http://netlib.org/linalg/html_templates/node92.html#SECTION0... http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csc_matrix.html http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/s... Actually, it's not obvious to me how to do arithmetic on it (without converting to a denser format), though the scipy docs say it's fairly efficient, so I'm having a little think about that. Interesting. Anyway, sounds like you're glad you didn't get that job, and I'd imagine that they're glad they didn't get you, so everybody wins.
  - x0x0 11y ago
    3 arrays is directly equivalent to an array of 2 arrays or an array of tuples of index,value. As for how it's efficient, that's obvious: column eg 3 will be an array of tuples like [(1,3), (11,17), (9936,3)] so there are nz values in locations [1, 3] = 3 [11, 3] = 17 [9936, 3] = 3 so csc makes it efficient to read down columns, ie right multiply by the transpose. My implementation makes it easier to update in the sense of inserting values at indices where previously the value was empty, since you only have to reorder a single column instead of all following data from top to bottom then left to right. Once finished inserting values, if ever, you may want to move to two packed arrays. What makes me shake my head is you don't understand what csc matrices are but didn't let that stop you from telling me I don't understand them. HN in a nutshell.

by wging 11y ago

x0x0 11y ago

True story of how an interview exploded for me: I'm asked to code a simple matrix in java. I ask about the fill factor, and get told quite low. The constructor takes the dimension and it's assumed square. I ask the interviewer if a csc matrix is ok, and he kind of says he's not sure what a csc matrix is. I tell him it's column sparse, and proceed to quickly write out, on a whiteboard, a simple csc matrix -- basically, an array of dimension columns of ArrayList of tuple <index, value>. The constructor is pretty much ArrayList<Tuple>[] columns; void SparseCSCMatrix(int dim){ columns = new ArrayList<Tuple>[ dim ]; } The interviewer then starts going at me because having, eg, a million columns requires an array with a million elements in it. I say yes, duh. He says it's quite inefficient -- what if I only use 10 columns out of the million? My response is, well, that's fine -- but what you're describing isn't a matrix. It turns out that what he really wanted was a HashMap from tuple: (x idx, y idx) to value, and that a typical load would be perhaps 1k elements in a space of 1 million by 1 million. We then go at it about whether I should have asked him to clarify, and I basically decide I don't have to play along with stupid gotcha questions so I told him words have meanings and a "matrix" with only 10 non-empty columns is not a matrix. And I don't have time for wankers. At least I learned what they were like fast...

wging 11y ago
I think I disagree. What he wanted can certainly be called a matrix. An m-by-n matrix has an entry for every (x, y), 0<=x<m 0<=y<n, but that's not a description of the way to represent a matrix in memory. That is an implementation decision. Of course I wasn't there, and I don't know the fine details that got you mad.
sharth 11y ago
It's certainly a matrix if the other elements are 0. If they have no value then a hash-map or what not makes sense.
jholman 11y ago
I agree that many words "have meanings", including "matrix" in general, and "CSC matrix" in particular. I think you have the wrong definitions for both. In my experience, "matrix" is a mathematical concept, and is independent of the implementation. As such, an extremely sparse matrix, such as your alleged interviewer described, is absolutely a matrix. And for such a matrix (density 10^-9), such a dictionary-style approach seems fairly reasonable. Next, it seems to me that "CSC matrix" is a particular encoding that works well for sparse matrices, that is not related to the code that you wrote. It contains no index/value tuples, and it consists of three top-level arrays (that, in the general case, are of different lengths). https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_column_.28CSC_or_CCS.29 https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_spars... http://netlib.org/linalg/html_templates/node92.html#SECTION00931200000000000000 http://netlib.org/linalg/html_templates/node92.html#SECTION0... http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csc_matrix.html http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/s... Actually, it's not obvious to me how to do arithmetic on it (without converting to a denser format), though the scipy docs say it's fairly efficient, so I'm having a little think about that. Interesting. Anyway, sounds like you're glad you didn't get that job, and I'd imagine that they're glad they didn't get you, so everybody wins.
- x0x0 11y ago
  3 arrays is directly equivalent to an array of 2 arrays or an array of tuples of index,value. As for how it's efficient, that's obvious: column eg 3 will be an array of tuples like [(1,3), (11,17), (9936,3)] so there are nz values in locations [1, 3] = 3 [11, 3] = 17 [9936, 3] = 3 so csc makes it efficient to read down columns, ie right multiply by the transpose. My implementation makes it easier to update in the sense of inserting values at indices where previously the value was empty, since you only have to reorder a single column instead of all following data from top to bottom then left to right. Once finished inserting values, if ever, you may want to move to two packed arrays. What makes me shake my head is you don't understand what csc matrices are but didn't let that stop you from telling me I don't understand them. HN in a nutshell.