Author Topic: Algorithms Quiz (anyone can give it a shot, please!)  (Read 6597 times)

0 Members and 1 Guest are viewing this topic.

Offline chief1983

  • Still lacks a custom title
  • 212
  • ⬇️⬆️⬅️⬅️🅰➡️⬇️
    • Minecraft
    • Skype
    • Steam
    • Twitter
    • Fate of the Galaxy
Algorithms Quiz (anyone can give it a shot, please!)
I'm not an algorithms guy really, so this isn't exactly my forte.  But I'm supposed to be evaluating some answers to these quiz questions tomorrow, and if I could see some ideas of what you guys come up with before then, I'll be better prepared tomorrow.  So here's the questions.

Code: [Select]
1) Given a prime number, N, write an algorithm to get the next prime number.
2) Given an array of red, black and yellow balls, sketch an algorithm to produce 3 arrays of balls, each containing all balls of a single color.
3) Given a file of 50 million strings, sketch an algorithm to find a string that appears at least twice.

Anyone is welcome to give it a shot, whether you think it's a very good answer or not.  I'll be judging all sorts of answers tomorrow so the broader range of solutions I can be aware of the better.  Remember, no actual code required, pseudo code or just verbal explanation is fine, correctness proofs preferred.
Fate of the Galaxy - Now Hiring!  Apply within | Diaspora | SCP Home | Collada Importer for PCS2
Karajorma's 'How to report bugs' | Mantis
#freespace | #scp-swc | #diaspora | #SCP | #hard-light on EsperNet

"You may not sell or otherwise commercially exploit the source or things you created based on the source." -- Excerpt from FSO license, for reference

Nuclear1:  Jesus Christ zack you're a little too hamyurger for HLP right now...
iamzack:  i dont have hamynerge i just want ptatoc hips D:
redsniper:  Platonic hips?!
iamzack:  lays

 

Offline Colonol Dekker

  • HLP is my mistress
  • 213
  • Aken Tigh Dekker
    • My old squad sub-domain
Re: Algorithms Quiz (anyone can give it a shot, please!)
1.

if x= not x/1 or x/x :nervous:

I have no idea how to write these things down...
Your friendly Orestes tactical controller
GO GO DEKKER RANGERSSSS!!!!!!!!!!!!!!!!!
President of the Scooby Doo Model Appreciation Society
The only good Zod is a dead Zod
NEWGROUNDS COMEDY GOLD, UPDATED DAILY
http://badges.steamprofile.com/profile/default/steam/76561198011784807.png

 

Offline Herra Tohtori

  • The Academic
  • 211
  • Bad command or file name
Re: Algorithms Quiz (anyone can give it a shot, please!)
Does "next" imply that N1<N2? :drevil: Sequences can go to either direction, so I would say the question is a bit ambiguous if it doesn't define the direction (next doesn't really cover it, it just says "adjacent").

How large primes are we talking here? I mean you can bruteforce check whether N is a multiple of M (M<N/2), and if you get negative answer you do N++ and re-check. Can't bother to figure out how to do it with programming.

There are super computers looking for the next prime all the time. The biggest one they have determined to be a prime so far is N=(2^43112609)-1 so you can understand if checking if a large natural number is a prime can take a bit long. And brute forcing them is hopeless so I think there are advanced algorithms to determine prime candidates, but I haven't really ever had any passing interest in raw mathemathics like this. Aside from getting an array of random numbers, what use is knowing primes really, aside from just knowing that a really big number can only be divided by one and itself...

You can't really even put 2^43112609 - 1 into a comprehensible form so it's not even useable for that. Well, if you have a huge array of hard disk drives that can store the number, then I guess you could use it that way but really, there are better ways to gain random numbers. :p

The others are fundamentally easier. Abstractizing the properties (colour) of the balls and then sorting them by that property would not be that hard.

The final one is a bit trickier... 50 million strings takes a while to go through. Bruteforcing would be possible, I guess. Save the strings into an array, take the first string (string.0) and check if it appears again in the file (if string1==string2 etc.), if not, take the second string (string.1) and check match for all the string.(>1). It would, at least, work. But whether or not I could write it in formal logic language or any given programming language is a different thing, I hate being limited by syntax. :blah:
There are three things that last forever: Abort, Retry, Fail - and the greatest of these is Fail.

 

