Brute-force approach #

Here I present a few approaches to deduce “minimum insertions” required to convert a string into a palindrome.

The basic brute force approach is quite simple, given a string with length L, start comparing, the first character from left and the last character while scanning inwards.

Here is a basic test for a palindrome.

   L = len(s) 
   for i in range(L):
       if s[i] != s[L - i - 1]:
           return False,i,L-i -1
   return True,0,0

The above code returns True if the string is a palindrome or returns False with mismatching indices.

Inverse distance weighting (IDW) is a type of deterministic method for multivariate interpolation with a known scattered set of points. The assigned values to unknown points are calculated with a weighted average of the values available at the known points.

This technique, explicitly makes the assumption that things that are close to one another are more alike than those that are farther apart. To predict a value for any unmeasured location, IDW uses the measured values surrounding the prediction location. The measured values closest to the prediction location have more influence on the predicted value than those farther away. IDW assumes that each measured point has a local influence that diminishes with distance. It gives greater weights to points closest to the prediction location, and the weights diminish as a function of distance, hence the name inverse distance weighted.

This post includes go-lang based implementation of some of the classic sorting algorithms.

This article primarily, has been written, as an academic exercise, to not forget the basic principles of sorting.

Bubble Sort #

wiki

Bubble sort is perhaps the simplest of all sorting algorithms, the basic principle is to bubble up the largest (or the smallest) and then the second largest and then the third largest and so on. Each bubble takes the full sweep of the list, hence best-case, average-case as well as the worst-case performance are all O(n2)

Reading and writing binary files can often be a fast and very efficient alternatives to csv. They obviously have their challenges, however in this post I intent to present a very basic example of saving models (struct) into binary file and later reading it.

package main

import (
	"log"
	"os"
	"encoding/binary"
	"bytes"
	"fmt"
	"math/rand"
	"time"
)

//this type represnts a record with three fields
type payload struct {
	One float32
	Two float64
	Three uint32
}

func main() {

	writeFile()
	readFile()

}

func readFile() {

	file, err := os.Open("test.bin")
	defer file.Close()
	if err != nil {
		log.Fatal(err)
	}

	m := payload{}
	for i := 0; i < 10; i++ {
		data := readNextBytes(file, 16)
		buffer := bytes.NewBuffer(data)
		err = binary.Read(buffer, binary.BigEndian, &m)
		if err != nil {
			log.Fatal("binary.Read failed", err)
		}

		fmt.Println(m)
	}

}

func readNextBytes(file *os.File, number int) []byte {
	bytes := make([]byte, number)

	\_, err := file.Read(bytes)
	if err != nil {
		log.Fatal(err)
	}

	return bytes
}

func writeFile() {
	file, err := os.Create("test.bin")
	defer file.Close()
	if err != nil {
		log.Fatal(err)
	}

	r := rand.New(rand.NewSource(time.Now().UnixNano()))

	for i := 0; i < 10; i++ {


		s := &payload{
			r.Float32(),
			r.Float64(),
			r.Uint32(),
		}
		var bin\_buf bytes.Buffer
		binary.Write(&bin\_buf, binary.BigEndian, s)
		//b :=bin\_buf.Bytes()
		//l := len(b)
		//fmt.Println(l)
		writeNextBytes(file, bin\_buf.Bytes())

	}
}
func writeNextBytes(file *os.File, bytes []byte) {

	\_, err := file.Write(bytes)

	if err != nil {
		log.Fatal(err)
	}

}

The code presented above will randomly populate 10 records of type payload and save it to a binary file, then it will read those 10 records as well.