From Reddit I’ve seen this common hiring problem:
It has various solutions, the last one is (in Rust):
fn sums_to_target<T>(arr: &mut [T], k: T) -> bool
where T: Copy + Add<Output=T> + PartialEq + Ord {
arr.sort_unstable();
let mut left = 0;
let mut right = arr.len() - 1;
while left < right {
let sum = arr[left] + arr[right];
if sum == k {
return true;
} else if sum < k {
left += 1;
} else {
right -= 1;
}
}
false
}
In D language you probably want to write that solution in a way more similar to this (it lacks some template constraints, please bear with me):
bool sums_to_target2(T)(T[] arr, in T k) {
arr.sort();
while (!arr.empty) {
const sum = arr.front + arr.back;
if (sum == k) {
return true;
} else if (sum < k) {
arr.popFront;
} else {
arr.popBack;
}
}
return false;
}
A similar solution in Rust:
#![feature(nll)]
fn sums_to_target2<T>(mut arr: &mut [T], k: T) -> bool
where T: Copy + Add<Output=T> + PartialEq + Ord {
use std::cmp::Ordering::*;
arr.sort_unstable();
while let (Some(&x), Some(&y)) = (arr.first(), arr.last()) {
match (x + y).cmp(&k) {
Less => { arr = &mut arr[1 ..]; },
Equal => return true,
Greater => { arr = &mut arr[.. arr.len() - 1]; },
}
}
false
}
Is it a good idea to put in the Rust std lib two functions that implement those pop_first and pop_last?