Be interviewer

>be interviewer
>find a decent candidate
>ask him to come in for an interview
>he comes in and I ask him to take a seat
>instead he rolls in a whiteboard and asks me to sum the primes under 2 million
>run home crying
>still haven't gotten a call back

Other urls found in this thread:

stackoverflow.com/questions/1538644/c-determine-if-a-number-is-prime
en.wikipedia.org/wiki/Amdahl's_law
twitter.com/SFWRedditImages

I love this new epic meme.

you are the interviewer but you dont get the job?

looks like a classic case of bipolar disoder

...

>tfw can't sum all primes above 2 million

>This is me
Worst part of cofounding a startup

int sum = 0;
for (int i=0; i

kek

>start at zero
>divide by zero
>add each i several times
try again

So, what is a good way to figure out if a number is a prime? Or are you expected to use some sort of premade function anyway?

you ask the number if he/she/xe/ze/ve/zie/fae is prime

>let's check if all numbers under 2 million are divisible by 2 million, because why not?

we already have this thread fegget

*blocks your path*

Don't worry user, I can't either.

12%5 is greater than 1, I guess this means 12 is a prime number.

if(i.isPrime())
j+=i;
if(i >= 2000000)
break;

>primality test
Slow as fuck compared to sieve, even with hashing.

is prime checks the list of primes I created with the sieve class before

>Go to interview
>Interviewer pulls out whiteboard and tells me to solve esoteric problems X and Y
>Thank him for his time and leave
I'm okay with doing a CS101 level problem like fizzbuzz, but if I'm asked to build a linked list of the Fibonacci sequence in ASM for the Motorola 86000 I'm not going to even consider solving the problem, even if I know I can do it. Places with such retarded interview practices simply don't hire good workers. They hire autists.

its oop you probably wouldn't understand

stackoverflow.com/questions/1538644/c-determine-if-a-number-is-prime
fag

So, you just go and divide every number by every number (smaller than it) and check if it's a prime that way? That seems inefficient and I assumed there was some better way.

there is a better way
remove all multiples of primes up the list until sqrt(n)
remaining numbers are primes

for example, first you remove all multiples of 2 then multiples of 3 then 5 ect

I can easily think of a way: Only divide by odd numbers. Even numbers (other than two) cannot be prime due to how we define even numbers, so changing the i++ to i+=2 just made it twice as efficient.

I read one a time ago but can't find it

It's still the same basic "test every number" thing though, but yeah I guess there are ways to make it more efficient. I meant to say I assumed there was a simple catch-all formula to calculate if it's a prime without needing to go through (nearly) every number up to it.

have a table of all prime numbers beforehand and only divide by primes :^)

>by every number (smaller than it)
No, up to sqrt(n). And that's trial division, inefficient but good for small numbers. Then there's primality tests like Miller-Rabin, which can be easily made deterministic up to 2^64. For finding a large range of primes, sieves are the only method.

Explain sieves, though.

...

Wouldn't sieves be less efficient than just brute force for smaller primes, though? Because you'd have to calculate all primes up to the number first, then divide the number by the primes.

>Only divide by odd numbers
You can't find odd numbers without testing if they're divisible by 2 (before or after the implementation). You might as well say the same for every other number.
You know 3 is odd, a PC doesn't unless you tell it it is: then you're just doing a step yourself, much more inefficiently.

if you're testing a single number maybe, I think sieve is best for finding a list of primes though

>not running sieve-of-even-numbers before prime sieve

pleb

I cannot be asked to remember sieve's algorithm

>Places with such retarded interview practices simply don't hire good workers. They hire autists.
then you'd fit right in

the interviewer gives even less of a shit than you about the problem, they just want to see how you work

Read the second half of that post, user. Change the i++ to i+=2 instantly prevents it from ever even trying to divide by even numbers.

tfw at last interview had to identify Sata cables

>sieve's algorithm
A sieve is an object, not a person. It would just be called a sieve algorithm.

Basically, you mark off multiples of primes up to the sieve limit. This works because any multiple of a prime is composite, and therefore any numbers not marked are prime. There are various ways to optimize this, with straightforward optimization being sieving only odds numbers (since primes are odd), not sieving primes above sqrt(n), and utilizing truth testing instead of an array of numbers, to more robust optimizations (needed for larges sieves), such as segmented sieves for memory and cache efficiency, incremental sieving, to wheel factorization for speedup.

pretty much every tech company hires software engineers this way

I know. And changing it to i++3 instantly prevents it from trying to divide by multiples of 3. Get where I'm going? You're just doing the division by two step in your head when you think to type that in. And that's a lot slower than a CPU will do it. %2 is the second one it tests, anyway, assuming you don't bother skipping i=1. it doesn't cut the time in half unless you test divisors randomly.