Offline The E

  • He's Ebeneezer Goode
  • Global Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Algorithms Quiz (anyone can give it a shot, please!)
The first one is deceptively simple; finding a next number is, after all, as easy as just incrementing n. Checking whether or not that number is prime, however, is expensive.

Problem 2:
Iterate through the source array. Based on what is found at the current index, copy its contents into one of three vectors. Once you're done, destroy the source array an return the three vectors.

Problem 3:
Use a sorting algorithm on the array. Iterate through the sorted array. If this.element == next.element, return this.element. Or do whatever else you want to do with the elements.
Let there be light
Let there be moon
Let there be stars and let there be you
Let there be monsters and let there be pain
Let us begin to feel again
--Devin Townsend, Genesis

 

Offline Sushi

  • Art Critic
  • 211
Re: Algorithms Quiz (anyone can give it a shot, please!)
IMO #3 is the only really interesting one. :)

For #3, just create a really big hashtable. Iterate through the list of strings once, checking to see if each string is in the hashtable already. If it isn't there, add it to the hashtable. If it is there, then you've found a duplicate. Complexity: O(N)... but you need a lot of memory to hold that hashtable.

Or, alternately, use a binary search tree and do the same thing. It has much less up-front memory cost, but the worst-case complexity is now O(NlogN).

For #2: The problem description leaves a lot to be desired: what property does a "ball" have for us to deal with? Assuming it has a unique ID and a color, though, you can just iterate over the original array, stuff each ball into a list corresponding to its color, then read out the lists into fresh color-specific arrays.

#1, as The E pointed out, is tricky because it's hard to make it computationally feasible. Naive solution is just to increment & check until you find a prime. More efficient solutions exist, but I don't remember what they are and I don't know enough theoretical math to figure it out on my own. :p

 

Offline chief1983

  • Still lacks a custom title
  • 212
  • ⬇️⬆️⬅️⬅️🅰➡️⬇️
    • Minecraft
    • Skype
    • Steam
    • Twitter
    • Fate of the Galaxy
Re: Algorithms Quiz (anyone can give it a shot, please!)
I found some random functions for the prime stuff online, first is C++ and second is Javascript.  I'm pretty sure they're naive though at first glance but I haven't looked closely.

Code: [Select]
int NextPrime( int n)
{
if( n == 0)
return 2;
else if (n == 2)
return 3;

n++;

for(int d=2; d < n; d++)
{
if( n%d == 0)
{
n++;
d=2;
}
}

return n;
}

function checkPrime(n)
{
var dummy = 0
for (var i = 2; i <= Math.sqrt(n); i++)
{
if ( Math.round(n/i) == n/i)
{
var result = n + " = " + i + "*" +n/i
//alert(result)
theForm.Output.value = result
dummy = 1
break
}
}
if (dummy == 0)
{
var result = n + " is prime."
theForm.Output.value = result
}
}
Fate of the Galaxy - Now Hiring!  Apply within | Diaspora | SCP Home | Collada Importer for PCS2
Karajorma's 'How to report bugs' | Mantis
#freespace | #scp-swc | #diaspora | #SCP | #hard-light on EsperNet

"You may not sell or otherwise commercially exploit the source or things you created based on the source." -- Excerpt from FSO license, for reference

Nuclear1:  Jesus Christ zack you're a little too hamyurger for HLP right now...
iamzack:  i dont have hamynerge i just want ptatoc hips D:
redsniper:  Platonic hips?!
iamzack:  lays

 
Re: Algorithms Quiz (anyone can give it a shot, please!)
I'll think about the others, but I've got a good one for number 3

If all you wanted to know was whether a string repeated (for number 3), this might work (depending on how long your strings are going to be):
Create a tree structure:
Code: [Select]
structure
  child_nodes
  end_node
  character
endstructure

Add string characters into the tree, where the character doesn't exist, create the child node.
At the end of each string, see if you've hit an end node.

EDIT: That last part doesn't work right. Damn, don't algorithm while tired :P
EDIT2: Although, if you mark a node as an end node, you can be sure that the above would work.
EDIT3: It works, and is quite quick too :)

Would probably be faster if I didn't use a vector and didn't use std::string, but it's proof of concept.
Code: [Select]
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

#include "stdio.h"
#include "stdlib.h"

void challenge3( bool data );
void generate_data( const char* filename );
int rand_range( int max );

