When looking for a tech job you are probably spending some time practicing writing algorithms (on LeetCode or HackerRank or some site like that).
Writing a good algorithm often comes down to two parts.
1) writing the code (this one is obvious)
2) being aware of it's order of complexity (less obvious)
In an ideal world you'll write code that's quick, doesn't use a lot of resources, and solves the problem. But these problems you are attempting to solve are tricky. Sometimes that solution has lots of edge cases you need to take into account. And sometimes these problems lend themselves to solutions that eat up resources and are complex. Maybe O(n^2) or O(n^3) or even O(2^n) - for more on what those O's mean, read the answers to this stack overflow question.
I just want to talk, very quickly about being aware before you even start the problem that it is going to lead to a large order of complexity.
Fibonacci
The classic example of a problem that leads to a very high complexity solution is a function that takes a number and returns the Fibonacci number that you get in that position.
The Fibonacci Sequence is a sequence of numbers that equals the total of the previous two numbers in the sequence, with the sequence beginning with 0,1. So F(2) is F(0) + F(1) which equals 1. Then F(3) = F(2) + (F1) which equals 1 as well. But after that is starts expanding. The early part of that sequence is 0,1,1,2,3,5,8...
Here is a simple looking recursive function that determines the fibonacci number at the place in the sequence that is provided:
function fib(n) {
if ( n === 0 || n === 1) {
return n
} else {
return fib(n-1) + fib(n - 2)
}
}
This is a solution you might come up with if you aren't worried about complexity. But the complexity of this solution is O(2^n). That is an exponential time which is way too complex. Large numbers will become untenable for this function.
Take a look at that function. Every time you call it, it COULD call the function twice more. That's a signal that it could get out of control really fast. So you should begin thinking about a better solution. One that is not as short and neat, but will avoid the terrible run time this function creates.
Ideally you don't want your function to be called more than once for every element it checks. In this case, if I send a 10 in, I don't want the function run more than 10 times. (in this case it will run over 100 times!). So you need to start thinking of a better solution.
This blog entry is not about a better solution, but if you are curious about seeing a better way to solve this problem I'd recommend this video.
Searching for Anagrams
So the other day I was practicing algorithms on LeetCode and I had a problem that asked me to accept a string, and return the longest palindromic substring within it.
My first thought was this pseudo code:
//Accept a string s of n characters
//check if s[0] is an anagram
//Then check if s[0] + s[1] is an anagram
//continue checking until s[0]+s[1]+...s[n]
//then check s[1] and follow the same track until I check:
//s[1]+s[2]+...s[n]
//keep doing that until I check s[n]
That's a surefire way to be certain I check every possible substring of s. But my memory of that Fibonacci problem started getting triggered. For a string of length n I need to check n different substrings, plus n-1 substrings, plus n-2 substrings.... uh oh. That starting to sound real bad. If you have to run through an array (or a string in this case) more than once for every element (or character) you are getting to a bad place.
Turns out that solution is O(n^3) which isn't as bad as my bad fibonacci solution but it isn't great. (a string of 10 characters would loop through 55 times. A string of 11 would run 66 times. etc)
So right away, if you want to solve this problem, you should be aware that you are heading towards a high complexity.
If you are doing this in an interview, you might just want to give the answer you can think of. I would! But if you are aware of that complexity you can speak to that. Maybe you can solve it a better way once you get this inefficient way written out. Maybe you can't - but for some interviewers seeing that the person they are talking is aware of the issue is a huge step forward.
Yeah, but what's the solution?
Again - I wrote this blog post just to talk about the idea of identifying the problem, not solving it. I really do think identifying the problem is a huge step. The easier you can see that problem the more time you have to think of alternatives. Simply recognizing the complexity quickly shows a comprehension interviewers should value.
But you want an answer. I get it. So did I. And I couldn't figure out how to solve this efficiently on my own. But after some reading I did find a solution. I'll present my version of it here:
var longestPalindrome = function(s) {
if (s.length <= 1) return s;
let start = 0
let maxLen = 0
for (let i = 0; i < s.length; i++) {
const len1 = expandSearch(s, i, i);
const len2 = expandSearch(s, i, i + 1);
const len = Math.max(len1, len2);
if (len > maxLen) {
start = Math.ceil(i - (len-1) / 2);
maxLen = len
}
}
return s.slice(start, start + maxLen);
};
function expandSearch (s, left, right) {
let L = left,
R = right;
while (L > -1 && R < s.length) {
if (s[L] !== s[R]) break;
L--;
R++;
}
return R - L - 1;
}
What you are doing here, briefly, is taking a character (always a palindrome) and then checking on either side of it. If those characters are the same it's still a palindrome so keep checking on the next two characters around your starting spot. If it's not a palindrome stop checking. Then doing the same for two characters, because palindromes of even length have two characters in the center like hit Swedish pop band ABBA). You need to do this for every character. That's still O(n^2)... but that's better!
An even better solution is Manacher's algorithm which is a very complicated algorithm and not one I think you'd need to come up with on your own in an interview.
Top comments (0)