# Just had my first interview!

My background - I am two projects away from having all 3 freeCodeCamp certifications. I’ve contributed to other projects on the side, and I’ve become proficient in angular and react… and Node. For some reason I’m having issues getting interviews… but I’m still trying, and hopefully a nonprofit project will help my resume to get past HR filters. I think part of the problem is location (I just moved to Seattle, WA because there is lots of opportunity here. Unfortunately most employers here seem to fill roles by bringing in devs from around the world instead of bothering to train junior level devs)…

I had my first interview with a company in downtown Seattle yesterday, and it went fairly well. It was not a whiteboard interview – I was allowed to use my own laptop and environment. I shared my screen with the two interviewers on a go2meeting call. They asked me to solve the palindrome algorithm (basically exactly as it is in the basic algorithms here). I wrote a working solution in under a minute and felt really good about myself. That’s when the interviewer asked me to make it more efficient… my heart sank and the nerves kicked in. I spent the next 45 minutes getting hints from him until I finally arrived at a far more performant solution than even the advanced solution here in the FCC forums. After I finally got the best solution, I was to implement it into an angular2 app. That took me about 5 minutes thanks to the angular CLI. The interviewer said I did exceptional at the angular part, but I didn’t perform well enough on the algorithm.

I replaced the advanced solution on FCC to my final (and I believe most performant possible) solution –

Why is this solution so much better? Because the compiler doesn’t look at and operate on the whole string seven times over before deciding it’s not a palindrome. As the interviewer called it - the “Cyclomatic Complexity” is too high.

The basic solution:

``````-Iterates through the whole string to perform - toLowerCase(), replace(), split(), reverse(), join()

-Finally, iterates the entirety of both strings again to compare them.
``````

The performant solution:

``````-Only needs to go through the string once at the most

-Is able to determine if something is not a palindrome before even iterating over the whole string a first time
``````
``````//this solution performs at minimum 7x better, at maximum infinitely better.
//read the explanation for the reason why. I just failed this in an interview.
function palindrome(str) {
//assign a front and a back pointer
let front = 0
let back = str.length - 1

//back and front pointers won't always meet in the middle, so use (back > front)
while (back > front) {
//increments front pointer if current character doesn't meet criteria
if ( str[front].match(/[\W_]/) ) {
front++
continue
}
//decrements back pointer if current character doesn't meet criteria
if ( str[back].match(/[\W_]/) ) {
back--
continue
}
//finally does the comparison on the current character
if ( str[front].toLowerCase() !== str[back].toLowerCase() ) return false
front++
back--
}

//if the whole string has been compared without returning false, it's a palindrome!
return true

}
``````
17 Likes

Don’t worry, I think you did good impression anyway. It shouldn’t be about what you already know but what you’re capable of learning. If the company expect from Junior Developers to perform as good as Senior Developers then it might be not a good place to work with.

Anyway I cross my fingers for you! Don’t lose hope! As long as you keep trying you’re the winner.

3 Likes

Can’t answer your tech question because I am too noob in coding, yet But congrats for aiming big. My plan for getting Dev Job is to simply start with a paid internship (many opportunities in my country) and then luckily get a desired job Don’t give up and remember that you know things that 3/4 of population doesn’t and can do what approximately a half of them couldn’t do anyway.

1 Like

Interestingly, that performant algorithm is how you’d do it by eye.

2 Likes

Well, you tried, and for what it’s worth I probably would have done the same as you (except I don’t know how to set up an Angular project). My solution to the palindrome function has always been a simple one-liner, but it does iterate over the whole string. I guess that might matter if the company regularly checks to see if entire textbooks are palindromes.

Thanks a lot for sharing! These sorts of experiences really help out the community.

3 Likes

Yup… because it would be taxing for a 4.2Ghz, 16GB 8-core computer to go over a tiny short string multiple times…

Personally, I would have done the one-liner tolowercase, reverse, etc. solution also. It’s clearer in its intent.

2 Likes

Yeah, I definitely agree in the real world the one liner would be sufficient, but I think the interviewer wanted me just to demonstrate my ability to think outside the box to make it better, which I failed to do . It should have been easy… After working on it for 45 minutes and then finally getting it, it seemed so obvious. Ah well, now that I know what to expect, I think I can conquer my nerves on the next interview!

