Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
Search - "o(n^2)"
-
Me: *uses HashMap* for a problem to count some elements*
Lecturer: why are you using HashMap?
Me: it's the best way of solving the problem
Lecturer: I haven't explicitly taught you what a HashMap is so why are you using it?
Me: Because I learn outside of what university teaches me
Lecturer: there's another way to do this
Me: enlighten me
Lecturer: iterate through the array using a nested for loop and count as you go along
Me: why the hell would I want to do that? That literally decreases the efficiency of my program by alot
GG lecturer telling me it's a better idea of making my O(n) runtime into an O(n^2) instead of complimenting my code.
Seriously what the fuck is up with the fucking education system. Since when was it okay to teach students how to completely fuck your code up and promote ways of making your code so inefficient?33 -
Pessimist: a O(2^n) algorithm's performance decreases exponentially as input increases.
Optimist: a O(2^n) algorithm's performance increases exponentially as input decreases.2 -
(Interview for sde-3 position)
(continuation of https://devrant.com/rants/2132431/... )
Interviewer - *opens laptop. Gives a question.* solve this.
Me - *a bit surprised that such questions were being asked on a sde-3 level*
this is the 4th or 5th question from geeksforgeeks, isn't it? I know the answer to this. Do u still want me to solve it?
Interviewer - *not believing me* Yes
Me - okay. Well this *writing down the original solution mentioned on the site* is the verbatim code mentioned on the website, with complexity O(n^2).
However I feel this is not the optimal solution. Let me write a better solution.
*I provide a better solution*
This has a complexity of O(n log n) . What do you think?
Interviewer - Nope. This could be a lot better.
Me - okay. Let me see. Did some minor changes, added some caching (obviously this will have no effect on the base algorithm) etc
How about now?
Interviewer - nope. Still not good.
Me - okay. Can you tell me how to improve it?
Interviewer - no we are not allowed to solve problems for you. It is not our interview, it is yours.
Me - that makes no sense. Interviews are a two way street. I'd very much like to know the optimal answer to this.
Interviewer - okay
*copies down the answer from geeksforgeeks*
This is good
Me - *at first I thought this was a prank or something. *
I just mentioned this answer here.
Then I spent the next 10 minutes providing a BETTER solution.
May I know how yours is better?
Interviewer - this solution has 2-3 loops. Yours has a function calling itself.
Me - that's called divide and conquer using recursion mf!
Anyways let's take an example and do a dry run.
Interviewer - okay
*we do dry run*
Interviewer - oh yes. Yours ran faster. But it will run fast only sometimes.
Me - yes. Each time the algorithm rolls a dice to decide if it should run fast or slow. You have one goddamn awesome weed dealer man.
I got to go. Thank you for meeting me.14 -
I was asked to map a mathematical problem to an algorithm for first round of interview. I did it in 5 lines with O(n) and it worked. was told that was not the correct answer sent me an answer with O(n^2) and about 40 lines. in anger, I sent a five page mathematical proof along with analysis why mine was better. surprisingly, they took me in for second round. tanked it because I continually stuttered and froze. I was able to answer it once I got home. decided against sending it.1
-
Two big moments today:
1. Holy hell, how did I ever get on without a proper debugger? Was debugging some old code by eye (following along and keeping track mentally, of what the variables should be and what each step did). That didn't work because the code isn't intuitive. Tried the print() method, old reliable as it were. Kinda worked but didn't give me enough fine-grain control.
Bit the bullet and installed Wing IDE for python. And bam, it hit me. How did I ever live without step-through, and breakpoints before now?
2. Remember that non-sieve prime generator I wrote a while back? (well maybe some of you do). The one that generated quasi lucas carmichael (QLC) numbers? Well thats what I managed to debug. I figured out why it wasn't working. Last time I released it, I included two core methods, genprimes() and nextPrime(). The first generates a list of primes accurately, up to some n, and only needs a small handful of QLC numbers filtered out after the fact (because the set of primes generated and the set of QLC numbers overlap. Well I think they call it an embedding, as in QLC is included in the series generated by genprimes, but not the converse, but I digress).
nextPrime() was supposed to take any arbitrary n above zero, and accurately return the nearest prime number above the argument. But for some reason when it started, it would return 2,3,5,6...but genprimes() would work fine for some reason.
So genprimes loops over an index, i, and tests it for primality. It begins by entering the loop, and doing "result = gffi(i)".
This calls into something a function that runs four tests on the argument passed to it. I won't go into detail here about what those are because I don't even remember how I came up with them (I'll make a separate post when the code is fully fixed).
If the number fails any of these tests then gffi would just return the value of i that was passed to it, unaltered. Otherwise, if it did pass all of them, it would return i+1.
And once back in genPrimes() we would check if the variable 'result' was greater than the loop index. And if it was, then it was either prime (comparatively plentiful) or a QLC number (comparatively rare)--these two types and no others.
nextPrime() was only taking n, and didn't have this index to compare to, so the prior steps in genprimes were acting as a filter that nextPrime() didn't have, while internally gffi() was returning not only primes, and QLCs, but also plenty of composite numbers.
Now *why* that last step in genPrimes() was filtering out all the composites, idk.
But now that I understand whats going on I can fix it and hypothetically it should be possible to enter a positive n of any size, and without additional primality checks (such as is done with sieves, where you have to check off multiples of n), get the nearest prime numbers. Of course I'm not familiar enough with prime number generation to know if thats an achievement or worthwhile mentioning, so if anyone *is* familiar, and how something like that holds up compared to other linear generators (O(n)?), I'd be interested to hear about it.
I also am working on filtering out the intersection of the sets (QLC numbers), which I'm pretty sure I figured out how to incorporate into the prime generator itself.
I also think it may be possible to generator primes even faster, using the carmichael numbers or related set--or even derive a function that maps one set of upper-and-lower bounds around a semiprime, and map those same bounds to carmichael numbers that act as the upper and lower bound numbers on the factors of a semiprime.
Meanwhile I'm also looking into testing the prime generator on a larger set of numbers (to make sure it doesn't fail at large values of n) and so I'm looking for more computing power if anyone has it on hand, or is willing to test it at sufficiently large bit lengths (512, 1024, etc).
Lastly, the earlier work I posted (linked below), I realized could be applied with ECM to greatly reduce the smallest factor of a large number.
If ECM, being one of the best methods available, only handles 50-60 digit numbers, & your factors are 70+ digits, then being able to transform your semiprime product into another product tree thats non-semiprime, with factors that ARE in range of ECM, and which *does* contain either of the original factors, means products that *were not* formally factorable by ECM, *could* be now.
That wouldn't have been possible though withput enormous help from many others such as hitko who took the time to explain the solution was a form of modular exponentiation, Fast-Nop who contributed on other threads, Voxera who did as well, and support from Scor in particular, and many others.
Thank you all. And more to come.
Links mentioned (because DR wouldn't accept them as they were):
https://pastebin.com/MWechZj912 -
Jeff Dean Facts (Source: God)
Jeff Dean once failed a Turing test when he correctly identified the 203rd Fibonacci number in less than a second
Jeff Dean compiles and runs his code before submitting, but only to check for compiler and CPU bugs
Unsatisfied with constant time, Jeff Dean created the world's first O(1/n) algorithm
When Jeff Dean designs software, he first codes the binary and then writes the source as documentation
Compilers don't warn Jeff Dean. Jeff Dean warns compilers
Jeff Dean wrote an O(n^2) algorithm once. It was for the Traveling Salesman Problem
Jeff Dean's watch displays seconds since January 1st, 1970.
gcc -O4 sends your code to Jeff Dean for a complete rewrite -
List of shit my superior said and wrote in the project:
1. Prefer to write "pure" SQL statement rather than ORM to handle basic CRUD ops.
2. Mixing frontend and backend data transformation.
3. Dump validation, data transformation, DB update in one fucking single function.
4. Calculate the datetime manually instead of using library like momentjs or Carbon.
5. No version control until I requested it. Even with vcs, I still have to fucking FTP into the staging and upload file one by one because they don't use SSH (wtf you tell me you don't know basic unix command?)
6. Don't care about efficiency, just loop through thousands of record for every columns in the table. An O(n) ops becomes O(n * m)
7. 6MB for loading a fucking webpage are you kidding me?
Now you telling me you want to make it into AJAX so it'll response faster? #kthxbye2 -
The interface for time input in outlook Web on mobile is driving me crazy!! It's not as if there was a built in control that is well supported in all modern browsers.... Right
1. You can't tap on an hour to select it
2. You can only select by scrolling
3. The scrolling is "smooth scrolling". So you have N O fucking chance to select the time slot you wanted. After too much time has passed you just give up and accept that your meeting will be at 09:57
4. In order to go up in time you constantly activate the"pull to refresh" feature of Chrome.
I'm definitely no mindless MS hater but this I cannot tolerate.6 -
A server application pulled off some sort of listings as table. Problem was, it crashed with some thousand data files after one and a half hours. I looked into that, and couldn't stop WTFing.
A stupid server side script fetched the data in XML (WTF!) and then inserted shit node-wise (WTF!!), which was O(n^2) - in PHP and on XML! Then it converted the whole shebang into HTML for browser display although users would finally copy/paste the result into Excel anyway.
The original developer even had written a note on the application page that pulling the data "could take long". Yeah because it's so fucking STUPID that Clippy is an Einstein in comparison, that's why!
So I pulled the raw data via batch file without XML wrapping and wrote a little C program for merging the dumped stuff client-side in O(n), spitting out a final CSV for Excel import.
Instead of fucking the server for 1.5 hours and then crashing, shit is done after 7 seconds, out of which the actual data processing takes 40 bloody milliseconds!4 -
I want honest opinions. Do you think the following is a good or not so good interview question. Why or why not? Defend your argument.
Define a function where the input is a list of integers. It should find and return all the unique sets of three within the list that sum to x.
For example, given the list [1, 3, 2, 5, 6, 8, 10, 13, 15] and with x = 16, the function would return [(10,5,1), (13,2,1)]
If the candidate presents the trivial solution with time complexity of o(n^3), ask if can be done in o(n^2) or better.8 -
Programming contest assignments, first level:
1. "...if you don't know how to return values from a function, you can just print them"
2. "...if you don't know how to read files, you can assume data is in global variables"
3. Required recursion
4. "...and estimate its time complexity.", "You may pre-process the data, but use at most o(n^3)", "your algorithm must use under n^3 operations"
That escalated quickly!1 -
// Posting this as a standalone rant because I've written the best piece of code ever.
// Inspired by https://devrant.com/rants/1493042/... , here's one way to get to number 50. Written in C# (no, not Do diesis).
int x = 1;
int y = x + 1;
int z = y + 1;
int a = z + 1;
int b = a + 1;
int c = b + 1;
int d = c + 1;
int e = d + 1;
int f = e + 1;
int g = f + 1;
int h = g + 1;
int i = h + 1;
int j = i + 1;
int k = j + 1;
int l = k + 1;
int m = l + 1;
int n = m + 1;
int o = n + 1;
int p = o + 1;
int q = p + 1;
int r = q + 1;
int s = r + 1;
int t = s + 1;
int u = t + 1;
int v = u + 1;
int w = v * 2 * -1; // -50
w = w + (w * -1 / 2); // -25
w = w * -1 * 2; // 50
int addition = x+y+z+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v;
addition = addition * 2;
if (addition == w)
{
int result = addition + w - addition;
Console.Writeline(result * 1 / 1 + 1 - 1);
}
else
{
char[] error = new char[22];
error[0] = 'O';
error[1] = 'h';
error[2] = ' ';
error[3] = 's';
error[4] = 'h';
error[5] = 'i';
error[6] = 't';
error[7] = ' ';
error[8] = 'u';
error[9] = ' ';
error[10] = 'f';
error[11] = 'u';
error[12] = 'c';
error[13] = 'k';
error[14] = 'e';
error[15] = 'd';
error[16] = ' ';
error[17] = 'u';
error[18] = 'p';
error[19] = ' ';
error[20] = 'm';
error[21] = '8';
string error2 = "";
for (int error3 = 0; error3 < error.Length; error3++;)
{
error2 += error[error3];
}
Console.Writeline(error2);
}5 -
How do you explain to your client that no, you cannot have a perfect solution, because the algorithm is O(2^n)?
I mean, without requiring him to get a degree in CS. Also without making him think that you can't build efficient code because you're dumb. Or that the hardware is slow.3 -
Sometimes Im pretty impressed and envious by the skills of my fellow students.
Usually it looks like this:
me: So Uhm what u got for the <insert class here>?
him/her: Well its pretty simple algorithm which has big O of (Log(n)/1000000) which also mines bitcoin in the meanwhile and yeah, last night I figured out that it now generates electricity...
me: Uhm... My program prints Hello world... But backwards...
Like for real, sometimes I wish I find the motivation, to be awake 2 days straight just bursting with ideas of some crazy shit. Right now Im like 'You see that star behind that cloud? Jup it shines too bright, gotta get some sleep' -> Browsing devrant...2 -
When the monthly scrum retrospective reaches the 90 minute mark...
You know when people are being stress tested and they break by getting up, run around screaming and ultimately knock themselves unconscious by running into a wall?
That. I felt like doing that.
I swear someone activates some sort of gravity well when these meetings begin because time beings to stretch on and o........n....... while they meetings happen.
I began to list things I think I'd rather be doing than be in that meeting.
1) Tax returns.
2) Prostate exam (not old enough to need one yet but at least I'd be out the meeting).
3) Visiting the dentist.
4) Assembling IKEA furniture.
5) Watching soccer at least they have the decency to give you a break in the middle and I find sports as engaging as a dog turd on the sidewalk.
So bored was I that I began to notice notches and holes in the ceiling tiles and when I remarked upon them others became engrossed in them and began to speculate upon their origins.
I don't know who a speaker is, what department they are from, what product they're working on or what's so important about the algorithm they're working on. There is no context, no explanation and half way through a show and tell I had to check we were still in a show and tell.
I was bored shitless. I actually felt physical pain from boredom, I've not felt that way since I was a child.
I really, really hate that scrum is implemented in this way.
It left me with only half an hour of coding time left and really it sapped my energy and motivation to the point where I just went home early.
Excuse my language, but:
Fucking bloody cunting waste of time, I've had more productive moments in the restroom. They need to piss off or committed seppuku, ideally both. Dante got it wrong the seventh level of hell is this. I'm usually a very calm and balanced individual but yesterday, yesterday I just... Fuck! Argh! Fuck you meeting, fuck you.
If you are the type that schedules meetings like this:
May a thousand Jabberwockies plague your nightmares and be it that the next seventy seven times you lay with a human shall ye experience bitter failure! I hope Cthulhu himself visits his "enlightenment" upon you and you fear sleep henceforth.
I'm bringing a rubix cube or juggling balls into the next meeting so that I can say at least I learned something and it wasn't time wasted.3 -
My last week of vacations. A brake on bussiness programing... lol
Monday:
Receive a phone call from a colegue:
Hi the equipment it not working.
Me: ( upset with the acuracy) reboot that shit!
Colegue: Its working. Thank you.
Me: 😲😨😵😱
Today (Thursday):
Collegue: The printer is not working!
Me: 😡 Im on vacation. Check the cable or try to reinstall the printer...
Colegue: Its working. Thank you.
Me: 😱😱😱😱😱😱😱😱
2 fucking hours later:
Collegue try to call
Me: Did not answer... 😡 Fuch this shit.
Colegue send text message saying that they had a problem on the video projector but its ok now..
Me: 😠😡😢😢😢
I'M ON V A C A T I O N3 -
"f(n) is O(g(n)) if c and n0 f(n) <= cg(n) for all n > n0".
I have a couple of questions related to this equation.
1: why we use this equation?
2: which thing cg(n) is represented for?
3: what is the real-life example of this?10 -
That feeling when you are writing code and can't figure out anyway to make it better than O(n^2) and then suddenly you figure out how to do it waaaay better in O(1) :')
-
Optimization concepts/patterns or instances?
For pattern its gotta be any time i can take a O(n^2) and turn it into O(n) or literally anything better than O(n^2).
Instance would probably be the time that we took an api method that returned a json list made up of dictionaries CSV-style and changed it into a dictionary with the uid as the key and the other info as key-value pairs in a sub-dictionary. So instead of:
[
{
"Name": name,
"Info":info
}
]
We now return:
{
name:
{
"Info": info
}
}
Which can, if done right, make your runtime O(1), which i love. -
1. O(n)
2. Container queries
3. Supercomputer with a bunch of GPUs/TPUs running for free (solar, wind power)
Genuinely thanks!