Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Reverse A String (Main Thread)

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.

We covered the best ways to prepare in this lesson, in this one, and here. Be sure to visit those if you need some more guidance. Otherwise, let's jump into it.

Reverse a String

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.

Prompt

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 "ekaj".

reverseString("reverseastring") should return "gnirtsaesrever".

Constraints

  • Do not use the built-in #reverse() method or [::-1] if Python
  • Ideal solution would run in O(n) time complexity and O(1) space complexity

You can see the full challenge with visuals at this link.

Challenges • Asked over 1 year ago by Anonymous

Anonymous Commented on Oct 05, 2019:

[deleted]

Jake from AlgoDaily Commented on Oct 05, 2019:

This is the main discussion thread generated for Reverse A String.

Anonymous Commented on Mar 20, 2020:

[deleted]

Anonymous Commented on Jun 16, 2020:

[deleted]

Stanslaus Odhiambo Commented on Jan 02, 2021:

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

Jake from AlgoDaily Commented on Jan 02, 2021:

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 main method.
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.

Stanslaus Odhiambo Commented on Jan 03, 2021:

Thanks Jake for the clarification

TimWong17 Commented on Jan 05, 2021:

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?

Jake from AlgoDaily Commented on Jan 05, 2021:

Hi Tim,

Great questions!

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.

supuilam Commented on Jan 05, 2021:

something that stuck out for me: since string is immutable, it is not possible to achieve better than O(n) space complexity

fanfanfan Commented on Jan 08, 2021:

Hi,

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?

Jake from AlgoDaily Commented on Jan 08, 2021:

Hi supuilam,

In Java, C#, JavaScript, Python and Go, strings are immutable, so that is correct. In Ruby, PHP, and C, strings are mutable. So it depends on the language.

Jake from AlgoDaily Commented on Jan 08, 2021:

Hi fanfanfan,

That nuance is correct. Appending to a string can be O(1) or 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 O(1).

It's good to mention this during implementation!