I am now fairly involved in my company's interview process and Im constantly surprised that none of the resumes I get mention anything about the applicants character or professional demeanor.
For all the fear of being "culturally unfit" for a company, highlighting what kind of role you play and how you interact with your coworkers is fundamental.
Are you diligent and consistent with your work?
Are you the kind of person that bursts through work in a flash?
Do you prefer to work alone or in a team?
How do you feel working with people below your position or above it?
etc.
These questions have the issue, however, that you rarely ask them in an interview. You just gauge them from a conversation, that really doesnt speak to any of them. If someone is a complete technical ace, but is silent 100% of the interview besides technical points, i still get red flags. A co-worker is not a cog in a machine, its someone you will be spending 40 + hours a week with.
I disagree with hard theory NOT being important. Im a drop-out but i still went through all the algorithms and data structures classes out there and they gave me knowledge to communicate about hard problems, even though Im not the one solving them (we got some phds for that). And above all, at least in our case currently, several of the algorithm questions we do are actual problems we had in our product. In particular i wouldnt even call O(n) "hard". Its maybe the single most important performance computer science knowledge you need, and its not hard to calculate for the vast majority of applications.