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.
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 ???
@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.
Thanks for reporting this!
I’ve noted it for the team to have a look!
1 Like
Hey guys. Seems to me that you have an error in the code on page 196 when removing TrieNode. Adding parent = parent.parent at the bottom of the while loop(right below the current = parent statment) will do the trick.
Page 227.
Refactor suggestion:
replace this block of code
val leftChildIndex = index(element, leftChildIndex(i))
if (leftChildIndex != null) return leftChildIndex // 4
val rightChildIndex = index(element, rightChildIndex(i))
if (rightChildIndex != null) return rightChildIndex // 5
return null // 6
with this:
return index(element, leftChildIndex(i))?: index(element, rightChildIndex(i))
Page 230.
replace this:
val inverseComparator = Comparator { o1, o2 → // 2
override fun compare(o1: Int, o2: Int): Int =
o2.compareTo(o1)
}
with this:
val inverseComparator = Comparator { o1, o2 → // 2
o2.compareTo(o1)
}
I’m having a great time reading your article. I found this to be an interesting and instructional piece, thus I believe it to be really beneficial. Star Trek Picard Season 3 Leather Jacket
I was also looking for such a content for myself so I found a way to find it comfortably from this site. Thats why I like this site and this Bape Pink Hoodie site and clothes because there are many good clothes available here.
I am here to enjoy and learning new thing from Kodeco and this thread has a outstanding knowledge. I also want to share somthing stylish try James Bond No Time To Die Duster Coat.
I was facing a a lot of problem to understanding a Data Structure and Algoritn kotlin but this thread is so outstanding because my all doubts has been cleared. In the thanks i want to recommend you a best outfits for winte season try this Reality Check Kevin Hart Hoodie.
I found a simple method to locate this kind of stuff on this website while looking for it for myself. Because there are so many fantastic possibilities, I really like this website, especially the area on Bradley Cooper The Hangover Black Suit and clothing.