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
}