Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Key Concepts

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Stack & Queues

Stack

imagen

A stack is exactly what is sounds like, a last in first out data structure (LIFO). Whatever the most recent item added will be the first one removed.

It typically consists of 4 operations:

  • pop(): returns and removes the item from the top of the stack
  • push(item): adds the item to the top of the stack
  • peek(): return the top of the stack
  • isEmpty(): return true if the stack is empty

The benefit of using a stack versus an array is that it allows constant time for adds and removes, as it doesn't require shifting elements around.

Here is some simple code on a generic implementation of a stack:

public class Stack <T> {

    // internal class only used by the stack
    private static class StackNode<T> {
        private T data;
        private StackNode<T> next;

        public StackNode(T data) {
            this.data = data;
        }
    }

    private StackNode<T> top;

    public T pop() {
        if (top == null) throw new EmptyStackException();
        T item = top.data;
        top = top.next;
        return item;
    }

    public void push(T item) {
        StackNode<T> t = new StackNode<>(item);
        top = t;
        t.next = top;
    }

    public T peek() {
        if (top == null) throw new EmptyStackException();
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

Bear in mind when you are writing recursive algorithms that Stacks are particularly useful. Sometimes you need to push temporary data onto a stack as you recurse, but then remove them as you backtrack (for example, because the recursive check failed). A stack offers an intuitive way to do this.

A Stack is also really useful if you want to implement a recursive algorithm iteratively.

Queue

imagen

Very similar to a Stack, but the order is FIFO, first in first out. Imagine a line or a queue at a ticket stand, the items are removed from the data structure in the same order as they are added.

It uses the following functions:

  • add(item): adds to the end of the queue
  • remove(): returns and first item of the queue
  • peek(): returns the top of the queue
  • isEmpty(): return true if the queue is empty
public class Queue<T> {
    private static class QueueNode<T> {
        private T data;
        private QueueNode<T> next;
        public QueueNode(T data) {
            this.data = data;
        }
    }

    private QueueNode<T> first = null;
    private QueueNode<T> last = null;

    public void add(T item) {
        QueueNode<T> t = new QueueNode<>(item);
        if (last != null) last.next = t;
        last = t;
        if (first == null) first = last;
    }

    public T remove() {
        if (first == null) throw new NoSuchElementException();
        T data = first.data;
        first = first.next;
        if (first == null) last = null;
        return data;
    }

    public T peek() {
        if (first == null) throw new NoSuchElementException();
        return first.data;
    }

    public boolean isEmpty() {
        return first == null;
    }
}

To give you some context, Queues are often used in implementing caches or Breadth First Search (BFS).

In BFS for instance, we use a queue to store the list of nodes that we need to process. Each time we process a node we add its adjacent nodes to the back of the queue. This allows us to process the nodes in the order in which they are viewed.

Last updated on 3/26/2020
← Linked ListsTrees →
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr