Career Advice

[Digit]

He gave that hint that each value in the array can map to an index in the array

Then each index should be unique from 1 to n, right? Which means their sum would be (n)(n+1)/2. You could start with that value in your memory slot and go through the list subtracting each value's index field. If your memory slot doesn't have the value zero at the end, there's a duplicate, but you don't know where. Not sure if this idea's right, I just thought of it. Good luck!

[SMP]

I thought about that one as well. The problem is that there could be multiple duplicates. So, if it comes out to zero, then we know there is a duplicate; however, if it does come out to zero, the test is inconclusive.

And thanks for wishing me luck. But with regards to this question, it's not necessary. At this point it's just curiosity. I'll save the luck for future interviews.

[Digit]

I see. Well, if you ever get the answer to that duplicate problem, please post it here because now I'm curious too.

[Dragon Lady]

Don't worry, Yellow is nerding it out in his head right now.

[Yellow]

We have N numbers, from 1 to N. We're going to attempt to sort the list. If we succeed, we'll end up with '1' in the 1st slot, '4' in the 4th slot, etc. Normally, sorting a list requires examining each item and comparing it to at least log(N) of the other items. (Hence, O(N log N).) However, the ability to instantly know where a number should go simply by examining the number means we can skip the comparisons to other numbers. We'll just pick up numbers and swap them into place. If at any time the number we're swapping with is the same as the current number, then we've found our duplicate.

In pseudocode, it looks like this:

Code: Select all

For each position in the list:
  If the number in that position is correct, move to the next position
  Otherwise, do the following until the number is correct:
    Check the number in the place where the current number should go. If they're the same, STOP—you found your duplicate.
    Swap the current number into its correct position, moving the other number into the current position.
If you reach the end of the list without finding duplicates, you're good.

Each swap will put one number in place, so there are no more than N swaps. Since calculating the position to swap takes the same amount of time no matter how big N is, that part is O(1). All other operations are likewise O(1). So the algorithm has O(N) running time. The only extra storage is the amount required while doing the swap, since you have to store one of the numbers off in a temporary location while you overwrite its original.

I wrote up a python script to test it; haven't found any cases it can't handle. If you'd like to see some output of the steps it takes while running, I'd be happy to paste it in.

[SMP]

Dang. I was actually thinking of that during the interview, but for some reason I though it wouldn't work, so I moved on. It's hard to think clearly on the spot.

[Digit]

There's even a way to swap without using a temporary memory location, though in practice it's not more efficient. As shown here, to swap X and Y, you do

Code: Select all

X := X XOR Y
Y := X XOR Y
X := X XOR Y

You probably already knew about this, but there's another site with pretty challenging problems meant to be solved with math and programming skills called Project Euler.

[SMP]

So, after a few weeks of stress and anxiety, I am pleased to report back that I have accepted a job offer and start next week. I will be working at a pretty exciting startup, and I will be making quite a bit more money than I expected I would. I will also be getting stock options, which will potentially be quite a financial windfall in the years to come.

I had a couple other job offers, but this one seemed like an opportunity that I simply couldn't pass up, even though I expect that I will be extremely busy at this job (whereas the other offers seemed a little more balanced). The interviews were tough, but they were willing to accept that I am not an expert in computer science, and looked more at generally problem solving skills and such.

Obviously I won't know for sure until I've been at this job for a while, but right now I am thinking that quitting grad school was a very good decision.

Thanks everyone for the advice given in this thread.

[SMP]

Oh, and thanks Digit for introducing me to Project Euler. I don't think it helped me in finding a job, but it definitely made me stay up, literally, all night last week.

[NerdGirl]

Awesome! Congratulations! I'm glad things are working out for you.

[Katya]

Congrats!

[wired]

SMP: good for you. High education pricing is a bubble right now anyway.

[Digit]

Congratulations! Sounds like a great job. Yeah Project Euler can be addicting.

[SMP]

It's been more than a year since I asked this question, and just in case anyone cares, I thought I would let everyone known how things turned out. Or at least how things have turned out so far.

Basically, I have no regrets at all about my decision to quit grad school and take this job. Really, I should say decisions. Both the decision to drop out of grad school and the decision to take this particular job have turned out pretty well for me. I actually enjoy what I am doing much more now than when I was in grad school. Making a real salary instead of grad student salary is an added bonus. What's funny is, I always looked at grad school as something that generally improved your salary in the long run, because the higher earnings (and also greater opportunity for more interesting jobs) you can get with a graduate degree will more than offset the opportunity cost of grad school (that cost being the actual salary you make during those years, as well as the work experience and salary increases you get while on the job). I think that is definitely the case with physics, but I don't think it is true for computer science/software engineering. I really think the experience you get on the job is much more useful than what you would get in graduate school, and I also believe that salaries reflect that (I don't have actual data to support this, but from talking to the people I work with, this seems to be true).

Anyway, I thought I would share for the benefit of those who are interested, or anyone who is considering starting or dropping out of grad school.

On another note, if anyone with solid programming skills is looking for an interesting job, feel free to message me to find out more. I can tell you about the job and refer you if you are interested and it seems like you might be a match.

The company is a startup located in San Jose, CA. We develop software in the field commonly known as "Big Data".

(I apologize if this shameless recruiting attempt is inappropriate.)

[NerdGirl]

That's awesome, SMP! So happy it worked out for you.

[Whistler]

I'm glad it worked out for you too! Sometimes I wish I had completed my Master's though... I'll get over it.

[Katya]

Hooray!

[Yarjka]

Still in graduate school... you're tempting me.