struct c3_node
{
std::vector< c3_node > children;
bool end;
char c;
};

const char alphabet[] = {"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"};

int rand_range( int max )
{
   int r = (int)((((double)rand( ))/((double)RAND_MAX+1))*(double)max);
   if ( r == max )
  r--;
   return r;
}


void generate_data( const char* filename )
{
std::ofstream f( filename );
/* Generate 100000 random phrases */
for ( size_t n = 0; n < 100000; n++ )
{
/* Random length for this phrase */
int length = rand_range( 200 );
if ( length == 0 )
length++;
std::string s;
s.reserve( length );
for ( int l = 0; l < length; l++ )
{
s += alphabet[ rand_range( sizeof( alphabet ) / sizeof( alphabet[ 0 ] ) - 1 ) ];
}
f << s << std::endl;
}
}

void challenge3( bool data )
{
if ( data )
{
generate_data( "data.txt" );
return;
}

c3_node root;
std::ifstream f( "data.txt" );
bool oldeof = false;
size_t count = 0;
while ( true )
{
count++;
std::string line;
std::getline( f, line );
if ( f.eof( ) && ( oldeof || line.length( ) == 0 ) )
break;

/* Process this string */
c3_node* cur = &root;
for ( size_t i = 0; i < line.length( ); i++ )
{
/* Find the current letter */
bool found = false;
for ( size_t curr_letter = 0; curr_letter < cur->children.size( ); curr_letter++ )
{
if ( cur->children[ curr_letter ].c == line[ i ] )
{
cur = &cur->children[ curr_letter ];
found = true;
break;
}
}

/* Insert unfound node */
if ( !found )
{
c3_node n;
n.end = false;
n.c = line[ i ];
cur->children.push_back( n );
cur = &cur->children[ cur->children.size( ) - 1 ];
}

if ( i == line.length( ) - 1 )
{
/* Are we at an end node? */
if ( cur->end )
std::cout << "Duplicate: " << line << " @ " << count << std::endl;
else
cur->end = true;
}
}
}

std::cout << "END" << std::endl;
}
« Last Edit: February 09, 2010, 01:16:03 am by portej05 »
STRONGTEA. Why can't the x86 be sane?

 
Re: Algorithms Quiz (anyone can give it a shot, please!)
Without further information on #2, the best I can do is to overallocate the 3 destination arrays and you end up with an O(N) 1-pass algorithm.

#1 is interesting - how big is N going to be?
STRONGTEA. Why can't the x86 be sane?

 

Offline karajorma

  • King Louie - Jungle VIP
  • Administrator
  • 214
    • Karajorma's Freespace FAQ
Re: Algorithms Quiz (anyone can give it a shot, please!)
For the prime number question you only need to check if the number is perfectly divisible by all the preceding prime numbers up to half it's value.

So what I'd do is create a vector and push the number 2 onto it.
I'd then start a loop.
Every time you find a number that isn't divisible by a numbers in the vector you add it to the vector.
Keep doing that until you get to N/2.

Now test the numbers after N against the vector.


Then I'd save the contents of the vector for next time. :p
« Last Edit: February 09, 2010, 02:05:24 am by karajorma »
Karajorma's Freespace FAQ. It's almost like asking me yourself.

[ Diaspora ] - [ Seeds Of Rebellion ] - [ Mind Games ]

 

Offline Spicious

  • Master Chief John-158
  • 210
Re: Algorithms Quiz (anyone can give it a shot, please!)
Probably Miller-Rabin test.

Trie with a count/bool on each node or a hash table.

 

Offline Bobboau

  • Just a MODern kinda guy
    Just MODerately cool
    And MODest too
  • 213
Re: Algorithms Quiz (anyone can give it a shot, please!)
what use is knowing primes really, aside from just knowing that a really big number can only be divided by one and itself...

if you can quickly generate huge primes you can break RSA encryption and thereby win the internet, undoing such things as secure online banking or bill paying.

For the prime number question you only need to check if the number is perfectly divisible by all the preceding prime numbers up to half it's value.

square root of it's value.


as for the third question, as others have said use a hash table or a binary search tree.
« Last Edit: February 09, 2010, 08:45:48 am by Bobboau »
Bobboau, bringing you products that work... in theory
learn to use PCS
creator of the ProXimus Procedural Texture and Effect Generator
My latest build of PCS2, get it while it's hot!
PCS 2.0.3


