Scott Duncombe mojowen

I beefed an interview with AirBNB last week when my interviewee asked me to solve the NP-Complete problem described in this XKCD comic.

I got in my head almost immediately and got lost trying to design a recursive solution - instead attempting to iterate over the possibilities and then sub-iterate over a smaller set while keeping track of price.

Clear of the interview by a few days (and with a rejection letter in the inbox 😎) I wanted to try the problem again - starting from the very basic question: what are all the possible combinations of a N lengthed array of i length?

In the simplest form - how many 3-letter combinations can be produced from ['a', 'b', 'c']?

def possibilities(options, steps, prefix=nil)

	data = [
	[75],
	[95, 64],
	[17, 47, 82],
	[18, 35, 87, 10],
	[20, 04, 82, 47, 65],
	[19, 01, 23, 75, 03, 34],
	[88, 02, 77, 73, 07, 63, 67],
	[99, 65, 04, 28, 06, 16, 70, 92],
	[41, 41, 26, 56, 83, 40, 80, 70, 33],

	<?php

	$url = $_POST['url'];

	$url_count = get_fb_info( $url );

	echo json_encode( $url_count );

	function get_fb_info( $site_name ) {
	$query = "https://api.facebook.com/method/fql.query?query=select url,share_count,like_count,comment_count from link_stat where url = ";

	<!DOCTYPE html>
	<html>
	<head>
	<meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
	<style type="text/css">

	body {
	background: #333;
	}

	# Easier navigation: .., ..., ...., ....., ~ and -
	alias ..="cd .."
	alias ...="cd ../.."
	alias ....="cd ../../.."
	alias .....="cd ../../../.."
	alias ~="cd ~" # `cd` is probably faster to type though
	alias -- -="cd -"

	# Shortcuts
	alias d="cd ~/desktop"

	<?xml version="1.0" encoding="UTF-8" ?>
	<Response>
	<Say>Hello World</Say>
	<Play>https://api.twilio.com/Cowbell.mp3</Play>
	</Response>

	find . -iname "*.jpg" -type f -exec sh -c 'sips --resampleHeight 500 -s format gif "$0" --out "${0%.JPG}.gif"' {} \;
	# http://www.lcdf.org/gifsicle/
	gifsicle --delay=30 --loop *.gif > anim.gif

	<?php

	// Redirects brooklynkindershule.org to campkinderland.org/shule and respects sub paths
	function custom_rewrite_basic() {
	if( $_SERVER['SERVER_NAME'] == 'brooklynkindershule.org') {
	$location = 'http://campkinderland.org/shule';
	if( $_SERVER['REQUEST_URI'] && $_SERVER['REQUEST_URI'] != '/shule' ) $location .= '/'.$_SERVER['REQUEST_URI'];
	header( 'Location: '.$location );
	}
	}

	require 'csv'

	raw = CSV.read('/tmp/pipeline_stat_table.csv')

	labels = raw.shift
	labels.delete('sample_id')
	labels.delete('index')

	data = raw.map{ \|row\| better = {}; labels.each_with_index{\|k,i\| v = row[i+2]; better[k] = v.index('.').nil? ? v.to_i : v.to_f }; [row.second, better] }
	data.each{ \|row\| sample = Sample.find_by(name: row[0]); result = sample ? sample.results.first : nil; result ? (result.pipeline_metrics.update(row.second); result.save) : '' }