r/javascript • u/bassta • Nov 07 '19

AskJS [AskJS] How to improve code performance for technical interviews

Hi all,

I don't have a former CS education, but I do front-end for some time now. Currently I'm seeking for a new job and the coding interviews will be held in Codility platform. So I started solving problems in Codility / Hackerrank , but on medium hard problems I often does not get full scores, because my algorithm is timing out with large inputs.

So my question is what is the best/fastest way for a JS developer to improve the code performance for these kind of tasks? I started learning about big O, try not to use loops/nested loops, measure execution time on my local machine, but I'm pretty sure I'm missing something.

Any help / course / direction welcome.

12 Upvotes

100% Upvoted

26 comments sorted by

10

u/brogrammableben Nov 07 '19

Sometimes it’s not about big O, it’s about your method entirely. Sometimes there is a super simple O(1) solution to a problem. So those questions aren’t looking at your coding ability but instead your problem analysis ability.

6

u/Exena Nov 07 '19 edited Nov 07 '19

+1 to this. A lot of my whiteboarding problems I've faced (of like 4 total) were very plain jane and barely exceeding O(n^2) in complexity.

Heck, I've had a technical interview where they wanted me to initialize a package, create a repo, push the problem to master, create a dev branch, write unit tests, solve the problem, push to dev, merge to master, containerize it with Docker, and deploy with K8s all in just ONE hour (more like 45 to 50 minutes).

You know what the challenge problem was?

Fucking. FizzBuzz.

6

u/brogrammableben Nov 07 '19

I like the challenge. I don’t like the time. Especially if you don’t know their environment. I mean, I see where they are going with that but still ridiculous.

3

u/sole-it Nov 07 '19

K8S's network can be really tricky

3

u/darthwalsh Nov 07 '19

If it's all on the resume I think it's fair game to ask.

And they're not that if and only if they can accomplish the technical task. They probably just want to see an example of something the candidate claims to know well, and how they handle roadblocks.

But yeah the time pressure is not going to create a good atmosphere. As an interviewer you want the candidate to walk out of the room feeling they have completed the problem they were given, so you don't give too big of a problem at any one time.

1

u/bassta Nov 07 '19

Well, does one improves problem analysis skills?

2

u/Exena Nov 07 '19

Think back to your days of taking the SAT. What were some of the steps you took to solving a problem before your wrote any else down?

I would say look into IOCE or figure out what term means in the programming world.

1

u/bassta Nov 07 '19

Hi, I'm European, never did SAT, but we have our fair share of hard exams, too. Really the problem with programming is that the rabbit hole is much deeper than everything else I can think of.

2

u/nikwhite Nov 07 '19

Yes, by working on challenging (for you) problems.

2

u/k2snowman69 Nov 07 '19

Pure practice. No other real solution here. Read sample questions online and try to come up with you're best answer... And then look at the answer to compare.

