Leetcode Binary Tree Array Format in Golang

In the Binary Tree section of leetcode, they provide an Input array with values used to create a binary tree.

It isn't necessary to reproduce the trees to solve the traversal problems as you can manually build a tree by adding Left and Right nodes manually.

Still using the input data helps to suss out bugs when it fails some tests. The difficulty I ran into was trying to implement a recursive solution when the approach was understanding (with some googling help) that a queue was needed.

Below are my comments and code.

// create binary tree given a leetcode compressed array

// a verbose version of a binary tree would have a NULL_VALUE

// for every node at the full height eg.

//

// 0

// null 2

//

// null null 3 null

// Input = [0, null, 2, null, null, 3]

//

// leetcode BT format is a little more efficient as it will

// skip the 2 lower nulls

//

// Input = [0, null, 2, 3]

// To build the binary tree use a queue that will allow us to

// process each level before continue to the next level.

// When a node is created we add it to the queue. The L/R logic

// proceeds and pops the next value from the Input array.

// If the value is a null, we don't add it to the queue which stops

// further processing on that branch

//

// We loop until the queue is empty.

func (b *BinaryTree) CreateUnsorted(arr []int) {

if len(arr) <= 0 {

fmt.Println("No Elements")

return

}

val, arr := ArrayPop(arr)

b.Root = &TreeNode{Val: val}

queue := []*TreeNode{b.Root}

var node *TreeNode

leftVal := 0

rightVal := 0

for len(queue) > 0 {

node, queue = ArrayPop(queue)

if len(arr) <= 0 {

continue

}

leftVal, arr = ArrayPop(arr)

if leftVal != NULL_VALUE {

node.Left = &TreeNode{Val: leftVal}

queue = append(queue, node.Left)

}

if len(arr) <= 0 {

continue

}

rightVal, arr = ArrayPop(arr)

if rightVal != NULL_VALUE {

node.Right = &TreeNode{Val: rightVal}

queue = append(queue, node.Right)

}

}

}

Setting up Express and Typescript August 2022

To learn express and typescript, I wanted to convert the default express skeleton app into a typescript one. This uses the tutorial link below and only adds minimal changes to the express framework.

https://expressjs.com/en/starter/installing.html

and some help from this url too

https://blog.logrocket.com/how-to-set-up-node-typescript-express/

# sets up package.json
mkdir myexpress; cd myexpress
npm init -y

###
# express
npm install express

# creates an express project using pug templating instead of default jade
npx express-generator --view=pug

npm install

# to start http://localhost:3000/
DEBUG=myapp:* npm start

###
# typescript
# save-dev packages used only during dev and does not need to be deployed to prod
# ts-node is cli/repl for typescript
npm install typescript ts-node --save-dev

# https://devblogs.microsoft.com/typescript/writing-dts-files-for-types/
npm install @types/node @types/express --save-dev

npx tsc --init # creates tsconfig.json

###
# Problems
# 1. convert all the .js files into typescript
# 2. create new directory called dist or built to store the transpiled js
# 3. copy static files into dist
# 4. transpile ts into js
# 5. run the server using `node dist/index.js`
# 6. update package.json and tsconfig.json so that you can run `DEBUG=myapp:* npm start`

## 1. convert all the .js files into typescript

# adapt app.js into app.ts
npm install @types/http-errors @types/cookie-parser @types/morgan

# routes/index.ts

import express from "express";
const router = express.Router();

router.get('/', function(req, res, next) {
  res.render('index', { title: 'Express' });
});

export default router;

# app.js
import createError from "http-errors";
import express from "express";
import path from "path";
import cookieParser from "cookie-parser";
import logger from "morgan";

import indexRouter from  "./routes/index";
import usersRouter from "./routes/users";
import {NextFunction, Request, Response} from "express-serve-static-core";

const app = express();

// view engine setup
app.set('views', path.join(__dirname, '../views'));

//...

app.use(express.static(path.join(__dirname, '../public')));

//...

