As for problem solving, solve problems: Do research, take a physics or mathematics heavy courselod, take computer science classes, intern at a software firm (as if that were so easy to do).
As for critical thinking, think critically: Do research, do college debate, write opinion articles for the college newspaper, take classes that challenge the way you think about the world (if you are Bacon's number one fan, take an animal ethics course; if you are a communist, take a finance and capital course; if you are an atheist, take intro to Islam for a core requirement; if you are a theist, take a class on secularism in culture), learn a foreign language, travel to a different part of the world, work with people who are not like you, TA for a course, mentor high school kids, etc.
Don't worry about people being able to tell if you have these skills or not. In the interview it should be plenty obvious as it is obvious in daily life when you are speaking to someone who has actually thought about the words coming out of their mouth and is considerate of opposing viewpoints.
