Tricky Golang interview questions - Part 2: BigO of len(...)

An example I want to discuss is quite simple and requires knowledge about how some data types are constructed under the hood.

Question: What is the time complexity of len(...) for each data type

package main

import (
    "fmt"
)

func main() {
    _ = len("string")
    _ = len([]int{1, 2, 3})
    _ = len(map[string]int{"one": 1, "two": 2, "three": 3})
}

The answer to this question is very easy:
The time complexity of the len(...) for all cases is O(1).

If you answer like this, the interviewer will come up with the following question: why? To answer this question, we need to look under the hood of each of the types.

String

According to the Go documentation string type can be represented as a struct, a StringHeader. StringHeader is the runtime representation of a string.

type StringHeader struct {
    Data uintptr
    Len  int
}

• Data is a pointer, which points to an underlying (backing) byte array that stores the string data
• Len is the length of an underlying (backing) byte array

Slice

Slice can also be represented as a struct, a SliceHeader. SliceHeader is the runtime representation of a slice.

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

• Data is a pointer, which points to an underlying (backing) byte array that stores the string data
• Len is the length of an underlying (backing) byte array
• Cap is the capacity of the slice.

Map

Map is a bit more complex data structure and is represented as a package in Go. In this package, we can find the map header struct with its corresponding fields.

type hmap struct {
    count      int
    flags      uint8
    B          uint8
    noverflow  uint16
    hash0      uint32
    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate  uintptr
    extra      *mapextra
}

We need the count field for this struct. According to the comments

• count is live cells == size of map or simply length of map

Now we know how these data structures are constructed under the hood we can answer the follow-up question by the interviewer:
Why len(...) operations are O(1)?

---

The Len function simply returns the value of the field in the header responsible for storing the length.

---

It's that easy!