DEUTERONOMY 22:11
Thou shalt not wear a garment of diverse sorts, [as] of woollen and linen together

 

Offline The E

  • He's Ebeneezer Goode
  • Global Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Algorithms Quiz (anyone can give it a shot, please!)
Errm. If you can quickly do factorization on large composites (the product of two primes multiplied), that's when you win the internet. That's somewhat harder.
Let there be light
Let there be moon
Let there be stars and let there be you
Let there be monsters and let there be pain
Let us begin to feel again
--Devin Townsend, Genesis

 

Offline Bobboau

  • Just a MODern kinda guy
    Just MODerately cool
    And MODest too
  • 213
Re: Algorithms Quiz (anyone can give it a shot, please!)
making a huge list of primes is a good way to do that.
Bobboau, bringing you products that work... in theory
learn to use PCS
creator of the ProXimus Procedural Texture and Effect Generator
My latest build of PCS2, get it while it's hot!
PCS 2.0.3


DEUTERONOMY 22:11
Thou shalt not wear a garment of diverse sorts, [as] of woollen and linen together

 

Offline Sushi

  • Art Critic
  • 211
Re: Algorithms Quiz (anyone can give it a shot, please!)
I like Portej's #3 solution, that's pretty clever.


 
Re: Algorithms Quiz (anyone can give it a shot, please!)
Sushi - can't claim full credit, I saw a note somewhere in a book I was reading during ACM training
It's also a total monster on the memory use depending on string length :P (potentially 26^averagestringlength - I think for suitably random strings)
The hash table approach could be better for limited memory systems,
STRONGTEA. Why can't the x86 be sane?

 

Offline castor

  • 29
    • http://www.ffighters.co.uk./home/
Re: Algorithms Quiz (anyone can give it a shot, please!)
Problem 3:
Use a sorting algorithm on the array. Iterate through the sorted array. If this.element == next.element, return this.element. Or do whatever else you want to do with the elements.
That's what I'd do too. Maybe adding another (preceding) sorting phase by string length.

 

Offline The E

  • He's Ebeneezer Goode
  • Global Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Algorithms Quiz (anyone can give it a shot, please!)
Yeah, but Sushi's (and especially portej's) solutions are much better. In terms of runtime, portej's will probably win (if not in terms of memory usage, it will balloon very quickly for very large strings). Sushi's solution is a close second, since it has the potential to deliver false positives, but checking for those adds only a negligible overhead to the whole function.

Personally, I prefer portej's approach due to its elegance.

Oh, and sorting for length will lengthen your runtime for no real benefits.
Let there be light
Let there be moon
Let there be stars and let there be you
Let there be monsters and let there be pain
Let us begin to feel again
--Devin Townsend, Genesis

 

Offline chief1983

  • Still lacks a custom title
  • 212
  • ⬇️⬆️⬅️⬅️🅰➡️⬇️
    • Minecraft
    • Skype
    • Steam
    • Twitter
    • Fate of the Galaxy
Re: Algorithms Quiz (anyone can give it a shot, please!)
#3 was changed to 250 million 200 character strings, apparently the point was that loading all of it into memory wouldn't be feasible.  We did get some solutions, a lot of brute force attempts but one guy in particular had some very interesting solutions for most of the problems.
Fate of the Galaxy - Now Hiring!  Apply within | Diaspora | SCP Home | Collada Importer for PCS2
Karajorma's 'How to report bugs' | Mantis
#freespace | #scp-swc | #diaspora | #SCP | #hard-light on EsperNet

"You may not sell or otherwise commercially exploit the source or things you created based on the source." -- Excerpt from FSO license, for reference

Nuclear1:  Jesus Christ zack you're a little too hamyurger for HLP right now...
iamzack:  i dont have hamynerge i just want ptatoc hips D:
redsniper:  Platonic hips?!
iamzack:  lays

 

Offline Spicious

  • Master Chief John-158
  • 210
Re: Algorithms Quiz (anyone can give it a shot, please!)
making a huge list of primes is a good way to do that.
Good luck storing them all.

 

Offline castor

  • 29
    • http://www.ffighters.co.uk./home/
Re: Algorithms Quiz (anyone can give it a shot, please!)
Oh, and sorting for length will lengthen your runtime for no real benefits.
Well, to be more specific, I meant splitting the input to multiple arrays that can be sorted separately and in parallel.