8 ms·

Algorithms playground for common questions solved in Ruby syntax

78 points by sagivo 12y ago

trynumber9 12y ago
Here's another similar repository. https://github.com/kennyledet/Algorithm-Implementations https://github.com/kennyledet/Algorithm-Implementations A fellow by handle of Yonaba implemented many of them in Lua. And Lua looks basically like a (Pascal-ish?) pseudo code.
whistlerbrk 12y ago
Great! I'm generally a Rubyist and am doing these same sort of fundamental exercises, except in JavaScript here: https://github.com/whistlerbrk/exercises https://github.com/whistlerbrk/exercises I want to knock off knapsack next
Yadi 12y ago
Dang I have an interview coming up and this really helps :)!
- whistlerbrk 12y ago
  Might I humbly suggest that you check out some videos of the algo you're trying to implement on YouTube first and then try implementing it w/o looking at (pseudo)code. I gave up my first 2 times and peeked at code, but after those I got the hang of it. Also tuples.
  - Yadi 12y ago
    Ah! Good suggestion actually! Thanks a bunch.
sagivo 12y ago
thanks for liking it guys. i did it while i was preparing for my interviews with Google and Facebook. hope it will help you too.
bl4ckdu5t 12y ago
really cool stuff. I was searching around for resources like this about a month ago. I still find it really useful though. Thanks!!!
chaoxu 12y ago
I want to see something like this but with Haskell. So I get to see if Haskell is nice for expressing algorithms.
lbarrow 12y ago
Does anyone actually ask this sort of thing in an interview anymore? (I don't mean this as a knock on the repository, which looks very nice aside from the lack of tests.)
- msoad 12y ago
  Yup! This is still the case. If you want to pass the interview you have to memorize a bunch of common algorithms and data structure implementation.
- arielweisberg 12y ago
  Yup. I just did an interview that was hours of this at one of the larger California companies. The only way to ace is to memorize the implementations otherwise there was no way to get it done on a whiteboard in 20 minutes. There were a lot of added weird constraints as well like implementing sorts with singly linked lists in constant space (not lg(n)) preventing the use of recursion or a stack in order to make a simple implementation. I would say that the entire interview was basically a test of your knowledge of the companies published information as well as the algorithms linked to in the prep email sent by the recruiter. Pretty much zero interest in the knowledge and skills you do have. Only one interviewer out of six asked questions about the resume and even then only briefly.
  - sagivo 12y ago
    i had the same experience with linkedin, facebook and google
- timtas 12y ago
  I recently interviewed with an SF consulting company (a sort of network/placement firm), which purports to offer only the most senior devs to the hottest companies. The process includes a timed puzzle-solving test. Ironically, fresh CS grads are more likely to do better on such a test because senior devs have filled their minds with ways of solving real problems and building complex living systems that actual humans use. They know that the once or twice a year they need to solve such a problem, they will likely find it well-solved in a library or site like this one. If not, they know that the boss will not be holding a stop watch over them -- she measures productivity in person-months, not person-minutes. Even more ironically, this particular test also rewards premature optimization by stress testing your solutions for micro-optimization.
JSno 12y ago
your dijkstra code is ugly as hell.
billforsternz 12y ago
From "Longest Common Substring" > p LCSLength('waaaa', 'bbbbasfaaewra') #returns 4 Visual inspection suggests the longest common substring is 'aa' which has length 2. What am I missing here?
- mkinitcpio 12y ago
  LCS stands for "Longest Common Subsequence". I don't know why their docs say "substring". Maybe they just made a mistake? https://en.wikipedia.org/wiki/Longest_common_subsequence_problem https://en.wikipedia.org/wiki/Longest_common_subsequence_pro...
  - billforsternz 12y ago
    That explains it, thanks. Amusingly the wikipedia "longest common subsequence" page emphasises that this is different to and commonly confused with the "longest common substring". Illustrating this confusion neatly, the OP's repository implements subsequence, but is not only called substring but documented by a wikipedia link to substring!
    - sagivo 12y ago
      already updated. thanks for pointing it out
gargarplex 12y ago
Could be cool if it included Big O notation in comments

78 points by sagivo 12y ago

Here's another similar repository. https://github.com/kennyledet/Algorithm-Implementations https://github.com/kennyledet/Algorithm-Implementations A fellow by handle of Yonaba implemented many of them in Lua. And Lua looks basically like a (Pascal-ish?) pseudo code.

whistlerbrk 12y ago

Great! I'm generally a Rubyist and am doing these same sort of fundamental exercises, except in JavaScript here: https://github.com/whistlerbrk/exercises https://github.com/whistlerbrk/exercises I want to knock off knapsack next

Yadi 12y ago

Dang I have an interview coming up and this really helps :)!

