Stuff Kotlin does

Have you heard of Kotlin?

It’s an interesting language that tries to prevent programmers from shooting themselves in the foot while trying to maintain the efficiency of the JVM. Here are some interesting and sometimes (pleasantly) surprising things Kotlin does.

Null needs to be explicity defined

if vs when

Both are expressions that can return values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fun main() {
print("Enter the temperature:")

val input = readLine()
if (input == null) return

val comment = if (input.toInt() > 37) {
println("seems hot...")
"Make an omlette on the pavement"
}
else if (input.toInt() < 0) {
"Brrr...that's cold"
}
else {
"Nice day for a walk"
}
println(comment)
}
1
2
3
4
5
6
7
8
9
10
11
fun main() {
print("Enter the temperature:")
val input = readLine()
val comment = when(input?.toInt()) {
in -40..5 -> "Brrr...that's cold"
in 6..24 -> "Mmmm...that's crisp"
in 25..37 -> "Getting hot in here"
else -> "Make an omlette on the pavement"
}
println(comment)
}

arrays

You can create arrays of mixed types

1
2
3
4
5
6
fun main() {
var collection = arrayOf("Apple", 23.6, 'D', 77)
for (e in collection) {
println(e)
}
}

If we convert to bytecodes and look at the Java equivalent we see it’s just an array of Objects.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import kotlin.Metadata;

@Metadata(
mv = {1, 1, 13},
bv = {1, 0, 3},
k = 2,
d1 = {"\u0000\b\n\u0000\n\u0002\u0010\u0002\n\u0000\u001a\u0006\u0010\u0000\u001a\u00020\u0001¨\u0006\u0002"},
d2 = {"main", "", "Test"}
)
public final class AppKt {
public static final void main() {
Object[] collection = new Object[]{"Apple", 23.6D, 'D', 77};
Object[] var3 = collection;
int var4 = collection.length;

for(int var2 = 0; var2 < var4; ++var2) {
Object e = var3[var2];
System.out.println(e);
}

}

// $FF: synthetic method
public static void main(String[] var0) {
main();
}
}

Strings

Strings characters can be accessed with index.

Named Loops

You can break out of specifically labeled loops.

1
2
3
4
5
6
7
8
fun main() {
outer@ for (i in "This is the outer loop") {
for (j in "This is the inner loop") {
if (j in "aeiou") break@outer
println("$i .. $j")
}
}
}

Functions

It’s cool that functions can be defined as expressions

1
fun product(a: Int, b: Int) = a * b

Smart Casts

Safe casts are inserted when needed.

1
2
3
4
5
6
7
val a :Any
a = "45"

if (a !is String) return
println("Len = ${a.length}")
println("this prints too")
println("and so does this")

The lines after the condition are only executed for Strings.

Properties

Classes can have properties which can be marked as read-only(val) or read-write(var). Variables be initialized to be used. If it cannot be initialized then qualify it with lateinit.

Constructors

There are primary and secondary constructors.

Primary

1
2
3
4
5
6
class Dog(val name :String)

fun main() {
var d = Dog("Spike")
println("My name is ${d.name}")
}

Secondary

1
2
3
4
5
6
7
8
9
10
11
class Dog {
val name: String
constructor(name: String) {
this.name = name
}
}

fun main() {
var d = Dog("Spike")
println("My name is ${d.name}")
}

Data classes

Inheritance

Modifiers are explicit at the function level. By default functions are marked as closed and need to be qualified with open to be able to override it.

1
2
3
4
5
6
7
open class Bird{
open fun squawk() {}
fun peck() {}
}
class Derived() : Bird() {
override fun squawk() {}
}

Classes and Properties

Getters and Setters are declared as follows:

1
2
3
var <propertyName>[: <PropertyType>] [= <property_initializer>]
[<getter>]
[<setter>]

Abstract classes

Abstract classes allow us to define specific traits similar to interfaces.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
abstract class Plane(val name: String) {
abstract fun fly()
}

fun main() {
val p = F120("Zippy")
println(p)
}

class F120(myname: String): Plane(myname) {
override fun fly() {
println("zooooom")
}
override fun toString(): String {
return "name --> $name"
}
}

Functional Programming [TODO]

One of the paradigms that can be used.

1
2


Coroutines

Basic example

1
2
3
4
5
6
7
8
9
10
import kotlinx.coroutines.*