I believe the performant solution is like the one I did with a for loop instead of a while loop.

``````function palindrome(str) {
str = str.replace(/_|\W/g,'').toLowerCase();
for (var i=0;i<=(str.length-1)/2;i++) if (str[i] !== str[str.length-1-i]) return false;
return true;
}
``````
1 Like

Now that is VERY interesting. That was the direction I was going when he asked me to improve it, actually my second answer looked almost exactly like @rmdawson71 's… and he told me that it still shouldn’t iterate over the whole string if it doesn’t need to. I’m going to try benchmark testing myself, and I may send my interviewer an email with the results, and shamelessly ask for another opportunity. haha. What’s the worst that could happen

His requirement was that he wanted it to perform fast if he passed the Holy Bible in as the string argument. Ultimately I’ll test that, which is apparently approx. 4,000,000 characters… and see what happens.

I made an app that let’s you run the tests and compare them side-by-side:
https://palindrome-benchmark-tests.herokuapp.com/#

It looks to me like options 2 and 3 both have trade-offs, and I’m not sure we could even call one better than the other… but if you added up the total time of all the tests, option 2 definitely wins That’s a really good catch Marko, thanks for doing all those tests too. I used the performance.now() function for benchmarking, because it’s accurate in microseconds… (just learned about it actually, this was my first time doing any performance testing)

2 Likes

I am not sure about the behind-the-scenes mechanics of str.replace, but I assume it is iterating over the entire string, so I suppose by me adding the str.replace at the beginning of my solution, it adds an extra iteration before starting comparisons.

Also, you can shrink the third solution by 2 lines (removing front++ and back–) by using:

``````if ( str[front++].toLowerCase() !== str[back--].toLowerCase() ) return false;
``````

When I did the algorithm lesson, by default I did something exactly like option 2. If someone had asked me to do it by chaining native functions, I might’ve been a bit stuck because I don’t have those stuff memorized. In fact, I thought my answer was inadequate because it wasn’t concise enough. Everyone has some doubts about their code I guess.

I have a feeling that if someone had presented option 2 at the interview, he would have asked them to do both a concise solution (option 1) and/or ask them to make it even faster in a ‘false’ scenario (option 3). They just want to see the interviewee’s thought process through a problem.

That said I think he was also testing your knowledge of basic computer science concepts. The idea that a function should stop immediately once it finds its solution, and that it should do as little calculation as possible to get there, is one of the very first concepts they’ll teach you at a university.

I don’t mean to be harsh, but when CS students tell self-taught developers “You don’t know what you’re missing” this might be the kind of thing they’re talking about. I’m not saying you know less than a college freshman, but it’s more like, your learning might’ve been a bit reversed. A college freshman looking to major in CS wouldn’t be able to make apps like you, but you have to wonder what they were learning from their introductory CS courses.

The good news is that there actually are free online courses/resources that teach you these things and since you’re already that far in FCC (which is very impressive btw, not many have the dedication to make it that far), the concepts should be much easier to grasp. It could be as simple as googling the right terms. For example, (“big O notation” for algorithm complexity).

Anyway, if you’re looking for the next thing to learn, I definitely recommend looking into computer science instead of just web development.

And to emphasize, I don’t mean to discourage you from your job search at all. I mention these things because you quite clearly still have that drive to learn.

1 Like

Thanks for that input! I definitely agree with everything you said. The interviewer asked me if I knew what cyclomatic complexity was, and my answer was of course, no. And at the end of the interview, he gave me a piece of advise – “never start writing a for loop unless you know the exit criteria” … I definitely missed all the wise advise without a CS degree

Maybe I’m missing something, but isn’t a for( ) loop’s exit criteria is the ending index number? for i=1 to 10 for example, when 10 is reach, it’s the end of the loop.

Not unless he meant a do { } while(cond) loop, or a while(cond){ } loop?

Ah yes, my bad. He didn’t say for loop I miswrote that, I think he just was talking about loops in general, because it can make sense to have a different exit condition in a for loop… but he may have been talking about specifically a while loop (which was the type of loop that he preferred for the solution).

