“Is reversing a string in JavaScript using an iterator for better efficiency?”
Had a job interview today where I was asked to reverse a string in plain JS. The interviewer’s solution was to use the iterator from the last character to the first one.
Though I argued both methods had O(n) complexity, am I wrong in not considering her solution more efficient? #JavaScriptInterview #StringReversal #Efficiency
I think what the interviewer meant is that you could have reversed the string backwards (basically have a loop that counts down) and, therefore, only needed one loop. Your solution essentially iterates the string twice when it can be done with one.
Something like this:
let name = “xyz”;
let result = “”;
for (let i = name.length – 1; i >= 0; i–) {
result += name.charAt(i);
}
console.log({result});
Yes, it should be somewhat more efficient to iterate directly over the characters in the original string instead of first copying them to a separate list.
Even though both solutions are O(n), that only tells you the asymptotic “order” of how the running time grows, and not the real-world constant factors. Your solution is doing more work, and also creating an extra data structure which means the GC has to do more work to clean up after it.
In a big O sense, no, it’s not more efficient. In a time spent, it probably is less efficient.
In particular, you could have gone through the array backwards
let result = “”;
for (let i = name.length – 1; i >= 0; i–) {
result = result.concat(xxx);
}
where xxx is the character at position/index i.
> I said that that was certainly a way to do it, but it’s basically similar because both solutions have O(n) time and space complexity
for i in range(n):
print(i)
and
for i in range(n):
time.sleep(10)
print(i)
Are also both O(n)
I think you didn’t say anything wrong. You explained that they have a similar complexity. This is wrong. Sadly you didn’t notice that her solution is more efficient in a realistic way, as other comments pointed out. If you are applying for a junior position, perhaps one of your first, it probably isn’t a huge issue but could be decisive.
What I would do, depending on the company, is to send an email to the interviewer and tell them you researched the algorithms and found that the popular solution is more efficient. I can’t tell you if this is the right way to go since I wasn’t there. I would appreciate this because in that moment you showed you are able to learn and that makes you valuable.
Sorry, but yes, the interviewer’s solution is both more efficient and cleaner:
1. You’re needlessly utilizing an entire separate data structure – a pseudo-stack – instead of simply reversing the string in place or in a single other variable.
2. You’re using `String.charAt(index)`, rather than `String[index]`. Why? Using an older, outdated method without reason here would make me concerned about your knowledge of modern JavaScript.
3. For that matter, why are `stack`, ~~i~~ , and `c` all `let`s and not `const`s? They’re not reassigned. (nevermind, not `i`. Not sure why I thought that would work!)
4. You run your loop twice, which is already bad, but you’re also inexplicably using `Array.concat()` rather than something like `Array.unshift()`. Both methods are bad choices for this question, but concat is designed to combine arrays, not individual values.
5. You reference `name.length` twice, and yet don’t abstract it to a variable (frankly, I’d use a destructuring statement here). Why?
6. Finally, you return the result in an object. Was this part of the original question? If not, it’s not helpful.
As you are learning, time and space complexity aren’t everything. Although Big O says n/2, 2n, and 999999999n are all O(n), they’re different in real life. You can omit one loop from your code as well as the stack, saving both time and space.
There’s no denying that their solution is more efficient. I tried benchmarking and their solution is 2x the speed of yours on that short string and 1.5x the speed on a longer string. But maybe more importantly, it’s cleaner, shorter, and easier.
The main efficiency problem here is repeatedly calling “result.concat”. This creates new strings over and over again, and every time you do it, you need to traverse the whole string.
Say that the string had a billion letters. To add the last five letters with “result.concat”, we’d need to iterate over nearly a billion letters five times. That’s no good. So let’s say instead that you replaced that second for loop with stack.reverse().join(). Now we’re back in linear time.
“Efficient” is a funny word. Sometimes in interviews it means “complexity.” Your solution, and the solution they probably meant, have equal complexity: O(N). In that sense, they are the same. However, your solution might take longer because you need to reverse the list. If you create the array from back to front from the get-go, you get to skip a step. That’s probably going to be a faster solution, which makes it more efficient, but more more complex.
I wish you luck, but your solution is not O(n), it’s O(n log n), because of the `concat`, which is log n in js, and you do it n times (where n is name.length). You are also using extra unneeded memory (the stack), instead of simply iterating from right to left. I assume your interviewer was looking for something smarter, like using a list and join or at least some use of map/reduce/filter (ex: `name.split””.reduce((x, y) => y + x)`). Don’t worry, that’s how you learn for the future. 🙂
In the future you could just ask your interviewer? “Can you explain why your solution is better? It seems to me they have similar complexity.”
Showing eagerness to learn from a senior developer rather than trying to defend your initial position will really help how you come off in interviews.
var newString = string.reverse(myString);
Basically you’re both wrong here 🤣
These interview questions are dumb as fuck. This is like freshman homework in the first semester. How does this determine if you are fit for a job or not? Geez
Big O notation is an indicator to measure performance, but it’s not everything. If you actually calculate the amount of operations (let’s assume accessing a character of a String is 1, adding an element to a list is 1, reading an element from the start and end of a list is 1 and concatenating a character to a String as 1. Let’s additionally assume the cost for creating a List or String is 5 and incrementing the loop variable is 1), your implementation executes 6n+10 operations. The solution proposed by your interviewer executes 3n+5 operations. That’s exactly half and while this may not matter for big O notation, it does matter in real life. If you execute this function over and over again, your implementation is going to take almost twice as long as your interviewer’s, that’s electricity wasted and increased waiting times for doing useless work. As for space requirements: In the worst case, you’re storing the input String, the list of characters and the output String. This amounts to 3n if you put aside the constant part. In the best case, your solution needs to store both the input and the full list or the full list and the output. This amounts to 2n. Your interviewer’s solution always needs at most 2n.
So your solution takes about twice as long and needs up to 50% more memory. While this may not be obvious for you as a beginner, filling up memory with data you don’t need can lead to data you might need later on being deleted by the garbage collector. If that data had stayed in memory, access would have been fast, but if it has to be loaded from slower storage first, the whole program might have to wait quite a while for that process to complete. So yes, your interviewer’s solution is more efficient than yours.
The wording “certainly a way to do it” would probably rub some of my former colleagues the wrong way if it came from a junior hire. It might have been good to concede that they gave a more straightforward solution.
complexity != efficiency
There are a lot of good answers here – and also a few misunderstandings.
Your solution is fine – it treats the original string as an array, creates a stack of said array, and then builds a new string by continuously popping from that stack.
The “inefficiency” can be in time-complexity, where you iterate through the characters twice, and it could maybe be done just once. Meaning you have O(2n).
Or it could be in space-complexity, where you introduce a third datastructure – the stack – rather than just the input and output. Meaning you also have O(2n) in space, where you could have O(n). (If the original input was an array, and you were asked to reverse ‘in-place’ it could be done in O(1) space, but not for strings).
Of course, O(2n) is formally the same as O(n), but in real life it really does require twice the time and memory, so it is always a good thing to be aware of and understand!
All the fancy built-in functions, like .reverse! or split, join, concat, reduce, map, filter, etc. doesn’t impact the big-O complexity, as much as they just hide it. But they do show knowledge of an API, so it is always fine to suggest just using one/some of those, but also show your own implementation to show that you know how to program in addition to knowing the API.
Don’t make assumptions about the performance or complexity of the built-in functions! If you do, think that every .split, .concat, .join, .reverse, .map, etc takes at least O(n), and if you chain them together, they’ll probably add up. But in reality you don’t know – unless of course, you are applying for a job in improving the compiler 🙂
You’re doing a pointless data conversion of a string to array to a string. Under the hood they’re not all that different in JS anyway, but it is worse. Yes, both O(n), but your way is inferior. The counting down is only relevant because it enables the least data transformations. They didn’t explain well, but they were correct.