I think I'd have to excuse myself just because it's a fucking whiteboard. I write at less than 2% of my typing speed, so I would never finish programming on a whiteboard. Bring out a projector and a keyboard and I can do it.

every *big 4 tech company which doesn't worry about scaring away qualified candidates from their overflowing pool, and the moronic tech companies that copy them.

well If you can't work through an algorithm in a way that shows an interviewer how you think then you're probably an autist who can't handle social interaction anyway

Are you actually retarded? The linked algorithm would test EVERY number up to n. Changing it to i+=2 would stop it from checking all even numbers, thus cutting the number of operations in half.

You can't just ignore my post, retype yours, and expect it to change anything

You didn't address my point though, you just said that i%2 is the first one tested. What about i%4, or i%6, or i%8, or i%10, or i%12, ad infinitum? How would eliminating them not cut the number of operations in half?

>What about i%4, or i%6, or i%8, or i%10, or i%12, ad infinitum
It would never reach them, because it would fail on i%2.

In fact, one thing I said earlier was wrong. I said it'd be the second one you tested. But obviously you'd skip 1 because they're all divisible by on, including primes. So 2 would be the first you test.

Let's do some pseudo code:

>your implementation:
candidate is 5
not divisible by 2
or 3
or 4
therefore prime
add two to 5, it's 7
not divisible by 2
or 3
or 4
or 5
or 6
therefore prime
add two to 7, it's 9
not divisible by 2
but divisible by 3
therefore not prime
>etc

16 lines

>implementation without +2

candidate is 5
not divisible by 2
or 3
or 4
therefore prime
add one to 5, it's 6
divisible by 2
therefore not prime
add one to 6, it's 7
not divisible by 2
or 3
or 4
or 5
or 6
therefore prime
add one to 7, it's 8
divisible by 2
therefore not prime
add one to 8, it's 9
not divisible by 2
divisible by 3
therefore not prime
>etc

22 lines, not 32, not twice as long.

Now, assuming i+2 is as fast as i++ (it isn't), that's a fairly minor increase in speed for a not insignificant amount of engineer time which will decrease as the candidates get larger and are more likely to not be primes or even. And, with any sort of problem where you'd have to find primes (they don't exist) your engineer time is much more important than your execution time.

