These types of questions basically boil down very cookie cutter patterns that generally bucket into graph traversal/search, being comfortable with coding/manipulating linked data structures, enumerating+pruning search spaces, and knowing little tricks to reduce an order of magnitude from the runtime or space complexity after having applied one of these patterns. These all generally require knowing all your basic data structures as a prereq (stack/queue/deque/vector/hash table/self-balancing search tree, then using those primitives to compose graphs etc).

My advice for people who wanted to prep for these interviews originally used to be to read through some books that prep you for algorithm competitions (e.g. ICPC, IOI, GCJ), but I find that to be a bit overkill and not as efficient a use of time (although some of these books do a much better job of explaining things than any of these interview prep books I've gone through). Today the advice I'd give is get a book like 'Elements of Programming Interviews' in the language you plan on using and a leetcode subscription and just get down to learning about a data structure/algorithm/problem solving paradigm and then solving a bunch of questions that fit that technique.

If you really want to go with the overkill approach, I'd recommend a book like Competitive Programming 3: https://cpbook.net/