The following problem is the Reverse Integer problem on LeetCode.

Given a 32-bit signed integer, reverse its digits.

```
fun reverse(x: Int): Int {
// TODO
}
```

This problem is not too difficult (i.e. this is absolutely a fair interview question!). The approach we’re going to take is ** breaking down the number by multiples of 10, and using the broken off piece to construct the reversed number**.

There might be a temptation to convert the value to a string, reverse it, then convert it back again. Don’t do that, it’s completely against the spirit of the problem. I also trust math more than I trust type conversion, if code like this were to ever make it into production.

```
fun reverse(x: Int): Int {
var int = x
var sum = 0
while (int != 0) {
val digit = (int % 10)
val newSum = 10*sum.toLong() + digit.toLong()
check(newSum > Integer.MIN_VALUE && newSum < Integer.MAX_VALUE) {
"Integer overflowed, input too large"
}
sum = newSum.toInt()
int /= 10
}
return sum
}
```

You can see the progression of our `sum`

variable in the following example.

```
1234
10*0 + 4 = 4
10*4 + 3 = 43
10*43 + 2 = 432
10*432 + 1 = 4321
```

But how does idiomatic Kotlin code fit into this problem?

A pure function is a function that doesn’t mutate it’s input, and it has no side effects. Because of these two things, when a pure function is run multiple times with the same input, it gives the same result.

It’s not obvious in the above code, but Kotlin is making me go out of my way to write a pure function. Try the following:

```
fun foo(x: Int) {
x = 4 // an error pops up: "Val cannot be reassigned"
}
```

In a similar vein, collections are immutable by default.

```
fun foo(list: List<Int>) {
list.add(4) // nope! the compiler won't allow it!
}
```

The above isn’t allowed, because the `List`

interface extends the `Collection`

interface, *which doesn’t contain an add method*. If you want an add method, you have to declare

`MutableList`

, which extends `MutableCollection`

. And putting `MutableList`

as a type of a function input parameter should set off a red flag in your head.The `check`

function checks some condition. If it is `false`

, it throws an `IllegalStateException`

. We can use it to make sure people are only calling our function at the right time.

Similar to `check`

is the function `require`

. We pass it a condition, and if `false`

, it throws an `IllegalArgumentException`

. So it is used for validating input. e.g.

```
fun poundsToKilograms(weightInPounds: Double) {
require(weightInPounds >= 0) {
"There's no such thing as a negative weight."
}
return weightInPounds / 2.2
}
```

The slightly funny looking operator `/=`

means divide and then assign. That line is equivalent to the following.

`int = int / 10`

◾

]]>The following problem is the Longest Substring Without Repeating Characters problem on LeetCode.

Given a string, find the length of the longest substring without repeating characters.

```
# Example 1
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
# Example 2
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
# Example 3
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
```

There’s one nice example that comes up in the submissions that highlights an edge case as well, which is:

```
Input: "abba"
Output: 2
```

When we’re iterating through the array, and evaluating whether a new substring should be the max substring, we need to know two things:

- the length of the current max substring
- what characters are included in the current substring

Once we have those two things, it’s just a matter of iterating through the array once, and it’s not so complicated.

Getting the current max is simple, it’s just a matter of maintaining a max, initialized at 0, and update it as we go through the array.

This part is a little bit more complicated.

```
abcabcbb
^ ^
i j
```

Say we’re iterating through the above string. We’re at position *j*. The current substring we’re looking at is everything up until *i*.

If we can easily find *i*, then the length of the current substring is simply *j - i*. But how do we find *i*?

Speaking generally, *i* is the last occurrence of *any* char in our current substring.

We can break that into two cases:

*i*is the index of the last occurrence of the char we are currently sitting at, as we iterate through.*i*is the index of the last occurrence of any other char in the current substring

I’ve renamed `i`

to `lastRepeat`

, because what it actually represents is the last repeat of *any* char in the current substring.

Here is the final code:

```
fun maxSubstring(str: String): Int {
val map: HashMap<Char, Int> = hashMapOf()
var max = 0
var lastRepeat = -1
str.forEachIndexed { j, value ->
val lastOccurence = map.get(value)
if (lastOccurence != null) {
lastRepeat = maxOf(lastRepeat, lastOccurence)
}
max = maxOf(max, j - lastRepeat)
map.put(value, j)
}
return max
}
```

We’re iterating through the array once, so the time complexity is `O(n)`

.

The space usage is constant, because while we do have a hashmap, the maximum number of keys is limited by the total number of ASCII characters.

Here we’re the results of my submission on LeetCode.

I was a bit curious why it wasn’t a bit higher in terms of time, given that you really can’t make it any more efficient in terms of iteration.

Turns out, `forEachIndexed`

is less efficient than a simple for loop, e.g.

```
import kotlin.system.measureNanoTime
val x = (1..10000).toList().toTypedArray()
fun foo(): Unit {}
measureNanoTime { x.forEachIndexed { _, _ -> foo() } } // 674349
measureNanoTime { for (temp in 0 until x.size) { foo() } } // 192791
```

