Camel Case Words Count

 

I've recently had to analyze URL path elements, and check each word in it. However I ran into an issue that I need to check each camel case word. For this, I've create a function to split a string to camel case words.

import (
  "fmt"
  "unicode"
)

func SplitCamelWords(segment string) []string {
  var words []string
  var word string

  var prevCharLetter bool
  var prevCharUpper bool
  inUpperWord := false
  for charIndex, currentChar := range segment {

   currCharUpper := unicode.IsUpper(currentChar)
   currCharLetter := unicode.IsLetter(currentChar)

   if charIndex > 0 {

    if currCharLetter {
     if prevCharLetter {
      if prevCharUpper {
       if currCharUpper {
        inUpperWord = true
       } else {
        if inUpperWord {
         words = append(words, word)
         word = ""
        }
       }
      } else {
       if currCharUpper {
        words = append(words, word)
        word = ""
       } else {
        inUpperWord = false
       }
      }
     }

    } else {
     inUpperWord = false
     if prevCharLetter {
      words = append(words, word)
      word = ""
     }
    }
   }

   prevCharUpper = currCharUpper
   prevCharLetter = currCharLetter
   word += fmt.Sprintf("%c", currentChar)
  }

  if prevCharLetter {
   words = append(words, word)
   word = ""
  }

  return words
}

and a test output is:

A -> [A]
a -> [a]
Aaaaa -> [Aaaaa]
AAAAA -> [AAAAA]
aaaaa -> [aaaaa]
A1 -> [A]
a1 -> [a]
Aaaaa1 -> [Aaaaa]
AAAAA1 -> [AAAAA]
aaaaa1 -> [aaaaa]
aB -> [a B]
aaaaB -> [aaaa B]
AaaaB -> [Aaaa B]
AaaaBBBB -> [Aaaa BBBB]
AaaaBbbbb -> [Aaaa Bbbbb]
aB2 -> [a B]
aaaaB2 -> [aaaa B]
AaaaB2 -> [Aaaa B]
AaaaBBBB2 -> [Aaaa BBBB]
AaaaBbbbb2 -> [Aaaa Bbbbb]
Aaaa1b -> [Aaaa 1b]
Aaaa1B -> [Aaaa 1B]
Aaaa1bbb -> [Aaaa 1bbb]
Aaaa1Bbb -> [Aaaa 1Bbb]
AaBbCc -> [Aa Bb Cc]
A1B2C3 -> [A 1B 2C]
Aa1Bb2Cc3 -> [Aa 1Bb 2Cc]
AAA BBB Ccc -> [AAA  BBB  Ccc]
AAA1BBB Ccc -> [AAA 1BBB  Ccc]
AAA1BBB Ccc -> [AAA 1BBB  Ccc]

Notice that the task is not as obvious as it might appear at first glace. We cannot just split whenever we find an upper case character, but instead we need to consider the sequence of characters.

For example: HouseOfLove would count as 3 words: House, Of, Love.

However, houseOFLove would still count as 3 words, since we have a sequence of upper case characters: House, OF, Love.

Frequent Pattern Growth Algoritm

 

In this post we will review the frequest pattern growth algorithm (aka FP Growth).

The goal of the algorithm is to find frequent sets in a large database. This goal is similar to the Apriori algorithm, but it requires only a single scan of the database. To achieve it goal, FP Growth builds a FP tree that is used to find the relations.

Let's assume that we have a database of transactions, each containing list of items.

First we count occurrences for each item, and notice the order of items by count.

The transactions are treated as if items were sorted by the occurrences. For simplicity, let update the transactions:

Now we construct the FP tree, keeping counters on each node. Notice that the items are added according to the ordered transaction. 

After the 1st transaction:

After the 2nd transaction:

After the 3rd transaction:

After the 4th transaction:

After the 5th transaction:

After the 6th transaction:

After the 7th transaction:

After the 8th transaction:

After the 9th transaction:

Next, for each item, we mark what are the paths that lead to the item, and keep the item node score.

For example, item A can be reached by :

• C, where the A node has count of 1
• D,E, where the A node has count of 1
• D,C,E, where the A node has count of 1

Now let us use a minimum support of 2 occurrences, which configures of common patterns we are searching.

For each item, we find sets of items which are common in the conditional paths, and have count at least as the minimum support.

Finally, we create frequent pattern rules where the conditional FP tree is used with the item:

 

