Can Sup Forums code basic problems?

>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

Example 2:
Input: 17
Returns: False

Other urls found in this thread:

codemaestro.com/reviews/9
en.wikipedia.org/wiki/Newton's_method
en.wikipedia.org/wiki/Big_O_notation
leetcode.com/problems/valid-perfect-square/
twitter.com/SFWRedditImages

>failing on trivial problems
just use stack overflow

>do my homework for me pls

Three minutes later :

#include
#include

int isPerfect(int input){

for(int i = input; i > 0;i--)
if(input % i == 0)
if(input / i == i)
return 1;

return 0;
}

int main(int argc, char* argv[]){

int input = 0;

printf("input : ");
scanf("%d", &input);
printf("\n");

if(isPerfect(input))
printf("Perfect !\n");
else
printf("NOT perfect !\n");

return 0;
}


Here's your fucking homework

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.

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.

shit skipped that line

Because checking numbers inbetween input and input/2 is retarded and redundant(for input>1), forgot to add.

/** C Program to check Perfect Square **/

#include

int main()
{
int a, n;
printf("Enter a number: ");
scanf("%d", &n);
for(a = 0; a

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.

damn im bored

less o d d n u m b e r s

literally 10 seconds

it's nothing crazy as far as big four interviews go.

you have a masters in CS and gave up that quick?

function isSqrt(x) {
return Math.round(Math.sqrt(x)) ** 2 == x;
}

>Efficient solutions don't count

what does this even mean user

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.

well shit user this isn't that binary, if you have some impressive tricks that involve a little guessing feel free to post it.

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.

template
bool issquare(T v) { return false; }
bool issquare(square v) { return true; }

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

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 ) );

sqrt = (long)(1.0F/y);
}
else
{
//Carmack hack gives incorrect answer for n >= 410881.
sqrt = (long)Math.sqrt(n);
}
return sqrt*sqrt == n;

default:
return false;
}
}

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.

Post it then, you dumb asshole.

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

big-ol precomputed table.

Probably a RLE encoded thing would work well.

You could change (a

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.

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?

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.

You either cannot properly read comments, don't have basic understanding of the english language or are trolling.

so you don't know what you're talking about, got it.

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?

1 + 3 + ... + (2n-1) = n^2

Would be another way to do it. Still bruteforce though...

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.

i thought about it even more and this won't work well for bigger numbers.

Why aren't you allowed to use ^0.5 when it is the simplest manner to test?
Just because it is?

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?

static bool IsSquare(int n)
{
int i = 1;
while(true)
{
if (n < 0)
return false;
if (n == 0)
return true;
n -= i;
i += 2;
}
}

C# here, enjoy.

Oh I just actually read the OP properly.

It's one of those bullshit ones.

Never mind.

>number 9
>NONONOYESNONONONONONO

This.
My solution in case anyone is interested

bool isPerfectSquare(int n){
for(int i=1;;i++)
if(i*i >= n)
return 0;
else if(i*i==n)
return 1;
}

give me a break

you mean this?
9-4=5
16-9=7
25-16=9
36-25=11
49-36=13

I don't see an algorithm to exploit this regularity

I think he means that
1+3=4
1+3+5=9
1+3+5+7=16
if n is the number of odd numbers than it is n^2

en.wikipedia.org/wiki/Newton's_method

this

What's the rationale for NOT bruteforcing it?

maximum meme points

How are you this fucking braindead? 0 1 2 3, retard.

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

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.

That is the intuitive way.

Here you go big boy en.wikipedia.org/wiki/Big_O_notation

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.

#!/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

im sorry senpai
took me 20 secs
perfect n = n `elem` map (^2) [1..n]

function st(n){var i,j;for(i=1,j=3;i 1
st(2044)
=> 0

more efficient but excludes 1
perfect n = n `elem` map (^2) [1..div n 2]

would somebody explain this portion:


for(a = 0; a

>>>/web-dev/

but srs

for a = 0, a

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

Are you retarded?

Oh I get it now.

The loop keeps going while a is

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

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.

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

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;
}

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?

You guys can try your code on this website. Supports a bunch of languages.
leetcode.com/problems/valid-perfect-square/

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.

It took op 30 minutes to solve that problem but Sup Forumsingers are arguing for 2h.

>sign in

nope

>30 minutes on a perfect square problem
are you clinically braindead

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)

copying code off wikipedia is cheating user

Or you could do a dichotomy search. It's faster than brute forcing every possibility and it's applicable to floating points.

let's see the code user
:)

pls show and/or explain user, i'm interested

int checker = num^1/2
if checker != float {
return true;
}

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

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

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

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.

This is slick as fuck. Going to try and internalize this shit.

Thanks user.

what is Sup Forumss favorite interview question so I may acquire more practice

#include

void FizzBuzz()
{
for (int i = 1; i

...

Is this one of this "Some dumb will do my homework" thread?

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

You could do it in O(logn) with a binary search, but there may be some math wizardry that is more efficient

Invert a binary search tree in haskell

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

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

That's still brute-forcing. OP wants an elegant solution.

If the OP is expecting a constant time complexity algorithm he's actually a dumbass. And so are you.

if(Math.sqrt(num)==(int)num

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

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

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.

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

Using heuristics doesn't make the algorithm non-brute-force.

Can Sup Forums write a program that will find me a gf?