What is the proper way to approach a competitive coding problem?

Question

***Climbing Stairs Problem: https://leetcode.com/problems/climbing-stairs/

1) Take the "***Climbing Stairs" Problem for instance: If I was given a problem like this on a test after mastering "Fibbionacci Series" and "Factorial Implementation", I would not be able to solve it, despite the fact that "Climbing Stairs" problem boils down to "Fibbionacci Series"; I would not know that it resembles the Fibbionacci Series until I actually solve the first 6 OR MORE instances of this problem, by hand (before recognizing the (Fibbionacci) pattern).

Problem with solving things manually: I personally think that for some problems (other than those, that are similar to the "Climbing Stairs" problem), it only feels like you have found a pattern, but in reality, that is the case only for the first couple instances; and as you continue to solve the following instances, you will realize that there is no pattern or it is a completely different pattern. So, how is solving problems manually, by hand, to find patterns ideal?

2) Now, lets take the "Bubble Sort" Algorithm for instance: In order to understand that one iteration is not enough, you have to manually solve it. How do you even get the idea of sorting things this way? I would never be able to come up with an idea like "Bubble Sort" on my own.

So my question essentially is:

1. How do you deal with situations where you are given a problem which you have never seen before?
2. To what extent does practice help? I thought that in Computer Science/FAANG people started refraining from giving students/interviewees "Tricky" programming questions where, once you get to know the solution (logic part), you go "ohhhh, I get it now".
3. In what situations is it ideal to manually solve instances (iterations) to find a pattern or to see if the logic actually works that way you think it works?
4. And in what situations is it ideal to let the computer solve everything? (For instance, in the "Climbing Stairs" problem: letting the computer figure out everything instead of telling it the pattern that we found, like everyone else is doing on the leetcode platform).

Answer 1

1. How do you deal with situations where you are given a problem which you have never seen before?

You sit down with a pen and a paper and draw out examples and counter-examples. Then you recognize patterns. There are many algorithmic techniques that you can use or try first. Does greedy work? Does the problem have nice non-overlapping subproblems, does divide and conquer work? Does the problem have somewhat less nice overlapping subproblems, can you do dynamic programming on the subproblems? Is it a matching-type problem?

Furthermore, you have a bunch of algorithms available, such as

• linear search, binary search, sorting
• sliding window, prefix sum
• path finding (weighted, unweighted, with or without negative weights, with or without negative cycles)
• minimum spanning tree
• network flow
• brute force (subsets, permutations)

and also a bunch of data structures

• lists, stacks, queues,
• trees, graphs,
• tries
• segment trees, sqrt decomposition
• hash maps, hash sets, skip lists
• union-find

All of this, and more, you will learn in a couple of algorithms classes.

2. To what extent does practice help? I thought that in Computer Science/FAANG people started refraining from giving students/interviewees "Tricky" programming questions where, once you get to know the solution (logic part), you go "ohhhh, I get it now".

Practice helps a lot. If you want to learn, for example, dynamic programming, I believe that most students need to do tens if not hundreds of exercises on dynamic programming. Only then they start seeing it. When you get dynamic programming, very many problems go from impossible to doable.

3. In what situations is it ideal to manually solve instances (iterations) to find a pattern or to see if the logic actually works that way you think it works?

I'd say this is an integral part of solving a problem. The way you usually come up with algorithms is by coming up with a stupid idea, and then find an instance where it fails. Now you must ask yourself: why does it fail? Then you need to fix it.

Many, but not all, problems can be solved in this incremental manner, by coming up with a sequence of algorithms that solve larger and larger parts of the problem.

4. And in what situations is it ideal to let the computer solve everything? (For instance, in the "Climbing Stairs" problem: letting the computer figure out everything instead of telling it the pattern that we found, like everyone else is doing on the leetcode platform).

In the climbing stairs problem, an experienced algorithmician will immediately realize that the solution for $n$ only depends on the solution for $n-1$ and $n-2$, hence they will simply write down the equation $f(n) = f(n-1) + f(n-2)$. Most will immediately recognize this as Fibonacci, and then the actual algorithm is trivial, e.g.

def f(n):
    stairs = [1, 1]
    for i in range(2, n):
        stairs.append(stairs[i - 1] + stairs[i - 2])
    return stairs[-1]