# Tag: #ctci

Is there a route between these two nodes in this directed graph?

An algorithm in Haskell using a breadth-first search to find the reachable set of nodes. 2020-01-24

How to check if a binary tree is balanced

An O(n) algorithm to check if a binary tree is balanced, by passing up the height from recursive calls. 2020-01-23

How to sort a stack using one additional stack

We can model “infinite tape” using two stacks. Then we can navigate the list in both directions. This lets us bubble-sort the list in O(n^2) time. 2020-01-22

Implementing a queue using two stacks

Implement a queue using two stacks, with one stack for the back of the queue and one for the front. Reverse the back stack onto the front stack when dequeuing to maintain the queue order. 2020-01-21

Towers of Hanoi in Haskell

A Haskell solution to the classic Towers of Hanoi problem. 2020-01-20

A stack with minimum element

A stack with a

`min`

operation that runs in O(1) time. Store the current minimum alongside each element, or use run-length encoding to compress the stack of minimums. 2020-01-19Implementing a queue using a linked list

The head is the front of the queue, allowing efficient dequeue. The tail is the back of the list. To enqueue efficiently, we keep a reference to the tail. 2020-01-18

Implementing a stack using a linked list

The head of the list is the top of the stack. 2020-01-17

How to check whether a linked list is a palindrome

Find the middle node of the linked list using the “runner” trick. Reverse the first half, then compare the nodes pairwise from the middle outwards. Restore the list to its original state before returning. 2020-01-16

How to partition a linked list

A C function to partition a linked list around a value

`x`

, running in optimal time and space. 2020-01-13How to delete a node from the middle of a linked list

To delete a node from the middle of a linked list, copy the value and next pointer of the next node to the current node, then free the next node. 2020-01-12

How to find kth last node of a linked list

Use the “runner” technique with two pointers - one leading by k nodes - to find the kth last element of a singly linked list without knowing the list length in advance. 2020-01-11

How to remove duplicates from an unsorted linked list

To remove duplicates from an unsorted linked list with no extra memory, use a nested loop to check each node against all others, removing duplicates as you go. Time complexity is O(n^2). 2020-01-10

How to rotate a square matrix in-place

An in-place algorithm to rotate a square matrix by 90 degrees. The key is to rotate 4 corresponding points using a formula, applying this to all points in the top-left corner. 2020-01-09

Run-length encoding in C

Compresses a string by replacing consecutive repeated characters with the character and its count. The solution requires two passes to first calculate the length of the compressed string, then generate it. 2020-01-08

How to percent-encode strings in-place

A C function to replacing spaces with

`"%20"`

in-place, by iterating from the end, preserving true string length. 2020-01-07Determine whether one string is a permutation of the other

A C function to determine if one string is a permutation of another, using a character distribution representation for optimal time and space complexity. 2020-01-06

How to reverse a string in C

An in-place string reversal function in C, starting by swapping the first and last characters, then iterating towards the middle. 2020-01-05

Determine if a string has all unique characters

A recursive algorithm to determine if a string has all unique characters, with an analysis of its time complexity. 2020-01-04

All content copyright James Fisher.