fun main() {
GlobalScope.launch { // launch new coroutine in background and continue
delay(3333L) // non-blocking delay for 1 second (default time unit is ms)
println("${Thread.currentThread()} World!") // print after delay
}
println("${Thread.currentThread()} Hello,") // main thread continues while coroutine is delayed
Thread.sleep(5000L) // block main thread for 2 seconds to keep JVM alive
}

The definitive guide to Kotlin Coroutines

Example: Reversing Lists

1
2
3
4
5
6
7
8
9
10
11
fun main() {
println(reverse(listOf(1,2,3,4,5,6)))
}

fun reverse(list: List<Int>): List<Int> {
val result = arrayListOf<Int>()
for (i in 0..list.size - 1) {
result.add(list[list.size - 1 - i])
}
return result
}

A little more intuitive solution

1
2
3
4
5
6
7
8
9
10
11
fun main() {
println(reverse(listOf(1,2,3,4,5,6)))
}

fun reverse(list: List<Int>): List<Int> {
val result = arrayListOf<Int>()
for (i in list.size - 1 downTo 0) {
result.add(list[i])
}
return result
}

Example: A game of Hangman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package codealong

data class Result(val failed: Boolean, val numTries: Int)

fun main(args: Array<String>) {
print("What word do you want to guess? ")
val word = readLine()
if (word == null) {
println("No word provided...exiting")
return
}

for (i in 1..100) println()

val letters = word.toLowerCase().toCharArray().toHashSet()
val correctGuesses = mutableSetOf<Char>()
var totalTries = 0

while (letters != correctGuesses) {
print("Enter letter: ")
val c = readLine()
if (c == null) {
println("Bad input")
return
}
val (failed , numTries) = guessWord(c.first(), correctGuesses, totalTries, word)
totalTries = numTries
if (!failed) break
}
println("Number of wrong guesses = $totalTries");
}

fun guessWord(char: Char, correctGuesses: MutableSet<Char>, fails: Int, word: String): Result {
var failed = false
var count = fails
//if (correctGuesses.contains(char)) return Result(false, fails)
for(c in word) {
if (c == char) {
print("$c ")
correctGuesses.add(c)
} else if (correctGuesses.contains(c)) {
print("$c ")
} else {
print("_ ")
failed = true
}
}
if (failed) count++
return Result(failed, count)
}

Example: Get Max IP address count from file

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package collections

import java.io.File

fun main(args: Array<String>) {
var file = File("input.txt")
val addrCount = mutableMapOf<String, Int>()
var maxPair: Pair<String, Int> = Pair("", 0)
file.forEachLine {
addrCount.put(it, addrCount.getOrDefault(it, 0) + 1)
maxPair = if (maxPair.second < addrCount.get(it)!!) Pair(it, addrCount[it]!!) else maxPair
}
println(maxPair)
}

Example: Capitalize Words in a Sentence

Implementation

1
2
3
4
5
6
package capitalizeSentence

fun capitalizeLetter(sentence: String) : String {
val s = sentence.split(" ").joinToString(separator = " ") { it.capitalize()}
return s
}

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package capitalizeSentence

import org.junit.jupiter.api.Assertions.*
import org.junit.jupiter.api.Test

internal class MainKtTest {

@Test
fun capitalizeLetterBasic() {
assertEquals(capitalizeSentence.capitalizeLetter("hello world"), "Hello World")
}

@org.junit.jupiter.api.Test
fun checkWithMoreSpaces() {
assertEquals(capitalizeSentence.capitalizeLetter("hello world"), "Hello World")
}

@org.junit.jupiter.api.Test
fun checkWithComma() {
assertEquals(capitalizeSentence.capitalizeLetter("hello , world"), "Hello , World")
}

}

Example: Range Within Range

Given two ranges implement a function which checks if range1 contains range2.

Implementation

1
2
3
4
5
6
7
8
package Ranges

/**
* Checks if range1 contains range2
*/
fun checkSubrange(range1: IntRange, range2: IntRange): Boolean {
return ((range2.first in range1) and (range2.last in range1))
}

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package Ranges

import org.junit.jupiter.api.Test

import org.junit.jupiter.api.Assertions.*

internal class CheckSubrangeKtTest {

@Test
fun `range 5-7 contains 5-7`() {
assertTrue(checkSubrange(5..7, 5..7))
}

@Test
fun `range 6-7 does not contain 5-7`() {
assertFalse(checkSubrange(6..7, 5..7))
}

@Test
fun `range 5-8 does not contain 3-5`() {
assertFalse(checkSubrange(5..8, 3..5))
}
}

Example: Add number up to N

