You could prepare for months but if you don't understand the core CS concepts then it's difficult to hack these kinds of interview problems. Having a solution is one thing, but coming up with 3 different solutions to the same problem based on various constraints (preprocessing, space/time constraints) requires understanding.
If they "hacked" this, then thru likely understand the concepts well enough such that its sufficient for the job.
Also, interviewers should ask if they interviewee has seen the coding problem before and come prepared with a backup. Interviewers are also looking to see if the interviewee derives the answer too easily. Usually scraping the surface reveals whether the person really knows what they're talking about or not.