I agree that a lot of story around interviewing is broken and that many of the questions don't relate to day to day jobs... like creating a binary tree or "how do you move a mountain" (IE: https://www.amazon.com/How-Would-Move-Mount-Fuji/dp/03167784...) - but they do show that you know CS basics, know how to learn them or have basic problem solving skills.
As much as people bemoan CS interviews... currently? They are a necessary evil to certain segments of the job market. Can you get jobs without them? Sure... just like you can get jobs without degrees - but your resume will get round-filed for a large number of jobs without a degree and you'll not make it past initial filters without knowing "basic" CS trivia like binary trees.
Whether you're okay with a limited job pool or not is on you... I don't have a 4 year... but I have a 2 year with many years of experience and I'm okay with some of the limits until I eventually get a BA. I still make six figures and know I can find a new job if it comes to it - as I've done repeatedly with limits. I've never balanced a binary tree for a job interview but I have "failed" online tests because I wasn't "fast enough" on code tests. I'm still employable and successful.
- Estimation ('market sizing') is a standard part of management consulting company case interviews . The reason is because clients will be throwing you questions and one part of the job is to look smart and give reasonable answers on the fly, without going to a computer or grabbing a calculator first.
- Physicists call them Fermi problems 
- Microsoft (in)famously asked 'How many ping pong balls fit into a 747?' as a brain teaser . This was common enough that someone wrote a book about these brain teasers .
- Fast mental math is a standard part of many trader interviews, since you'll be making split-second decisions under pressure 
One technique is converting everything into log10 first, e.g. 3 billion is about 3 * 10^9 ~ 10^9.5, then you're just adding / subtracting exponents to multiply / divide. Another way is to always round inputs to 'easy' numbers (2, 3, 5), and calculate them separately from exponents.
A few minutes with a napkin can easily save several hours doing something that can't possibly be worthwhile 
Edit: These are not puzzle books specifically, but books about puzzles.
Now back to the article: it was an enjoyable read, but I believe the title is somewhat misleading. High IQ does not make you less creative. However high IQ does not imply creativity. The converse is also not true. I am a bit tired of IQ being used as some kind of objective measure of capabilities, let alone success. Is there any other test that would be more representative of one's mental abilities?
Microsoft has, of late, moved away from these sorts of questions because they don't really translate into job performance, from what I understand. ;)
Fresh book recommendations delivered straight to your inbox every Thursday.