Given positive integer n implement a function which calculates sum of all numbers from 1 up to (and including) number n.

Implementations

1
2
3
4
5
6
7
8
9
10
import java.lang.IllegalArgumentException

fun addUpTo(p: Int): Int {
if (p < 0) throw IllegalArgumentException("Cannot solve for negatives!")
var amount = 0
for (e in 0..p) {
amount += e
}
return amount
}

More idiomatic solutions

1
2
3
4
5
6
7
8
9
fun addUpTo2(p: Int): Int {
if (p < 0) throw IllegalArgumentException("Cannot solve for negatives!")
return (1..p).sum()
}

fun addUpTo3(p: Int): Int {
if (p < 0) throw IllegalArgumentException("Cannot solve for negatives!")
return (0..p).fold(0) {accumulated, current -> accumulated + current}
}

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
internal class MainKtTest {

@Test
fun `fail with negative`() {
assertFailsWith<IllegalArgumentException> { addUpTo(-4) }
}

@Test
fun `add upto 3`() {
assertEquals(addUpTo(3), 6)
}
}

internal class MainKtTest2 {

@Test
fun `fail with negative`() {
assertFailsWith<IllegalArgumentException> { addUpTo2(-4) }
}

@Test
fun `add upto 3`() {
assertEquals(addUpTo2(3), 6)
}

@Test
fun `check 0`() {
assertEquals(addUpTo2(0), 0)
}
}

internal class MainKtTest3 {

@Test
fun `fail with negative`() {
assertFailsWith<IllegalArgumentException> { addUpTo3(-4) }
}

@Test
fun `add upto 3`() {
assertEquals(addUpTo3(3), 6)
}

@Test
fun `check 0`() {
assertEquals(addUpTo3(0), 0)
}
}

Resources

Longest Valid Parentheses

Problem

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”

Example 2:

Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”

Requirements

  • string containing just the characters ‘(‘ and ‘)’
  • find the length of the longest valid (well-formed) parentheses substring
  • string can be empty? yes

Approach

We can use a stack to keep track of opening parentheses. When we see an opening parenthesis, we push index of opening parenthesis to stack. When we see closing, we pop off stack and add 2 to a running counter. After stack is empty we update the global max of counts.

1
2
3
4
5
6
7
class Solution {
public:
int longestValidParentheses(string s) {
int max_len = 0;
int curr_len = 0;
// TODO
};

Top k Frequent Words

Problem

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

Input: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
Output: [“i”, “love”]
Explanation: “i” and “love” are the two most frequent words.
Note that “i” comes before “love” due to a lower alphabetical order.

Example 2:

Input: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
Output: [“the”, “is”, “sunny”, “day”]
Explanation: “the”, “is”, “sunny” and “day” are the four most frequent words,
with the number of occurrence being 4, 3, 2 and 1 respectively.

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Input words contain only lowercase letters.

Follow up:

Try to solve it in O(n log k) time and O(n) extra space.

Requirements