Requirements for a Production Grade Kubernetes Based Solution

In this post we will review list of requirements for a production grade kubernetes solution. These requirements are standard for any deployment that is deployed in a shared resources kubernetes, and aim to provide security, reliability, and maintability for the deployment. 

Helm Chart

A deployment should provide a helm chart to install it. The helm chart should be customizable, enabling add and change of:

• Labels
• Annotations
• Image repo
• Image version
• Node selector
• Affinity
• CPU and memory resource per container
• Log verbosity
• Service definitions: types, ports
• Additional volume and volumes mounts

In terms of security:

• The RBAC should have least privileges settings
• Use read-only file system whereever possible

In addition, helm upgrade should run with minimum downtime.

Communication

All communication should support both clear text and TLS. In case of TLS, there should be an ability to specify the location of the PKI files.

Containers

All containers should follow the next guidelines:

• Run as non-root user
• Log to STDOUT
• Support liveness and readiness probes
• Accept SIGTERM and exit gracefully, and log termination upon exit

Benchmarking

• Detailed benchmarking should be done for the deployment, that specifies for a range of specified loads, the expected resources for each container.
• In case of need, auto scaling should be handled automatically.
• There should be no single point of failure. All services should high availability.

Tests

Development stage should include both unit tests, and end-to-end tests.

Full code coverage should be achieved as part of the tests.

Interview Questions

 

In this post we will review 2 interview questions. These were served to a colleage of mine on a job interview. His answers are the second solutions to each question. Looks quite smart to me, but he did not pass the test. I could not find the reason. Maybe you can?

Question 1: Buildings Heights

An array contains integer numbers specifying the max allowed height of a building in each location (index). 

We need to find a combination of buildings heights so that it follows the heights restrictions, and no two buildings have the same height.

Solution Alternative 1: Sorting

The first possible solution is to sort the array, and keep a set of used heights.

def find_building_heights(max_heights):
    sorted_heights = sorted(max_heights)
    building_heights = [0] * len(max_heights)
    used_heights = set()

    for i in range(len(sorted_heights)):
        height = sorted_heights[i]

        while height in used_heights:
            height -= 1

        if height <= 0:
            return None

        building_heights[i] = height
        used_heights.add(height)

    return building_heights


max_heights = [5, 3, 4, 6, 1, 10, 10, 10]
result = find_building_heights(max_heights)
if result:
    print("The building heights are:", result)
else:
    print("It's not possible to assign unique building heights.")

Solution Alternative 2: No Sorting

We can do this without sorting, and just keep a set of the used heights.

def find_building_heights(max_heights):
    building_heights = [0] * len(max_heights)
    used_heights = set()

    for i in range(len(max_heights)):
        height = max_heights[i]

        while height in used_heights and height > 0:
            height -= 1

        if height <= 0:
            return None

        building_heights[i] = height
        used_heights.add(height)

    return building_heights


max_heights = [5, 3, 4, 6, 1, 77, 77, 77]
result = find_building_heights(max_heights)
if result:
    print("The building heights are:", result)
else:
    print("It's not possible to assign unique building heights.")

Question 2: Post Office

We have queue of packages numbered 1 to n. 

Whenever a person arrives, and asks for his package, we move all the packages from the queue to a shelf until we get to his package. 

If the package is already on the shelf, just give it  to him. 

Given a list of the requested packages numbers, find the max items on the shelf.

Solution 1: Simulation

This solution is the naive one, just simulate the whole process.

def max_items_on_shelf(n, requests):
    queue = list(range(1, n + 1))
    shelf = set()
    max_shelf_size = 0

    for request in requests:
        if request in shelf:
            shelf.remove(request)
        else:
            while queue and queue[0] != request:
                shelf.add(queue.pop(0))

            if queue and queue[0] == request:
                queue.pop(0)

        max_shelf_size = max(max_shelf_size, len(shelf))

    return max_shelf_size


n = 7
requests = [4, 3, 8, 2, 1, 5]
print(max_items_on_shelf(n, requests))

Solution 2: Shortcut

This solution uses the understanding that the number of packages on the shelf is the number of items that should be removed minus the number of items that were already removed.

def max_items_on_shelf(requests):
    max_difference = 0

    for index, package in enumerate(requests):
        difference = package - (index + 1)
        max_difference = max(max_difference, difference)

    return max_difference


requests = [4, 3, 2, 10, 1, 5]
print(max_items_on_shelf(requests))