// error handler
app.use(function(err: any, req: Request, res: Response, next: NextFunction) {
  // set locals, only providing error in development
  res.locals.message = err.message;
  res.locals.error = req.app.get('env') === 'development' ? err : {};

  // render the error page
  res.status(err.status || 500);
  res.render('error');
});

app.listen(3000, '127.0.0.1');
export = app

## 3. Update the views/public paths used in app.js
# views and public need to be updated to ../ as app.js will be in ./dist and these two dirs will be one level up. This has been done in the above code snippet.

## 4. transpile cli
# this will search all ts files from the root directory and store the js files into the dist directory with the same hierarchy
npx tsc --outDir dist

## 5. run the server using `node dist/app.js`
With the addition of the last line above app.listen(//...), we can run node server using the `node` command.

## 6. update package.json and tsconfig.json so that you can run `DEBUG=myapp:* npm start`
# tsconfig.json
"outDir": "./dist",                                  /* Specify an output folder for all emitted files. */

# package.json
# this exists
  "scripts": {
    "start": "node ./bin/www"
  },

# edit ./bin/www
var app = require('../dist/app');

# Remove the app.listen line in app.ts as it's not needed any more
app.listen(3000, '127.0.0.1');

# and now it will work using the express way of starting the server
DEBUG=myapp:* npm start

## Bonus
# You can add a build to "scripts" in package.json
"build": "npx tsc"
# or use the cli
`npx tsc --watch`

Fedora 30 Add another port for ssh'ing to get around some wifi filters

Some ISP's that offer free wifi will not allow you to ssh. To get around this you can set your ssh server to use another port like 8080.

For Fedora 30

1) sudo vim /etc/ssh/sshd_config

Change

#Port 22
to
Port 22
Port 8080

# This allows two ports to connect to ssh

2) Update selinux to allow ssh on port 8080

sudo semanage port -m -t ssh_port_t -p tcp 8080

If you use -a you will get an error like
ValueError: Port tcp/8080 already defined

If you -d you will get another error like
ValueError: Port tcp/8080 is defined in policy, cannot be deleted

Use this to check:

sudo semanage port -l | grep 8080
http_cache_port_t              tcp      8080, 8118, 8123, 10001-10010
ssh_port_t                     tcp      8080, 22

Create an interface array consisting of a generic struct type in golang

I was looking at how to get a result set from a golang sql query. It seemed that a lot of the examples explicitly defined the fields or declared a struct that are passed into the Scan() method such as:

var id int
var name string
err = rows.Scan(&id, &name)
// or
row = MyStruct{}

err = rows.Scan(&row.Id, &row.Name)

This seemed like a lot of repetition if every query required this logic. My next thought was to see if I could pass in a struct, use reflect to obtain the fields and return a slice of values.

Here are two examples, the first one uses uses append and requires type assertion to access the fields. The second example uses reflect.append and each field can be accessed directly from the element.

Note: Additional checks should be added, such as making sure the address of the object is passed in.

First

package main

import (

    "fmt"

    "reflect"

)

type MyStruct struct {

    Id int

    Name string

}

func main() {

    me := MyStruct{}

    result := doIt(&me)

    for _, v := range result {

        fmt.Printf("%d %s\n", v.(MyStruct).Id, v.(MyStruct).Name)

    }

}

func doIt(genericStruct interface{}) []interface{} {

    params := []interface{}{}

    var myStruct reflect.Value

    structType := reflect.TypeOf(genericStruct).Elem()

    // First Element

    myStruct = reflect.New(structType).Elem()

    myStruct.FieldByName("Id").SetInt(1)

    myStruct.FieldByName("Name").SetString("one")

    fmt.Printf("%#v\n", myStruct)

    params = append(params, myStruct.Interface())

    // Second Element

    myStruct = reflect.New(structType).Elem()

    myStruct.FieldByName("Id").SetInt(2)

    myStruct.FieldByName("Name").SetString("two")

    fmt.Printf("%#v\n", myStruct)

    params = append(params, myStruct.Interface())

    return params

}

Second

package main