>assuming i+2 is as fast as i++ (it isn't)
What the fuck are you smoking? Adding 0010b is exactly as fast as fast as adding 0001b.

You can use only previously found prime numbers as divisors.
No need trying to divide shit with numbers you know aren't prime themselves.

It's not adding 1, it's incrementing. The former will get optimised to the latter by the compiler. Since it's so commonly used, it's highly optimised and faster than addition.

en.wikipedia.org/wiki/Amdahl's_law

Incrementing by one is faster than adding an arbitrary number. The compiler might actually choose to do (i++)++ instead of i+2.

>So 2 would be the first you test
No, you idiot. If you're using trivial optimizations, like only checking odd numbers, you'd start from 3 and increment in 2 (odd numbers), since any odd number isn't going to be dividable by an even integer regardless.
>that's a fairly minor increase in speed
You're wrong. Testing all numbers:
SUM = 2
for i in range(3, int(2e6), 2):
if not any(i % ii == 0 for ii in range(2, int(i**0.5)+1)):
SUM += i
print(SUM)

$ time python3 test2.py
142913828922

real 0m26.963s
user 0m26.948s
sys 0m0.004s
Testing odd for divisibility only:
SUM = 2
for i in range(3, int(2e6), 2):
if not any(i % ii == 0 for ii in range(3, int(i**0.5)+1, 2)):
SUM += i
print(SUM)

$ time python3 test2.py
142913828922

real 0m13.467s
user 0m13.452s
sys 0m0.012s
Twice the speedup, since you check only half the numbers of sqrt(n) for divisibility.

Autists make terrible programmers. Their code is generally not maintainable, and they have difficulty working with others on projects.
If you want to see how someone works a real problem, then give them a real problem, not a CS homework problem.

Big companies do because they're completely fucked and they cargo cult their interview process, just like they cargo cult literally everything. Through generally good pay, location, and law of averages, these companies inevitably get a few hero workers who pull 80 hour weeks to get projects done, but the environment is always toxic.

Good (general) interview problems:
>There's a bug in this code, find it.
>Implement this feature.
>Refactor this code to be more readable/maintainable.
Block model an architecture to solve this complex problem.
>Normalize this table.
>Give them a real production API doc and ask them how to query for something
>Have them gather project requirements from a "user". The user should be vague and drop tons of red herrings like a real user would. Make them dig for what the actual problem is.

The idea is to ask about things you can't cram for, and get results which are actually useful. Being an engineer is not about writing toy math code, it's about solving real world problems quickly, cheaply and safely, and always considering the full life cycle of a project. If you don't hire problem solvers then you might as well outsource to pooland.

>candidate is 5
>not divisible by 2
>it's 7
>not divisible by 2
Holy shit, I see you're actually talking about incrementing by 1 as well as testing all even ranges instead of just odd. This makes you retarded, since those are the two most trivial optimizations you can make.

I see what you mean now, I thought you just meant increment candidates by two. So I was wrong.

26 seconds for the slow version, though. Still less time than it took to write it.

>j starting at 0
>j not ending on i
>not breaking if it's not a prime number
>prime number check is wrong

huh

>26 seconds for the slow version, though. Still less time than it took to write it.
Because it's only 2 million. Try a billion with trail division - you're fucked. So the most you can do is optimize it trivially. And a sieve takes ~0.4s in Python for 2 million, and 0.01 seconds written in C.

>Try a billion
But you wouldn't with this method.

And only in internet forums or poorly thought out whiteboard interviews would you try to find n primes anyway since you might as well just copy what's been done before you by people who are finding primes of much higher orders with much higher efficiency than you ever would. And that's for any strange project where you actually need n primes.

Trivial optimisation for a write-once run-once program are largely pointless unless you're renting the CPU for a similar price point to the engineer's salary.

POST EM:
import math

rang = 2000000

xaxis = range(2,int(math.sqrt(rang)))
primeGrid = range(rang)

for ii in xaxis:
jj = 2
while jj*ii < rang:
primeGrid[ii*jj] = False
jj += 1

print sum([x if x else 0 for x in primeGrid][2:])[\code]

For any number N, test all uneven numbers starting from 3 up until sqrt(N). There's no need to test beyond sqrt(N).

Never taken an algorithms course?

Yes I realize, that doesn't change my comment.

Nope. Still a professional software engineer who knows what kind of interviewing questions aren't applicable to real world situations, though. But enjoy your higher Algos grades.

There's also no need to test non-prime numbers, so if you're on hardware with the memory to spare, you'd want to track the previously found primes. Don't think there's a way to make the division-test method any more efficient than that.

Oi can- it's infinity :^D

>Software engineering
Not even once, CE/EE mustard race

That's a job, not a course title, you mong. I got it with an (E)EE degree.

>Trivial optimisation for a write-once run-once program are largely pointless
You know why it's called "trivial"? Because it's the default goto optimization, in this case know to anyone with high school maths under their belt. E.g. you'd have to be a retard or go out of your way to fail these optimizations.
>since you might as well just copy
No. Code would never improve if that were the case. You're supposed to be able to able to implement an efficient optimized method to the best of your means, to test your abilities. And it's clear that you fail at even the most basics - just admit it. I mean, you're arguing that for suboptimal trail division just because you couldn't figure out how else to do it.

Dynamic programming

Why bother even thinking about it to save 13s of run time? How quickly can you implement the trivialities so the cost of your salary is less than the cost of computation?

>Code would never improve if that were the case. You're supposed to be able to able to implement an efficient optimized method to the best of your means, to test your abilities.

Yawn. This isn't a CS paper or a challenge to get the most efficient method. It's the real world. I spend many 13s of seconds shitting every day.

>Why bother even thinking about it to save 13s of run time?
Your method is the worst-case scenario for trial division. Those trivial optimizations amount to understanding of arithmetic and what a prime number is. You could ask a child on how to check for primes and they come up with that. How utterly retarded do you have to view this as not only valid but defend it? I've had enough of this banal discourse - arguing with an illiterate codemonkey who can't even read a wikipedia page on primes, much more do elementary arithmetic.

in the real world to be called an engineer you actually need to be able to optimize

Person A spends one minute writing a program to find the primes. It executes in 26 seconds. He moves on to the next task.

Person B spends two minutes writing the program: one for the basic loop, another for some simple optimisations. It executes in 13 seconds. 47 seconds after person A, he moves on to the next task.

Person C spends a day researching the quickest methods to list the primes in n numbers. To save extra time, instead of using Python (there's your fucking trivial optimisation) he uses C, compiles it, then manually edits the assembly to make it faster. He delves deeper, using specialised hardware and more targeted code for the task. A year and three papers later, he is finished. It takes less time to run the program than it takes for the PC to receive the interrupt from the keyboard telling it to run it.

Who is the most optimal here? Engineer time is much more valuable than computation time and is itself a variable to be optimised.

or person D who uses the correct algorithm the first time because his name isn't pajeet finishes faster than all those jokers gets a raise because he made you look like a god damn retard

Real jobs don't involve listing primes.

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

>Person B spends two minutes writing the program
They're combined with writing, by not considering anything but odds from the start, so it actually takes 1 minutes, and since they actually know what they're doing, they finish before person A even figures out what a prime is. Just fuck off and save face, you retard of an "engineer".