Improving problem solving skills.

[Bop]

I'm graduating in a few months with a CS degree so I decided to try some interview questions. I found out that I am absolutely terrible at brain teaser type questions! I don't consider myself stupid (I'm actually toward the top of my class), but these puzzles sure make me feel dumb. Be it a lack of creative thinking or something else I feel as if I am lacking some skill.

Questions that actually directly relate to programming I can answer, but probably slower than I would like. For example, it took me 25 minutes to reverse a linked list. For a function like strstr I almost immediately saw a solution. I feel in general my ability to create algorithms is not as good as it can be.

I feel as if doing more of these problems is only marginally improving my abilities. So I was wondering, do you feel as if this is some ability you either have or you don't? If it isn't some inherent ability, is solving more problems the only way to improve?

 

[Thuleman]

Practice makes permanent.

Other than that I wouldn't worry about reversing a linked list. No one in their right mind would ask this as an interview question. Based on my own experience hiring staff and what I have been hearing from other supervisors the trend has largely moved away from hardcore skill testing.

The way I see it skill testing is not nearly as relevant as some make it out to be. The answer to most problems is the first hit on Google. It's not about what you know it's about whether you can find a solution to the problem quickly and that in the real world means having Google-fu and interpersonal skills so that you can collaborate with others and motivate them to solve the problem.

Skills can be acquired through training and repetition. Personality and attitude are largely set in stone and that is what recruiters are looking for in applicants. How well can you interact with other humans in difficult situations. What are your conflict resolution skills. Do you have leadership potential. Are you willing to collaborate (i.e. have other people read and monkey with "your" code). Do you have the confidence to give a presentation to clients without generating tidal waves made of sweat while keeping eye contact and explaining complex issues in a way non-technical folks can understand it.

Reversing a linked list and contrived problems like that are meaningless in the real world, especially if you don't fit into the existing team.

 

[LuminaryJanitor]

So I was wondering, do you feel as if this is some ability you either have or you don't? If it isn't some inherent ability, is solving more problems the only way to improve?

Those brain-teasers may well be something you can do or you can't. I know I'm pretty awful at them.

But as for the rest of them - the kind of things you could actually call problems, rather than just riddles - are certainly something you can get better at. It just takes a lot of practice, with a lot of different types of questions. It's not like writing algorithms is one monolithic skill; you can sit there solving string-processing problems until your fingers bleed, but it's not going to help you much with juggling pointers in a binary tree.

So I'd say just keep at it. It's probably not the only way to improve, but I can't think of a better way to convey the things you pick up from experience. Take recursion for example. Most struggle to get their heads around it at first, but with enough experience, it can become more natural than iteration. But there's still not a lot you can say to bring a newbie up to that level. Partly because it's so hard to articulate the intuitive, almost unconscious thought process that goes into it, but also because your own mental model is unlikely to fit. That moment of realisation where it all just clicks isn't something someone can hand to you. You need to piece it together for yourself.

FWIW, I found the TopCoder practice rooms to be a pretty good resource for this kind of thing.

Skills can be acquired through training and repetition.

Not necessarily. Some people just don't get it (and having taught first-year programming courses myself, I can vouch for that). Skills can certainly be improved, but only if you've got something solid to build on.

The way I see it skill testing is not nearly as relevant as some make it out to be. The answer to most problems is the first hit on Google.

I can't think of anything more relevant to a programming position than the ability to actually program. The last person you want to hire is someone who needs Google to solve FizzBuzz. You make it sound like a high school dropout would make a better software developer than a CS grad, as long as he's a nice enough guy.

Reversing a linked list and contrived problems like that are meaningless in the real world

A lot of those problems are contrived, but I wouldn't say that reversing a linked list is one of them. Sure, you're probably not going to be writing this exact function in many "real-world" situations, but I don't think it's too much to expect a professional software developer to have a basic understanding of linked data structures, and I can't think of a much simpler problem to demonstrate that in an interview.

 

[mikeblas]

Other than that I wouldn't worry about reversing a linked list. No one in their right mind would ask this as an interview question.

Why not? What questions would you ask a programming candidate, if you don't ask about their programming skills?

The way I see it skill testing is not nearly as relevant as some make it out to be. The answer to most problems is the first hit on Google. It's not about what you know it's about whether you can find a solution to the problem quickly and that in the real world means having Google-fu and interpersonal skills so that you can collaborate with others and motivate them to solve the problem.

This means that you're never going to be better than anyone around you, and your organization is never going to be better than any other organization. Or worse: never better than what any other organization decides to publish. Because your organization doesn't excel and isn't innovating, finding and keeping good candidates is going to be terribly difficult because nobody good will want to work there -- they'll never get better, and they'll never do anything meaningful.

Skills can be acquired through training and repetition. Personality and attitude are largely set in stone and that is what recruiters are looking for in applicants. How well can you interact with other humans in difficult situations. What are your conflict resolution skills. Do you have leadership potential. Are you willing to collaborate (i.e. have other people read and monkey with "your" code). Do you have the confidence to give a presentation to clients without generating tidal waves made of sweat while keeping eye contact and explaining complex issues in a way non-technical folks can understand it.

Certainly, these are important skills. But without the ability to write code in the first place, an engineering candidate isn't going to have anything to add.

Questions that actually directly relate to programming I can answer, but probably slower than I would like. For example, it took me 25 minutes to reverse a linked list. For a function like strstr I almost immediately saw a solution. I feel in general my ability to create algorithms is not as good as it can be.

What strstr() solution did you see? Was it efficient? How did you attack the linked list problem?

I think that problem solving as a skill decomposes into a couple of areas. One part of it is knowing the tools you have at your disposal. If you know a tool and its traits -- how easy is it to use, what shortcomings it has, what capabilities it has -- you know what problems that tool can be used to solve. There's also decomposition; if you see a problem, how can it be solved step by step? Once you identify the steps, then you can think about the tools you have available and see how they might apply to the problem.

Another part is idea generation. If you can think of a few different ways to solve a problem, you can then decide which one is better and why. Given some framework for that decision (are you trying to be fast to finish, or trying to write something that's stable, or trying to write something that's very efficient, or ... ?) you should be able to choose which solution fits the goals best, and which you should pursue.

I feel as if doing more of these problems is only marginally improving my abilities. So I was wondering, do you feel as if this is some ability you either have or you don't? If it isn't some inherent ability, is solving more problems the only way to improve?

Just like any other skill, I think there's a mix. Some people have innate ability. Other people are smart or trainable, and they'll learn enough to overcome their lack of built-in skill.

If you're trying to learn, then you have to figure out how you, yourself, best learn. Explaining problem solving to someone is quite difficult; many people focus on learning the answer when they should really focus, instead, on learning the path to the answer. (That's why I'm eager to hear how you solved strstr().) If you think about the solution to strstr(), you'll learn about strstr(). If you think about how someone might arrive at different solutions to strstr(), and how to ferret out which one might be better, only then will you end up learning something about how to solve problems in general.

 

[aL Mac]

I agree with mikeblas. If I asked a candidate how to reverse a linked list and he didn't come a solution I would be very concerned. I would think most programmers could immediately suggest a solution.. throw it into a stack and pop them all off, or put them in an array and iterate through it in reverse, or jokingly say well if I had a doubly linked list it would be more efficient to start at the end and just go backwards! I thought of all these ideas almost immediately after reading that question and a good programmer should be able to have similar or better ideas.

I was once asked by my boss to ask a candidate programming questions. I asked him increasingly easy questions to which he answered absolutely none of them. It was quite uncomfortable, but my boss wanted to make sure he knew how to program. It turns out that even though his resume claimed he almost had a M.S. degree in computer science and supposedly had over 5 years experience, he could not tell me how to allocate or deallocate memory in his stated core language (C++), what a multi-threaded program was, or the difference between a linked-list and an array. Could you imagine if I had not asked that guy programming questions? He could have been a real nice guy but what if he had moved a few thousand miles to work for the company and then we found out he didn't know how to program?

Anyway, I'm not trying to be hard to the original poster. I think you probably just over thought the problem and got nervous. Try to stay cool and think it out logically. I once was helping a girl in my assembly class. She thought since I was good at programming that I could just sit down and start typing out the solution from start to finish. Instead, she saw that I would break it down into smaller pieces in plain English and then come up with an implementation for each piece and put them together. She also had the problem of feeling like she was not good at it... I think if feel like you aren't good at solving those types of problems than you are going to make it harder on yourself. Even simple problems stump for a while sometimes, just have to think through it.

 

[Bop]

Those brain-teasers may well be something you can do or you can't. I know I'm pretty awful at them.

It seems like I'm a new permanent member of the club. Tried several more this morning and found myself stuck on each one. "How would you pay an employee a gold piece every day for a week if you had a gold bar with 7 contiguous pieces that can only be cut twice?" I tried seeing if there was a trick to somehow cutting the bar in seven pieces (ie cutting once and then stacking and cutting once through two layers). I got stuck and didn't think you could take pieces back. Starting to think it's hopeless for improvement. I did manage to solve the four travelers crossing a bridge in 17 minutes problem a few days ago, though.

What strstr() solution did you see? Was it efficient?

I'm not sure if you were asking those questions simply for me to reflect upon(which I will) or to respond to, but either way I will provide some insight into my thought process. Some weakness may scream out.

For strstr() I first thought how do you verify some substring is part of some string? You must travel along the string until you reach a point where the current character matches the first character of the substring and then check if the full substring is contained from that point on. If not, move to the next position in str1 and try again. Without much time I was able to construct the approach that uses nested looping and checks the length(inner for loop counter +1) against strlen() of str2. It appears to have a worst case run time of O(n^2). I'm having difficulty finding a different approach (A version that uses memcmp()?).

How did you attack the linked list problem?

For reversing a linked list I first brainstormed possible approaches I could take. I first thought maybe the program could travel to the end of a given list each time, remove the last node, and add it to a new list. I quickly scrapped that idea since traveling down a list each time seemed too inefficient. It didn't occur to me at the time to explore if it could possibly be workable with a recursive method. Didn't think to use other data structures either.

My next approach, was that I could proceed down the list and simply set the next pointer to previous. I then realized that I would have to create a temp variable that would serve as the current pointer for the next iteration (setting the previous pointer to current before setting current to temp) . This turned out to be a correct approach. At completion I thought of a standard case and a few boundary cases to help verify its correctness. I had one small pointless complexity present at the end, but the program was still logically correct.

For both problems I drew diagrams at nearly each step. I have to write things down as my concentration is poor and I can't juggle too many things in my mind at once. I'm at least aware that I am highly visually oriented in my learning and thinking. I had a few pauses with points of confusion/uncertainty here and there so my transition from step to step wasn't smooth which certainly added extra time.

From doing these problems I feel like my weak area is creative thinking (when I can't determine a solution quickly I tend to fall apart and get completely stuck). Which gives me cause for concern. I may be pulling a near perfect GPA in school, but it gives me serious doubt as to how I will perform in the profession (if I can even pass an interview!).

 

[mikeblas]

I'm not sure if you were asking those questions simply for me to reflect upon(which I will) or to respond to, but either way I will provide some insight into my thought process. Some weakness may scream out.

I'm happy to help if you want to think your process over.

For strstr() I first thought how do you verify some substring is part of some string? You must travel along the string until you reach a point where the current character matches the first character of the substring and then check if the full substring is contained from that point on. If not, move to the next position in str1 and try again. Without much time I was able to construct the approach that uses nested looping and checks the length(inner for loop counter +1) against strlen() of str2. It appears to have a worst case run time of O(n^2). I'm having difficulty finding a different approach (A version that uses memcmp()?).

memcmp() would just do the same thing the inner loop does; start comparing at the beginning of s2 and the offset into s1, and tell you if it found a match.

You've done a good job to find the brute-force, basic case. Lots of people wouldn't get that far, and even among those that do, many can't code it and make it actually work.

There's a couple faster ways to do strstr(), though. One is a very well-documented algorithm, and you can find it if you search around. That just leads you to the answer, though, and doesn't teach you to think about problems.

You're right, the worst-case running time for strstr() is O(n^2). Really, it's O( len(s1) * len(s2) ). It's also good that you've identified that case; if shows you understand the pattern of the algorithm that you're thinking about.

If you think about that specific worst case, what do you notice? Why does it take so long to run, and how can you try to pick away some of the work that it is doing? This is what your real problem is: take what you have and make it faster. Is there some work that you feel like you could skip? Some way that you could do comparisons (you have to do comparisons, right?) and just make less comparisons with either len(s1) or len(s2), such that when you've got the loops nested your total complexity is lower?

For reversing a linked list I first brainstormed possible approaches I could take. I first thought maybe the program could travel to the end of a given list each time, remove the last node, and add it to a new list. I quickly scrapped that idea since traveling down a list each time seemed too inefficient. It didn't occur to me at the time to explore if it could possibly be workable with a recursive method. Didn't think to use other data structures either.

I think it's good to nix an idea that sounds bad, but you always want to hold on to it loosely. Most people who struggle with programming are either not generating good ideas or are generating some ideas, but picking ones that might be bad (for one reason or another) and sticking with that idea without entertaining other ideas, solutions, or opportunities.

My next approach, was that I could proceed down the list and simply set the next pointer to previous. I then realized that I would have to create a temp variable that would serve as the current pointer for the next iteration (setting the previous pointer to current before setting current to temp) . This turned out to be a correct approach. At completion I thought of a standard case and a few boundary cases to help verify its correctness. I had one small pointless complexity present at the end, but the program was still logically correct.

That's the solution a lot of people write. It works well, but as you note it is a bit complicated -- there's a couple of edge cases, you need the temporary variable (or two?) and you need to keep them organized. That might be challenging on a whiteboard.

For both problems I drew diagrams at nearly each step. I have to write things down as my concentration is poor and I can't juggle too many things in my mind at once. I'm at least aware that I am highly visually oriented in my learning and thinking. I had a few pauses with points of confusion/uncertainty here and there so my transition from step to step wasn't smooth which certainly added extra time.

Making a sketch is a good idea. I was actually asked this question the last time I interviewed, and I wanted two or three different colors of white board pens to keep my drawings readable!

One way to approach all data structure problems is pretty simple, and that might help you get a bit further. I like to think of the data structure as some object (a noun) and think of all the things I can do that object (verbs). If I told you to write a CBopLinkedList class for me, what methods would it have? What verbs could you do to that noun?

If you enumerate all of them exhaustively, it shouldn't take you too long if you're much of a programmer at all. Once you have enumerated that list -- a list of all the valid actions you can take on a linked list -- I think you'll have a better catalog of your tools. What operations can you combine in a loop to traverse the list I give you and make it reversed?

 

[Zangmonkey]

Other than that I wouldn't worry about reversing a linked list. No one in their right mind would ask this as an interview question.

I was asked this very question in a tier 3 interview by a panel of engineers at GE a little over a year ago.

 

[Bop]

If you enumerate all of them exhaustively, it shouldn't take you too long if you're much of a programmer at all. Once you have enumerated that list -- a list of all the valid actions you can take on a linked list -- I think you'll have a better catalog of your tools. What operations can you combine in a loop to traverse the list I give you and make it reversed?

I thought of some possible actions and came up with these: One action that could be useful in such a class could be a move to front/make head function. The move to front function could be called when traversing though the nodes in the original list. Another possibility is similar to my very first list reversal idea. The original list could be passed to an object with a null list (or use a tail pointer in the original). A recursive function could then continuously be called until the last node is reached in the original list and then begin using an insert at end function with the nodes as the function stack winds down.

Those are a few ideas; at this point I'm having trouble of thinking of other ways.

 

[mikeblas]

Thats a good insight. Linked lists make it easy to put a node a the front of the list. If you could use that facet of linked lists, does it make a solution easier? What other facets of linked lists from your enumeration of their benefits makes this problem easier?

Is ther something about recursion that you think makes he problem easier, similarly? What feature of recursion migh include or exclude it from the solution to the linked list problem?

 

[Bop]

Thats a good insight. Linked lists make it easy to put a node a the front of the list. If you could use that facet of linked lists, does it make a solution easier? What other facets of linked lists from your enumeration of their benefits makes this problem easier?

Is ther something about recursion that you think makes he problem easier, similarly? What feature of recursion migh include or exclude it from the solution to the linked list problem?

I think it makes the solution easier. It breaks the problem down in such a way that you can move on to tackle a slightly different and smaller problem (that is hopefully not more difficult!). Lists are extremely dynamic and using a recursive method seems logical. Why? By breaking it down into sub problems and viewing lists as sub-lists it's almost a natural use of recursion. I may be incorrect but since a reverse method using a move to front function could probably be implemented using tail recursion it may be equivalent to an iterative version. Therefore, it would not include or exclude it compared to an iterative version (since a compiler may not add to the stack with tail recursion).

I read the book How Would You Move Mount Fuji? recently and I have been wondering how most companies treat these logic puzzles today. Would a large tech company expect a correct answer? I know one company referenced in the book prizes itself on the fact that every employee answered the "Five Pirates" puzzle correctly. Would they hire someone who got an incorrect answer or didn't arrive at a solution, but showed a good thought process?

 

[mikeblas]

If you're using recursion, your solution has a really serious problem: it'll run out of stack space. Let's say you've got a list with 250 million elements in it. If you try to reverse that recursively, then you'll run out of stack space, crash, and that's that. Your recursive solution is also slower than an iterative solution, so I think it's best to avoid recursion.

Indeed, if you can implement the problem using tail recursion, you'll have a win -- but I don't think you can. Even if you can, you're relying on the compiler to do your magic. (And, even if you can, and I don't want a recursive solution, I just tell you that our compiler is broken.)

There's a better way. Indeed, linked lists are very easy to manipulate. Can you think of one facet of a linked list that makes solving this problem a snap?

I think that the "Mount Fuji" book spends too much time talking about that class of logic problems and too little talking about their weakness as a question genre for interviews.

One inherent weakness is smart asses. I'm in that group. When someone asks me why man hole covers are round, I tell them that it's because man holes are round. If the covers weren't the same shape as the hole, they wouldn't fucking fit, now would they? When someone asks me about how to move Mount Fuji, I ask them how they move their mom. She so fat, I had to take a train and transfer to a bus ride to get on her good side. Your mom is so fat that, if we know how to move her, we can probably scale the solution down to Mount Fuji pretty easily.

Another inherent weakness with these logic problems is that the candidate is very likely to just jam up. They start thinking, and they're afraid to express ideas and tell you what they think. They can't make progress without hints, and those hints have to be really close to give aways just because of the nature of the problem.

So, what does the interviewer do? Pose the question and wait through five minutes of awkward silence, and then give up? During that time, he's learned nothing about the candidate. The candidate hasn't learned anything about the job, either.

We don't ask those questions where I work. Instead, we ask questions that have multiple possible solutions, and we talk over the possibilities. If the candidate comes up with a decent but simple solution, weask questions to make it more complicated. We ask questions to try and figure out where they break. If they have some resiliency, and so on.

Arguably, moving Mt Fuji is such a question. The real answer is: you can't. So, you either say: "LOL, you can't" and stick with it, or you talk about alternatives to actually moving it. Why do you want it moved, and how could we realize the same net effect? Realistically, some jobs are about convincing people not to do the wrong things.

But I still think it's too abstract to tell us much about the candidate. Other companies don't hold this opinion, and they end up hiring a bunch of riddle writers.