phc-discussions - OT: Pw0nd the tech riddle

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAOLP8p4oJv+ooCLfysKFOEuU89KoFHF+HoezsbL2=ZEimeO3DA@mail.gmail.com>
Date: Sat, 17 May 2014 21:53:09 -0400
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: OT: Pw0nd the tech riddle

You guys are the biggest online geeks I've run across, on average, so if
you enjoy dumb tech riddles (which I suspect many of you do), read on, but
it's way off topic.

I was challenged with a puzzle yesterday, but I don't believe the guy
offering the puzzle understands the solution very well.  Once I understood
his puzzle (which took me a while - I can be slow), I gave him the optimal
solution, running in O(N), in about 10 seconds.  He didn't seem to like it,
so we moved into highly unoptimal territory, and before giving up on the
discussion, he pressed me on how long I though his preferred solution would
take, "in my gut".  I stuck to O(N*log2(N)).  He was clearly unimpressed.
 I'm giving myself kudos for sticking with my gut, which turned out to be
exactly right, but only if I give the guy the benefit of the doubt and
improve his algorithm slightly - doing a binary search on the diagonal,
rather than picking the middle element.  I simply couldn't accept that he
was advocating picking the middle element and then recursing on 3 N/2xN/2
sub-matricies... that's just nuts.  Here's a link to an online discussion
of the puzzle I found today:

http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

It seems that most of the geeks on this forum have trouble with this
problem.  I'm not looking for confirmation of my solution - I know it's
right.  I'd just prefer talking with a level of geek where I don't have to
keep explaining things.  Even better, I prefer talking to geeks I can learn
from, and I've had the best luck in years on this forum.  I hope you enjoy
it.  I did!

Bill

Content of type "text/html" skipped