TestVagrant

How to approach a complex-looking programming problem?

Programming, coding
  • Blog

Blog

How to approach a complex-looking programming problem?

Solving programming problems can be complicated and overwhelming at first, but there are steps we can take to approach these complex-looking problems in a more manageable way.

The first step is to carefully read and understand the problem.

Make sure we identify –

  1. Input parameters or constraints of the problem
  2. The required output or key requirements
  3. Pattern -Try to match the given problem to the existing techniques that solve similar problems.

There are a few existing techniques that have solved most, if not all, of the programming problems. The more such techniques you know the easier it will be to match and solve a given problem. All these techniques have a general format and only a few conditions change to solve different variations of the problems.

Below are some common techniques that you must have heard of-

  1. Sliding Window — Fixed/Variable
  2. Two Pointer — Forward/backward pointer
  3. Binary Search
  4. Divide and Conquer
  5. Dynamic Programming
  6. Greedy Algorithm
  7. Backtracking
  8. Breadth-First Search (BFS) and Depth-First Search (DFS)
  9. Hashing
  10. Branch and Bound
  11. KMP Algorithm: The Knuth-Morris-Pratt (KMP) algorithm
  12. Dijkstra’s Algorithm

Then there are a few others that are less known-

  1. Union-Find
  2. Pre-sum
  3. Toposort
  4. Monostack
  5. Memoization and Tabulation
  6. Topological Sorting
  7. Bit Manipulation & Bit-masking
  8. Trie (Prefix Tree):
  9. Hill Climbing
  10. Heuristics
  11. Rolling Snowball Technique
  12. Simulated Annealing
  13. Randomized Algorithms
  14. Monte Carlo Simulation

By practicing the techniques, we can approach even the most complex programming problems with confidence and come up with effective solutions.

For demonstration, let’s try to solve the following problem –

Question — Find the longest substring that has all non-repeating characters.

Analyzing the problem

1. Input — A String (this can go as a parameter to our method)

				
					String input = "aababcdefabcdefgbebe";

2. Output — A String — This is the longest substring from the given String that has all non-repeating characters in it 

				
					String output = "abcdefg";

3. Pattern — From our problem, we see that we need to find a substring (of variable length), which is continuous and that meets a given condition(non-repeating characters)

Sliding window technique — This technique works to find continuous SubString or SubArray from a given Sting/Array with the given condition.

In this given question, we need to find the longest SubString with a condition that characters should be non-repeating. This perfectly fits the definition of the sliding window technique.

Sliding Window technique

Terminology

  1. start(left-most element of the window),
  2. end(right-most element of the window),
  3. window — There will be a window with finite size (end-start)

Solution Format

The code will probably look something like this – 

				
					while(end<length)
{
if() //condition where we get the required output and update the output variable

//for fixed size sliding window
else if() //condition where we can't get required output from out current window also condition where we move the window forward

//for variable size sliding window
else if() //condition where we can't get required output from out current window also the condition where we decrease window size by start++
}

Following is an article that lists some problems that could be solved using:

Sliding Window Technique 
https://medium.com/techie-delight/top-problems-on-sliding-window-technique-8e63f1e2b1fa

That’s how we can solve most programming problems easily if we know the above-mentioned common programming techniques and the steps that solve them.

Do follow and subscribe to receive more of such articles.

Share This Article

Other Related Articles

See More Articles
See More Articles
Scroll to Top