While traditional fairness metrics like statistical disparity evaluate equal treatment across social groups, they fail to account for real-world constraints, such as in hiring, where a predefined acceptance rate across all groups is demanded. To achieve fair datasets for machine learning, we propose two fast and exact sampling methods, FairFESDown and FairFESUp, that are capable of aligning datasets with a specified targeted fairness goal. Unlike existing methods, our approaches have a linear time complexity regarding the datasets’ sizes and can handle non-binary protected attributes. We evaluate our methods on several popular classifiers and datasets from the fairness literature, achieving optimal fairness with statistical disparity scores close to zero while maintaining classification performances similar to the original datasets. Our pre-processing methods outperform existing approaches, including FairGAN, FairSMOTE, and FairUS, regarding statistical disparity, classification accuracy, and runtime.