Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lessons from 3,000 technical interviews

blog.interviewing.io

Post reply on HN
Print view View original

301–310 of 330 posts

Re: Lessons from 3,000 technical interviews

#301

Post by SomeStupidPoint »

timr wrote: post #284
SomeStupidPoint wrote: post #269

Earlier quoted context omitted.

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 crea…

"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 cert…

If your algorithm overflows counters and produces incorrect output as a result, then you don't have a correct solution.

There's no way to solve the unbounded stream case correctly with finite counters as you admit.

So you didn't actually present a bounded memory solution to the problem.

Re: Lessons from 3,000 technical interviews

#302

Post by n-exploit »

cr0sh wrote: post #289
forrestbrazeal wrote: post #71

The author draws a hard distinction between Udacity/Coursera MOOCs (good) and traditional master's degrees (bad). I'll interject that with Georgia Tech's Online Master's in Computer Science program [0], which is delivered via Udacity and insanely cheap [1], you can get the best of both! (Their "Computability, Complexity and Algorithms" class is one of the top Udacity courses cited in the article.) Keep in mind that a…

I so want to enroll and take the OMSCS; I know I could succeed at it if I took it, but the school requires you to have at least a Batchelor's degree to attend (they don't count work experience in software development - so my 25+ years mean nothing). I found out about the OMSCS after I started my work on Udacity's "Self-Driving Car Engineer" nanodegree course, which I am currently taking. My plan (hopefully) is after…

Western Governors University (non-profit, accredited, affordable) offers a few different B.S. programs that you could look at to use as a buffer. I received my undergraduate degree from WGU and highly recommend it. It's self-paced and there are ways to fast-track the degree in less than the typical 4 years.

Re: Lessons from 3,000 technical interviews

#303

Post by pklausler »

I conducts lots of tech interviews for SWE positions, and as everybody's boning up on algorithmic trivia, I've learned that I can get a stronger hiring signal by asking simpler questions that people with an aptitude for programming will succeed on and people with an aptitude for memorizing the implementations of algorithms will not.

(Simple example: given two closed intervals [a..b] and [c..d], how do you compare the four values to determine whether or not the intervals overlap? You may laugh, but it defeats about 50% of candidates in the first minute of an interview because they just don't understand simple relationships and Boolean expressions.)

Re: Lessons from 3,000 technical interviews

#304

Post by dsp1234 »

SomeStupidPoint wrote: post #299
dsp1234 wrote: post #287

Earlier quoted context omitted.

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…

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…

You can't have finite counters per word

You only need one counter per word.

a quick sketch of the basic algorithm is:

  1.) Create a new list of type  into COUNTS
  2.) Read a word from the stream into WORD
  3.) if WORD exists in COUNTS, then increment the number for that entry
  4.) if WORD does not exist in COUNTS, then add WORD to COUNTS with a number of 1
  5.) if not end of stream, goto 2
  6.) traverse through COUNTS keeping a running list of the top 10 highest entries (Note that this and step 4 can often be combined to keep a running total of the top 10) into TOPCOUNTS
  7.) print TOPCOUNTS
This algorithm is O(N) space where N is the number of distinct items, as I mentioned previously.

Re: Lessons from 3,000 technical interviews

#305

Post by timr »

SomeStupidPoint wrote: post #301
timr wrote: post #284

Earlier quoted context omitted.

"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 cert…

If your algorithm overflows counters and produces incorrect output as a result, then you don't have a correct solution. There's no way to solve the unbounded stream case correctly with finite counters as you admit . So you didn't actually present a bounded memory solution to the problem.

The number of bytes in a machine number is not the limiting factor here. You could use arbitrary precision numbers (with some constant factor of additional storage), and solve the precision problem.

Being pedantic about this point doesn't get you closer to a correct answer. Read dsp1234's responses. They are correct.

Re: Lessons from 3,000 technical interviews

#306

Post by odbol_ »

witty_username wrote: post #275
thomasahle wrote: post #249

Earlier quoted context omitted.

> So why can't it voluntary via donations to universities? You could say that about any tax founded expense?

For some things like courts and police it's required to stop violence and fraud; i.e. to maintain the rules of the game. But, yes, I am in favor of a small, limited government.

Education is perhaps more important for preventing crime and violence than police and courts are. Remember, police and courts just deal with the crime; they don't prevent it like having a proper education and employment does.

Re: Lessons from 3,000 technical interviews

#307

Post by timr »

dsp1234 wrote: post #295
timr wrote: post #284

Earlier quoted context omitted.

"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 cert…

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 qu…

Well, "algorithm" is just a way of saying "procedure", so a heuristic applies (IMO). I would accept a reasonable heuristic without much argument because the problem of random text is much harder...but honestly, if you got to this part, you've already passed the interview. A total flameout on this question is not even realizing that the storage scales with vocabulary size, instead of sequence length.

An exact solution to an unbounded sequence of purely random text probably does require unbounded memory (I say 'probably' only to hedge my bets here). But depending on the definition of "random", you can put pretty tight bounds on it and only be off by a little. I haven't done the math, but my gut says that a bloom filter, followed by incrementing counts only for positive hits from the filter, would scale well. There may be simpler approaches that make use of word length and the size of the latin alphabet (e.g. "all tokens of size N have 1/C(26,N) probability of colliding if letters are chosen from a uniform distribution, therefore...")

But again, if we actually had this conversation in an interview, there'd be no danger of not passing. Unless you were a jerk or something.

Re: Lessons from 3,000 technical interviews

#308

Post by manishyt »

blindhippo wrote: post #271
FLUX-YOU wrote: post #254

Earlier quoted context omitted.

Is he talking about this problem (with a filter at the end)? 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.

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.

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.c...

Re: Lessons from 3,000 technical interviews

#309

Post by jcadam »

blindhippo wrote: post #271
FLUX-YOU wrote: post #254

Earlier quoted context omitted.

Is he talking about this problem (with a filter at the end)? 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.

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.

Heh, at my previous employer the only coding question we asked during interviews was: "Find the largest element in an array of integers." Some of the ways people found to not solve that simple problem were amazing.

Now, I'm generally against asking hard-core CS questions in a live interview... but a simple bozo filter is probably a good idea.

Re: Lessons from 3,000 technical interviews

#310

Post by SomeStupidPoint »

dsp1234 wrote: post #304
SomeStupidPoint wrote: post #299

Earlier quoted context omitted.

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…

You can't have finite counters per word You only need one counter per word. a quick sketch of the basic algorithm is: 1.) Create a new list of type into COUNTS 2.) Read a word from the stream into WORD 3.) if WORD exists in COUNTS, then increment the number for that entry 4.) if WORD does not exist in COUNTS, then add WORD to COUNTS with a number of 1 5.) if not end of stream, goto 2 6.) traverse through COUNTS keepi…

Again, you're assuming count has a bound size per word, which isn't true for an unbounded stream.

Step 3 of your algorithm either requires unboundedness of count (ie, count can use arbitrary amounts of memory) or can overflow on arbitrary length streams of words (and hence, has cases where it produces the wrong output).

Post reply on HN