>be interviewer >find a decent candidate >ask him to

>>59734190
I love this new epic meme.

you are the interviewer but you dont get the job?

>>59734190
looks like a classic case of bipolar disoder

>>59736370
>tfw can't sum all primes above 2 million

>>59734190
>This is me
Worst part of cofounding a startup

int sum = 0;
for (int i=0; i<2000000; i++)
for (int j=0; j<2000000; j++)
if (i%j > 0)
sum += i;


Lol you faggots are fucking useless

>>59737437
kek

>>59737437
>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?

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

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

>>59734190
we already have this thread fegget

File: 1587.jpg (180KB, 3008x3306px) Image search: [Google]

180KB, 3008x3306px

*blocks your path*

>>59736562
Don't worry Anon, I can't either.

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

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

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

>>59738107
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.

File: Unsorted:V 35.jpg (324KB, 1600x900px) Image search: [Google]

324KB, 1600x900px

>>59738135
>>59738107
its oop you probably wouldn't understand

>>59737653
https://stackoverflow.com/questions/1538644/c-determine-if-a-number-is-prime
fag

>>59738206
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.

>>59738303
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

>>59738303
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.

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

>>59738333
>>59738338
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.

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

>>59738303
>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.

>>59738443
Explain sieves, though.

>>59738474
>>59738333

>>59738443
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.

>>59738338
>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.

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

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

pleb

I cannot be asked to remember sieve's algorithm

>>59738142
>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

>>59738580
Read the second half of that post, anon. 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

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

>>59738474
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.

>>59738142
pretty much every tech company hires software engineers this way

>>59738619
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.

>>59738142
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.

>>59738659
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.

>>59738717
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

>>59738693
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.

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

>>59738759
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?

>>59738811
>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.

>>59738941
>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.

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

>>59739069
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.

https://en.wikipedia.org/wiki/Amdahl%27s_law

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

>>59738941
>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.

>>59738617
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.

>>59738659
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.

>>59738941
>>59739155
>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.

>>59739155
>>59739270
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.

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

huh

>>59739306
>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.

>>59739369
>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.

>>59734190
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]

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

>>59739429
Never taken an algorithms course?

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

>>59739523
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.

>>59739535
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.

>>59736562
Oi can- it's infinity :^D

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

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

>>59739429
>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.

>>59738303
Dynamic programming

>>59739628
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.

File: 1400356788722.png (134KB, 334x393px) Image search: [Google]

134KB, 334x393px

>>59739668
>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.

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

>>59739796
>>59739823

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.

>>59739888
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

>>59739979
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%.

>>59739888
>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".