Create and Parse JWT in GO

 

In this post we will review how to create and parse JWT in GO.

We use the "user" claim to specify the user. We create a signed JWT, and then parse it back to get the user from the JWT.

package jwtparsing

import (
  "fmt"
  "github.com/golang-jwt/jwt"
  "testing"
  "time"
)

const userClaim = "user"

func TestValidation(t *testing.T) {
  signedToken := createJwtToken("myUser1")
  fmt.Printf("token is: %v\n", signedToken)

  user := parseJwtToken(signedToken)
  fmt.Printf("user is: %v\n", user)
}

To create a JWT we should use a secret know only at the server side. The JWT is based on a specific signing method that should be supported on the client side as well.

func createJwtToken(
  user string,
) string {
  var secretKey = []byte("secret-key")

  token := jwt.NewWithClaims(
   jwt.SigningMethodHS256,
   jwt.MapClaims{
    userClaim: user,
    "exp":     time.Now().Add(time.Hour * 24).Unix(),
   })

  signedToken, err := token.SignedString(secretKey)
  if err != nil {
   panic(err)
  }
  return signedToken
}

In this case we choose to parse the JWT without verifying it. It is important to understand the content of the JWT is not encrypted by only signed, hence we can parse it anywhere we want, without verification of the signature. This is ok only if we know that someone had already previously verified it, otherwise our system is broken.

func parseJwtToken(
  signedToken string,
) string {
  var jwtParser jwt.Parser
  claims := jwt.MapClaims{}
  _, _, err := jwtParser.ParseUnverified(signedToken, claims)
  if err != nil {
   panic(err)
  }
  jwtValue := claims[userClaim]
  user, ok := jwtValue.(string)
  if !ok {
   panic("convert claim failed")
  }

  return user
}

The output of the test is:

=== RUN   TestValidation
token is: eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJleHAiOjE3MTU2NzA3NDcsInVzZXIiOiJteVVzZXIxIn0.ynQLZ47Eup60OgkE0vbOtvii1g3MVSv4MxnvEE4Cv1U
user is: myUser1
--- PASS: TestValidation (0.00s)

Sending a Multipart Request

Multipart request is usually used by browsers to upload files to the server. Additional parameters can be also specified as part of the body. In this post we show an example of building a multipart request.

The following is an example to build a multipart HTTP request:

const Boundary = "MyBoundary"
const fileName = "file"

func CreateFormRequest(
  parameters map[string]string,
  fileData string,
) string {
  var stringBuilder strings.Builder
  for key, value := range parameters {
   stringBuilder.WriteString("--" + Boundary + "\n")
   line := fmt.Sprintf(`Content-Disposition: form-data; name="%v"`, key)
   stringBuilder.WriteString(line + "\n\n")
   stringBuilder.WriteString(value)
   stringBuilder.WriteString("\n")

  }
  stringBuilder.WriteString("--" + Boundary + "\n")
  line := fmt.Sprintf(`Content-Disposition: form-data; name="%v"; filename="%v"`, fileName, fileName)
  stringBuilder.WriteString(line + "\n")
  stringBuilder.WriteString("Content-Type: text/plain\n")
  stringBuilder.WriteString("\n")
  stringBuilder.WriteString(fileData)
  stringBuilder.WriteString("\n")
  stringBuilder.WriteString("--" + Boundary + "--\n")

  return stringBuilder.String()
}

Note the HTTP request should specify the multipart boundary string in the content type header:

headers := map[string]string{
  "Content-Type": "multipart/form-data; boundary=" + Boundary,
}

On the server side we will use a struct to read the multipart content:

type FormContent struct {
  File   *multipart.FileHeader `form:"file"`
  Values map[string]string
}

The server will read the multipart using a dedicated bind function:

func NewBindFile(originalBinder echo.Binder) echo.Binder {
  return BindFunc(func(i interface{}, ctx echo.Context) error {
   contentType := ctx.Request().Header.Get(echo.HeaderContentType)
   if !strings.HasPrefix(contentType, echo.MIMEApplicationForm) && !strings.HasPrefix(contentType, echo.MIMEMultipartForm) {
    return originalBinder.Bind(i, ctx)
   }

   formContent, ok := i.(*web.FormContent)
   if !ok {
    return fmt.Errorf("fail casting to form content")
   }

   form, err := ctx.MultipartForm()
   if err != nil {
    return err
   }

   formContent.File = form.File["file"][0]
   formContent.Values = make(map[string]string)
   for key, value := range form.Value {
    formContent.Values[key] = value[0]
   }

   return nil
  })
}

