On solving a prolem, you're facing a complicated challengue, some problem that is not that straight forward, this section will help you to identify how to approach complicated problems. There are a lot of strategies, blueprints or archetypes you can have in your pocket to help you solve many probles.
Objectives
- Define what an algorithm is
- Devise a plan to solve algorithms
- Compare and contrast problem solving patterns including
- Frecuency counters
- Two poiters
- Divide and conquer
What is an algorithm
Means a process or set of steps to acommplish a certan task.
Examples We could be talking about:
- A set of mathematical steps.
- Facebook's algorithm to suggest adds
- Google's algorithm for searching on the web
Something simple also can be an algorithm
- Show results in chronological order
- Calculate the first 100 numbers
Almost everything that you do in programming involves some kind of algorithm.
Devise a plan
This will show you a set of steps that can help you to solve algorithm problems, it's not a miracle but definetly it can be super helpful to know how to target the problem.
Step 1: Understand the problem
The hard problems use to be something new, even if you know perfectly the programming language it can be difficult. Many of these strategies come from sources that has helped a lot of people, books and courses that has been proved how efficient they are. Most of the cases we just want to get started as soon as we have the problem in front of us. But, before even writing a line of code it is important to understand the task ahead and also ask yourselves or the interviewer questions to open your panorama.
- Can you restate the problem in your own words?
- What are the inputs that go into the problem?
- What are the outputs expected?
- Can the outputs be determined from the inputs? That means, do you have enough information to complete the algorithm?
- How should I label the imporant pieces of data that are part of the problem?
Example
// Write a function that takes two numbers and resturn their sum
// 1. Can I restate the problem in your own words?
"Add two numbers"
// 2. What are the inputs that go into the problem?
"How big the numbers are?"
"Are you only using integers? Or it has to include floats?"
"What validations or sanitizations need to be implemented?"
"Only positive or will it include also negative numbers?"
"Do you have to apply some special rules?"
// 3. What are the outputs expected?
"What type is expected?"
"Should we round from float numbers to int?"
// 4. Can the outputs be determined from the inputs?
"Do I have all the information to complete the problem?"
// 5. How should I label the imporant pieces of data that are part of the problem?
"Are they inputs? Are they rules? Are the edge cases?"Step 2: Concrete examples
Examples also provide sanity checks so that your eventual solution. If you have those examples. you can check your work, and also thin about more information that can be ingested into your problem. With the time you'll start even to create user stories, which is pretty much given an input what should happen to provide certain output.
Step to explore examples.
- Get simple inputs, the most obvious inputs ones
- Get comples examples
- Explore empty inputs
- Explore invalid inputs
Example
// Write a function which takes a string and returns counts of each character in the string
function charCount(input){
// All the algorithm goes here
}
// 1. Simple inputs
"aaa" => { a: 3 }
"hello" => {h: 1, e: 1, l: 2, o: 1}
// 2. Complex inputs
"my phone number is 123456"
Do we want to consider spaces?
Should we only consider letters or also if they are capitalized?
// 3. Explore examples with empty inputs
" ", null, undefined
What should be the outcome? an error maybe? or null?
// 4. Explore invalid inputs
are ints supported?
What kind of inputs will or should throw errors?Step 3: Break it down
A lot of interviewers are looking for you to communicate what you're doing. It'll be much better to say and describe the steps or hints you have seen instead of silently solve the issue . We recommend writing out the steps that you need to take, it doesn't have to be with alot of details or all the lines. but it has to be the basic components or steps of your solutions. It can also help you to realize how complex is the problem and if there are more questions that you missed in previous steps
Example Write a function which takes a string and returns count of each character in the string
- The interviwer give you a rule : we are lower casing the string of input
How to break it down?
- Make an object for the output result
- Loop the string
- We need to look at each character
- We need to lower case the chars individually or the input
- Check if the char is already in the result to add to the count
- If the chat is not present in the result, add a new key and set value to one
- Return the object with the counts
We are leaving out some cleaning process like
- If the char is an empty object
- If the char is not a valid char
- If the char is valid but you don't want to count it
All those points are valid questions we may need to clarify with the interviewer
Step 4: Solve or Simplify
Some times there are one or two things you're not sure on how to do it or how to simplify it. Try to ignore the parts that are very complicated and focus on show something to yourselves.
Instead of solving 100% at the beginning is much better to write the things you now and once almost every is ready solve and simplify.
- Find the core difficulty in what you're trying to do
- Temprary ignore that complex part
- Writie a simplified solution
- Then incorporate that dificculty back in the problem
Step 5: Look back and refactor
Most people care about is efficiency when they are reading code. We may want to find a balance between performance, efficiency, legibility, and any other core priority you'd like to set in your problem or code base.
Once a problem has been solve the following questions can help you to provide a better presentation of the solution.
- Can you check the result?
- Can you derive the result differently?
- Can you understand it at a glance?
- Can you use the result or method for some other problem?
- Can you improve the performance of your solution?
- Can you think of other ways to refactor?
- How have other people solved this problem?