Errata for Data Structures & Algorithms in Kotlin 2nd Edition

Creating this topic to catch any typos and bugs in the 2nd Edition of Data Structures & Algorithms in Kotlin.

There seem to be some problems with the challenge problem for Chapter 11, that is,
implementing a function ArrayList.findIndices(value: T) where T: Comparable
which returns a range of indices satisfying this[index] == value.

arrayListOf(0,1,3,3).findIndices(2)
// -> This will throw a StackOverflowException
//    with the subroutine call 
//    startIndex(2, 0..3) going into an infinite recursion 
//    on the empty range 2..1

The problem here is with missing a check for emptiness of the range.

A second problem with both subfunctions startindex and endIndex on the pages 221 and 222 is the checking for the middleIndex lying on either boundary of the list.

val arr = arrayListOf(0,1)
arr.findIndices(0)
// → returns null where it should return 0..0

Here the first computed middleIndex 1 is already the right boundary of the list.
Then the following will falsely return null in the previous example:

// 2 
if (middleIndex == 0 || middleIndex == size – 1) { // ?????
    return if (this[middleIndex] == value) {
        middleIndex 
    } else {
        null    // ?????
    }
}

I didn’t quite succeed in fixing every issue with the book implementation though.
There seem to be yet more issues with corner cases.
I did however find a solution which is loosely based on the approach from the following video lecture

Here’s an alternative solution:

/**
 * binaryFindFirst is only applicable on 'this' with argument prop if 
 *
 * this.map{ prop(this,it) } == [false, ... , false, true, ... , true]
 *    or
 * this.map{ prop(this,it) } == [false, ... , false]
 *    or 
 * this.map{ prop(this,it) } == [true , ... , true]
 * 
 * In other words:
 * If there exist indices i such that prop(this, i) == true 
 * then the list 'this' is partitioned such that all elements j with 
 * prop(this, j) == false lie on the left, and those indices 
 * i with prop(this,i) == true lie on the right.
 */
 
fun <T> List<T>.binaryFindFirst(
    prop: (l: List<T>, ind: Int) -> Boolean
): Int? {
    var res: Int? = null 
    var l = 0
    var r = this.lastIndex 
    while(l <= r) {
        val m = l + (r - l)/2 
        if (prop(this,m)) {
            res = m 
            r = m - 1
        }
        else 
            l = m + 1
    }
    return res
}

/**
 * binaryFindLast is only applicable on 'this' with argument prop if 
 *
 * this.map{ prop(this,it) } == [true, ... , true, false, ... , false]
 *    or
 * this.map{ prop(this,it) } == [false, ... , false]
 *    or 
 * this.map{ prop(this,it) } == [true , ... , true]
 *
 * In other words:
 * If there exist indices i such that prop(this, i) == true 
 * then the list 'this' is partitioned such that all elements j with 
 * prop(this, j) == false lie on the right, and those indices 
 * i with prop(this,i) == true lie on the left.
 */

fun <T> List<T>.binaryFindLast(
    prop: (l: List<T>, ind: Int) -> Boolean
): Int? {
    var res: Int? = null 
    var l = 0
    var r = this.lastIndex 
    while(l <= r) {
        val m = l + (r - l)/2 
        if (prop(this,m)) {
            res = m 
            l = m + 1
        }
        else 
            r = m - 1
    }
    return res    
}

/**
 * findIndices only applies to sorted lists.
 */
fun <T: Comparable<T>> List<T>.findIndices(value: T): IntRange? {
    // 1
    val left = binaryFindFirst { list, index ->
        list[index] >= value
    } ?: return null
    
    // 2
    if (this[left] != value) return null

    // 3
    val right = binaryFindLast { list, index -> 
        list[index] <= value
    } ?: return null

    // 4
    return left..right
}

/*
  1. The list must by assumption be sorted and any indices k 
     such that list[k] >= value are on the right.
     So binaryFindFirst is applicable.
 
  2. By assumption the list is sorted.
     Thus if the first index k such that list[k] >= value 
     does not satisfy list[k] == value, then list[k] > value
     and there can be no index j satisfying 
     list[j] == value. Hence we can return null.
 
  3. The list is by assumption sorted and all indices k such that 
     list[k] <= value are on the left (if existant).
     So binaryFindLast is applicable.
 
  4. If there exists any index k with list[k] == value,
     then all indices j within left..right satisfy list[j] == value.
 */

Note:

I guess technically for this problem we don’t need to pass both list and index to the lambdas. But this way the binaryFindFirst and binaryFindLast methods are also applicable in situations, where the property does not only depend on the list’s value at the current index.

For instance, there is a problem from the above video around minute 14:

Assume we are given a formerly sorted array from small to big, that was changed by applying a circular shift, e.g. [6,7,9,15,19,2,3] is the sorted array [2,3,6,7,9,15,19] after a two-fold circular left shift.

Find the smallest element in such a rotated sorted array.

In this case we can just use our binaryFindFirst method to find the first element smaller or equal to the leftmost entry.

fun <T: Comparable<T>> List<T>.findMinInRotatedList(): Int =
    binaryFindFirst { list, index -> list[index] <= list[0] }!!

Here the property does not only depend on the value at current index,
but also on the value at 0.

[Edited for better names and readability.]

Hi, great book, massive help so far.

There seems to be a double print of the code associated with Creating a Vertex, in Chapter 19 - Graphs. The code for createVertex() is printed twice in the code section, but each with a different set of steps.

test2

The same thing happens in the same chapter, couple of pages further along, in the Visualize an adjacency matrix section, the toString() method is printed twice in the code section

Since I’m a new user here I cannot attach more than 1 media element but you can see this in the section mentioned above

Thanks a lot for all your efforts, this book helped a lot in everything

yes. thanks for information

I already bought the 1st edition, how different is the 2nd edition??
Is there an “errata” page that can save me another $60 ???

It’s very helpful and informative. Thanks for your efforts. Chrissy White Hoodie

This book helped a lot in everything. Thank you for sharing this book with us. Stranger Things S04 Hoodie

Thanks for sharing this informative. Your efforts are greatly appreciated.
Building and Pest inspection in Melbourne

@jellodiil There seems to be a mistake in Chapter 5 Queues, in DoubleLinkedList.kt’s remove() method:

The code is:

fun remove(node: Node<T>): T {

    val prev = node.previous
    val next = node.next

    if (prev != null) {
      prev.next = node.previous
    } else {
      head = next
    }

    next?.previous = prev

    if (next == null) {
      tail = prev
    }

    node.previous = null
    node.next = null

    return node.value
  }

However, I believe it’s meant to be the following code below. The change is inside the first if statement:

fun remove(node: Node<T>): T {

    val prev = node.previous
    val next = node.next

    if (prev != null) {
      prev.next = node.next
    } else {
      head = next
    }

    next?.previous = prev

    if (next == null) {
      tail = prev
    }

    node.previous = null
    node.next = null

    return node.value
  }

If a node is removed, then the previous node’s next value should point to the removed node’s next value: prev.next = node.next Does this seem accurate? Trying to use the current implementation produces errors if you remove elements from a Linked List and try to print out the new list.