Hao Wu swuecho

The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.

Considering each permutation of the letters as a variable, we get a number of simultaneous equations which can be solved using Gaussian Elimination to compute the expected value of each permutation. However, the number of variables is very large. This can be reduced by making the observation that many states such as "abab" and "baba" are essentially the same since the letters in them are simply relabelled. Thus we can normalize each string by letting it start with an 'a', replacing the next occuring character with a 'b' and so on. For example, string "paddpa" would be normalized to "abccab". This reduces the number of variables greatly, and also helps us efficiently memoize across various test cases. Also, we should note that running one Gaussian Elimination gives us the expected values for many states (and not just one), all of which should be saved for future reference.

Latency numbers every programmer should know

L1 cache reference ......................... 0.5 ns
Branch mispredict ............................ 5 ns
L2 cache reference ........................... 7 ns
Mutex lock/unlock ........................... 25 ns
Main memory reference ...................... 100 ns             
Compress 1K bytes with Zippy ............. 3,000 ns  =   3 µs
Send 2K bytes over 1 Gbps network ....... 20,000 ns  =  20 µs
SSD random read ........................ 150,000 ns  = 150 µs

Read 1 MB sequentially from memory ..... 250,000 ns = 250 µs

	#!/usr/bin/env perl6

	# see:
	# * http://transfixedbutnotdead.com/2010/01/13/anyone_for_metaprogramming/
	# * http://transfixedbutnotdead.com/2010/01/14/anyone-for-perl-6-metaprogramming/
	# * http://fingernailsinoatmeal.com/post/292301859/metaprogramming-ruby-vs-javascript
	# * http://transfixedbutnotdead.com/2010/10/31/perl6-metaprogramming-update/

	# below runs on Rakudo Star (2010.10 release).

	#! /usr/bin/env perl6
	use v6;

	my $article_template = slurp("templates/post.html");
	my $default_template = slurp("templates/default.html");
	my $root_url = "http://strangelyconsistent.org/blog";

	my @monthnames = <Jan Feb Mar Apr
	May Jun Jul Aug
	Sep Oct Nov Dec>;

	-- translate Markdown with code blocks into HTML
	-- with syntax highlighting.
	-- If article.md was the source, Lua was the language and we
	-- wanted a preview:
	-- lua prettify.lua article lua preview
	-- Without the last argument it will just write out the HTML body.
	-- Languages supported are 'lua', 'cpp', 'java' and 'go
	-- Indented code blocks may begin with an explicit @lang name line;
	-- if you do this then mark every code block explicitly
	-- e.g

	(* ocamlfind ocamlopt -o exmpl -package curl -linkpkg exmpl.ml *)
	open Printf

	let _ = Curl.global_init Curl.CURLINIT_GLOBALALL

	(*
	*************************************************************************
	** Aux. functions
	*************************************************************************
	*)

	p <- ggplot(mtcars, aes(factor(cyl),mpg,
	fill=factor(cyl),
	colour=factor(cyl)))

	p1 <- p+geom_violin(alpha=0.3, width=0.5) +
	geom_boxplot(width=0.2, outlier.colour=NA)

	p2 <- p+geom_violin(alpha=0.3, width=0.5) +
	geom_dotplot(binaxis='y', stackdir='center', dotsize=0.5)

	import com.cloudera.crunch._
	import com.cloudera.scrunch._

	class ScrunchWordCount {
	def wordCount(inputFile: String, outputFile: String) = {
	val pipeline = new Pipeline[ScrunchWordCount]
	pipeline.read(from.textFile(inputFile))
	.flatMap(_.toLowerCase.split("\\W+"))
	.filter(!_.isEmpty())
	.count

	;; echowuhao's solution to Intro to Vectors
	;; https://4clojure.com/problem/6

	:a :b :c