# Kotlin Whiteboard

Level up your whiteboard interview skills by solving a number of common coding interview questions using Kotlin. By Joe Howard.

## Who is this for?

Kotlin developers preparing for job interviews or looking to refresh their coding interview skills.

## Covered concepts

- Binary search
- Linear data structures: linked lists, stacks, and queues
- Trees, Binary Trees, BSTs, and AVL Trees
- Heaps and Priority Queues
- Basic sorting algorithms
- Merge Sort, Radix Sort, Heap Sort, and Quicksort
- Graphs, BFS, and DFS

## Part 1: Introduction

Learn about the common developer interview practice of whiteboarding, and see some strategies for preparing for whiteboard interviews.

Understand the prerequisites for following along with the course, and see some resources for learning about data structures and algorithms.

See how to create IntelliJ IDEA Kotlin JVM projects that allow you to work with the sample code from the course episodes and how to use the Kotlin playground.

Learn about binary search and solve a warm-up question that uses a technique similar to binary search.

## Part 2: Linear Data Structures

See a review of some of the key properties of linear data structures: arrays, linked lists, stacks, and queues.

Given a linked list, create an extension function on the LinkedList class to print the nodes in reverse order.

Given a linked list, find the middle node in the list.

Given a linked list, reverse the linked list itself, so that the nodes are linked in the opposite direction.

Create a function that takes two sorted linked lists and merges them into a single sorted linked list.

Given a linked list, create an extension function on the LinkedList class to print the nodes in reverse order, but this time, with no recursion.

Given a string, check whether the string has matching parentheses.

Imagine youâ€™re playing a game of Monopoly with your friends. Create a Monopoly organizer that tells you whose turn it is.

Implement a method to reverse the contents of a queue using an extension function.

## Part 3: Trees

Review the definitions surrounding tree data structures and the properties of a number of tree variants.

Print the values in a tree in an order based on their level.

Given a Binary Tree, write an extension function to find the height of the tree.

Devise a way to serialize a Binary Tree into a list, and a way to deserialize the list back into the same Binary Tree.

Create a function that checks if a Binary Tree is a Binary Search Tree.

Add methods to a BinarySearchTree class and BinaryNode class to check whether two BSTs are equal.

Create a method to checks if one BST contains all of the elements of another BST.

How many leaf nodes are there in a perfectly balanced Binary Tree of height 3? What about a perfectly balanced Binary Tree of height h?

How many nodes are there in a perfectly balanced Binary Tree of height 3? What about a perfectly balanced Binary Tree of height h?

## Part 4: Heaps and Priority Queues

Review the heap and priority queue data structures as well as their properties and applications.

Write a function to find the nth smallest integer in an unsorted array.

Instead of a heap, use an ArrayList to implement a Priority Queue.

Use a priority queue to get a list of people on a waitlist by the appropriate priority.

## Part 5: Basic Sorting

See an animated review of the basic sorting algorithms.

Review Bubble Sort visually then add Bubble Sort as an extension function on MutableList.

Review Selection Sort visually then add Selection Sort as an extension function on MutableList.

Review Insertion Sort visually then add Insertion Sort as an extension function on MutableList.

Given a list of Comparable elements, bring all instances of a given value in the list to the right side of the list.

Given a list of Comparable elements, return the largest element thatâ€™s a duplicate in the list.

Create a function to reverse a mutable list of elements without relying on any library functions.

## Part 6: Advanced Sorting

Review some of the more advanced sorting algorithms: Merge Sort, Radix Sort, Heap Sort, and Quicksort.

Write a function that takes two sorted Kotlin iterables and merges them into a single iterable.

Implement a most-significant-digit (MSD) Radix Sort, also called lexicographical sorting.

When performing a Heap Sort in ascending order, choose which of two starting arrays require the fewest comparisons.

Use Heap Sort to sort an array in descending order instead of ascending order.

The Quicksort algorithm is typically implemented using recursion. Can you implement it iteratively?

## Part 7: Graphs

Review the definition of graphs as well as some of the properties of graphs and their implementation.

Write a method to count the number of paths between two vertices in a directed graph.

Determine the maximum number of items ever in the queue used to perform a breadth-first traversal on a given undirected graph.

Implement a graph breadth-first traversal using recursion and not iteration.

Create a graph method to detect whether or not a graph is disconnected.

For a given graph, determine which traversal (DFS or BFS) is better for discovering if a path exists between certain nodes.

Create a graph method to detect if a directed graph has a cycle.