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

Don't write on the whiteboard

jperla.com

Post reply on HN
Print view View original

91–100 of 118 posts

Re: Don't write on the whiteboard

#91

Post by jodrellblank »

ljlolel wrote: post #76
jodrellblank wrote: post #70

Earlier quoted context omitted.

Setup a hashtable of keyword -> wikipedia link. Check every word in the document against it. One check per word should be O(word count) ish, shouldn't it? Hashing every word will have a cost, but will be roughly the same for each word so I'll brush it aside as a constant, setting up the hash will have a cost, but shared over the number of documents to check. Checking every word sounds expensive but so does looking ev…

That works if each phrase is one word. Many (most?) of the terms in the vocabulary are multi-word phrases. How would your algorithm work for multiple word phrases? What is its running time?

It would have to be altered; let's see:

Create hashtable where the key is the first word and the value is (rest of sentence, link). In the case of collisions, a list of rest of sentences and links.

Checking the document would still go word by word, if no lookup fine, if one result compare the rest of phrase with the following document words, if a list, do that repeatedly.

Runtime varies a lot with distribution of input phrases - if there are 50,000 beginning "phospholipid" that's not good.

I don't know how to estimate the runtime well, best case is no matches or single word phrases, and then as above. Worst case is every document word matches a long list of phrase endings but none of them complete, but even then the searching is only searching a fraction of the phrases in len(longest-phrase) chars of the document.

O(doc_words * num_of_phrases_by_prefix * avg_phrase_length)

I'm uncomfortable here, wishing I had more algorithm/data knowledge to draw on, and maybe wouldn't have gone down this route had I paid attention to many words from the start. Every problem doesn't need a hashtable. Maybe phrase-trees...

Re: Don't write on the whiteboard

#92

Post by psykotic »

reledi wrote: post #87
barkingllama wrote: post #11

Earlier quoted context omitted.

I'm glad the author mentioned Project Euler... I've never heard of it. Anyone else have experience with these problems? Is it a good way to improve your development skills?

Here's a list of sites I keep for ACM ICPC preparation or problem solving for fun: http://livearchive.onlinejudge.org http://coj.uci.cu/OnlineJudge http://www.spoj.pl http://uva.onlinejudge.org http://acm.timus.ru http://acm.sgu.ru http://acm.zju.edu.cn http://plg.uwaterloo.ca/~acm00 http://cs.stanford.edu/group/acm http://dwite.ca https://www.facebook.com/careers/puzzles.php http://code.google.com/codejam/contests.h…

You left out Berkeley's annual programming contest:

http://www.cs.berkeley.edu/~hilfingr/programming-contest/

The bottom of the page also has links to problem sets from a bunch of other contests.

Re: Don't write on the whiteboard

#93

Post by SatvikBeri »

286c8cb04bda wrote: post #68
SatvikBeri wrote: post #65

Earlier quoted context omitted.

How often do you hear of a programmer saving a company millions of dollars/thousands of man-hours and receiving no reward for it? All the time! Excellent performance (saving the company ~$3MM) at my last job merited me a 15% raise. Learning and applying negotiation skills made that an 80% raise. Presentation matters.

The first time I read your comment I thought it was disagreeing with the parent post. Upon thinking about it, I now believe that you are agreeing with him. Right? I'm not trying to criticize your post, but I hope someone could point out why I read it so wrongly -- if there are attributes why make it more likely to be read that way, or if there's something flawed in my perception.

I am agreeing with the parent and disagreeing with the grandparent post.

I think the confusion comes from the "How often do you..." which is frequently used sarcastically-although in my case I meant it literally.

Re: Don't write on the whiteboard

#94

Post by psykotic »

Herring wrote: post #57

Did anyone get the O(document size) solution? I can't see how it would work without checking each word against the list.

Yet another approach: Translate the regular expression for the disjunction of the search terms into a DFA. Then traverse each document with the DFA to find all matches. Traversing a string of length n with a DFA takes O(n) time regardless of the DFA's size.

The DFA turns out to be basically the same thing as the trie. Indeed, the standard DFA construction factors out common prefixes of the search terms, just like a trie. But this formulation has the advantage that anyone can implement it in a few minutes with their language's regex library. In Python you might do something like this:

    def searcher(terms):
        pattern = r"(?:^|\s)(%s)(?:$|\s|,|\.|!|\?)"
        dfa = re.compile(pattern % ('|'.join(map(re.escape, terms)),))
        return lambda string: dfa.findall(string)
