Here is the interview question prompt, presented for reference.
Hey there, welcome to the challenges portion of the AlgoDaily technical interview course! Over the next few days, you'll get some hands-on experience with the essential data structures and algorithms that will help you nail your interview, and land your dream software engineering job.
The only way to get better at solving these problems is to power through a few.
Let's reverse a string!
We'll usually start with a simple prompt, as you would in a regular technical interview. Like most, this one will be intentionally open-ended.
Can you write a function that reverses an inputted string without using the built-in Array#reverse method?
Let's look at some examples. So, calling:
reverseString("jake") should return
reverseString("reverseastring") should return
O(n)time complexity and
You can see the full challenge with visuals at this link.
Challenges • Asked over 1 year ago by Anonymous
This is the main discussion thread generated for Reverse A String.
I encountered an issue running Java code on the platform that may need checking to allow learners just focus on the tasks at hand
Error: Main method not found in class Main, please define the main method as:
public static void main(String args)
or a JavaFX application class must extend javafx.application.Application
Hey Stanslaus Odhiambo,
It's a common confusion with Java that we're working on solving. For now, there are two differences:
1) To execute "Run Tests", the
main method needs to be commented out. This is because we wrap the user's input with our own class and run our own
2) With "Run Code", the
main method must be kept, because the execution environment is different.
I'm working with the team to solve for this, as it's not a great UX -- but hopefully that clears it up.
Thanks Jake for the clarification
In an interview setting does the one line solution "return str[::-1]" suffice in python syntax or is the best code solution to showcase using the two pointer technique?
I also have another question on the solution provided for this problem using the Two-Pointer Method. I dont really understand what the two lines are for using temp:
temp = StrList[Pointer1]
strList[Pointer2] = temp
I am unclear of what these two lines actually do. I understand the purpose of the two pointers where they are basically just flip-flopping locations in the array, but im not 100% sure what the two lines using temp really does?
I typically advise folks interviewing to actually mention that there's a built in method. Interviewers will almost surely never allow it as the final answer, but it demonstrates mastery of the language - e.g. "I'm going to implement this from scratch, but wanted to call out that we can just call the [::-1] or reverse() method, which would be the way to do it in production."
The two lines outlined are just doing a swap. Using the two pointer method doesn't necessitate swapping, sometimes you just have two pointers that track two different things (no flip-flopping locations happens, it's literally two variables/references). However, in this case specifically, we do an in-place swap in order to achieve a new string value.
something that stuck out for me: since string is immutable, it is not possible to achieve better than O(n) space complexity
Since appending to a string is O(N), wouldn't appending to a string with the two pointer approach of swapping still be quadratic time?
That nuance is correct. Appending to a string can be
O(n) depending on the implementation-- related to the above comment. Instead of appending directly to a mutable string, you can also keep an ArrayList/dynamic array that you append to-- in that case, worst time complexity is
O(n) but amortized, average complexity is
It's good to mention this during implementation!