whistlerbrk 12y ago
Might I humbly suggest that you check out some videos of the algo you're trying to implement on YouTube first and then try implementing it w/o looking at (pseudo)code. I gave up my first 2 times and peeked at code, but after those I got the hang of it. Also tuples.
- Yadi 12y ago
  Ah! Good suggestion actually! Thanks a bunch.

sagivo 12y ago

thanks for liking it guys. i did it while i was preparing for my interviews with Google and Facebook. hope it will help you too.

bl4ckdu5t 12y ago

really cool stuff. I was searching around for resources like this about a month ago. I still find it really useful though. Thanks!!!

chaoxu 12y ago

I want to see something like this but with Haskell. So I get to see if Haskell is nice for expressing algorithms.

lbarrow 12y ago

Does anyone actually ask this sort of thing in an interview anymore? (I don't mean this as a knock on the repository, which looks very nice aside from the lack of tests.)

msoad 12y ago
Yup! This is still the case. If you want to pass the interview you have to memorize a bunch of common algorithms and data structure implementation.
arielweisberg 12y ago
Yup. I just did an interview that was hours of this at one of the larger California companies. The only way to ace is to memorize the implementations otherwise there was no way to get it done on a whiteboard in 20 minutes. There were a lot of added weird constraints as well like implementing sorts with singly linked lists in constant space (not lg(n)) preventing the use of recursion or a stack in order to make a simple implementation. I would say that the entire interview was basically a test of your knowledge of the companies published information as well as the algorithms linked to in the prep email sent by the recruiter. Pretty much zero interest in the knowledge and skills you do have. Only one interviewer out of six asked questions about the resume and even then only briefly.
- sagivo 12y ago
  i had the same experience with linkedin, facebook and google
timtas 12y ago
I recently interviewed with an SF consulting company (a sort of network/placement firm), which purports to offer only the most senior devs to the hottest companies. The process includes a timed puzzle-solving test. Ironically, fresh CS grads are more likely to do better on such a test because senior devs have filled their minds with ways of solving real problems and building complex living systems that actual humans use. They know that the once or twice a year they need to solve such a problem, they will likely find it well-solved in a library or site like this one. If not, they know that the boss will not be holding a stop watch over them -- she measures productivity in person-months, not person-minutes. Even more ironically, this particular test also rewards premature optimization by stress testing your solutions for micro-optimization.

JSno 12y ago

your dijkstra code is ugly as hell.

billforsternz 12y ago

From "Longest Common Substring" > p LCSLength('waaaa', 'bbbbasfaaewra') #returns 4 Visual inspection suggests the longest common substring is 'aa' which has length 2. What am I missing here?

mkinitcpio 12y ago
LCS stands for "Longest Common Subsequence". I don't know why their docs say "substring". Maybe they just made a mistake? https://en.wikipedia.org/wiki/Longest_common_subsequence_problem https://en.wikipedia.org/wiki/Longest_common_subsequence_pro...
- billforsternz 12y ago
  That explains it, thanks. Amusingly the wikipedia "longest common subsequence" page emphasises that this is different to and commonly confused with the "longest common substring". Illustrating this confusion neatly, the OP's repository implements subsequence, but is not only called substring but documented by a wikipedia link to substring!
  - sagivo 12y ago
    already updated. thanks for pointing it out

gargarplex 12y ago

Could be cool if it included Big O notation in comments