The related request handler can get the file data using:

fileData := web.ReadFormFile(formContent.File)

func ReadFormFile(fileHeader *multipart.FileHeader) []byte {
  if fileHeader == nil {
   return nil
  }
  file, err := fileHeader.Open()
  kiterr.RaiseIfError(err)
  body, err := io.ReadAll(file)
  kiterr.RaiseIfError(err)
  return body
}

Streaming Messages to a Go gRPC Server

 

In this post we will demonstrate streaming gRPC messages to a server using Go.

Create proto file

The proto file describes the gRPC service APIs. In this example we create a single API to send stream of persons from the client to the server.

persons.proto

syntax = "proto3";
option go_package = "my.example.com/com/grpctemplates";

service Persons {
  rpc StreamPersons(stream Person) returns(ProcessedIndication){

  }
}

message Person{
  string name = 1;
  int32 age = 2;
}

message ProcessedIndication{

}

Generate Go templates

To generate go sources using the proto file, we first install the required tools:

sudo apt install -y protobuf-compiler
protoc --version  
go install google.golang.org/protobuf/cmd/protoc-gen-go@v1.28
go install google.golang.org/grpc/cmd/protoc-gen-go-grpc@v1.2

Next we run the tools to generate the Go templates:

export PATH="$PATH:$(go env GOPATH)/bin"
protoc --go_out=. --go_opt=paths=source_relative \
    --go-grpc_out=. --go-grpc_opt=paths=source_relative \
    persons.proto

rm -rf grpctemplates
mkdir grpctemplates
mv persons.pb.go grpctemplates/
mv persons_grpc.pb.go grpctemplates/

The Main

In our example we will run both the client and the server in the same process.

package main

import (
  "grpcexample/personsclient"
  "grpcexample/personsserver"
  "time"
)

func main() {
  go func() {
   time.Sleep(time.Second)
   personsclient.RunClient()
  }()

  personsserver.RunServer()
}

The Server

The server implements an API to get the stream of persons, prints them, and return a complete indication.

package personsserver

import (
  "fmt"
  "google.golang.org/grpc"
  "grpcexample/grpctemplates"
  "io"
  "log"
  "net"
)

type personsServer struct {
  grpctemplates.UnimplementedPersonsServer
}

func (s *personsServer) StreamPersons(stream grpctemplates.Persons_StreamPersonsServer) error {
  for {
   person, err := stream.Recv()
   if err == io.EOF {
    return stream.SendAndClose(&grpctemplates.ProcessedIndication{})
   }
   if err != nil {
    panic(err)
   }

   log.Printf("got person %v\n", person.Name)
  }
}

func RunServer() {
  log.Print("starting gRPC server")
  port := 8080
  listener, err := net.Listen("tcp", fmt.Sprintf("localhost:%d", port))
  if err != nil {
   panic(err)
  }

  persons := personsServer{}
  grpcServer := grpc.NewServer()
  grpctemplates.RegisterPersonsServer(grpcServer, &persons)

  err = grpcServer.Serve(listener)
  if err != nil {
   panic(err)
  }
}

The Client

The client sends a stream of persons to the server, and waits for completion before closing the connection.

package personsclient

import (
  "context"
  "fmt"
  "google.golang.org/grpc"
  "google.golang.org/grpc/credentials/insecure"
  "grpcexample/grpctemplates"
  "log"
)

func RunClient() {
  log.Printf("client sending data starting\n")

  connection, err := grpc.Dial(
   "localhost:8080",
   grpc.WithTransportCredentials(insecure.NewCredentials()),
  )
  if err != nil {
   panic(err)
  }

  defer func() {
   err = connection.Close()
   if err != nil {
    panic(err)
   }
  }()

  client := grpctemplates.NewPersonsClient(connection)
  stream, err := client.StreamPersons(context.Background())
  if err != nil {
   panic(err)
  }

  for i := range 10 {
   person := grpctemplates.Person{
    Name: fmt.Sprintf("person %v", i),
    Age:  int32(i),
   }
   err = stream.Send(&person)
   if err != nil {
    panic(err)
   }
  }
  _, err = stream.CloseAndRecv()
  if err != nil {
   panic(err)
  }
  log.Printf("client sending data done\n")
}