- Forum
- General C++ Programming
- Can someone explain this pseudocode
Can someone explain this pseudocode
It was one programming question for a telecom entry-level new grad job.
I am just wondering if the variables define a pattern of something.
if x < y swap (x,y)
while y!=0
r = x % y
x = y
y = r
end while
end if
output x
I am just wondering if the variables define a pattern of something.
if x < y swap (x,y)
while y!=0
r = x % y
x = y
y = r
end while
end if
output x
Last edited on
I agree. Its an ancient algorithm and a classic, but asking someone to recognize it cold seems like the old 'look what you don't know' type of question, on par with swapping with xors. Says nothing about your ability whether you get it or miss it.
If you had tons of time, you could run some numbers and see what it is doing. But I don't see how anyone would get what it does just reading it.
If you had tons of time, you could run some numbers and see what it is doing. But I don't see how anyone would get what it does just reading it.
Last edited on
Disagree with jonnin.
This is a 'separate the newbies (and posers) from the experienced' kind of question. If you have made it through university CS, the algorithm should at least look like something you have seen before.
If they are asking, then you failed the interview. They want someone capable of recognizing and working with basic algorithms. The code base you would be expected to work on probably has a number of different algorithms they would not like you to screw up because you couldn't understand it.
This is a 'separate the newbies (and posers) from the experienced' kind of question. If you have made it through university CS, the algorithm should at least look like something you have seen before.
If they are asking, then you failed the interview. They want someone capable of recognizing and working with basic algorithms. The code base you would be expected to work on probably has a number of different algorithms they would not like you to screw up because you couldn't understand it.
I'm not sure if I agree, I very easily could have gotten through college without taking a math/compsci course that had me program the GCD. I happened to take two classes that relied heavily on gcd (code theory, cryptography) but not everyone took those classes. I think a good interview question pokes at how you think in general, not if a particular algorithm is obvious to you. Unless the interviewee was claiming to know a lot about cryptography or something of that nature (I'm not sure what a telecom job entails, so I could be way off base here).
PS: Upon closer inspection of the OP, I realize it isn't correct when x >= y.
PS: Upon closer inspection of the OP, I realize it isn't correct when x >= y.
Last edited on
I can’t imagine how any university can give you a CS degree without having exposed you to basic algorithms like GCD. Heck, you have to have the basic idea at least to get through fractions in elementary school.
I didn't see it until out of school. I knew what a gcd was but would not have been able to recognize it by sight as such; its a clever/cute code segment that isn't obvious as to what it does.
And, Ive never used it outside of academic/challenge problems. I know there are practical applications, but I haven't hit one on the job. Crypto is done in a library that I couldn't begin to explain how it works inside.
Had a lot of other algorithms. Even the ancient square root one. Just not this one. /Shrug.
And, Ive never used it outside of academic/challenge problems. I know there are practical applications, but I haven't hit one on the job. Crypto is done in a library that I couldn't begin to explain how it works inside.
Had a lot of other algorithms. Even the ancient square root one. Just not this one. /Shrug.
Last edited on
I never heard of a GCD algorithm until this thread. Probably a deficiency in my "self-taught hobby" method.
To be fair I don't have a CSci degree but engineering instead.
Obviously you have to have a concept of what GCD is to simplify fractions in grade school, but that's really separate from being able to recognize the O(log n) algorithm, IMO.
Obviously you have to have a concept of what GCD is to simplify fractions in grade school, but that's really separate from being able to recognize the O(log n) algorithm, IMO.
Last edited on
Furry, GCD is in the <algorithms> in C++, you don't need to write this anymore.
That said, the above was known in ancient times, like the square root algorithm, it converges fast enough to do on paper (!!). Its age and simplicity make it fairly well known, but as you see in this thread, not universally well known :P
Its pretty amazing the ancients figured this stuff out, to me.
That said, the above was known in ancient times, like the square root algorithm, it converges fast enough to do on paper (!!). Its age and simplicity make it fairly well known, but as you see in this thread, not universally well known :P
Its pretty amazing the ancients figured this stuff out, to me.
Last edited on
Ah, C++17, and in <numeric>.
https://en.cppreference.com/w/cpp/numeric/gcd
I understand the concept of what std::gcd does, I simply don't remember hearing/reading it referred to as GCD/gcd before. It has been decades since I last haunted school/university learning anything math related.
I would have learned the pencil and paper process way back then, most likely in grade school. Personal computers were but a dream at the time.
Calculators were slide-rules, if we'd been taught to use them.
https://en.cppreference.com/w/cpp/numeric/gcd
I understand the concept of what std::gcd does, I simply don't remember hearing/reading it referred to as GCD/gcd before. It has been decades since I last haunted school/university learning anything math related.
I would have learned the pencil and paper process way back then, most likely in grade school. Personal computers were but a dream at the time.
Calculators were slide-rules, if we'd been taught to use them.
Topic archived. No new replies allowed.