With Youtube as a guide you could probably do it in 2-3 hours if it's your first build. Once you get it down, then the next time will be 30 minutes or so including the time to install an OS.

Might want to also look at pre-assembled boxes on newegg. You can get quality parts, but someone else does the labor of putting it all together for you. You'll pay a bit more but it could be worth it for you.

Is there a way to do that question in less than n^2? The question specifies that the array cannot be modified and the memory use must be constant.

Of course, a smart-ass would helpfully point out that assigning any intermediate variable, whether via functional or imperative means, uses extra memory, so the question, as asked, is invalid.

By the way, if there were only one duplicate there is actually a very neat O(n) solution. I'm trying to see if that's extendable to more than one number having a duplicate, but I don't think so.

ETA: when they say "constant memory" they don't mean you can't use any more. They just mean that it can't scale upwards with the size of the problem.

but the point is there's a tradeoff between time and memory here, and the problem is specifically asking for the constant memory solution.

constant memory doesn't mean you can't use any memory, it just means the memory has to be a fixed amount. as long as it's not growing with N, you can have a million variables and still be constant memory

i think i know the one you mean, and i don't think it can be extended. i will be pretty surprised and impressed if you can find O(n) constant memory solution to the problem which allows any number of duplicates of any of the elements.

creative ternary usage there!

Yeah I'm not really seeing anything. Too bad. It's funny though, because if that's not the solution they have in mind, they gave an irrelevant piece of information in the puzzle.

We didn't use left-pad or apparently have it as a sub-dependency. Or possibly we just didn't do any new builds that day.

It's a pretty rare occurrence and npm did the right thing by restoring right away. In the real world we'd have to get pretty unlucky to have a key module go down on the day we're trying to push a build to production. And even then we can probably just copy an old node_modules folder from a previous build, as we don't update our dependencies often.

Heh, we're still on node 0.12.5. I'm debating whether I want to take on the pushing 2 tons of mud uphill it's going to take to get our dev ops and ops guys to upgrade our 25-30 dev, test and prod environments.

We did get in trouble when a guy who had npm/pacakge/util or npm/packages/utils decided to just delete whatever was in his repo and replace it with a shell repo. (Park it basically) Took me a while to figure out why our builds were failing. Then I realized we weren't even using whatever it was anyway so I removed it. Looks like someone is doing something with the repo name now. He might have sold it.

That's the only time we've had any issues with npm weirdness. We use about 20 first-level npm packages for production and about 30 more for development (if you look into all those packages, sub-dependencies are probably 1000 or more).

I follow Forrest Norvell on twitter who is either Mr. NPM or close to it. He's incredibly responsive when I've had any questions or issues. That's reassuring.

Reading more on this I kind of like where people are ripping on developers for using an external software package to add padding to the beginning of a string. Probably not worth the risk, just write the damn thing into your code yourself or copy and paste it from somewhere.

I borrowed a similar-length piece of code when our app first got going to call multiple middleware functions in parallel as part of a larger middleware function. It didn't do exactly what I wanted, and it was so simple I decided to just copy the code and modify it for my needs. Checking later that repo isn't even on npm anymore, so that worked out well.

What's the Node mess you guys are talking about? Did an important module get an update that boned it or something?

You can set a dependency on a specific version of a module and not necessarily "latest", right?

Read the link in my post directly above yours for a recap.

Yes you can select any version. But if the author un-publishes the entire repo it doesn't matter (I think). Also you can't control sub-dependencies.

I don't do npm but is there not an option to essentially "install" npm packages from a local repo? That's what we do with all of our python dependencies. It's a little bit of a pain because if you want to add a library, you have to do a little magic to get it into the local repo, but after that, you're golden. (It's also a lot faster)

ETA: one of the annoyances of javascript sort of seems to be that there is not much of a "standard library", i.e. a set of basic library functionality that every javascript interpreter can be expected to have. Is that right? Is there any move to change that?

Yeah you need to install a local npm mirror and cache all the dependencies and sub-dependencies you need (or just d/l all of NPM). It's kind of a PITA. We got one sort of working because we wanted to host our company-specific node framework as a private repo (wouldn't make sense as open source).

But then I realized it's really hard to switch your local NPM client back and forth between the internal repo and external NPM repo. There doesn't seem to be a way to tell the NPM client to "Check my local repo first, then check NPM". Unless they recently added it or I missed something. This would slow our devs down a lot, not worth it.

