Categories
How To Studio

Kotlin for Interviews — Part 1: Common Data Types | by Sherry Yuan

Sherry Yuan
Photo courtesy Christina Lampf on Release the splash

I spent most of May and June preparing for the interview. Preparing for an interview means doing a lot of Letcode. Having applied for an Android position, I decided to tackle most of Kotlin’s issues. I noticed that the Kotlin I’m writing is very different from the Kotlin I use at work. After summarizing the code snippets that came up frequently during the interview preparation in a cheat sheet, I decided to take a closer look at the code snippets in a series of five medium posts.You can find cheat sheets Here..

Part 1 describes some common data types commonly found in algorithmic and data structure questions. How to initialize them, how to do some common operations on them, and some use cases. confirm:

You can find part 2 Here, Part 3 Here,Four – Here And Part 5— Here..

This is the data structure I’ve come to use most often, and you probably already know it. It should be pointed out that if you encounter a problem you need, you can easily use it as a stack or queue. I usually use MutableList to represent a queue in breadth-first search.

// Create an empty MutableList
val list1 = mutableListOf<Int>()
// Create a MutableList with elements [0, 1, 2, 3, 4]
val list2 = mutableListOf(0, 1, 2, 3, 4)

Use MutableList as a stack

  • add() You can add an element to the end of the list and use it like this: push
  • removeLast() You can remove the last element from the list and return it, and use it like this: pop
  • last() You can return the last element without removing it and use it like this: peek
val stack: MutableList<Int> = mutableListOf()
// push
stack.add(1)
stack.add(2)
// peek
stack.last()
// returns 2
// pop

stack.removeLast() // returns 2
stack.removeLast() // returns 1

Use MutableList as a queue

  • add() Can be used as enqueue
  • removeAt(0) You can remove the first element from the list and return it, and use it like this: dequeue
  • get(0) Returns the first element and can be used as follows peek
val queue: MutableList<Int> = mutableListOf()
// enqueue
queue.add(1)
queue.add(2)

// peek

queue[0]
// returns 1
// dequeue

queue.removeAt(0) // returns 1
queue.removeAt(0) // returns 2

Arrays look basic, but when I started preparing for an interview, I realized I wasn’t familiar with arrays because I tend to use lists instead. If the Leetcode problem had array inputs, or expected array outputs, I had to google.

Arrays are fixed size and supported in Kotlin get(), set(),and size, And most Kotlin collection function..You can use []The alias index operator makes getting and setting more concise. You cannot resize or delete elements. Arrays are useful for problems where you need to keep track of a fixed number of counters or flags.

There are two ways to initialize the array.You can use arrayOf<T>():

// Create an array with elements [0, 1, 2, 3, 4]
val array1 = arrayOf<Int>(0, 1, 2, 3, 4)

Or use Array<T>(n) { initFunction }..This will create an array of sizes n, Each element is created using initFunction..The· initFunction It can be the default value, such as -1 in the array of. Ints, Or a code block.

// Create an array with elements [0, 0, 0, 0, 0]
val array2 = Array<Int>(5) { 0 }
// Create an array with elements [0, 2, 4, 6, 8]
// The initFunction block can access the index as a parameter.
// Here, each element is initialized by taking its index and multiplying it by 2.

val array3 = Array<Int>(5) { index -> 2 * index }

There is also a dedicated arrayOf The following primitive type methods: double, float, long, int, char, short, byte, booleanImproves performance by avoiding Kotlin Boxing overhead:

// Create an array with elements [0, 1, 2, 3, 4]
val intArray1 = intArrayOf(0, 1, 2, 3, 4)
// Create an array with elements [0, 0, 0, 0, 0]
val intArray2 = IntArray(5) { 0 }
// Create an array with elements [true, true, false, true, true]
val booleanArray1 = booleanArrayOf(true, true, false, true, true)
// Create an array with elements [true, false, true, false, true]
// Each element is initialized by by whether or not its index is even
val booleanArray2 = BooleanArray(5) { index -> index % 2 == 0 }

Running total of 1d array Here is an example of a simple Letcode problem where you can use. IntArray To track the results:

