Categories
Studio

Kotlin for Interviews — Part 5: Frequently Used Code Snippets | by Sherry Yuan

Sherry Yuan
Photo courtesy Fabrice Billard on Release the splash

This is Part 5 of Kotlin for Interviews. This series describes Kotlin’s functions and code snippets that came up frequently while preparing for an Android interview. We have also created a cheat sheet that covers all five parts of this series. Here..

Part 1: You can find common data types Here, Part 2: Collection function Here, Part 3: Numbers and Mathematics Here, And Part 4: Iteration Here..

The contents of this part are as follows:

Describes blocks of code that are frequently used for various issues. For example, many of the interview issues are summarized in depth-first search, and I used a variation of the basic depth-first search code snippet to solve them.

Many graph problems display a list of node pairs. Here, the second node depends on the first node (or vice versa, depending on the interviewer).For example, the following pair [0, 1] That is, to access node 1, you must first access 0. However, with most graph algorithms, Adjacency list representationSo, here’s an algorithm that takes a list of node pairs and converts them to an adjacency list:

Given this sample input:

[[1, 2], [1, 3], [1, 4], [2, 4], [2, 5], [3, 6], [4, 3], [4,6], [4, 7], [5, 4], [5, 7], [7, 6]]

This represents this graph:

Create the following adjacency list.

[[1: [2, 4, 3]] [2: [4, 5]] [3: [6]] [4: [6, 7, 3]] [5: [4, 7]] [7: [6]]]]

fun createAdjacencyList(pairs: Array<IntArray>) {
val graph: HashMap<Int, MutableList<Int>> = hashMapOf()
pairs.forEach { pair ->
if (!graph.containsKey(pair[0])) {

// If the current node isn't in the adjacency list yet,
// add it and create its dependency list starting with
// pair[1]

graph[pair[0]] = mutableListOf(pair[1])
} else {
// Otherwise, append pair[1] to its existing dependency
// list.
val dependencies = graph[pair[0]]
dependencies.add(pair[1])
graph[pair[0]] = dependencies
}
}
}

Note that this algorithm is for directed graphs.If the graph is said to be unsuitable — means a pair [0, 1] Means that there is an edge between 0 and 1 — just repeat the code forEach() loop pair[0] And pair[1] I exchanged it, so MutableListThe s in the graph represents all adjacent nodes, not just directed dependencies.

Many interview issues require traversing the graph, from finding nodes to checking cycles to finding the length of the path between two nodes. Breadth-first search is one way to do that. The algorithm starts at one node in the graph and, with the help of a queue, explores all adjacent nodes at the current depth before moving to the next depth level node.

This is the base version that traverses all the nodes reachable from the first node. You can change it depending on the graph problem you are trying to solve.

fun bfs(nodes: List<List<Int>>) {
val visited = BooleanArray(nodes.size) { false }
// Create a queue and add 0 to represent the index of the
// first node

val queue: MutableList<Int> = mutableListOf(0)
while (queue.isNotEmpty()) {
// Dequeue a node from queue
val node = queue.removeAt(0)
// Add all of the node's unvisited neighbors to the queue
if (!visited[node]) {
nodes[node].forEach {
queue.add(it)
}
// Mark the dequeued node as visited
visited[node] = true
}
}
}

Depth-first search can also be used for graph scanning problems. This algorithm uses the stack instead of the queue and is forced to explore the current node branch as much as possible and then backtrack to other nodes for expansion.

This is a recursive version that relies on the function call stack, not an explicit stack variable. You can also use stack variables to create iterative versions of the algorithm.

fun dfs(nodes: List<List<Int>>) {
val visited = BooleanArray(nodes.size) { false }
helper(nodes, 0, visited)
}fun helper(nodes: List<List<Int>>, node: Int, visited: BooleanArray){
visited[node] = true
nodes[node].forEach {
if (!visited[it]) {
helper(nodes, it, visited)
}
}
}

Tree problems are very common in interviews. Some examples include finding the lowest common ancestor of two nodes, summing the values ​​of all nodes in the tree, and so on.

Binary tree

