Thread
#feed
    elizarov

    elizarov

    1 year ago
    Nit: Don’t use
    MutableList
    as a queue. You’ll get
    O(n)
    removes from the queue. Use
    ArrayDeque
    . Also, instead of
    remoteAt(0)
    you can write
    removeFirst()
    .
    n

    nkiesel

    1 year ago
    Some more nit: typos (e.g. "wind" instead of "Wind"), most hashMap/hashMap can be replaced with mutableMapOf/MutableMapOf, IMHO too much usage of arrays
    Michael de Kaste

    Michael de Kaste

    1 year ago
    Very cool sheet! For memoization I use a mutableMap a lot of times since the array example only works if the inputs are integers, connected and with a well defined range. e.g.
    fun main(){
        fibonacci(13U).let(::println)
    }
    
    private fun fibonacci(input: UInt) : BigInteger = memoizationMap.getOrPut(input){
        fibonacci(input - 1U) + fibonacci(input - 2U)
    }
    
    private val memoizationMap = mutableMapOf(0U to BigInteger.ZERO, 1U to BigInteger.ONE)
    Colton Idle

    Colton Idle

    1 year ago
    Trying to follow up on what @elizarov said. Does anyone know why a MutableList removes in O(n) vs what does ArrayDeque do? O(1)?
    bezrukov

    bezrukov

    1 year ago
    array deque just bumps the pointer, while MutableList (ArrayList under the hood) copies all the data starting from 1-index to 0
    Dmitry Kandalov

    Dmitry Kandalov

    1 year ago
    Cool cheatsheet! 👍 I’m not a designer but the fonts looks a bit funny to me (not sure why… maybe they’re different fonts in the headers, or some of the fonts are italic).
    It’s also interesting if the cheatsheet represents a particular code style encouraged by coding interviews, because the first two “common data types”
    MutableList
    and
    Array
    are the ones I normally try to avoid if possible.
    Colton Idle

    Colton Idle

    1 year ago
    @bezrukov so linked list vs array under the hood basically?
    bezrukov

    bezrukov

    1 year ago
    @Colton Idle high level idea may look similar, but no linked list is implemented as a linked nodes, so it has few cons comparing to array deque:1. It consumes more memory (prev/next references + Node's header) 2. it allocates objects more often than array deque (and produces garbage more often as well) 3. elements are placed in none consecutive memory segment ArrayDeque (JDK version) implements similar idea but over array, it's optimized for operations: add/peek/poll (to/from both ends). It doesn't implement List, so it don't need to implement other methods like add(index, value)/remove(index, value)/get(index) etc. There is important note: in kotlin 1.4 they implemented their own ArrayDeque that implements MutableList with mentioned functions (add/remove/get by index). That means you can use it as a replacement for ArrayList if you expect a lot of add/remove operations to the ends.