  • return the k most frequent elements
  • answer should be sorted by frequency from highest to lowest
  • If two words have the same frequency, then the word with the lower alphabetical order comes first
  • words contain only lowercase letters
  • solve it in O(n log k) time and O(n) extra space

Approach

We can use a map for gathering the counts of all the words. This can be done in O(n) time and will use O(n) space. Once we have this, we can use a priority queue with a custom comparator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {

public:
vector<string> topKFrequent(vector<string>& words, int k) {
using word_map_t = unordered_map<string, int>;
using pair_t = pair<string, int>;
using vec_t = vector<pair_t>;

word_map_t word_map;
for (auto w : words) {
++word_map[w];
}

auto cmp = [&](pair_t& a, pair_t& b) {
return (a.second < b.second || (a.second == b.second && a.first > b.first));
};

priority_queue<pair_t, vec_t, decltype(cmp)> pq(cmp);

for (auto w : word_map) {
pq.emplace(w.first, w.second);
}
vector<string> res;
while (k > 0 && !pq.empty()) {
//res.insert(res.begin(), pq.top().first);
res.push_back(pq.top().first);
pq.pop();
k--;
}

return res;
}
};

Git over here!

Git is a fantastic piece of technology. It’s been a game-changer for me, both professionally as well as personally. I started using it for the first time six years ago. At first I was quite repulsed by it. Over time though, I’ve grown quite fond of it.

In this post, I will be diving deeper into the internals of git to see what makes it such a solid piece of software.

Stay tuned.

References

Random Flip Matrix

Problem

You are given the number of rows n_rows and number of columns n_cols of a 2D binary matrix where all values are initially 0. Write a function flip which chooses a 0 value uniformly at random, changes it to 1, and then returns the position [row.id, col.id] of that value. Also, write a function reset which sets all values back to 0. Try to minimize the number of calls to system’s Math.random() and optimize the time and space complexity.

Note:

1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows and 0 <= col.id < n_cols
flip will not be called when the matrix has no 0 values left.
the total number of calls to flip and reset will not exceed 1000.

Example 1:

Input:
[“Solution”,”flip”,”flip”,”flip”,”flip”]
[[2,3],[],[],[],[]]
Output: [null,[0,1],[1,2],[1,0],[1,1]]

Example 2:

Input:
[“Solution”,”flip”,”flip”,”reset”,”flip”]
[[1,2],[],[],[],[]]
Output: [null,[0,0],[0,1],null,[0,0]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution’s constructor has two arguments, n_rows and n_cols. flip and reset have no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Constraints etc

  • minimize calls to random function
  • optimize the time and space complexity
    -

Approaches

We can use a reservoir sampling approach.

Mapping a 2D matrix to an array.

Given an index from an array we can compute the row and column of the original matrix as long as we know the number of rows and columns.

[TODO] add example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
private:

int n_samples,n_rows,n_cols;
unordered_map<int,int> indices;

vector<int> mapToMatrix(int i) {
vector<int> v;
// row
v[0] = i / n_cols;
// column
v[1] = i % n_cols;

return v;
}

public:
Solution(int n_rows, int n_cols) {
this.n_rows = n_rows;
this.n_cols = n_cols;
n_samples = n_rows * n_cols;
srand(time(0));
}

/*
pick a number between 0 and n_samples - 1
*/
vector<int> flip() {
int selected;
int last = n_samples;
// pick random number from 0 to n_samples - 1
int r = rand() % n_samples;

if (indices.find(r) != indices.end()) {
// if index already selected before then pick
// the next available one from map
selected = indices[r];
} else {
selected = r;
}
// store it for when we hit the same index again
indices[r] = n_samples;
//reduce sample size for next run
n_samples--;

return mapToMatrix(selected);

}

void reset() {
srand(time(0));
indices.clear();
n_samples = n_rows * n_rows;
}
};

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(n_rows, n_cols);
* vector<int> param_1 = obj.flip();
* obj.reset();
*/

Argg 😞

I cannot do

1
2
3
4
5
vector<int> v;
// row
v[0] = i / n_cols;
// column
v[1] = i % n_cols;

We should do push_back().

There is also a division by zero problem here.

1
2
// pick random number from 0 to n_samples - 1
int r = rand() % n_samples;

Updated but not yet accepted 😵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
private:

int n_samples, n_rows, n_cols;
unordered_map<int, int> indices;

vector<int> mapToMatrix(int i) {
vector<int> v;
// row
v.push_back(i / n_cols);
// column
v.push_back(i % n_cols);

return v;
}

public:
Solution(int n_rows, int n_cols) {
this->n_rows = n_rows;
this->n_cols = n_cols;
n_samples = n_rows * n_cols;
srand(time(0));
}

/*
pick a number between 0 and n_samples - 1
*/
vector<int> flip() {
int selected;
int last = n_samples;
int r = 0;
if (n_samples) r = rand() % n_samples;

if (indices.find(r) != indices.end()) {
// if index already selected before then pick
// the next available one from map
selected = indices[r];
}
else {
selected = r;
}

//reduce sample size for next run
n_samples--;

// store it for when we hit the same index again,
// we want to store it after decrement so we pick the right one
indices[r] = n_samples;


return mapToMatrix(selected);

}

void reset() {
srand(time(0));
indices.clear();
n_samples = n_rows * n_rows;
}
};

The issue seems to be this logic

1
2
3
// store it for when we hit the same index again,
// we want to store it after decrement so we pick the right one
indices[r] = n_samples;

We need to lookup indices[n_samples]. If that does not exist then we store n_samples into indices[r].

Updated and cleaned up but still fails

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
private:

int n_samples, n_rows, n_cols;
unordered_map<int, int> indices;

public:
Solution(int n_rows, int n_cols):n_rows(n_rows), n_cols(n_cols),
n_samples(n_rows*n_cols) {
srand(time(0));
}

