Hacker News Reader

Comment by smsm42 | Hacker News Reader

I interviewed at Facebook and the tech part was completely sane and appropriate, the technical task was a bit fizzbuzzy but not something you'd need to spend nights digging into obscure algorithms book, but rather simple task which required some thinking, but not too much of it. No experience with Google or Netflix. As of looking at CV, I've seen people with great CVs that proved utterly useless and of course the opposite too. CV can be very misleading, both unintentionally and intentionally. You need to speak with the person.

View on HN

The issue with that is that if my CV is incredibly specialized in one area that happens to match the job I’m going for (eg compilers), why test my knowledge in designing things like a distributed system and in how great I do dynamic programming (that is not useful in my area)??? It feels like there is no verification at all of what my CV claims, nor does it give me a chance to show off the skills I’ve been working on for them last 20 years, both of which are very relevant to the job. Instead, I’m tested on what I knew when I graduated with my BS, and that’s it; it’s like my PhD was a waste.

In larger corporations it may not be 100% finalized where you would end up.

Knowing that yes, you master compilers (that's usually quickly determined, potentially fast enough for you not to notice it since you live and breath compilers), have basic knowledge in smashing together enough html tags to build a simple dashboard but you never had to deal with processes that spanned multiple computers, allows more flexible allocation:

Ideally, they'll give you a compiler related task, but if they find someone even more suited for that one open position in compiler internals, they might offer you a job in the adjacent compiler-as-a-service team where you'd start out doing dashboards and then move to whatever more complex task needs work.

But they won't need to bother offering you the distributed systems position that scales up the compiler-as-a-service product across the whole world without sending you to some training first.

I’m not going to take the job if I don’t wind up in a group working on problems that interest me. That is part of the bidirectional interview right? I hesitated even applying to a big Corp until a few people there convinced me they had problems right up my ally. I don’t want to work at big corp just to be working at big corp!

The hiring pipeline at every big company I've been at is not always the same. Yeah, part of it is always just a big funnel that takes general applicants in and assumes they might end up anywhere in the company. But, there is also going to be a way for specialized teams to hire specialized candidates. If you find yourself in the big funnel, by all means, just tell them you aren't interested if that's not what you want. If you want to work on compilers, you need to find a way to get into the pipeline for a compiler team, and that's not really much different than finding a job with a small company.

Yes, I already did this with Amazon who hires for specific roles, but the recruiters I’ve dealt with seem to be into bait and switch (substitute very appropriate role I applied for with something completely inappropriate).

The job opportunities are definitely out there, but many of them really require a referral (the JDs aren’t posted), and even then you might have to do a generalist interview because the company is not capable of doing anything else.

Because at big corps engineers might get assigned interviews as a routine work. And any engineer has their favourite questions that they know the answer to. They dont want to take.the extra effort and come up with new questions just to adapt to your profile or expertise. It goes the other way around. I.e.the interviewer is not going to do.extra work to validate the candidate but the candidate has to prove him/herself. Take it or leave it.

The one size fits all interview at a big corp is game-able at least, with plenty of practice material available online. It isn’t a huge hurdle if you have a month or two to practice, but that makes the whole process even more questionable.

I tech screened at Facebook and the whiteboard question was to partially implement a regex parser.

Meanwhile some of us are just happy if candidates know of the existence of regexes, even if they forgot the exact usage, and can mention using them rather than trying to write a parser from scratch when given a problem statement of extracting phone numbers of various formats from several thousand unstructured files of web page scrapes...

How partially? I could probably do a very simple one, without backtracking (though they'd need a big whiteboard if they want full code there) but if it's something like PCRE then I don't think Facebook headquarters have enough whiteboards to fit the code :)

Though I just realized "regex parser" can mean either "parsing some text using regex" or "code that compiles regex syntax into some kind of data structure but does not actually do anything else". The latter obviously is a much easier task.

The question was: Write a method that can take in a regex and a string and return whether the string matches it, with the regex limited to the characters . * ? (And backtracking is definitely where I started coming unstuck)

If the regex is really just a sequence of dots followed by a question mark, asterisk or nothing, thus cannot contain literals, the only thing you need to check for is the length of the string.

The minimum length will be the number of dots without a quantifier (i.e. exactly one character). If there is any dot followed by an asterisk, there is no maximum length. Otherwise, the maximum length will be the minimum length plus the number of dots followed by a question mark.

Writing the code for this is left as an exercise to the reader. ;)

The regex can be any string made up of any number of those three characters in any order.

Ah, that's definitely different than I understood your first post. You're writing a regex to match a given type of string. The regex parser is in the language itself, consuming what you've written and evaluating it.

No, I was writing the regex parsing code. The regex was one of the inputs.

It's neither. There's a DP solution for this problem and a recursive solution without memoization (with exponential complexity). The shortest solution I have seen was 18 lines of code.

Please show me a regex parser in 18 lines of code! Even 36! I did this exercise once and it took 100s of lines, I think using C++... but it's been a long time. Maybe it's significantly shorter in Python? But still 18 lines is impressive.

I probably screwed something up, but here's a 16 line attempt in Python, where the regex specials are limited to .?:
def matches(pattern, s): if len(pattern) == 0: return True c = pattern[0] assert c not in ("*", "?") if len(pattern) > 1: if pattern[1] == "?": return ( len(s) > 0 and c in (".", s[0]) and matches(pattern[2:], s[1:]) ) or matches(pattern[2:], s) elif pattern[1] == "*": for i, d in enumerate(s): if c not in (".", d): break return any(matches(pattern[2:], s[j:]) for j in range(i, -1, -1)) return len(s) > 0 and c in (".", s[0])

Pretty much something along these lines, except it's also required that both pattern and s end at the same time for a full match (this complicates the base case a tiny bit). The C/C++ solution looks more elegant because you can use pointers. Note that this particular version requires no prior knowledge of the algorithm and can be solved on the spot fairly easily.

Thanks for the demonstration!

This is LeetCode #10, this is a common question.

I got this same question from 2 other companies.

A simple one isn't that hard to put together in an Hour. I've gotten this and thought it to be mildly interesting.

You don’t even have an hour in an initial tech screen.

Reply on news.ycombinator.com