Note that we’re talking in nanoseconds here—I definitely think the readability gains from Kotlin’s functional APIs are worth a few extra nanoseconds.◾

]]>The following problem is the Add Two Numbers problem on LeetCode.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

For example:

```
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
```

We’ll use the following class as the basis for our linked list.

```
data class ListNode(val num: Int, val next: ListNode?)
// 342, would be 2 -> 4 -> 3
ListNode(2, ListNode(4, ListNode(3, null)))
```

In order to add the 2 linked lists, we’ll convert them to numbers, then add them, then convert the result back to a linked list.

As a first step, let’s create a function that takes in a ListNode, and returns the integer it represents.

The goal here is to iterate through the list, maintaining a sum of the final number. With each iteration, we add the value of the current node (multiplied by a factor of 10) to the running total. The factor of 10 is just 10 to the power of it’s place in the list.

Note that we’re iterating through a linked list, so we’ll do that with a `while`

loop until the `node.next = null`

.

```
import kotlin.math.pow
fun collapse(node: ListNode): Int {
var runningTotal = 0
var current: ListNode? = node
var i = 0
while (current != null) {
runningTotal += (10.0.pow(i).toInt() * current.num)
i++
current = current.next
}
return runningTotal
}
```

Let’s check if our function works as imagined. Recall that the numbers in the linked list are the starting at the least significant digits.

```
collapse(ListNode(4, null)) // 4
collapse(ListNode(4, ListNode(5, null))) // 54
collapse(ListNode(4, ListNode(5, ListNode(3, null)))) // 354
```

Conversely, let’s write a function that takes in an integer and returns a `ListNode`

. This’ll be useful because the final result is supposed to be a `ListNode`

. Also it helps us with testing.

As with the `collapse`

function, there are two main approaches we could take to go to and from the linked list to an integer.

The easiest data structure to handle this problem is an list of the digits. In order to get there, we could take the numeric route using powers of 10 like we did in the `collapse`

function, but it’s simpler to just use string parsing.

Once we have a list of the digits, then we just need to reduce the list to a single list node. For this, we’re going to use the Kotlin `fold`

function.

`fold`

is very similar to `reduce`

, but reduce takes the first value we’re iterating over as the initial value, whereas with `fold`

we can specify our own. In our case this is important, because we want the final value to be a `ListNode`

, not an `Int`

.

So, we’ll create a list node with the first digit and use it as our initial value, e.g. `ListNode(digits.get(0), null)`

.

```
fun expand(num: Int): ListNode {
val digits: List<Int> = num.toString().toCharArray().map { it.toString().toInt() }.toList()
return digits
.subList(1, digits.size)
.fold(ListNode(digits.get(0), null)) { acc, current -> ListNode(current, acc) }
}
```

```
expand(342) // ListNode(num=2, next=ListNode(num=4, next=ListNode(num=3, next=null)))
expand(76) // ListNode(num=6, next=ListNode(num=7, next=null))
```

Notice how clean the output is. This is because we specified the `ListNode`

class as a `data`

class. This overcomes one of the main daily annoyances of working with Java—classes that have useless `toString()`

functions. If we hadn’t specified the class as a `data`

class, the output would look like this: `ListNode@48bc2fce`

. Which is useless.

Lastly, just for a sanity check, let’s use our `collapse`

and `expand`

function in conjunction.

`collapse(expand(76)) // 76`

Awesome.

Gonna be honest, the first time I did this problem, the above was my solution. But 30 minutes after I published this, it was gnawing at me that I had to go collapse and expand the lists, going through them multiple times.

A few things made me think I was on the wrong path:

- They want you to return a linked list. Why would I go to a number, then re-expand to a linked list?
- There’s really no reason you can’t traverse both at the same time, although you do have to maintain state because the sum of two digits can be greater than 9, meaning we’d carry over to the next digit.

Here’s my final solution; it’s simpler, but a little tougher to follow. Let’s create a recursive helper function, that takes in 2 nodes, and adds them together, and allows us to pass state through in a function parameter.

```
fun addTwoNodes(x: ListNode?, y: ListNode?, carry: Int): ListNode? {
if (x == null && y == null && carry == 0) {
return null
}
val sum = (x?.num ?: 0) + (y?.num ?: 0) + carry
return ListNode(sum % 10, addTwoNodes(x?.next, y?.next, sum / 10))
}
```

This function is much cleaner—there's no while loop. The key things that might be confusing are Kotlin’s null safety and the elvis operator.

Anyway, once we have this helper function, we get a `O(log_10(x + y))`

solution.

```
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode {
return addTwoNodes(l1, l2, 0)!!
}
```

This was an interesting problem to solve. As you guys see, my first inclination is technically correct, but isn’t the most efficient or concise way of going about it. I had to let it marinate for a while before I actually got the succinct recursive solution.

That’s how these problems go a lot of the time.◾

]]>