News for hackers. Stuff that matters.
Re:Gaming CS Interviews by orlp on Wednesday September 28, 2022 @05:59AM (#33006251)
Not if you use a hash set. This is expected O(n) time to de-duplicate an array of integers while maintaining the original order (more explicitly written than I normally would in Rust for didactical purposes):

    let mut hash_set = HashSet::new();
    let mut len = 0;

    for i in 0..arr.len() {
        if !hash_set.contains(&arr[i]) {
            hash_set.insert(arr[i]);
            arr[len] = arr[i];
            len += 1;
        }
    }

    arr.truncate(len);
Re:Gaming CS Interviews by trinovantes on Wednesday September 28, 2022 @06:40AM (#33006481)
Good point but it's not exactly a free lunch. You're trading memory for the speedup.

You can also use radix sort for what I'd like to call "fake" O(n) sort since physical hardware puts an upper limit on the hidden constant.

Re:Gaming CS Interviews by saagarjha on Wednesday September 28, 2022 @06:22PM (#33014006)
Radix sort generally places far more restrictions on the keys than a set would.