vector<int> flip() {
int r = 0;
if (n_samples) r = rand() % n_samples;

// if index already selected before then pick
// the next available one from map
int selected = indices.count(r) ? indices[r] : r;

//reduce sample size for next run
n_samples--;

// store it for when we hit the same index again,
// we want to store it after decrement so we pick the right one
// if the last element
indices[r] = indices.count(n_samples) ? indices[n_samples] : n_samples;

return { selected / n_cols, selected % n_cols };
}

void reset() {
indices.clear();
n_samples = n_rows * n_rows;
}
};

Looks like a typo 😵. Can you see it?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private:

int n_samples, n_rows, n_cols;
unordered_map<int, int> indices;

public:
Solution(int n_rows, int n_cols):n_rows(n_rows), n_cols(n_cols),
n_samples(n_rows*n_cols) {
srand(time(0));
}

vector<int> flip() {
int r = 0;
if (n_samples) r = rand() % n_samples;

// if index already selected before then pick
// the next available one from map
int selected = indices.count(r) ? indices[r] : r;

//reduce sample size for next run
n_samples--;

// store it for when we hit the same index again,
// we want to store it after decrement so we pick the right one
// if the tail element is the map then we pick from map
// otherwise we can just store the index
indices[r] = indices.count(n_samples) ? indices[n_samples] : n_samples;

return { selected / n_cols, selected % n_cols };
}

void reset() {
indices.clear();
n_samples = n_rows * n_cols;
}
};

Permutations

Problem

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Requirements

  • duplicates not allowed since distinct

Approach

DFS

  • Use an array of size of input to track when an element is picked
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
template<std::size_t N>
void build(const vector<int>& nums, vector<vector<int>>& res, vector<int>& elem,
bitset<N>& picked) {
if (elem.size() == nums.size()) {
res.emplace_back(elem);
return;
}

for (int i = 0; i < nums.size(); i++) {
if (picked[i]) continue;
picked[i] = 1;
elem.push_back(nums[i]);
build(nums, res, running, picked);
picked[i] = 0;
elem.pop_back();
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
bitset<nums.size()> picked;
vector<int> running;
build(nums, res, running, picked);
return res;
}
};

This solution has issues since bitset size needs to be fixed at compile time.

Here is an alternate approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
template<std::size_t N>
void build(const vector<int>& nums, vector<vector<int>>& res, vector<int>& elem,
bool *picked) {
if (elem.size() == nums.size()) {
res.emplace_back(elem);
return;
}

for (int i = 0; i < nums.size(); i++) {
if (picked[i]) continue;
picked[i] = true;
elem.push_back(nums[i]);
build(nums, res, elem, picked);
picked[i] = false;
elem.pop_back();
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
bool picked[nums.size()] = {false};
vector<int> running;
build(nums, res, running, picked);
return res;
}
};

So looks like passing arrays needs to be revisited(?)

And the winner is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private:
void build(vector<int>& nums,
vector<vector<int>>& res,
vector<int>& elem,
vector<bool>& picked) {
if (elem.size() == nums.size()) {
res.emplace_back(elem);
return;
}

for (int i = 0; i < nums.size(); i++) {
if (picked[i]) continue;
picked[i] = true;
elem.push_back(nums[i]);
build(nums, res, elem, picked);
picked[i] = false;
elem.pop_back();
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<bool> picked(nums.size(), false);
vector<int> elem;
build(nums, res, elem, picked);
return res;
}
};

Modulo Arithmetic and friends

I discovered this interesting discussion on Fast Exponentiation.

Here I try to capture some main points for better intuition and understanding.

Khan Academy has an interesting exercise of visualizing modulus as a clock.

Question: What is -29 mod 4

Answer: 3

Divide -29 by 4 and pick the first positive value.

  • 26≡11 (mod 5) => 26 mod 5 is equal to 11 mod 5

Additional References

Next Permutation

Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution

It really helps to draw this one out on grid. I was able to figure out the swapping logging, but missed the reversing part in my analysis.

Found this pretty concise solution here

1
2
3
4
5
6
void nextPermutation(vector<int>& nums) {
auto i = is_sorted_until(nums.rbegin(), nums.rend());
if (i != nums.rend())
swap(*i, *upper_bound(nums.rbegin(), i, *i));
reverse(nums.rbegin(), i);
}

Other Good solutions

Bloom Filters

Let’s say you have a really cool website where your visitors always randomly see a new image. Kind of like the illustration of a person here. I suspect this uses some kind of a naive algorithm to change the image. But let’s say you had millions of images at you disposal because you are using an endless stream of images from instagram.

And you want to (almost) always pick an image uniquely. How could you do this?

Reference

video