Programming problems & Data Structures In Rust
A collection of Rust implementations for common programming problems, interview questions, and fundamental data structures. This project serves as a resource for those looking to understand algorithmic problem-solving in Rust with detailed explanations and efficient implementations.
About the Project
This repository provides well-structured and optimized solutions to classical algorithmic problems using Rust. Each problem includes:
- Clear Problem Descriptions: Understanding the problem statement.
- Rust Implementations: Efficiently written, idiomatic Rust code.
- Algorithmic Insights: Explanation of the approach, trade-offs, and optimizations.
- Test Cases: Ensuring correctness and performance.
Featured Problems & Implementations
The project covers a variety of topics, including:
Array & Number Problems
- Segregate negatives & positives
- Buy and sell stock once
- Contains duplicate
- Contains nearby duplicate
- Maximum subarray sum
- Two sum
- Maximum product subarray
- Product of array except self
- K nearest points from a given point
String Problems
- Segregate RGB characters
- Longest common prefix
- Longest common suffix
Dynamic Programming & Recursion
- Longest increasing subsequence
- Number of ways to reach matrix end
- Palindrome partitioning
- N-Queens problem
- Subsets (backtracking, iterative, bit manipulation)
- Combination sum (multiple variants)
Search & Sorting
- Minimum in sorted rotated array
- Insert a new interval to a list of sorted intervals
- Search in a row and column-wise sorted matrix
- Search a target in a sorted rotated array
Data Structures Implementations
- Binary Search Tree (BST) with parent pointers
- Trie (Prefix Tree) for efficient string searching
- Min Heap & Max Heap for priority queue operations
Why Rust?
Rust provides memory safety, performance, and concurrency without the overhead of garbage collection. This makes it an excellent choice for implementing algorithmic solutions that require efficiency and reliability.
Example: Binary Search Tree (BST) with Parent Pointers
A BST (Binary Search Tree) allows efficient searching, insertion, and deletion of elements. Our implementation uses parent pointers to facilitate operations such as node deletion efficiently.
Node Definition
#![allow(unused)]
fn main() {
struct Node<T: Ord + Default + Clone + std::fmt::Debug> {
key: T,
left: Option<Rc<RefCell<Tree<T>>>>,
right: Option<Rc<RefCell<Tree<T>>>>,
parent: Option<Weak<RefCell<Node<T>>>>,
}
}Key Features
- Uses
Rc<RefCell<Node<T>>for shared ownership and interior mutability. - Weak parent references to prevent memory leaks.
Example: Max Heap Implementation
A Max Heap ensures that the parent node is always larger than its children. It is useful for implementing priority queues.
#![allow(unused)]
fn main() {
#[derive(Debug)]
pub struct MaxHeap<T: Ord> {
elements: Vec<T>,
}
}Heap Operations
- Insertion: Adds an element and maintains heap property.
- Deletion: Removes the largest element and rebalances the heap.
Who Is This For?
This project is perfect for:
- Rust developers looking to practice algorithms.
- Engineers preparing for coding interviews.
- Students learning data structures and algorithms.
Contributing
Contributions are welcome! Feel free to open issues, suggest improvements, or submit pull requests.
Note: The source code of the repository can be found here