Am I the only one here thinking it was a “human” thing and not the “problem” thing?
Were you interviewed by a standard-series computer with standard, emotion-less programming that was standardized over a 100 years ago? Probably not. In that case:

Umm… maybe interviewer didn’t like your shoes? And your solution wasn’t the problem there?

I’ve been on over 5 technical programming interviews so far and I noticed that it isn’t always your solution (or lack of thereof) that is lacking. Humans tend to hire people with good “communication skills” over anyone else. In other words, if you’re funny and well-mannered, you often get a better chance to get hired over “very smart people who can’t work in a team”. It is justified, to a degree - no large-scale program can be made within reasonable time frame by a single person.

As for solutions discussed: magnificent. There are a few bits that can be changed here and there (I, for one, prefer to write anything that is used more than once into a variable… like that regexp) but overall it is very creative. And very complex - it takes time to read and realize what it does. A lot of people (me included) prefer a different coding style - where you can get what it does in a moment. With classic palindrome solution you can tell at a glance, but it takes a while to understand the “performant” solution. This works well everywhere where performance is not top-class priority, and where it is, you’re more likely to be using C++ over Javascript.

Also I find it curious everyone talks about “enhancing” a solution but nobody asked the main question: what exactly should be enhanced, what is the goal? A lot of people simply forget it and start doing work without knowing where they want to end up, just my personal observation.

As always, no offence meant, just sharing my point of view.

2 Likes

I think the main focus was how many loops you take.
Since you are going the whole loop it will take O(n) while converting the lower case first then reversing will take two extra loop. So the computer is doing extra work and also for front++ and back-- the loop will take n/2 time

Thank you for sharing your story! This is something I feel like many people who are using FCC need to read. You should probably take CS courses on Coursera and Udacity. Palindrome detection is usually covered in an intro CS course because it’s a good example of recursion. I recommend Stanford’s free version of their algorithms courses. Tim Roughgarden is one of the best CS professors out there, and you can use any language you want in his class (this is a slight weakness though, since you don’t learn much about the performance of your language in particular).

Rob Sedgewick teaches the Princeton courses on algorithms and data structures on Coursera, and is also great. He teaches his course in Java, and you’ll get a lot more information about how implementation details impact data structure performance, but it won’t always translate very well into performance boosts in Javascript. It is a really good series to at least watch though. It’ll make the Standford courses easier.

Even if you get a job before you complete the courses, or even start them, keep going / take them anyway! Algorithms are a huge part of CS, and Read-Search-Ask is significantly less effective if you don’t know what to read, search, or ask for in the first place (i.e. asking about implementations of binary search trees will make it a lot easier to solve a 1D nearest neighbor problem, as opposed to starting with a less efficient method and asking how to make it work). Good luck with your job search!

2 Likes

This seems like a popular thing. I was asked the exact same question, with the exact same sequence of events (I solved it, then the interviewer asked for a better one, and walked me to this solution), but it was for an internship. I would say this interview question and solution should be something every dev is familiar with.

1 Like

I used to live in Seattle and I found it to be one of the hardest places to find a job in development at the entry or junior level. If you are already familiar with Angular, React and Node, you are definitely employable.

I think that you shouldn’t try to find a job IN Seattle. Look for jobs on a site that specializes in Remote Workers and Freelancer like Guru, Remotive, We Work Remote, Remote.co, Jobspresso, Remote OK, Working Nomads, etc.

I also think that you should use the Front-End Developer Handbook 2017 and all of it’s resources.

I would also set up a USB Drive that has everything loaded that you would need to actually work on a real project. That way, instead of using a computer you are not used to, you can plug it in to any computer and have everything you need right there.

I actually created this and then tested it out in job interviews. What happened was that the interviewers were very impressed with my ingenuity and problem solving, which is one of the strongest factors in hiring.

I did a lot of actual interviews for my own practice, and I would say that I was actually offered the job by doing this, more than half of all my interviews. I freelance and don’t actually want a “real job”. I just do interviews for fun and to tell how successful I WOULD BE if I actually tried to find a job.

I hope this helps you and good luck in your job search!

6 Likes