>tfw it took me 30 fucking minutes to do this problem I fucking suck. How long will it take Sup Forums? Don't bother if you've already done this problem please.
Retard brute-forcing comparisons don't count and neither do functions like ^(1/2) or any other cheap tricks.
Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt. Example 1: Input: 25 Returns: True
He said no brute-force comparisons. That's not even the efficient way to go, faggot. You start from 1 to input/2 when verifying.
Parker Russell
It's an interview question you retard, and a pretty common one at that.
I'm not even a CS major nor am I in school at the moment. >b-but memes.
David Parker
shit skipped that line
Brody Evans
Because checking numbers inbetween input and input/2 is retarded and redundant(for input>1), forgot to add.
Jack Rivera
/** C Program to check Perfect Square **/
#include
int main() { int a, n; printf("Enter a number: "); scanf("%d", &n); for(a = 0; a
Gavin Flores
I googled the answer. I have a masters degree in CS. The solution using Hensel's Lemma is not a basic interview question/homework, you faggots.
Parker Gray
damn im bored
less o d d n u m b e r s
literally 10 seconds
Jackson Morris
it's nothing crazy as far as big four interviews go.
you have a masters in CS and gave up that quick?
Austin Parker
function isSqrt(x) { return Math.round(Math.sqrt(x)) ** 2 == x; }
Luke Smith
>Efficient solutions don't count
Joshua Evans
what does this even mean user
Michael Adams
Your first mistake is thinking anyone in here will give you an honest answer about their coding experience, logic solving skills or general intelligence.
The time it took you does not matter unless you're under certain contractual time constraints or some malady that is greatly reducing your life span.
What matters is you learn from it. Go fucking learn.
Noah Carter
well shit user this isn't that binary, if you have some impressive tricks that involve a little guessing feel free to post it.
Jason Hall
I already figured out the solution and I did learn user.
I just thought it was a very interesting problem that some people on Sup Forums may enjoy. It's good practice and i'm curious to see the extent of difficulties that people have on here.
We've fucking had enough fizz buzz memes, get coding faggots.
this is my solution too, as a CS undergrad. is this not the solution??? you can use some conditions to prevent checking really low numbers for really large numbers, though obviously that breaks down eventually for very high values.
maybe it should try squaring n/2, then n/4, then n/8 till it gets a value
Joseph Long
What an elegant, intuitive and intelligent solution. Stop being smartasses on the internet.
private final static boolean isPerfectSquare(long n) { if (n < 0) return false;
switch((int)(n & 0x3F)) { case 0x00: case 0x01: case 0x04: case 0x09: case 0x10: case 0x11: case 0x19: case 0x21: case 0x24: case 0x29: case 0x31: case 0x39: long sqrt; if(n < 410881L) { //John Carmack hack, converted to Java. // See: codemaestro.com/reviews/9 int i; float x2, y;
x2 = n * 0.5F; y = n; i = Float.floatToRawIntBits(y); i = 0x5f3759df - ( i >> 1 ); y = Float.intBitsToFloat(i); y = y * ( 1.5F - ( x2 * y * y ) );
No it's not. It's literally calculating all square roots until whoopty fuckin' doo you have a match. In a real interview they would eventually steer you towards what the correct answers look like because it's trivial to just do monkey guessing even if you do some chopping off at parts
There is a VERY elegant and distinct solution to the problem. Might even be several. When you get the answer you'll know it right away.
Easton Cooper
Post it then, you dumb asshole.
John Miller
he's probably talking about binary searching the actual root, given some decimal point you take out off your ass. Or just generating all the squares and checking (i from 1 to whatever, i+=2, s+=i if input==s, 1, input
Dylan Barnes
big-ol precomputed table.
Probably a RLE encoded thing would work well.
Parker Hall
You could change (a
Zachary Edwards
Yeah fuck no. It's interview time faggots. If you can't figure it out too bad.
Learn to spot regularities. That should be the first thing that comes to one's mind if you have any mathematical competence and look at this type of problem. Or you could learn to google.
Chase Anderson
You're clearly talking about the odd number adding up solution then. Calculate your execution time you fag, is this an interview for IT manager at burger king?
Xavier Rivera
it has nothing to do with caching or having some kind of buffer or table to refer to. Jesus fuck you guys would have people laugh at you in the competitive interviews.
It's just about one level above having if statements for every number in fizz buzz.
Nicholas Adams
You either cannot properly read comments, don't have basic understanding of the english language or are trolling.
Gabriel Gutierrez
so you don't know what you're talking about, got it.
Charles Hughes
I thought about it a little bit more, should I use newton's method? if i do enough iterations i should get very close to the answer, then i can check the nearest integer and see if it's a match.
you can tune the number of iterations to get speedier results that are less accurate, or vice versa?
Adrian Morris
1 + 3 + ... + (2n-1) = n^2
Would be another way to do it. Still bruteforce though...
Kayden Miller
You can do the same type of filtering/optimizing for the odd number summation too. Or are you too stupid to realize this?
That's the entire fucking point, the trick is to find the route without any type of guessing or bullfuckery, the point isn't necessarily execution time faggots.
But yes, the odd number summation is the answer expected in almost every interview they ask this question.
Brandon Kelly
i thought about it even more and this won't work well for bigger numbers.
Asher Evans
Why aren't you allowed to use ^0.5 when it is the simplest manner to test? Just because it is?
Samuel Sanchez
O(sqrt(n)) for the summation. Checking if i*i==input from 1 till i*i>n is O(sqrt(n)). Why is your solution better?
Colton Richardson
static bool IsSquare(int n) { int i = 1; while(true) { if (n < 0) return false; if (n == 0) return true; n -= i; i += 2; } }
How are you this fucking braindead? 0 1 2 3, retard.
Grayson Bailey
first time trying to use code tags
#include
using namespace std;
int num=0,mitad=0,raiz=0; bool sqr=false;
int main() { cout > num; mitad = (num/2); for (int i=0; i
Nathan Bailey
again it's not necessarily about execution time. it's about recognizing the pattern of prime numbers and building a concrete check that is ENTIRELY composed of simple addition and an intuitive construction.
in the I*I check you are directly wasting loop cycles to just ramp up to the number range necessary. It's NOT the intuitive solution at all, I guarantee in an interview this is the answer they hear the most and they will not take it positively that you can do simple if statements until shit matches.
Also I don't think it's faster on average. I tried in leetcode (which tries a bunch of different sample inputs) and the i*i solution didn't even compile in time for me (failed) while odd summations succeeded.
Also if you're interviewing for firms that accept one trivial O(sqrtn) solution but don't accept another trivial solution with the same complexity, you're interviewing for the wrong firms.
Parker Wilson
#!/usr/bin/python3
def psq(n): if n == 1: return True
if not n == round(n): return False n = int(n)
for i in range(2, n): if n % i == 0: return psq(n / i**2)
return False
x = int(input()) if psq(x): print('yes') else: print('no')
how's this senpaitachi
Nathan Roberts
im sorry senpai took me 20 secs perfect n = n `elem` map (^2) [1..n]
Parker Roberts
function st(n){var i,j;for(i=1,j=3;i 1 st(2044) => 0
Jaxson James
more efficient but excludes 1 perfect n = n `elem` map (^2) [1..div n 2]
Kayden Gray
would somebody explain this portion:
for(a = 0; a
Angel Reyes
>>>/web-dev/
but srs
for a = 0, a
David Jones
>n = 25 , a = 0 [0*0 != 25] >n , a = 1 [1*1 != 25] >n , a = 2 [2*2 != 25] >n , a = 3 [3*3 != 25] >n , a = 4 [4*4 != 25] >n , a = 5 [5*5 == 25] {yes}
Josiah Nelson
Are you retarded?
Adam Jones
Oh I get it now.
The loop keeps going while a is
Sebastian Jenkins
it's a for loop, which has 4 parts. 1. Some variable(s) for the loop to work on. 2. A condition that has to be met for the loop to run. 3. An action to perform every time the loop is run. 4. The body, which is the "stuff" that gets done every go around of the loop.
So 1. is a=0, 2. is a
Gavin Peterson
yeah it took me a bit with the logic and what the for loop was doing there.
i don't program (obviously). just a passing interest.
Brody Kelly
>has no idea what the fuck embarrassingly parallel means or too retarded to know it's applicable in the odd summation method >but I sent you the big O wiki!
>Also if you're interviewing for firms that accept one trivial O(sqrtn) solution but don't accept another trivial solution with the same complexity, you're interviewing for the wrong firms. I never claimed this. The problem (and similar ones) are often directed towards pattern recognition because that type of thinking and resulting solution goes one step higher than what is essentially smashing numbers together until it works and wasting a fuck load of loop cycles unless you do some butchering and hard-coded guessing of the scope, but that can also be applied to the odd summation in the same way anyways so it's not a valid argument.
They want to hear the answer that shows a deeper understanding of how prime numbers relate and can be verified through pure induction and other discrete tricks, ideally.
Jaxon Bell
thanks, is this a valid solution? int perfect(int n) { int i = 1; int a = i; while (a < n) { i += 2; a += i; } return a == n; }
Julian Long
this solution seems just as bad as the others.
how would this be implemented though? Do you still generate each square or I'm missing something?
It will auto try a ton of sample inputs that leave no corner of logic untested and let you know if the code passes. If your code is also too slow it will fail the test too.
Noah Lee
It took op 30 minutes to solve that problem but Sup Forumsingers are arguing for 2h.
Aiden Wilson
>sign in
nope
Adrian Martin
>30 minutes on a perfect square problem are you clinically braindead
Mason Scott
yeah I just noticed. sucks but the website is good, tons of great questions but a decent amount locked under the shill wall. The OP question is also rated as medium difficulty for anyone wondering (at least with odd summation solution)
Leo Parker
copying code off wikipedia is cheating user
Christian Roberts
Or you could do a dichotomy search. It's faster than brute forcing every possibility and it's applicable to floating points.
Ryan Roberts
let's see the code user :)
Noah Jones
pls show and/or explain user, i'm interested
Nathan Cruz
int checker = num^1/2 if checker != float { return true; }
Carson Rogers
A dichotomy search is choosing between to alternatives and progressively reducing the range of search. Say you're searching for the square root of 16. Your domain of search is between 2 and 16/2 = 8. You divide this domain in two equals parts, by dividing the highest+lowest extreme by two which gives you a number delimiting the two sub domains, in our case 4. Then you test this number, if it's higher than what you're supposed to get, your new domain is the delimiting number to the highest extreme. If its lower, your new domain is the delimiting number to the lowest extreme. It can be applied to floating points because you get find a square root with some precision with it, and you can define the precision.
Heres an example in python, it's pretty straightforward. def sqrt(n): low = 0 high = n+1 while high-low > 1: mid = (low+high) / 2 if mid*mid
Dylan Roberts
>how would this be implemented though? Do you still generate each square or I'm missing something?
Pretty sure odd summation is embarrassingly parallel because it's entirely deterministic, it's literally just a summation of all odd numbers. 0 guessing or wasted cycles/cpu time. When an algorithm is deterministic, it's much easier to implement efficiently in a manner such that the CPU pipeline/cores are all being used simultaneously and not sitting idle.
maximum resource utilization is inherently more difficult when the algorithm is not deterministic. Correct me if i'm wrong, but i'm pretty sure this is how it goes down.
Noah Carter
> I guarantee in an interview this is the answer they hear the most and they will not take it positively that you can do simple if statements until shit matches.
have you even done an interview question?? It's mostly "how do pointers work" and "find a thing inside another thing"
They're impressed with candidates who can answer anything other than "Potato", because you know what? Some candidates don't even get that far.
Joseph Campbell
user you must have interviewed at some shit companies or just for intern positions. Some companies are definitely selective, and it's in their best monetary interest to be.
Big four will really push your shit in most interviews. Constant white-boarding interview after interview for almost a day. Not sure where you live but in my area (NYC), their is definitely talent too. At the good companies the questions go beyond pointers and fizzbuzz and if you don't know your shit they will sniff you out like a dog.
Andrew Clark
This is slick as fuck. Going to try and internalize this shit.
Thanks user.
Oliver White
what is Sup Forumss favorite interview question so I may acquire more practice
Asher Young
#include
void FizzBuzz() { for (int i = 1; i
Elijah Miller
...
Adam Watson
Is this one of this "Some dumb will do my homework" thread?
Brody Powell
>chapter 1 of SICP Still took me a while. I didn't remember the algorithm correctly. They even warn you: > Consider an initial guess y1. [If] the next guess is y2 = x/y1 [then] the next guess is y3 = x/y2 = x/(x/y1) = y1. This results in an infinite loop in which the two guesses y1 and y2 repeat over and over, oscillating about the answer. >One way to control such oscillations is to prevent the guesses from changing so much. Since the answer is always between our guess y and x/y, we can make a new guess that is not as far from y as x/y by averaging y with x/y, so that the next guess after y is (1/2)(y + x/y) instead of x/y.
Oliver Morales
You could do it in O(logn) with a binary search, but there may be some math wizardry that is more efficient
Nicholas Williams
Invert a binary search tree in haskell
Hunter King
>You could do it in O(logn) with a binary search Wouldn't that still be brute forcing? Wouldn't anything involving a loop be a brute force?
Hudson Cruz
>Some companies are definitely selective, and it's in their best monetary interest to be.
Depends on the job. The big companies have more vigorous interviews because they have a lot of applicants. They have the luxury of being very selective in who they hire.
Mason Phillips
That's still brute-forcing. OP wants an elegant solution.
Justin Parker
If the OP is expecting a constant time complexity algorithm he's actually a dumbass. And so are you.
Jack Ramirez
if(Math.sqrt(num)==(int)num
Jacob Miller
>but there may be some math wizardry that is more efficient There can't be. The input contains O(log n) bits, and you need to read all of them, which means you need at least O(log n) time. (I should write an omega or theta here but I don't feel like copypasting those symbols from somewhere so fuck it.) Since binary search is O(log n), it is optimal for this problem.
You clearly haven't got a clue what "brute force" means. This isn't it.
Ethan Russell
>You clearly haven't got a clue what "brute force" means. This isn't it.
Why isn't it brute force? It does an exhaustive search for a solution. It's only slightly less retarded than going through every number.
Jeremiah Taylor
Why do you care what company you work at? Google's 6 figs work just as well as bob's backyard consultancy's 6 figs.
Cooper Morgan
>It does an exhaustive search for a solution. No, it doesn't. "exhaustive search" is jargon for "going through every number", which as you say this algorithm does not do.
Charles Green
Using heuristics doesn't make the algorithm non-brute-force.
Henry Hughes
Can Sup Forums write a program that will find me a gf?