JustDifferent
BAN USER
Comments (2)
Followers (1)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Did a solution in golang see comment for explanation:
package main
import (
"fmt"
"math"
)
func main() {
arr := []Point{Point{X: 3, Y: 40}, Point{X: 19, Y: 4}, Point{X: 7, Y: 4}, Point{X: 1, Y: 4}, Point{X: 17, Y: 4}, Point{X: 11, Y: 4}}
fmt.Println(Closest(arr, 2))
}
type Point struct {
X int
Y int
}
func (point Point) distance() float64 {
a := math.Pow(float64(point.X), 2)
b := math.Pow(float64(point.Y), 2)
return math.Sqrt(a + b)
}
func Closest(points []Point, k int) []Point {
position := selection(points, k)
//return slice of k closest points
return points[0:position]
}
//Quick Selection algorithm
//Basically what amounts to a partial insertion sort
//Customized for Point struct
//Return position kth Point
func selection(arr []Point, k int) int {
to := len(arr)  1
for from := 0; from < to; {
read := from
write := to
midV := arr[(read+write)/2].distance()
for read < write {
if arr[read].distance() >= midV {
swap(arr, read, write)
write = write  1
} else {
read = read + 1
}
}
if arr[read].distance() > midV {
read = read  1
}
if k <= read {
to = read
} else {
from = read + 1
}
}
return k
}
func swap(arr []Point, i int, j int) {
temp := arr[i]
arr[i] = arr[j]
arr[j] = temp
}

JustDifferent
January 18, 2014 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Solution done in golang. Converts each word to an array of character counts in one pass. O(n).
This array is the key, the word list is the value.
So O(n+m) where n is the word length and m is the number of words. Also uses stores a 256 length byte array for each anagram (regardless of length of each word and frequency of each anagram)
Sorting at best is O(n log n) so be careful of sorting based solutions. Also since strings are usually immutable across most languages be careful of solutions that use string split and string append as they add (and hide) complexity.
 JustDifferent January 18, 2014