This snippet also tries to deal properly (if simplistically) with search term occurrences bracketed by whitespace and punctuation.

As a side note, the problem didn't specify whether matches could overlap. Actualy, it isn't even solvable in O(n) time (plus precomputation) if overlapping matches are allowed. Let's say the search terms are "a", "aa", "aaa", etc, and the search string consists of n copies of "a". Then every substring of the string is a match and so there are O(n^2) matches, which obviously cannot be listed in O(n) time.

Re: Don't write on the whiteboard

#95

Post by HoLyVieR »

barkingllama wrote: post #56
Jabbles wrote: post #30

Earlier quoted context omitted.

Whenever I recommend Project Euler to people wishing to practise coding I always caveat it by saying "the first 50 problems are useful". After that Project Euler quickly becomes more mathematical, which is great if you wish to practise your maths skills, but may not be what you're looking for. There are exceptions, of course, and some questions may require implementing an important algorithm, but it is difficult to t…

Thanks for the advice... I was looking at the last pages and I've got no clue what's going on.

If your someone who isn't very experienced in mathematics, it's better to do them in order (easiest to harder) that's how your suppose to progress. If you're starting with the last one, it's normal you feel lost, it's like starting mountain climbing with the Mount Everest.

Re: Don't write on the whiteboard

#96

Post by tptacek »

edw519 wrote: post #9

Sorry OP, I realize that you're just trying to be helpful sharing what's worked for you and I appreciate that, but frankly, I hate posts like this... I think the best preparation for any interview is to simply get good at what you do. All the rest is window dressing that distracts from that goal. Every minute spent practicing interviewing would be better spent building stuff. The natural byproduct of this will be exe…

Wow, couldn't disagree more. "Ask for paper" may be the single most pragmatic and useful interview tip I've ever gotten on this site. I grinned ear-to-ear when I realized that was the point he was making.

The Project Euler stuff I could go either way on, but I thought this was such a great post.

Re: Don't write on the whiteboard

#97

Post by MrMan »

is the OP a professional employee/interviewee or something? the energy spent preparing for (seemingly countless) interviews could have been spent working on things s/he is passionate about.

Re: Don't write on the whiteboard

#98

Post by dlevine »

I have dinged people because they wouldn't write on the whiteboard. To be fair, every time this actually happened, I gave the candidate the chance to write his solution on paper, and I ended up dinged him anyways because his work was sub-par.

At every company I have worked at, from two-person startups all the way to Google, we have used whiteboards extensively. Most meetings and architecture reviews are conducted in front of a whiteboard. The first thing I do when I found a startup is to buy a whiteboard and nail it to the wall. Whiteboards are a necessity for collaborative brainstorming and working together.

I'm not sure I agree with anything the OP says in this article. I think he's trying to sound smart and rationalize the reasons he didn't get hired. I say this not as a troll, but to provide constructive feedback. If you want to get hired by a big company, you have to play by their rules. End of story. There are a few exceptions (like engineers at Google without college degrees), but they are exceptions - most people who work for Google or Facebook or Palantir went to good schools, and did well, and wrote on the whiteboard during their interviews.

Re: Don't write on the whiteboard

#99

Post by [deleted] »

larelli wrote: post #66
Herring wrote: post #57

Did anyone get the O(document size) solution? I can't see how it would work without checking each word against the list.

At first glance I don't think you can achieve O(document size) without some form of preprocessing. Each word in the vocabulary has to be looked at, so a natural lower boundary seems to be O(document size + vocabulary size). Also it is unclear what will count as an atomic operation. Although the description reads as if word comparisons were counted, this makes for another simplification, as words could be of arbitrary…

[deleted]

Re: Don't write on the whiteboard

#100

Post by [deleted] »

larelli wrote: post #66
Herring wrote: post #57

Did anyone get the O(document size) solution? I can't see how it would work without checking each word against the list.

At first glance I don't think you can achieve O(document size) without some form of preprocessing. Each word in the vocabulary has to be looked at, so a natural lower boundary seems to be O(document size + vocabulary size). Also it is unclear what will count as an atomic operation. Although the description reads as if word comparisons were counted, this makes for another simplification, as words could be of arbitrary…

[deleted]
Post reply on HN