This is one unexpected way in which I think my academic background has served me well: We give presentations and take questions about our work all the time, or

This is one unexpected way in which I think my academic background has served me well: We give presentations and take questions about our work all the time, or have whiteboard discussions with colleagues about how things work. We also giving practice talks before giving important ones, with a friendly audience taking notes, asking questions, and giving you feedback on what was good and what was not. If white board algorithm problems terrify you, the only thing that will help is practice. Take the opportunity to try to discuss different solutions with colleagues at work. Or, if you can't do it at work, try to get a couple of friends together and just take turns presenting and asking questions. Yeah, you won't get the adversarial atmosphere that way, but you will get used to the setting.