Latest Posts

Interview Questions in Go - 3SUM Problem 2012-09-09

In this post, I'll introduce the 3SUM problem that is commonly encountered in technical interviews, and go through a solution in Go.

3SUM can be explained as follows:

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

So for example, if we have the integers [1, 2, -3], we do in fact have a, b, and c such that a + b + c = 0, since we can add 1 + 2 + (-3) to get 0.

A simple solution to this problem is to iterate over the list with 3 for loops, like so:

package main

import (
    "fmt"
)

func threeSum(lon []int) (result []int) {
    for i, x := range lon {
        for j, y := range lon[i+1:] {
            for _, z := range lon[j+1:] {
                if x+y+z == 0 {
                    result = []int{x, y, z}
                    return
                }
            }
        }
    }
    return
}

Go and Vim 2012-07-27

The Go distribution comes with some great tools for writing Go in Vim. I frequently use the :Import, :Drop, and :Fmt commands.

The simplest way to enable all of the Vim plugins is to add the following lines to your vimrc:

set rtp+=$GOROOT/misc/vim
filetype plugin indent on
syntax on

Here is some of the functionality you get from the plugins:

:Import

:Import is a Vim command for importing Go packages.

For example, if you have some Go source code open in Vim:

package main

import (
    "net/http"
)

and you want to import the encoding/json package, you can type this in Vim:

:Import encoding/json

and it will result in the following:

The Case of encoding/xml 2012-07-09

I've been using Go a lot lately, and after reading Parsing huge XML files with Go, I had decided I wanted to try out parsing XML in Go. One sizeable XML file that I've used before in a project is KANJIDIC2, so I went with that.

The Japanese language has three writing systems: hiragana, katakana, and kanji. Kanji are adopted from Chinese characters, and a single kanji may be used to write multiple different words. For example, 人 can be used by itself to mean "person," but it can also be used in words like 日本人 to mean "Japanese person." The KANJIDIC2 file is essentially a comprehensive database of kanji in the Japanese language.

So, one can imagine that there is a lot of information attached to any one kanji character, such as number of strokes, readings, meanings, and so on. Here's the entry for the 人 character:

<!-- Entry for Kanji: 人 -->
<character>
<literal>人</literal>
<codepoint>
<cp_value cp_type="ucs">4eba</cp_value>
<cp_value cp_type="jis208">31-45</cp_value>
</codepoint>
<radical>
<rad_value rad_type="classical">9</rad_value>
</radical>
<misc>
<grade>1</grade>
<stroke_count>2</stroke_count>
<freq>5</freq>
<jlpt>4</jlpt>
</misc>
<dic_number>
<dic_ref dr_type="nelson_c">339</dic_ref>
<dic_ref dr_type="nelson_n">99</dic_ref>
<dic_ref dr_type="halpern_njecd">3368</dic_ref>
<dic_ref dr_type="halpern_kkld">2111</dic_ref>
<dic_ref dr_type="heisig">951</dic_ref>
<dic_ref dr_type="gakken">9</dic_ref>
<dic_ref dr_type="oneill_names">14</dic_ref>
<dic_ref dr_type="oneill_kk">4</dic_ref>
<dic_ref dr_type="moro" m_vol="1" m_page="0556">344</dic_ref>
<dic_ref dr_type="henshall">39</dic_ref>
<dic_ref dr_type="sh_kk">1</dic_ref>
<dic_ref dr_type="sakade">30</dic_ref>
<dic_ref dr_type="jf_cards">11</dic_ref>
<dic_ref dr_type="henshall3">39</dic_ref>
<dic_ref dr_type="tutt_cards">7</dic_ref>
<dic_ref dr_type="crowley">2</dic_ref>
<dic_ref dr_type="kanji_in_context">15</dic_ref>
<dic_ref dr_type="busy_people">2.5</dic_ref>
<dic_ref dr_type="kodansha_compact">42</dic_ref>
<dic_ref dr_type="maniette">960</dic_ref>
</dic_number>
<query_code>
<q_code qc_type="skip">4-2-4</q_code>
<q_code qc_type="sh_desc">2a0.1</q_code>
<q_code qc_type="four_corner">8000.0</q_code>
<q_code qc_type="deroo">1262</q_code>
</query_code>
<reading_meaning>
<rmgroup>
<reading r_type="pinyin">ren2</reading>
<reading r_type="korean_r">in</reading>
<reading r_type="korean_h">인</reading>
<reading r_type="ja_on">ジン</reading>
<reading r_type="ja_on">ニン</reading>
<reading r_type="ja_kun">ひと</reading>
<reading r_type="ja_kun">-り</reading>
<reading r_type="ja_kun">-と</reading>
<meaning>person</meaning>
<meaning m_lang="fr">être humain</meaning>
<meaning m_lang="fr">personne</meaning>
<meaning m_lang="es">persona</meaning>
<meaning m_lang="pt">pessoa</meaning>
</rmgroup>
<nanori>じ</nanori>
<nanori>と</nanori>
<nanori>ね</nanori>
<nanori>ひこ</nanori>
<nanori>ふみ</nanori>
</reading_meaning>
</character>

Hmac Sha1 Digest In Racket 2012-07-08

I wanted to do the same thing as this in Python:

import hmac
from hashlib import sha1

hmac.new("private-key", "some-string", sha1)

Or, from the command line:

% echo -n "some-string" | openssl dgst -sha1 -hmac "private-key"  

Eventually, Norman Gray on the Racket users mailing list told me to simply do:

(require web-server/stuffers/hmac-sha1
             openssl/sha1)

(bytes->hex-string
 (HMAC-SHA1
  (string->bytes/locale "private-key")
  (string->bytes/locale "some-string")))