No libraries meant we had to manage our own data structures. We had our own UI system, so understanding how to walk trees and manipulate them efficiently was crucial. Removing duplicates from an array in an efficient manner, important.

Linked list stuff? Oh yeah, very important. Linked Lists underlay a lot of basic OS data structures.

We did have real world problems in the interview mix as well. We'd give an underlying low level API and ask how it could be used to construct a more user friendly wrapper API. We'd give examples of in memory layout of objects and ask how that layout could be improved.

At the end of the day, we wanted to hire people who could solve problems, but also sit down and have a good discussion about how to solve problems.

FWIW it was always possible to tell, with junior employees, the engineers who had gone through CS and those who hadn't.

A good decade of self study of course bridges the gap, but right out of college? I've seen very smart people, good coders, who didn't realize they were working with relational data, and over-complicated solutions.

I also saw people trained as game programmers write mind blowingly fast code that computer scientists would be hard pressed to understand without a fair bit of study.

I had to spend a fair bit of time explaining isomorphic tranforms of code/data structures/concepts though. Game programmers pick up on that one quick, "like a matrix, but instead provable facts about software."