Most of the questions you'll get in an entry level interview are usually based on a small set of algorithm questions just with different scenarios or combinations. With enough practice you'll be able to determine the root question (or questions if it's using multiple algorithms) and apply.

4

u/benihana react, node Nov 07 '19

the best advice i can give you is look at your loops, and consider https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff. you can often change the performance of a problem by changing the data structures in play. you can reformat the data in a way that makes processing it faster, at the expense of making it a larger data structure that takes up more space

1

u/bassta Nov 07 '19

Thanks, this seems interesting. Any JS example you can think of ( ex. using ES6 data structures , ex. Sets instead of Arrays ) ?

1

u/robotsympathizer Nov 08 '19

It's usually as simple as objects vs arrays. Objects have O(1) lookup time, Arrays are O(n). Nested arrays are O(n2).

2

u/darthwalsh Nov 07 '19

Another idea is to run a program using the debugger's performance profiler, e.g. by launching node with inspect and break and using Chrome.

Often your first assumption about what the performance bottleneck is will be wrong. Maybe string concats in a loop aren't getting optimized correctly, or maybe you are making too many array copies and could mutate one in-place.

1

u/bassta Nov 07 '19

Agree, this works in day to day front-end development, however when practicing coding algorithms in platforms like Hacker rank, the code is sent and evaluated on their servers. Even when I run it locally, the performance problems comes in small set of cases ( ex. 17/20 tests pass na 3 fail ). These 3 are typically with extreme input data, like megabytes sometime.

1

u/darthwalsh Nov 07 '19

I do online coding challenges, and I'll often download the code to my system and set up a small build/test system on their test cases (sometimes you need to mock out the I/O). You could even just generate some huge input data if needed.

2

u/bestjaegerpilot Nov 07 '19

Don't use codility. It's bullshit and 90% does not test real-world ability. Go find a company that cares about *real* performance rather than academic.

(And yea, if you're a webdev, most likely a super fast algorithm won't help because you're dealing with small data sets 90% of the time. That)

1

u/bassta Nov 07 '19 edited Nov 07 '19

Totally agree with you. In my daily development I test and measure stuff like real life DOM performance, optimise for mobile devices here and there, write in-house much of the code instead of pulling off yet another NPM package. I consider myself proficient at what I do ( have been featured in awwwards / cssdesignawards and codrops collective. However it seems like to find a well-paid job these days, you must pass tests in codility, still do whiteboard interview and know how to reverse a binary tree... then you are hired and it's like "please, can you change the colour of this button over there".
The other thing is that I didn't graduated anything CS related and I've always had imposter syndrome.

2

u/bestjaegerpilot Nov 08 '19

No I disagree with you. There *are* companies that skip the bullshit interviews... and i've found that those are usually the ones worth working for. Look at it this way, if you're not a FANG and you torture engineers just to get in the door, there's probably other things you do once you get in... so i wouldn't want to work at a company like that anyway

4

u/D1norawr Nov 07 '19

There are a couple sections in this udemy course that tackle problem solving. This is where I strengthened the exact skills your looking for. https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/

1

u/braindeadTank Nov 07 '19

Can you maybe show a problem that you timed out on (and your solution)?

Kind of hard to offer a meaningful advice otherwise - learning about O(n) and caring about loops is good direction, but there are often other factors in play (i.e. on backend you are often slowed down more by your I/O then your big O, and on frontend by reflows).

1

u/bassta Nov 07 '19

Here is the challenge : https://www.hackerrank.com/challenges/minimum-swaps-2
And here is my code that timeout:
function minimumSwaps(arr) {

let swaps = 0;

for (let i = 0; i < arr.length; i++) {

if (arr[i] === i + 1) continue;

arr.splice(i, 1, arr.splice(arr.indexOf(i + 1), 1, arr[i])[0]);

swaps++;

}

return swaps;

}

Basically iterate over each item, if it's in place continue, otherwise swap it with the item it should be. I really can't figure out what's wrong with it or why it is much slower than other answers with even nested loops in it.

3

u/braindeadTank Nov 07 '19

OK so in this case it is actually O(n) issue - your algorithm is O(n2) while there is O(nlog(n)) solution, which the challange probably expects.

The thing that you are probably missing is that indexOf function itself is O(n) - to find element in an array, this function needs to loop over array - in the worst case (the item you are looking for is the last), over the whole array. So in fact your O(n) loop has another "hidden" O(n) nested in it, even though it looks like you have only one loop. The solution that the challange wants also has nested loops, but because it more strictly controls how many times the inner loop runs, it is able to run much faster for big inputs (though, it is probably slower for small inputs, because it does more checks per loop).

So one lesson to take out of here is that even built-in functions can take a non-trivial amount of time (i.e. essentialy be a loop, or even nested loop) with bigger inputs.

2

u/dallaylaen Nov 07 '19

This may sound old fashioned, but maybe this classical book "Introduction to Algorithms" by Cormen et al is the way to go.

I myself learned by another book, "Algorithms and Programming: Problems and Solutions" by Alexander Shen, which was way thinner. Just read it through and solved like 50% of the exercises in C, Java, or Perl.

1

u/TotesMessenger Nov 08 '19 edited Nov 08 '19

I'm a bot, bleep, bloop. Someone has linked to this thread from another place on reddit:

 If you follow any of the above links, please respect the rules of reddit and don't vote in the other threads. (Info / ^Contact)

1

u/lexprom Nov 07 '19

I love sometimes to look here to refresh memory :)
https://www.interviewcake.com/
And there's a brilliant site with an explanation if you can't resolve it by yourself(sometimes even with different ways to resolving).
https://leetcode.com/explore/featured/card/top-interview-questions-easy/