I know putting it together isn't hard, I just don't know if I have time for all the research to get exactly what I want. I'll check out some of their pre-assembled stuff. I just found out today my budget is more like 1000 bucks, so I really wanna put more than a bare minimum effort looking into what'll be the best for me for the next 2-3 years.

I basically just want something that can play some games on reasonably high settings and something I can also code with and it'll last me a few years. The pre-assembled gaming pc's are kinda lackluster on the vid cards from what I'm seeing, at least in my price range.

Array is not sorted (otherwise this could be solved in a single traversal).

The optimal solution is O(n log(n)).

The O(n^2) solution is fairly trivial (for each element in the array, loop through the array and try to find a matching element).

I think I know your solution for one duplicate. Just sum up the numbers in the array as you are traversing through the array, and use that value to derive what the duplicate value is. Unfortunately this solution does not scale for multiple duplicates.

By 'constant memory', I only mean your solution cannot scale due to the size of the array. You are allowed to use additional memory. You can create additional in memory variables and for/while loops as needed.

--

Personally I feel this question is very hard and it's not fair to 'no hire' a candidate because they cannot answer this question in O(n log(n)) runtime.

Is the answer a variation on the max subarray algorithm? I'm guessing you are saying this is divide-and-conquer based on your runtime, but that requires splitting the array, which I'd assume, if asked, is not allowed.

Might be a relevant question when execution speed effeciency is critical like OS development. One alternative approach in an interview would be to ask the candidate about O(n log(n)) algorithms they are familiar with, the criteria that they would use to determine when it was necessary to use one, what overriding factors they would consider in using an alternative algorithm, how they balance conflicting coding goals. FWIW algorithm effeciency often runs counter to code maintainability and readability. I fully acknowledge that "readability" and "maintainability" are often determined in a qualitative manner. Guessing that a complexity evaluation program would shed some light.

to clarify:

1. constant memory
2. n log n running time
3. cannot modify the original array
4. array holds values between 1 and N-1, and has length N
5. 1 repeat is guaranteed by 4, but it's possible there could be N-1 repeats, or any other number

problem is to find 1 repeated value, doesn't matter which, correct?

The key here is dividing the range, not the array. If you divide the range into halves, you can search in linear time which half of the range contains at least one number that is duplicated in the array.

I've commenced the little home project I have that I'm going to learn to use Angular 2. Right now though, because I want to try out the whole MEAN stack I'm watching videos on node.js, express.js and MongoDB, none of which I have used before. The project is that I have a bunch of recipe files, already in JSON, and want to serve them to an Angular app that lets you do meal planning for a week and creates a shopping list, so it seems pretty tailor made for Mongo.

I'll report back on Angular 2 vs Angular 1.x.

Today is family day...tomorrow+ is project coding week. Yay

Ah, so the stipulation on the maximum size of the integers matters after all. I should have seen that probably. If someone insisted it could be done in nlogn I think I might have eventually come across it.

But I think it's a terrible interview question. It's the equivalent of something like crossword solving or something. The whole problem is the insight. Once you see the solution, programming it is really trivial. Forcing people to have insight on demand is really kind of bad form I think (but unfortunately really common)

I have forced myself to train for interviews by working on stuff like this - skipping the obvious solution entirely and trying to get to the optimal solution first. Because
a) if you show someone the n^2 algorithm and they're looking for nlogn they are not gonna be impressed at all
b) you just wasted X minutes writing something on the whiteboard that you're just gonna have to replace when they say "n^2 is too slow"
or worse... they might just smile and write you off.

And finally, the bad thing about it is that it doesn't filter what you think it does. Anyone who's seen the problem before is going to pretend to think about it for a minute and get it. Anyone who hasn't is either going to be someone who gets it quick (which proves what?) or isn't going to get it. I don't think it tells you anything interesting about the person.

If I couldn't derive it, I would semi-panic and probably just show them the n^2 algorithm and say "I know there's a better way to do this, it's just not coming to me right at this moment." but I'm pretty sure I had the exact same problem in my first semester of programming so meh.

My first semester of programming was about 20 years ago. Guess how many times I have needed to turn an n^2 algorithm into a clever nlogn algorithm since then.