Tag: #ctci

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

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

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

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

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

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-19

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

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

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

A C function to partition a linked list around a value x, running in optimal time and space. 2020-01-13

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

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

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

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

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

A C function to replacing spaces with "%20" in-place, by iterating from the end, preserving true string length. 2020-01-07

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

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

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