Friedrich Ewald · My Personal Website

Leetcode: Copy list with random pointer

Nov 3, 2022 · 7 min read

Given a head of a list with pointers to next and a random element, copy the list to a new list without any random pointers pointing to the old list.

# Definition for a Node.
class Node:
  def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
    self.val = int(x)
    self.next = next
    self.random = random

Leetcode: Decode ways

Nov 2, 2022 · 3 min read

Characters can be encoded via different numbers. A -> 1, B -> 2, ..., Z -> 26. Given a string s of numbers, return the number of possible decodings. For example 12 can be decoded as A,B and as L.

Leetcode: Reconstruct binary tree

Nov 1, 2022 · 5 min read

Given two lists of a preorder and inorder, create a tree and return the root node.

preorder: [3,9,20,15,7]
inorder:  [9,3,15,20,7]

Resulting tree:

      3
    /   \
   9    20
       /  \
      15   7

The problem is not so obvious at first. If the preorder list would also contain null values for the places where the tree does not contain nodes, we could simply iterate over this list and reconstruct the tree from there. But since the null values are missing, we also need to take a look at the inorder list.

Leetcode: Validate Binary Search Tree

Oct 31, 2022 · 5 min read

Given the root node of a tree, validate whether it is a valid Binary Search Tree. This is a tree where each node is unique, left children are smaller than the root and right children are greater than the root.

Leetcode: Palindrome partitioning

Oct 30, 2022 · 3 min read

Given a string s, return a list containing of all possible partitions of that string that are palindromes. A palindrome is a string that is the same backwards as forwards. For example, abba is a palindrome. The string aab can be partitioned as follows: [['a','a','b'], ['aa','b']]. This is because a single character is by definition a palindrome.