2018-12-12

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.

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)
}

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

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.

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.

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.

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

class Dog(val name :String)

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

Secondary

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.

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.

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

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

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

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

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

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

package capitalizeSentence

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

Test

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

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

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

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
}

Test

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

2018-11-04

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.

class Solution {
public:
    int longestValidParentheses(string s) {
    int max_len = 0;
    int curr_len = 0;
    // TODO
};

2018-11-04

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.

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;
  }
};

2018-11-01

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

git internals

2018-11-01

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

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

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 😵

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

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?

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;
  }
};

2018-10-30

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

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.

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:

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;
  }
};

2018-10-26

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

Khan Academy’s article on modulo arithmetic

2018-10-25

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

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);
}

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

2018-10-23

Null needs to be explicity defined

if vs when

arrays

Strings

Named Loops

Functions

Smart Casts

Properties

Constructors

Primary

Secondary

Data classes

Inheritance

Classes and Properties

Abstract classes

Functional Programming [TODO]

Coroutines

Basic example

Example: Reversing Lists

Example: A game of Hangman

Example: Get Max IP address count from file

Example: Capitalize Words in a Sentence

Implementation

Test

Example: Range Within Range

Implementation

Test

Example: Add number up to N

Implementations

Test

Resources

Requirements

Approach

Requirements

Approach

References

Constraints etc

Approaches

Mapping a 2D matrix to an array.

Requirements

Approach

DFS

Additional References

Solution

Other Good solutions

Reference

`if` vs `when`