JavaScript Algorithms and Data Structures Masterclass
by Colt Steele
Section 4 Problem solving strategies
What is an Algorithm?
- A process or set of steps to solve problems(accomplish a certain task).
- It's foundation for being a successful problem solving and developer.
- It is important part of INTERVIEWs!!!!!
How do you improve?
- Devise a plan for solving problems.
- Master common problem solving patterns.
[Problem solving strategies]
hardest thing is solving a new problem!
1. understand the problem
2. explore concrete examples
3. break it down
4. solve/simplify
5. look back and refactor
- understand the problem
1. can you restate the problem in my own words?
2. What are inputs of the problem?
3. What are ouputs of the problem solution?
4. Do you have enoungh infomation(input) to solve the problem?
== can the ouput be determined from the input?
most of the case, Yes!
but in this case, we don't know how large numbers would be -> than ask more infomations.
5. How should I label the important pieces of data that are part of the problem?
ex) Write a funtion thar takes 2 numbers and return their sum.
get 2 num, add both and return.
2 numbers but what if they would input really large long numbers?
int or float? String for large numbers?
also, what if they would add really large number? use String instead of int? float?
- explore concrete examples
coming up with examples can help you understand the problem better.
examples also provide sanity checks that you eventual solution works how it should.
User Stories! Unit tests!
1. start with simple examples.
2. progress to more complex.
3. explore examples with empty inputs.
4. explore examples with invalid inputs.
ex) write a funtion which takes in a String and returns counts of each character.
charCount("aaaa"); // {a:4}
charCount("hello");// {h:1, e:1, l:2, o:1}
"My phone number is 10101010."
//are we gonna count spacing? numbers? how abaut uppercans and lowecase?
charCount(" "); //what if they put empty input?
charCount(null); //what if they put invalid input?
- break it down
1. write down the step you need to take.
2. write down basic components of the problem.
-> it makes you THINK!!
-> catch conceptual issues or misunderstandings before you dive in.
-> help to avoid language mistakes
ex) write a funtion which takes in a String and returns counts of each character.
function charCount(str){
//do something //make obj to return at end
//loop over String, for each character..
//if the char is a number/letter AND is a key in obj, add one to count
//if the char is a number/letter AND not in obj, add it to obj and set value to 1
//if character is something else (space, period, etc.) don't do anything
//return obj at end
}
- solve/simplify
solve the problem if you can't .. SOLVE A SIMPLER PROBLEM!
instead of stucking one problem and making zero progress, it is much better start the part you can solve.
AND you probably will get some idea while you are aproaching simple one.
//simplify
: find the core difficulty in what you're trying to do
: temporarily ignore that difficulty
: write a simplified solution first! aka worte down something at least (BRAINSTORMING)
: Then, re-back to the difficulty!
ex) write a funtion which takes in a String and returns counts of each character.
function charCount(str){
//do something //make obj to return at end
var result ={};
//loop over String, for each character..
for(var i=0;i<str.length;i++){
var char=str[i];
//if the char is a number/letter AND is a key in obj, add one to count
if(result[char]>0 && result[char]!==" "){
result [char]++;
}
//if the char is a number/letter AND not in obj, add it to obj and set value to 1
else{
result[char]=1;
};
}
//if character is something else (space, period, etc.) don't do anything
//return obj at end
return result;
}
if this was coding test of the actual job interview, you are almost there.
you can politly ask to interviewer that how they would aproach upper-lowercase or space.
ask their opinions.
MOST IMPORTANT THING: WRITE SOMETHING!!!!! START EASY ONE!!!!
- look back and refactor
try improve your code.
look at the indivisual components line by line,
talk about the parts you don't like or what do you not like about,
how the code itself looks,
how it read,
how easy it is to understand.
//refactoring questions
: can you check the result
: can you derive the result differently
: can you understand it easily
: can you use the result or method for other problems -> it's process of building your own develope sence
: can you improve perfomance of the solution
: can you think it other way
: how other people solved the problem
//code review, googling,
-> Build your own DataBase, tho It will takes sometime.
ex)write a funtion which takes in a String and returns counts of each character.
ver1) simplify
function charCount(str){
var obj={};
for(var i=0; i<str.length; i++){
var char=str[i].toLowerCase();
if(/[a-z0-9]/.test(char)){
if (obj[char]>0){
obj[char]++;
}else{
obj[char]=1;
};
}
}
return obj;
}
ver2) more simplify
function charCount(str){
var obj={};
for(var char of str){
char=char.toLowerCase();
if(/[a-z0-9]/.test(char)){
if (obj[char]>0){
obj[char]++;
}else{
obj[char]=1;
};
}
}
return obj;
}
ver3) even more simplify
function charCount(str){
var obj={};
for(var char of str){
char=char.toLowerCase();
if(/[a-z0-9]/.test(char)){
obj[char]= ++obj[char] || 1;
}
}
return obj;
}
ver4) you can use charCode too // this is more efficient way to search alphanumeric.
charCodeAt(0);
47 < numeric 0-9 < 58
64 < uppercase < 91
96 < lowercase < 123
function charCount(str){
var obj ={};
for(var char of str){
if (isAlphaNumeric(char)){
char=char.toLowerCase();
obj[char]=++obj[char]||1;
}
}
return obj;
}
function isAlphaNumeric(char){
var code = char.charCodeAt(0);
if(!(code > 47 && code < 58) &&
!(code > 64 && code < 91) &&
!(code > 96 && code < 123)) {
return false;
}
return true;
}
-> INTERVIEW!!!!!
start with understanding the problem
exploring examples one in two, do it out loud.
make sure the interviewer hears you bring them into the process.
tell them what you are doing. breaking it down. write down. talk out loud.
And SOLVE IT!!!
look back and refactor if you can.