root Posted November 10, 2022 Share Posted November 10, 2022 In this thread: anyone can share a programming problem and we will post solutions. The goal is to find solutions with impressive characteristics such as performance or brevity. This can be interpreted as recreational optimization or code golf. Your first question (I will provide an example answer if there are no biters): How would you locate gaps in a list of integers? Example use case: determining which IDs have been deleted from a database Example input: [1,3,4,5,8,9] Example output: [2,6,7] (Yes, this does not detect gaps at the tail of the list.) Link to comment Share on other sites More sharing options...
root Posted November 11, 2022 Author Share Posted November 11, 2022 (edited) Here is a naive implementation: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ce526c0085e7ca3ddda57d6a753ffe16 This iterates over the array several times when it should only be required to iterate once. Feel free to use any language or introduce your own problems! Edited November 11, 2022 by root added link Link to comment Share on other sites More sharing options...
Chauke Posted November 11, 2022 Share Posted November 11, 2022 function get_missing_ids(a) { var res = [] var max = Math.max(...a); for (i = 1; i < max; i++) { var found = false a.forEach(element => { if (i == element) found = true }); if (found == false) res.push(i) } return res } var a = [1, 3, 4, 5, 8, 9] console.log(get_missing_ids(a)) Link to comment Share on other sites More sharing options...
wacked Posted November 12, 2022 Share Posted November 12, 2022 $ python3 updatedsec.py 1 10 7 5 4 Missing: 2 3 6 8 9 from sys import stdin arr = [] for x in stdin: arr.append(int(x)) arr = sorted(arr) print("Missing:") for i in range(len(arr)-1): if arr[i+1] - 1 != arr[i]: for x in range(arr[i]+1, arr[i+1]): print(x) Link to comment Share on other sites More sharing options...
root Posted November 13, 2022 Author Share Posted November 13, 2022 (edited) Here is an implementation that uses (I think) two iterations, one to sort and then one for the gap detection. The gap detection algorithm should be O(n) rather than O(n^2) like my last implementation. https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f773c1d153eb55a2f0d07d0d71e9bb18 Edited November 13, 2022 by root Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now