/**
*
Problem description: Given an array nums. We define a running sum
* of an array as
runningSum[i] = sum(nums[0]…nums[i]). Return the
* running sum of
nums.
*
*
Example:
* Input: nums = [1,2,3,4]
* Output: [1,3,6,10]
* Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3,
* 1+2+3+4].
** /

fun runningSum(nums: IntArray): IntArray {
val results = IntArray(nums.size) { 0 }
results[0] = nums[0]
for (i in 1 until nums.size) {
results[i] = results[i - 1] + nums[i]
}
return results
}

HashMaps represent a collection of key / value pairs. The keys are unique and the map can have only one value per key. Often useful for interview issues to save information. For example HashMap<Node, Boolean> You can save which node in the graph is already accessed, HashMap<String, Int> You can save the number of different words that appear in a sentence.

Some useful features:

  • clear() Remove all elements from the map.
  • containsKey(key: K) Returns true if the map contains the specified key.
  • remove(key: K) Removes the specified key and its corresponding value from this map.
  • getOrPut(key: K, defaultValue: () -> V) If the specified key is in the map, it returns its value. If not, defaultValue Puts the function, its result in the map under the specified key and returns it.
// Create an empty HashMap
val map1 = hashMapOf<String, Int>()
// Create a HashMap with initial values
val map2 = hashMapOf(
"Never Let Me Go" to 2005,
"A Little Life" to 2015
)
// Two ways to insert a key-value pair
map2.put("The Name of the Wind", 2007)
map2["The Bell Jar"] = 1963
// Two ways to retrieve a value
map2.get("The Name of the Wind") // returns 2007
map2["The Bell Jar"]
// returns 1963
// Using getOrPut()
map2.getOrPut("The Name of the wind", 1990) // Returns 2007
map2.getOrPut("1984", 1949) // Inserts new entry and returns 1949

PriorityQueues are useful for processing elements based on priority. This class is implemented using the heap. These are often used in interview questions that ask for K-th largest, K-th smallest, top K frequency, and more.

Can be initialized using PriorityQueue<T>(), Where to use the type TNatural order for prioritization or using custom Comparator favorite PriorityQueue<T> { (a: T, b: T) -> Int }, Specifies a custom way to determine the priority.

Some useful features:

  • add(element: E) And offer(element: E) Both can insert elements and use either. PriorityQueue Since we have implemented two interfaces, we have two functions that do exactly the same thing. Collection And Queue..Use of collections add() For inserts, use the queue offer()..
  • peek() Returns the beginning of the queue, but does not delete it.
  • poll() Returns the beginning of the queue and deletes it.
// Create a PriorityQueue pq where the maximum value Int has highest 
// priority

val pq = PriorityQueue<Int> {
a, b -> b - a
}
// Add 2, 1, 3 to the pq
pq.offer(2)
pq.add(1)
pq.offer(3)
pq.peek() // returns 3 but does not remove it from pq

// pq will be empty after 3 iterations
while(pq.isNotEmpty()) {
pq.poll()
// returns 3, then 2, then 1
}

The· Comparator<T> The interface provides a comparison function to impose total order between instances of a type. T.. Most Kotlin sorting algorithms require sorting or prioritization, which often helps with technical interview issues. Comparator..

You can use Kotlin compareBy() Function to create Comparator Calculate the comparison result using the set of functions you passed. The sequence of functions is evaluated consecutively in pairs of values, and as soon as the results of the two values ​​returned by the function are no longer compared equally, the results are returned and the rest of the functions are skipped for that pair.

val customComparator = compareBy<T> { 
...
}

Here is an example Comparator It compares Ints Depends on absolute value:

val absComparator = compareBy<Int>{ Math.abs(it) }
val nums: MutableList<Int> = mutableListOf(-1, 3, 7, -5, 3)
nums.sortWith(absComparator)
// Or if you only need to use the comparator once, you can pass in
// the call to compareBy() directly.

val nums: MutableList<Int> = mutableListOf(-1, 3, 7, -5, 3)
nums.sortWith(compareBy{ Math.abs(it) })

Here is an example Comparator Compare custom Card With the class by its color property BLACK The card is “bigger” RED card. Use the number property to break the relationship.

enum class Color { RED, BLACK }data class Card(val number: Int, val color: Color)val cardComparator = compareBy(
// Compare by color first
{ if(it.color == BLACK) 1 else 0 },
// If the results of color comparison are equal, compare by
// number

{ it.number }
)
val cards: MutableList<Card> = mutableListOf(
Card(4, Color.RED),
Card(2, Color.BLACK),
Card(1, Color.RED),
Card(3, Color.BLACK)
)
cards.sortWith(cardComparator)

// cards becomes:
// [Card(1, RED), Card(4, RED), Card(2, BLACK), Card(3, BLACK)]

If the comparison is complex, it’s a good idea to create an object that you implement explicitly. Comparator Interfaces and overrides compare() function. Returns zero if the arguments are equal, returns a negative number if the first argument is less than the second argument, and returns a positive number if the first argument is greater than the second argument.

object CustomComparator: Comparator<T>{ 
override fun compare(a: T, b: T): Int {
...
return ...
}
}

What is this Comparator The card comparison object looks like this:

object cardComparator: Comparator<Card>{ 
override fun compare(a: Card, b: Card): Int {
if (a.color == b.color) {
return a.number - b.number
} else if (a.color == Color.BLACK) {
// Case where a is BLACK and b is RED
return 1
} else {
// Case where a is RED and b is BLACK
return -1
}
}
}

For custom classes, you can also extend to the class Comparable Interfaces and overrides compareTo() To impose total order rather than creating individual objects. You can use Kotlin compareValuesBy() Helper functions compareBy()Computes the comparison result using the set of functions passed.Therefore, there is no need to use sortWith() Passing in a custom comparator, you can use it like this: sort() The function knows how to do full ordering.

enum class Color { RED, BLACK }data class Card(val number: Int, val color: Color)
: Comparable<Card> {
override operator fun compareTo(other: Card): Int {
compareValuesBy(
this,
other,
// Compare by color first
{ it.color },
// If the results of color comparison are equal,
// compare by number
{ it.number }
)
}
}
val cards: MutableList<Card> = mutableListOf(
Card(4, Color.RED),
Card(2, Color.BLACK),
Card(1, Color.RED),
Card(3, Color.BLACK)
)
cards.sort()

// cards becomes:
// [Card(1, RED), Card(4, RED), Card(2, BLACK), Card(3, BLACK)]

Again, I have the option to implement compareTo() Without compareValuesBy() Helper if easy to understand:

data class Card(val number: Int, val color: Color)
: Comparable<Card> {
override operator fun compareTo(other: Card): Int {
if (this.color == other.color) {
return this.number - other.number
} else if (this.color == Color.BLACK) {
return 1
} else {
return -1
}
}
}

That’s it for Part 1.To part 2Describes the useful Kotlin collection functions.This is Link to cheat sheet Cover all five parts again.

Source

Leave a Reply

Your email address will not be published. Required fields are marked *