import (

    "fmt"

    "reflect"

)

type MyStruct struct {

    Id int

    Name string

}

func main() {

    myStruct := []MyStruct{}

    doIt(&myStruct)

    for _, v := range myStruct {

        fmt.Printf("%d %s\n", v.Id, v.Name)

    }

}

func doIt(genericStructArray interface{}) {

    var myStruct reflect.Value

    genericValue := reflect.ValueOf(genericStructArray).Elem()

    genericType := genericValue.Type().Elem()

    // First Element

    myStruct = reflect.New(genericType).Elem()

    myStruct.FieldByName("Id").SetInt(1)

    myStruct.FieldByName("Name").SetString("one")

    fmt.Printf("%#v\n", myStruct)

    genericValue.Set(reflect.Append(genericValue, myStruct))

    // Second Element

    myStruct = reflect.New(genericType).Elem()

    myStruct.FieldByName("Id").SetInt(2)

    myStruct.FieldByName("Name").SetString("two")

    fmt.Printf("%#v\n", myStruct)

    genericValue.Set(reflect.Append(genericValue, myStruct))

}

Output (same for both)

main.MyStruct{Id:5, Name:"one"}

main.MyStruct{Id:2, Name:"two"}

5 one

2 two

Learning middleware patterns in Golang

Middlewares are often applied using a wrapping a method wrapping pattern (chain of responsibility design pattern). To better understand how to do this in golang, I've started with the Handler interface and created a HandlerFunc that mimics the HandlerFunc in https://golang.org/src/net/http/server.go except I've replaced the args with (context string). This allowed me to trace the order that middlewares access the current context.

func (r *Request) Context() context.Context

Some useful links that helped guide me.
https://www.calhoun.io/why-cant-i-pass-this-function-as-an-http-handler/
https://www.alexedwards.net/blog/making-and-using-middleware
https://github.com/justinas/alice Ended with an implementation that resembles this. Thx!

Update July 2019: Middleware args changed to Handler instead of HandlerFunc

package main

import "fmt"

// HandlerFunc, ServeHTTP match the go standard libs except

// (w ResponseWriter, r *Request) has been replaced by (context string).

// We treat this as a buffer that we can read from add values to.

// Analagous to reading GET/POST args from Request and adding

// Information to Request.context()

// https://golang.org/src/net/http/server.go

// This implements Handler interface because it matches signature, meaning it has a

// ServerHTTP method with the same argument types

type Handler interface {

    ServeHTTP(context string)

}

type HandlerFunc func(context string)

func (f HandlerFunc) ServeHTTP(context string) {

    f(context)

}

func baseHandler(h Handler) Handler {

    fmt.Println("Before return baseHandler")

    return HandlerFunc(func(context string) {

        fmt.Println("Before baseHandler")

        context = context + " base"

        h.ServeHTTP(context) // call ServeHTTP on the original handler

        fmt.Println("After baseHandler")

    })

}

func first(h Handler) Handler {

    fmt.Println("Before return first")

    return HandlerFunc(func(context string) {

        fmt.Println("Before first")

        context = context + " first"

        h.ServeHTTP(context) // call ServeHTTP on the original handler

        fmt.Println("After first")

    })

}

func second(h Handler) Handler {

    fmt.Println("Before return second")

    return HandlerFunc(func(context string) {

        fmt.Println("Before second")

        context = context + " second"

        h.ServeHTTP(context) // call ServeHTTP on the original handler

        fmt.Println("After second")

    })

}

func IndexEndPoint(s string) {

    fmt.Println("Index EndPoint: ", s)

}

type Middleware func(Handler) Handler

type MiddlewareStack struct {

    middlewares []Middleware

}

func NewMiddlewareStack(middlewares ...Middleware) MiddlewareStack {

    return MiddlewareStack{middlewares: middlewares}

}

// The middleware wrap pattern eg. second(first(baseHandler(IndexEndPoint))

// means you need to find the deepest method and work backwards -

// baseHandler, then first, then second.

// This implementation stores the middlewares in an array and can mutate the

