https://kotlinlang.org logo
#feed
Title
e

elizarov

10/23/2020, 7:44 AM
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()
.
☝️ 11
👍 11
n

nkiesel

10/23/2020, 8:44 AM
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
m

Michael de Kaste

10/23/2020, 11:06 AM
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.
Copy code
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)
c

Colton Idle

10/23/2020, 12:22 PM
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)?
b

bezrukov

10/23/2020, 12:24 PM
array deque just bumps the pointer, while MutableList (ArrayList under the hood) copies all the data starting from 1-index to 0
☝️ 1
d

Dmitry Kandalov

10/23/2020, 4:02 PM
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.
c

Colton Idle

10/24/2020, 9:05 PM
@bezrukov so linked list vs array under the hood basically?
b

bezrukov

10/26/2020, 8:43 AM
@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.
👍 1
6 Views