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
}
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:
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>
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")))