6 ms·

Is he talking about this problem (with a filter at the end)? http://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/ http://www.geeksforgeeks.

Is he talking about this problem (with a filter at the end)? http://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/ http://www.geeksforgeeks.org/finding-all-subsets-of-a-given-... Because I have never done that. That's different than just running through a list and picking out items that meet a criteria.

timr 10y ago
Not that I can see. The OP said: "find the subset in a given collection that matches this specific criteria" So basically, a loop through a single table. That's as simple as it gets. You can make the problem more complicated, of course (e.g. "write a method to find the minimum and maximum ages of the male users"), but it's still pretty simple stuff. A slightly less trivial "algorithm" question that should be equally easy for any decent programmer: I give you a document of english words. Write a function that counts the words, and returns the top ten words seen, by frequency. Now...solve the same problem when it's not a single document, but a stream of words of unspecified length. Don't run out of memory.
- SomeStupidPoint 10y ago
  I would like to see a solution to your problem with bounded memory. In particular, the case where I want the top 3 words, you don't know the length of the stream, and you get random permutations of the same 4 words until I stop emitting them (where I will end by emitting 3 to break the tie). That's not to say your problem isn't interesting -- just that while specifically constructing a problem as an example, you created one that's unbounded in required memory (in both storage per value and potentially number of values to store) and then demanded a solution that doesn't run out of memory. I think most interview questions are similar nonsense.
  - deleted 10y ago
    [deleted]
  - timr 10y ago
    "I think most interview questions are similar nonsense." It's probably a good idea to be careful with your words when you admit that you don't know the answer to a question. First off: your example (random permutations of the same four words) doesn't require much memory at all. So if you think it does, you're wrong. You might overflow your counters, but that's a different problem. A stream of random gibberish is certainly more challenging. But the cardinality of the English language isn't infinite (the OED has about 230k words, and that's with lot of words that nobody ever uses), so even a naive solution doesn't require "unbounded memory", as long as you take the problem statement seriously and don't do something ridiculous. That would be good enough to pass an interview. But OK, let's say you do have a stream of random latin-encoded gibberish. What then? The problem statement is that you have to determine the top-10 words (or in this case "tokens") by frequency. The cardinality of the set is infinite, but the probability of duplication per token is small, and the output set is tiny. Do you really think you need unbounded storage? In any case, even if you think a problem is "nonsense", it's probably true that the interviewer has thought about it more than you have. The part that frustrates you is highly likely to be the bit worth probing. A bad candidate will bomb out immediately; a decent candidate will provide a solid, if not perfect solution; a great candidate will solve the problem, see the broader theoretical aspects, and investigate those as well.
    - dsp1234 10y ago
      Do you really think you need unbounded storage? This is an example of a trap that interviewers run into when they try to arbitrarily reword questions. While I could be mistaken, an exact solution to the top-k problem requires O(N) space where N is the number of distinct items. I can trivially think of a stream of tokens that would defeat any reasonable computer in both available memory and general "storage" (ex: 1 quintillion distinct words, then the next 10 words are a duplicate of an existing word, then end of stream). Since you asked for an algorithm and not a heuristic, it's clear you are looking for an exact answer. So the answer is "Yes, I would need unbounded storage for the new question as asked". Since this is an interview, I'd expect that'd you'd want me to give you the technically correct, and accurate answer. I've tripped up enough interviewers who have tried to slightly reword questions, but ended up changing their meaning.
  - dsp1234 10y ago
    In the given case, it's actually the "English words" limitation that saves the question. An exact answer to top-k problems is O(N) is storage space where N is the number of distinct items. So since N is ~200k, it's not a terrible problem to deal with. When N is 3 as in your given case, it's not really a problem. The general case, of when the stream is unbounded in the number of distinct items, is much harder, say the stream is 1 quintillion non-repeating words, then starts repeating. This requires an approximation algorithm, but is not likely the solution that was looked for since the person specifically said "slight less trivial", and the streaming approximation algorithm is more complex. Though it could be still be saved by flipping the question back onto the interviewer's phrasing. They said "don't run out of memory", not "don't run out of disk space". So you could also solve this problem by, for example, writing the data into a database, then using SQL group by and top X functions to solve it once the stream has ended. But as an interviewer, I probably wouldn't be amused.
    - timr 10y ago
      Hah! Hell, I'd even give credit to the SQL answer, if it came with the rest. ;-) The only thing I'd add is that you can probably come up with a pretty simple heuristic or three to solve the problem for the case of truly random gibberish, without the need for elaborate data structures. But yes, this would be the answer of a great candidate.
    - SomeStupidPoint 10y ago
      You can't have finite counters per word, else you can't disambiguate between counter length of a single word then the pattern I described and just the pattern I described, despite the fact it impacts the answer. Your solution is incorrect because it fails to handle arbitrary length streams as specified -- as do the other glib answers. My point was the specification didn't seem to align with the intended problem, and that interviewers tend to make such mistakes on the description, and then get mad when you ask them to clarify if we're talking practice or theory. Similarly, you don't account for arbitrary proper nouns, which could theoretically be unboundedly introduced to an arbitrary sized English corpus. I guess you can debate which of these are "English" (itself a proper noun!), but interviewers often treat you as dumb if you don't divine their intent in such underspecified situations.
- sten 10y ago
  I'm hard pressed to imagine how this couldn't be done efficiently. Do you have an example which correctly solves the problem but takes too long? The only thing I can think of is something like the output rewriting an array on update over and over.
  - timr 10y ago
    Which problem? The first one? Don't underestimate the badness of the average interviewee. For the "find the min and max of a set" in particular, a lot of folks start out with terrible solutions.
    - sten 10y ago
      Well either I suppose. For the subset problem as you say a filter critera can be applied while looping through the collection. And that should be it. Now if the question was multiple criteria I could see the solution diverging rapidly. If the filter can be expressed as a rank we could sort the collection first and then binary search through it to find the boundaries. I suppose I'm just trying to imagine some way an interviewee may turn that into two loops, or three loops... more?
  - dsp1234 10y ago
    Do you have an example which correctly solves the problem but takes too long? Behold var AGESORT = rows.bubblesort("AGE ASCENDING") var AGESORT1 = rows.bubblesort("AGE DESCENDING") var MALE = "None" var MALE1 = "None" for row in AGESORT if row.isMale MALE = row break for row in AGESORT1 if row.isMale MALE1 = row break print "Min age: " + MALE print "Max age: " + MALE1 Stuff like this is usually the result of thoughts like "Ok, I'll break this problem into two, then combine the pieces. First I'll find the minimum age, which is easy once I sort the rows. Done. Ok, now I can see I can slightly alter that code so that it finds the max age! Now, I just put the pieces of code together, and do a little code organization to put like with like. I"
    - sten 10y ago
      Good point.
- icefox 10y ago
  Depending on the wording it looks like his go to intro problem is actually easier than Fizz-Buzz as it is just filtering. For example say it was "Given a set return a subset where the values are less than 10." (such as set.Where(i => i < 10))
blindhippo 10y ago
That's more advanced then the question I ask typically. Though I might use something like this if I'm interviewing someone with many years of experience (10+). As I explained above, my question is a warm up - meant to break the ice, calm nerves. But it's surprising to me how effective even a simple list traversal is at identifying weaknesses in a candidates programming ability.
- Roboprog 10y ago
  Depending on the platform, there's at least 2 ways to do that :-) E.g. - "functional" is simply something like: subset = filter( predicate, superset ) ... but on a "procedural" platform, it's a bit more challenging, starting with how much space to allocate for the result, or whether to mutate the input, and other wading through the swamp. But, yeah, I can see how it would get people to start up talking somewhere, or else go into "deer in the headlights" mode.
- manishyt 10y ago
  Just out of curiosity: how would you feel if I answered this question by using existing function [1] in stdlib? Would you consider that as (good) sign of knowing the tools or would you prefer a fresh implementation? [1] https://docs.python.org/2/library/itertools.html#itertools.combinations https://docs.python.org/2/library/itertools.html#itertools.c...
  - blindhippo 10y ago
    I see it as a positive if a candidate uses an existing solution to the problem. That's exactly what a good engineer would do in the real world. But then I take away the library/method and re-state the problem. Because the point is to see if they can understand the problem, and devise a solution.
    - manishyt 10y ago
      Cool. Thanks for your comments.
- 10y ago

timr 10y ago

Not that I can see. The OP said: "find the subset in a given collection that matches this specific criteria" So basically, a loop through a single table. That's as simple as it gets. You can make the problem more complicated, of course (e.g. "write a method to find the minimum and maximum ages of the male users"), but it's still pretty simple stuff. A slightly less trivial "algorithm" question that should be equally easy for any decent programmer: I give you a document of english words. Write a function that counts the words, and returns the top ten words seen, by frequency. Now...solve the same problem when it's not a single document, but a stream of words of unspecified length. Don't run out of memory.

SomeStupidPoint 10y ago
I would like to see a solution to your problem with bounded memory. In particular, the case where I want the top 3 words, you don't know the length of the stream, and you get random permutations of the same 4 words until I stop emitting them (where I will end by emitting 3 to break the tie). That's not to say your problem isn't interesting -- just that while specifically constructing a problem as an example, you created one that's unbounded in required memory (in both storage per value and potentially number of values to store) and then demanded a solution that doesn't run out of memory. I think most interview questions are similar nonsense.
- deleted 10y ago
  [deleted]
- timr 10y ago
  "I think most interview questions are similar nonsense." It's probably a good idea to be careful with your words when you admit that you don't know the answer to a question. First off: your example (random permutations of the same four words) doesn't require much memory at all. So if you think it does, you're wrong. You might overflow your counters, but that's a different problem. A stream of random gibberish is certainly more challenging. But the cardinality of the English language isn't infinite (the OED has about 230k words, and that's with lot of words that nobody ever uses), so even a naive solution doesn't require "unbounded memory", as long as you take the problem statement seriously and don't do something ridiculous. That would be good enough to pass an interview. But OK, let's say you do have a stream of random latin-encoded gibberish. What then? The problem statement is that you have to determine the top-10 words (or in this case "tokens") by frequency. The cardinality of the set is infinite, but the probability of duplication per token is small, and the output set is tiny. Do you really think you need unbounded storage? In any case, even if you think a problem is "nonsense", it's probably true that the interviewer has thought about it more than you have. The part that frustrates you is highly likely to be the bit worth probing. A bad candidate will bomb out immediately; a decent candidate will provide a solid, if not perfect solution; a great candidate will solve the problem, see the broader theoretical aspects, and investigate those as well.
  - dsp1234 10y ago
    Do you really think you need unbounded storage? This is an example of a trap that interviewers run into when they try to arbitrarily reword questions. While I could be mistaken, an exact solution to the top-k problem requires O(N) space where N is the number of distinct items. I can trivially think of a stream of tokens that would defeat any reasonable computer in both available memory and general "storage" (ex: 1 quintillion distinct words, then the next 10 words are a duplicate of an existing word, then end of stream). Since you asked for an algorithm and not a heuristic, it's clear you are looking for an exact answer. So the answer is "Yes, I would need unbounded storage for the new question as asked". Since this is an interview, I'd expect that'd you'd want me to give you the technically correct, and accurate answer. I've tripped up enough interviewers who have tried to slightly reword questions, but ended up changing their meaning.
- dsp1234 10y ago
  In the given case, it's actually the "English words" limitation that saves the question. An exact answer to top-k problems is O(N) is storage space where N is the number of distinct items. So since N is ~200k, it's not a terrible problem to deal with. When N is 3 as in your given case, it's not really a problem. The general case, of when the stream is unbounded in the number of distinct items, is much harder, say the stream is 1 quintillion non-repeating words, then starts repeating. This requires an approximation algorithm, but is not likely the solution that was looked for since the person specifically said "slight less trivial", and the streaming approximation algorithm is more complex. Though it could be still be saved by flipping the question back onto the interviewer's phrasing. They said "don't run out of memory", not "don't run out of disk space". So you could also solve this problem by, for example, writing the data into a database, then using SQL group by and top X functions to solve it once the stream has ended. But as an interviewer, I probably wouldn't be amused.
  - timr 10y ago
    Hah! Hell, I'd even give credit to the SQL answer, if it came with the rest. ;-) The only thing I'd add is that you can probably come up with a pretty simple heuristic or three to solve the problem for the case of truly random gibberish, without the need for elaborate data structures. But yes, this would be the answer of a great candidate.
  - SomeStupidPoint 10y ago
    You can't have finite counters per word, else you can't disambiguate between counter length of a single word then the pattern I described and just the pattern I described, despite the fact it impacts the answer. Your solution is incorrect because it fails to handle arbitrary length streams as specified -- as do the other glib answers. My point was the specification didn't seem to align with the intended problem, and that interviewers tend to make such mistakes on the description, and then get mad when you ask them to clarify if we're talking practice or theory. Similarly, you don't account for arbitrary proper nouns, which could theoretically be unboundedly introduced to an arbitrary sized English corpus. I guess you can debate which of these are "English" (itself a proper noun!), but interviewers often treat you as dumb if you don't divine their intent in such underspecified situations.
sten 10y ago
I'm hard pressed to imagine how this couldn't be done efficiently. Do you have an example which correctly solves the problem but takes too long? The only thing I can think of is something like the output rewriting an array on update over and over.
- timr 10y ago
  Which problem? The first one? Don't underestimate the badness of the average interviewee. For the "find the min and max of a set" in particular, a lot of folks start out with terrible solutions.
  - sten 10y ago
    Well either I suppose. For the subset problem as you say a filter critera can be applied while looping through the collection. And that should be it. Now if the question was multiple criteria I could see the solution diverging rapidly. If the filter can be expressed as a rank we could sort the collection first and then binary search through it to find the boundaries. I suppose I'm just trying to imagine some way an interviewee may turn that into two loops, or three loops... more?
- dsp1234 10y ago
  Do you have an example which correctly solves the problem but takes too long? Behold var AGESORT = rows.bubblesort("AGE ASCENDING") var AGESORT1 = rows.bubblesort("AGE DESCENDING") var MALE = "None" var MALE1 = "None" for row in AGESORT if row.isMale MALE = row break for row in AGESORT1 if row.isMale MALE1 = row break print "Min age: " + MALE print "Max age: " + MALE1 Stuff like this is usually the result of thoughts like "Ok, I'll break this problem into two, then combine the pieces. First I'll find the minimum age, which is easy once I sort the rows. Done. Ok, now I can see I can slightly alter that code so that it finds the max age! Now, I just put the pieces of code together, and do a little code organization to put like with like. I"
  - sten 10y ago
    Good point.
icefox 10y ago
Depending on the wording it looks like his go to intro problem is actually easier than Fizz-Buzz as it is just filtering. For example say it was "Given a set return a subset where the values are less than 10." (such as set.Where(i => i < 10))

blindhippo 10y ago

That's more advanced then the question I ask typically. Though I might use something like this if I'm interviewing someone with many years of experience (10+). As I explained above, my question is a warm up - meant to break the ice, calm nerves. But it's surprising to me how effective even a simple list traversal is at identifying weaknesses in a candidates programming ability.

Roboprog 10y ago
Depending on the platform, there's at least 2 ways to do that :-) E.g. - "functional" is simply something like: subset = filter( predicate, superset ) ... but on a "procedural" platform, it's a bit more challenging, starting with how much space to allocate for the result, or whether to mutate the input, and other wading through the swamp. But, yeah, I can see how it would get people to start up talking somewhere, or else go into "deer in the headlights" mode.
manishyt 10y ago
Just out of curiosity: how would you feel if I answered this question by using existing function [1] in stdlib? Would you consider that as (good) sign of knowing the tools or would you prefer a fresh implementation? [1] https://docs.python.org/2/library/itertools.html#itertools.combinations https://docs.python.org/2/library/itertools.html#itertools.c...
- blindhippo 10y ago
  I see it as a positive if a candidate uses an existing solution to the problem. That's exactly what a good engineer would do in the real world. But then I take away the library/method and re-state the problem. Because the point is to see if they can understand the problem, and devise a solution.
  - manishyt 10y ago
    Cool. Thanks for your comments.
10y ago