Possible for Category Base and Custom post Type to share the same slug/permalink?

No, it’s not safe to use the /books/ URL for both a category base and custom post type base. WordPress uses the URLs to determine what type of content to serve. If you’ve set up 2 different types of content at the same URL, it won’t have any way to know which you’re requesting, and if you end up with a book slug that’s the same as a category slug, you’ll really have conflicts.

To keep the URL types segregated but still logical, you could use URLS such as

CPT: example.com/book/title-of-a-single-book

Category: example.com/books/category-name

Or, perhaps something like

CPT: example.com/books/title-of-a-single-book

Category: example.com/book-categories/category-name

Or, continue using your workaround, example.com/books/category/category-name, and they will all appear to be under “books.”