IWETHEY v. 0.3.0 | TODO
1,095 registered users | 0 active users | 0 LpH | Statistics
Login | Create New User
IWETHEY Banner

Welcome to IWETHEY!

New Taking a stab
Convert the SSN's to 32 bit numbers, so each ssn takes 4 bytes. Pack them in an array (so there's no added overhead per entry). Simple search algorithm would be to start searching in the middle, and dividing each search in half from there.

Search efficiency: log2(n) [10^9 = 2^30]
Storage space per entry: 4 bytes
Worst case n: 10^9
Worst case space = 4 x 10^9 = 4,000,000,000 = 4gigs
New Still doesn't beat O(1) :-)
Regards,

-scott anderson

"Welcome to Rivendell, Mr. Anderson..."
New Ok, I read the answer you gave...
...makes sense for the constraints given in the question. :-)
     Steve Yegge (who he? - ed) on Perl - (pwhysall) - (62)
         IRLRPD. (new thread) - (Another Scott)
         He worked for Amazon for many years - (tuberculosis) - (60)
             Well based on that ... - (folkert) - (59)
                 Key factors are - (tuberculosis) - (58)
                     do it all the time - (boxley)
                     I have never had an under spec'd system. - (folkert) - (56)
                         More to the point is will it fit on one machine? - (tuberculosis) - (55)
                             I guess I think to simply. - (folkert) - (22)
                                 You would filewalk for every query? - (crazy) - (18)
                                     RAMFS? -NT - (folkert) - (17)
                                         Doesn't matter - (crazy) - (5)
                                             That would be a radix-search, I think. - (static) - (3)
                                                 Nah, you want a hash - (tuberculosis) - (2)
                                                     I thought a radix search was also O(1). - (static) - (1)
                                                         Gah - my bad - (tuberculosis)
                                             Also, I just thought about your file size - (crazy)
                                         On a 32 bit machine? -NT - (tuberculosis) - (10)
                                             Ever heard of PAE? - (folkert) - (9)
                                                 I'd call that exotic technology -NT - (tuberculosis) - (8)
                                                     No, it is bone stock on everything since the P3 from Intel - (folkert) - (7)
                                                         And AMD? PowerPC? ARM? - (tuberculosis) - (6)
                                                             You said COMMON 32-bit - (folkert) - (5)
                                                                 That kind of weasel won't get you a job - (tuberculosis) - (4)
                                                                     This line of questioning wouldn't get you a candidate for - (folkert) - (3)
                                                                         Whoa - (crazy) - (2)
                                                                             No he got downright rude. -NT - (folkert) - (1)
                                                                                 I'm not trying to be rude - (tuberculosis)
                                 Where did you get 1G? - (tuberculosis) - (2)
                                     Not all 9 digit numbers are valid. - (Another Scott) - (1)
                                         I assumed so - (tuberculosis)
                             something you forgot, what lawyer to hire - (boxley) - (1)
                                 Nah - (crazy)
                             We talked about this one before - (admin) - (6)
                                 We did - he didn't - (tuberculosis) - (5)
                                     Just saying... - (admin) - (4)
                                         But we hardly talk about programming at all anymore - (tuberculosis) - (3)
                                             :-) - (Another Scott) - (2)
                                                 I agree on the eyeballs. - (static)
                                                 I put most of my programming rants on my blog - (tuberculosis)
                             non programmer answer, append a 0,1 or2 - (boxley) - (15)
                                 PICK?!?!?!?!?!?!?!?!?!?!? - (crazy) - (5)
                                     dont knock it until you have tried it, recently -NT - (boxley) - (4)
                                         I've spent the last 20 years systematically killing it - (crazy) - (3)
                                             again, see what the needs are and then ask what the solution - (boxley) - (2)
                                                 One trick pony - (crazy) - (1)
                                                     If that is the trick you need use it -NT - (boxley)
                                 The key is to stay off the disk - (tuberculosis) - (8)
                                     CramFS in RAM. -NT - (folkert) - (6)
                                         That's not a solution either - (tuberculosis) - (5)
                                             Okay, at this point... - (folkert) - (4)
                                                 Sure - just want to give you a taste - (tuberculosis) - (3)
                                                     personally I hate programming, I like debugging - (boxley)
                                                     Cheaper at Bookpool, btw. - (admin)
                                                     ICLRPD - (drewk)
                                     Math isnt my strong suit but - (boxley)
                             I hope you're going to outline the solution. :-) - (Another Scott) - (3)
                                 Admin did it very nicely. - (crazy) - (1)
                                     D'Oh! Thanks. -NT - (Another Scott)
                                 Cool sort paper - (crazy)
                             Taking a stab - (ChrisR) - (2)
                                 Still doesn't beat O(1) :-) -NT - (admin) - (1)
                                     Ok, I read the answer you gave... - (ChrisR)

If you throw enough pasta at the wall, some of it will stick.
116 ms