Splitting list interview question

Just made this up, feels like a good interview question

Part 1 –

Write a function that takes a list and splits it at a specific percentage.

f(mylist, pct) = list(mylist[0 ... len(mylist) * pct / 100.0],
                      mylist[len(mylist) * pct / 100.0 ... EOL])

Part 2 -

Now generalize that so that f(mylist, ..) takes an arbitrary number of percentages (in order) and returns you the list. This is interesting as an interview questions since I can see a bunch of interesting things coming up in the white board coding session.

  • How to deal with short lists, more percentages than list items
  • Approaches that end up with overlapping items (item #20 in the list twice)
  • General familiarity of the language of choice
  • How they understanding basic list processing – this is one list controlling the handling of another list.

Then again, somebody might pull a fast one on you and make you go huh?

# python code
def split_list(mylist, *args):
    # ilist not necessary, but makes formatting easier
    ilist = map(lambda p : int(p * len(mylist) / 100.0), args) + [len(mylist)]
    return reduce(lambda l, v : [l[0] + [mylist[l[1]:v]], v], ilist, [[],0])[0]

Using OpenID, OAuth, OAuth2 and OpenID+OAuth

Over the last year I’ve had an authentication library that I’ve used to slice and dice public services and like most things it’s collected more than it’s share of dust, cruft and other ugly appendages that you wonder if it’ll work then next time you use it.  I’ve been hot and heavy over django (even if it’s embedded inside of Tornado) as a general framework for a while, it’s not broke don’t fix it…

The general case of site authentication looks like this:

  • You need your own username + password
  • You’re perfectly willing to give it all to Facebok/Google/etc. to handle

Depeding on the project I’m quite happy with giving it away, but there are times when you want to have “ownership” of the users on your website.  In which case in this day and age it’s important to allow people to associate their well known credentials with your service — cool.  FYI – This is my “new favorite flow”

  • Ask for email + password + (any service required fields – screen name ….)
  • Require them to associate with  another service
    • Capture picture / full name and other bits from “Facebook”
  • Follow up with prompting to finish profile or other service specific tasks

That’s the simple part, the hard part has been dealing with OpenID, OAuth, OAuth2 and Hybrid protocols.   Since very rarely do you want just to get the fine photo for the user and forget about it.  You probably want to do one of these things:

  • Tweet something they did
  • Check in
  • Add to their facebook page
  • Scrape their friends
  • …etc…

Which means you need to store a token, not only that but some of these wonderful protocols don’t give you persistant identifiers.   Anyway, here’s a bit of commentary and some code excerpts for you to review, hopefully my refactorization makes life more interesting moving forward and those hulking if statements I used to have are gone.

OAuth — The big challenge is that the token you get is a transient identifier, it will change if you assocate account information with this your doomed.   So, typically what you end up needing to do is take your OAuth token and go back and pull the profile, which of course means that you need yet another round trip behind the scenes to get an authentication to happen.

class FoursquareOAuthClient(CommonOAuthClient):
    api_root_url = 'http://foursquare.com' #for testing 'http://term.ie'
    api_root_port = "80"

    #set api urls
    def request_token_url(self):
        return self.api_root_url + '/oauth/request_token'
    def authorize_url(self):
        return self.api_root_url + '/oauth/authorize'
    def access_token_url(self):
        return self.api_root_url + '/oauth/access_token'

class FoursquareBackend(OAuthOpenBackend) :
    name = 'foursquare'
    info = settings.OPENAUTH_DATA.get(name, {})

    oauth_class = FoursquareOAuthClient

    def get_profile(self, token) :
        raw = self._fetch(token, 'http://api.foursquare.com/v1/user.json')

        print raw

        data = json.loads(raw)
        data = data['user']

        identity = 'foursquare:%s' % data['id']

        return identity, {
                        'first_name' : data.get('firstname',''),
                        'last_name'  : data.get('lastname',''),
                        'email'      : data.get('email',''),
                    }, data

OAuth2 — The nice part is that it quick and easy to handshake up a token, but just like OAuth you still need an extra round trip.

class GowallaBackend(OpenBackend) :
    name = 'gowalla'
    info = settings.OPENAUTH_DATA.get(name, {})

    def prompt(self) :
        return 'https://api.gowalla.com/api/oauth/new?%s' % urllib.urlencode({
                                'client_id'    : self.key,
                                'redirect_uri' : self.return_to,
                        })

    def get_access_token(self) :
        url = 'https://api.gowalla.com/api/oauth/token'
        body = {
                    'client_id'     : self.key,
                    'client_secret' : self.secret,
                    'redirect_uri'  : self.return_to,
                    'code'          : self.request.GET['code'],
                    'grant_type'    : 'authorization_code',
        }

        data = self._fetch(url, postdata=body, headers={'Accept':'application/json'})

        vals = json.loads(data)

        return OpenToken(vals['access_token'])

    def get_profile(self, token) :
        from ..libs.gowalla import Gowalla

        go = Gowalla(self.key, access_token=token.token)

        profile = go.user_me()

        identity = "gowalla:%s" % profile['url']

        return identity, {
                        'first_name' : profile['first_name'],
                        'last_name'  : profile['last_name'],
                        'email'      : None,
                    }, profile

OAuth+OpenID — This is where life gets a bit more painful…  Typically over getting all of the URI bits worked out, where things go etc.  We won’t mention strange things like Yahoo doesn’t return the oauth token when asked unless you’ve approved yourself for non-public information…  Gack!

class GoogleBackend(OpenBackend) :
    name = 'google'
    info = settings.OPENAUTH_DATA.get(name,{})

    def _get_client(self) :
        client = consumer.Consumer(self.request.session, util.OpenIDStore())
        client.setAssociationPreference([('HMAC-SHA1', 'no-encryption')])
        return client

    def prompt(self) :
        client = self._get_client()

        auth_request = client.begin('https://www.google.com/accounts/o8/id')

        auth_request.addExtensionArg('http://openid.net/srv/ax/1.0', 'mode', 'fetch_request')
        auth_request.addExtensionArg('http://openid.net/srv/ax/1.0', 'required', 'email,firstname,lastname')
        auth_request.addExtensionArg('http://openid.net/srv/ax/1.0', 'type.email', 'http://schema.openid.net/contact/email')
        auth_request.addExtensionArg('http://openid.net/srv/ax/1.0', 'type.firstname', 'http://axschema.org/namePerson/first')
        auth_request.addExtensionArg('http://openid.net/srv/ax/1.0', 'type.lastname', 'http://axschema.org/namePerson/last')

        auth_request.addExtensionArg('http://specs.openid.net/extensions/oauth/1.0', 'consumer', self.key)
        auth_request.addExtensionArg('http://specs.openid.net/extensions/oauth/1.0', 'scope', 'http://www.google.com/m8/feeds')

        parts     = list(urlparse.urlparse(self.return_to))
        realm     = urlparse.urlunparse(parts[0:2] + [''] * 4)

        return auth_request.redirectURL(realm, self.return_to)

    def get_access_token(self) :
        if self.request.GET.get('openid.mode', None) == 'cancel' or self.request.GET.get('openid.mode', None) != 'id_res' :
            raise OpenBackendDeclineException()

        client = self._get_client()
        auth_response = client.complete(self.request.GET, self.return_to)

        if isinstance(auth_response, consumer.FailureResponse) :
            raise OpenBackendDeclineException("%s" % auth_response)

        ax = auth_response.extensionResponse('http://openid.net/srv/ax/1.0', True)

        self.email      = ax.get('value.email','')
        self.first_name = ax.get('value.firstname','')
        self.last_name  = ax.get('value.lastname','')

        self.identity = auth_response.getSigned(openid.message.OPENID2_NS, 'identity', None)

        otoken  = auth_response.extensionResponse('http://specs.openid.net/extensions/oauth/1.0', True)
        oclient = GoogleOAuthClient(self.key, self.secret)

        tok = oclient.get_access_token(otoken['request_token'])
        return OpenToken(tok['oauth_token'], tok['oauth_token_secret'])

    def get_profile(self, token) :
        v = {
            'email' : self.email,
            'first_name' : self.first_name,
            'last_name' : self.last_name,
        }
        return self.identity, v, v
Tagged ,

Email is Dead – Long live Email

Brief bio background – I’ve been doing email in some way shape or form since my address was:
…!uoregon!chemstor!koblas
or
…{ames,decwrl,pyramid,wyse}! mips!koblas

If that means something to you, then you probably have a clue that I’ve done this for a while.  If it doesn’t here’s some other tidbits, I can write a sendmail.cf file from $* rules, and written SMTP servers, managed 200M++ mailboxes for internet companies…  Mail is in my blood, but at this point it’s just something that I know, from GUI, Spam and Servers it’s not a challenge it’s just an hour here or there to get it working.

Point: I get email.

Now what’s totally funny is that about two years ago I decided to break the mold and really get Facebook, be an engaged social user.   Over the years I’ve posted status updates, read about who’s sick, etc., etc.  I don’t wonder what it’s for, it’s part of my life.

Point: I’m a Facebook user.

What’s interesting is that while I’ve got an address book with everybody in it, LinkedIn to manage those infrequent contacts, this that the other thing.  I continue to find my self sending more and more messages via Facebook…  Why?

Pocket theory, thanks Ryan for helping with the thinking:  We all have friends, when we want to reach out to them how?  Ok, so I’ve got three email addresses for you, one of which I’m 99% sure is no good (it’s your previous employer).  So, I’ve got at least two now..  Which one do I send to, which one do you check, do you check any of them…  This is where Facebook reigns, I know that if I send you a message on Facebook you’ll get it in at least two places without feeling like I’m spamming you.

Not only that but since you probably do want to receive messages from Facebook, you’ve got a good email address registered with them, so I now can totally ignore those “I’ve decided to change from Comcast to Pacbell and I’m not clueful enough to change to a free email account”.  I know I can Facebook you and you’ll get my message regardless of where you read your email…

Now if we could only convince Facebook to give a serious rev to the messaging GUI (should have said no to the mgmt job and come in as a geek, but that’s a story for another day).

ps.  Sometimes I wish I was a writer/editor…  These thoughts would be better framed.

Tagged ,

20% time revisited

I don’t get 20% time, though there are times I think I have 100% time, but that’s not the point.  Today’s topic is how Q&A services utilize our 20% time.

When I take a look at services like StackOverflow, Quora, and LinkedIn answers where professional people spend time to answer questions for others, I have to start wondering why, the obvious motivators are:

  • Status and reputation
  • A need to help others
  • Puzzle challenges

Recognition – It’s very clear when you look at those services that recognition based system are where they are focus on creating the greatest value.  Very similar to how farmville gets you to plans strawberries three times  a day and gift them to a friend…  At the heart of it your seeking some recognition for who you are, most likely you’re spending part of your day Dilberting away in an office.

Helpfulness – In general humans want to be teachers, we want to help others.  This Nova episode bring the point home:  ”Teaching may be the signature skill of our species”

Puzzles — Watch a while ago Wordplay where the topic is Crossword puzzles, but in it they spend quite a bit of time with Will Shortz (NY Times Crossword Editor), and I also realized he’s on PBS, etc.etc.  Think about it, Crosswords, Puzzles on Radio Shows, etc, etc.  Grandma & Grandpa sitting around watching Jeopardy.    There must be a whole class of people out there who will work on challenges just for the challenge sake.

Back to 20% time — I’m currently trying to figure out how to find new ways to involve people in interesting puzzle actives that both are challenging and seek to reward them with either reputation/recognition or other long term status bits.   The short code fragements of StackOverflow are too small, asking people to do code reviews is too big…  How can we turn peoples attention into fundamental productivity?

If you’re interested in finding out more, drop me a note via twitter.com (@koblas)

Tagged ,

Does it all devolve?

Had coffee with a friend recently and we drifted past the conversation of system designs. The crux is that we’ve both worked in organizations that are very bound to very large code bases… But, in many cases — products that have 100M+ users — they are monolithic piles of dung. Compile times that are non trivial, codebases that take minutes to startup, huge memory footprints. Systems that only survive because the DB is just a margin bigger than their usage.

Now as I set on on many other projects and build, code and create I have to wonder am I just creating the fore front of monolithic systems that will eventually succumb to the same pressures?  Or what internal force causes organizations to create “service oriented architectures” that have the loose coupling, but yet the high availability that is necessary to insure that you don’t need some HP NonStop system to keep your site running.  Is it force of will, design principals, or some bit of Computer Science DNA that isn’t taught?

I’ve gone off an seen the light of component systems, message queues and routers, design for failure, future proof APIs.   But, yet it’s something that people tend to turn up their noses at and go back to if it’s not integrated it doesn’t exist…

Other thoughts on how to create a culture that admires distributed simplicity?

Groups – Google vs. Facebook vs. (Notewave, Brizzly, Fridge)

Small rant attached – though it’s over groups which I’ve been thinking about for years

Facebook groups launched a short while ago, I’ve been using Google Groups for ages (along with Y!Groups).  Brizzly launced their groups product (though they didn’t call it groups) TheFridge has their view and Notewave (my own weekend project) has it’s view.  Groups is a necessary space, so much so there are fields of “mom-and-pop” startups doing it around pictures, sports teams, etc, etc.

Fundamentally I want Facebook to win — ok not really, but yes I do.  I wouldn’t mind if Google would give them a run for the money, but they appear to be going backwards.  I just received an email that says “were’ removing features from Groups — use other services”.  This really sucks google.

Long ago when I was at Yahoo I wanted to re-work groups, since the phylosophy was for groups of more than 500 people it didn’t work for “small” groups effectively, some ways Google didn’t either — but it was a trade off…

Here’s my necessary feature list, comparison matrix:

Feature Yahoo Google Facebook Notewave/Brizzly/Fridge
Mailing list Yes Yes Yes Yes
Calendar Yes No No No
Events Sort of No Yes No
Shared Docs No Going Away Yes No
Photos as 1st class No No Yes Yes
Privacy Yes Yes Yes Yes
Able to invite non-friends by email by email No by email
Public Facing Yes Yes Yes No

What most services fail to realize is that if they can nail groups of 20 people (soccer team, etc.) That they will become more much indispensable to people, sure I need groups for lots of anonymous people on the Internet (I’m a member of too many), but if you think that’s the core businss of groups you’ve missed one primary use case everybody has (their Friends/Associates). I’m not friends with my soccer team parents, but I want a group with them in it (Facebook fail).

Facebook — If you can fix a few little issues with groups you will rule my world:

  • Have a calendar — sync it via iCal to my phone/google
  • Allow me to invite people via email address

That’s it, then I’m yours… Don’t get caught up in “Databases”, “Poll” or other crufty features.

Tagged , ,