// values beginning with the lowest to highest index; which has some

// readability benefits.

func (ms *MiddlewareStack) EndPoint(endPoint HandlerFunc) Handler {

    var h Handler

    // first middlware in array can access the context first

    for i := len(ms.middlewares) - 1; i >= 0; i-- {

        mw := ms.middlewares[i]

        // for _, mw := range ms.middlewares {

        if h == nil {

            h = mw(endPoint)

        } else {

            h = mw(h)

        }

    }

    return h

}

func main() {

    // middleware function wrapping

    // Output: Index EndPoint: start second first base

    f := second(first(baseHandler(HandlerFunc(IndexEndPoint))))

    f.ServeHTTP("start")

    /*

        // array of middleware

        // Another version of above, but storing in an array

        middleWares := []MiddleWare{baseHandler, first, second}

        var hFunc HandlerFunc

        for _, mw := range middleWares {

            if hFunc == nil {

                hFunc = mw(IndexEndPoint)

            } else {

                hFunc = mw(hFunc)

            }

        }

        hFunc.ServeHTTP("start")

    */

    // middleware struct

    // Index EndPoint: start base first second

    middlewareStack := NewMiddlewareStack(baseHandler, first, second)

    hFunc := middlewareStack.EndPoint(IndexEndPoint)

    hFunc.ServeHTTP("start")

}

Firefox 57 and lost some shortcuts on mac

There was an old plugin called Customizeable Shortcuts that hadn't been updated for while and was not usable with Firefox 57. I was using it to remap the 'search location bar' shortcut.

Since I already use karabiner to remap some modifier keys for macos, it might be able to use it instead of waiting for a new firefox shortcut addon.

Note: If you're confused by the left_option/left_command it's cause I've first remap left_command to left_option.

1) Have a look at some of the examples for karabiner shortcuts
https://pqrs.org/osx/karabiner/complex_modifications/#key_specific

2) Create a json and take note of the path

{
  "title": "Firefox command-d search location",
  "rules": [
    {
      "description": "command-d search location",
      "manipulators": [
        {
          "type": "basic",
          "from": {
              "key_code": "d",
              "modifiers": {
                  "mandatory": ["left_option"],
                  "optional": ["any"]
              }
          },
          "to": [
              {
                "key_code": "l",
                "modifiers": [
                  "left_command"
                ]
              }
          ],
          "conditions": [
            {
              "type": "frontmost_application_if",
              "bundle_identifiers": [
                "^org\\.mozilla\\.firefox"
              ]
            }
          ]
        }
      ]
    }
  ]
}

I saved this to my desktop with the name firefox-command-d.json

What is going on? frontmost_application_if only runs the above shortcuts if it's the app focused.
bundle_identifiers is your app id that you can find in the plist.

3) Now run enter this in the url bar in firefox: karabiner://karabiner/assets/complex_modifications/import?url=file:///Users//Desktop/firefox-command-d.json

Enable this and you have your remap.

Blurry Font in Firefox after updating to Linux Fedora 25

I recently did a clean update of fedora and found the font to render quite blurry.

What I found out:

1) gnome-tweak-tool font settings do not work. At the time of the post any of the font settings did not make a difference.

2) You may start trying to use font-tweak-tool or font-manager. Be aware that these may create font config files in your ~/ or in ~/.config

These may need to be deleted so that your gnome settings take precedence.

Note: I've installed microsoft and ubuntu fonts for linux.

So what's the fix?

a) Go to Settings > Fonts and change the settings here to Anti Aliasing: rgba and Hinting: full

At this point your terminal should look good.

b) For me, firefox and sublime text had bad looking fonts.

There's a directory in /etc/fonts/conf.d that controls some additional font rendering. It's odd that there's no GUI to modify this directly.

sudo ln -s  /usr/share/fontconfig/conf.avail/10-hinting-full.conf /etc/fonts/conf.d/
sudo rm  /usr/share/fontconfig/conf.avail/10-hinting-slight.conf

Log out and Log back in and things should be clearer.