It is not hard to shuffle an array in O(n), with in place swapping,
array
How to do it for list in OCaml, with O(n)?
list
Requirement:
No array or in place usage
Consider this as an interview question