Binary trees are the most common trees encountered in interviews. The binary tree node looks like this:

class Node(
var key: Int,
var left: Node? = null,
var right: Node? = null
)

Note that not all binary trees are binary search trees. Do not assume that you have been given a BST unless the interviewer confirms it. Binary trees are BST only if they also meet the following criteria:

  • The subtree to the left of a node contains only nodes that have a key smaller than the node’s key.
  • The subtree to the right of a node contains only nodes that have a key that is greater than the node’s key.
  • The left and right subtrees must also be binary search trees.

Let’s use this tree (not BST!) As an example.

You can build it using the following code.

val node4 = Node(4)
val node7 = Node(7)
val node6 = Node(6, node4, node7)
val node11 = Node(11)
val node9 = Node(9, node6, node11)
val node2 = Node(2)
val node5 = Node(5)
val node12 = Node(12, node2, node5)
val node3 = Node(3, node12)
val node1 = Node(1, node9, node3)

The pre-order traversal looks like this:

fun preOrder(n: Node?) {
n?.let { node ->
print(node.key)
preOrder(node.left)
preOrder(node.right)
}
}
preOrder(node1) // prints 1 9 6 4 7 11 3 12 2 5

The traversal in order looks like this:

fun inOrder(n: Node?) {
n?.let { node ->
inOrder(node.left)
print(node.key)
inOrder(node.right)
}
}
inOrder(node1) // prints 4 6 7 9 11 1 2 12 5 3

The traversal after ordering is as follows.

fun postOrder(n: Node?) {
n?.let { node ->
postOrder(node.left)
postOrder(node.right)
print(node.key)
}
}
postOrder(node1) // prints 4 7 6 11 9 2 5 12 3 1

Tree with multiple children

You may also encounter a tree with an array of children instead of the left and right nodes. An example of this data structure is the Android view hierarchy, where each view can have multiple children.

class Node(var value: Int) {
val children: List<Node>
}

In this case, the function would have to be called recursively for all children, and the code would look like this:

fun traverse(node: Node) {
print(node.key)
node.children.forEach {
traverse(it)
}
}

Whenever you end up with a recursive algorithm that repeats calls on the same input, you may be able to optimize it using dynamic programming. The idea is to store the results of the sub-problems in a table so that you don’t have to recalculate them later when you need them. This reduces the complexity of time from an exponential function to a polynomial. It can be implemented using either iterative or recursion.

Iteration

Start with the smallest i From there, fill out the results table. All the sub-problems needed for the current iteration should have already been resolved. In the final iteration, we solve it as follows: i=n Returns the result.

fun fibonacci(n: Int): Int {
// Initialize an array to keep track of results of subproblems
// We'll use 0 as the placeholder initial value

val results = Array(n + 1) { 0 }
// Set the base cases
results[1] = 1
results[2] = 1
for (i in 3..n) {
results[i] = results[i-1] + results[i-2]
}
return results[n]

}

Recursion

Start from i = n.. If the results of the sub-problems required for the current iteration already exist in the results table, you can use them. If not, call the functions recursively to resolve them and save the result.

fun fibonacci(n: Int): Int {
// Initialize an array to keep track of results of subproblems
// We'll use 0 as the placeholder initial value

val results = Array(n + 1) { 0 }
// Set the base cases
results[1] = 1
results[2] = 1
return helper(n, results)
}
// Write a helper function that takes in the results array as an
// argument

fun helper(n: Int, results: Array<Int>): Int {
// Check for the result of the subproblem you need in the
// results table first

val nMinusOne: Int = if (results[n-1] != 0) {
results[n-1]
} else {
// Only make the recursive call to the subproblem if it's
// not in the results table yet

helper(n-1, results)
}
val nMinusTwo: Int = if (results[n-2] != 0) {
results[n-2]
} else {
helper(n-2, results)
}
// Fill in the results table with the current results
results[n] = nMinusOne + nMinusTwo
return nMinusOne + nMinusTwo
}

This concludes the Kotlin for Interview series.This is Link to cheat sheet Cover all five parts again. Good luck in the interview!

Source

Leave a Reply

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