One of the mutual Java coding interview questions is to write a plan to opposite a String inward house inward Java, without using additional memory. You cannot purpose whatever library classes or methods similar e.g. StringBuilder to solve this problem. This restriction is placed because StringBuilder in addition to StringBuffer degree define a reverse() method which tin easily opposite the given String. Since the original objective of this enquiry is to seek the programming science in addition to coding logic of candidate, at that spot is no indicate giving him the pick to purpose the library method which tin brand this enquiry trivial. Now, how create yous solve this problem? If yous are familiar amongst array information construction in addition to hence it would last slowly for you. Since String is backed yesteryear a graphic symbol array, yous tin purpose the same inward house algorithm nosotros lead keep used to reverse an array inward place.
That technique uses the two-pointer approach where i pointer starts from the offset in addition to other pointer starts from the halt of the array. You swap elements until they meet. At that indicate inward time, your String or array is already reversed.
This is an acceptable solution because nosotros lead keep non used additional retentivity in addition to whatever library method, but yous tin too last asked to explicate nigh the fourth dimension in addition to infinite complexity of your solution.
The fourth dimension complexity of this algorithm is O(n/2) + fourth dimension taken inward swapping, which effectively adds upward to O(n) time. This way fourth dimension volition growth inward the proportion of the length of String or publish of characters on it. The infinite complexity is O(1) because nosotros are non using whatever additional retentivity to opposite the String.
Btw, String is a real pop topic on interviews in addition to yous volition ofttimes consider a span of String based coding questions on interviews. Influenza A virus subtype H5N1 proficient noesis of String along amongst other information structures similar an array, linked list, in addition to binary tree is real important. If yous experience yous lack that noesis or desire to improve it, I propose yous convey a hold off at Data Structures in addition to Algorithms: Deep Dive Using Java course on Udemy. It's both affordable in addition to real comprehensive course of written report in addition to I highly recommend it for Java programmers.
If yous hold off closely this algorithm is similar to the algorithm nosotros lead keep before used to reverse an array inward place. That's obvious because String is backed yesteryear graphic symbol array inward Java.
If yous know how to opposite an array inward house in addition to hence reversing a String is non dissimilar for you. What is to a greater extent than of import is checking for null in addition to empty String because this is where many programmers larn lazy in addition to started writing code without validating input.
You must write your best code during programming interviews. The code which tin stand upward the seek of fourth dimension inward production is what every interview similar to see. If yous don't know how to write production lineament code, I propose yous convey a hold off at Clean Code, i of the books yous should read at the start of your programming career.
Btw, if yous are non familiar amongst recursion in addition to iteration or basic fundamentals of Data Structures in addition to Algorithms in addition to hence I propose yous bring together a comprehensive course of written report like reverse a String inward place, * without whatever additional buffer inward Java. * * @author WINDOWS 8 * */ public class StringReversal { /** * Java method to opposite a String inward house * @param str * @return opposite of String */ public static String reverse(String str) { if(str == null || str.isEmpty()){ return str; } char[] characters = str.toCharArray(); int i = 0; int j = characters.length - 1; while (i < j) { swap(characters, i, j); i++; j--; } return new String(characters); } /** * Java method to swap 2 numbers inward given array * @param str * @param i * @param j */ private static void swap(char[] str, int i, int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } @Test public void reverseEmptyString(){ Assert.assertEquals("", reverse("")); } @Test public void reverseString(){ Assert.assertEquals("cba", reverse("abc")); } @Test public void reverseNullString(){ Assert.assertEquals(null, reverse(null)); } @Test public void reversePalindromeString(){ Assert.assertEquals("aba", reverse("aba")); } @Test public void reverseSameCharacterString(){ Assert.assertEquals("aaa", reverse("aaa")); } @Test public void reverseAnagramString(){ Assert.assertEquals("mary", reverse("yram")); } }
You mightiness lead keep too noticed that this time, I lead keep non to purpose the main() method to seek the code, instead I lead keep written span of JUnit seek cases. It's truly ameliorate to write unit of measurement seek cases all the fourth dimension to seek your code instead of using main() method equally it pose unit of measurement testing inward your habit.
Btw, if yous experience reluctance on writing unit of measurement tests or non certain how to write tests, I propose yous read Test Driven, i of the best mass on Test drive evolution but fifty-fifty if yous don't follow TDD, it volition help yous to write ameliorate code in addition to unit of measurement tests.
I lead keep written next JUnit tests to banking corporation gibe whether our opposite method is working for dissimilar kinds of String or not, the JUnit seek outcome is too attached below:
And, hither is the outcome of running these JUnit tests:
You tin consider that all the unit of measurement tests are passing, which is good. You tin too add together to a greater extent than unit of measurement seek to farther seek our method of reversing String inward Java.
That's all nigh how to opposite String inward house inward Java. This is a mutual algorithm which uses 2 pointer approach. Since it requires us to traverse the array till middle, fourth dimension complexity is O(n/2) i.e. O(n). It doesn't purpose whatever external buffer instead simply purpose 2 variables to proceed runway of indices from start in addition to end.
Further Learning
Data Structures in addition to Algorithms: Deep Dive Using Java
solution)How to opposite String inward Java without StirngBuffer? (solution) How to count the publish of words inward given String? (solution) How to banking corporation gibe if a String is a palindrome inward Java? (solution) How to uncovering duplicate characters on String? (solution) How to count vowels in addition to consonants inward given String? (solution) How to opposite words inward a given String inward Java? (solution) 21 String Programming Questions for Programmers (questions) 100+ Data Structure in addition to Algorithms Questions for Java programmers (questions) 75+ Programming in addition to Coding Interview questions (questions)
That technique uses the two-pointer approach where i pointer starts from the offset in addition to other pointer starts from the halt of the array. You swap elements until they meet. At that indicate inward time, your String or array is already reversed.
This is an acceptable solution because nosotros lead keep non used additional retentivity in addition to whatever library method, but yous tin too last asked to explicate nigh the fourth dimension in addition to infinite complexity of your solution.
The fourth dimension complexity of this algorithm is O(n/2) + fourth dimension taken inward swapping, which effectively adds upward to O(n) time. This way fourth dimension volition growth inward the proportion of the length of String or publish of characters on it. The infinite complexity is O(1) because nosotros are non using whatever additional retentivity to opposite the String.
Btw, String is a real pop topic on interviews in addition to yous volition ofttimes consider a span of String based coding questions on interviews. Influenza A virus subtype H5N1 proficient noesis of String along amongst other information structures similar an array, linked list, in addition to binary tree is real important. If yous experience yous lack that noesis or desire to improve it, I propose yous convey a hold off at Data Structures in addition to Algorithms: Deep Dive Using Java course on Udemy. It's both affordable in addition to real comprehensive course of written report in addition to I highly recommend it for Java programmers.
Java Program to Reverse a String inward place
Here is the uncomplicated representative to opposite characters inward String yesteryear using 2 pointer technique. This is an in-place algorithm because it doesn't allocate whatever extra array, it simply uses the 2 int variables to concur positions from start in addition to end.If yous hold off closely this algorithm is similar to the algorithm nosotros lead keep before used to reverse an array inward place. That's obvious because String is backed yesteryear graphic symbol array inward Java.
If yous know how to opposite an array inward house in addition to hence reversing a String is non dissimilar for you. What is to a greater extent than of import is checking for null in addition to empty String because this is where many programmers larn lazy in addition to started writing code without validating input.
You must write your best code during programming interviews. The code which tin stand upward the seek of fourth dimension inward production is what every interview similar to see. If yous don't know how to write production lineament code, I propose yous convey a hold off at Clean Code, i of the books yous should read at the start of your programming career.
Btw, if yous are non familiar amongst recursion in addition to iteration or basic fundamentals of Data Structures in addition to Algorithms in addition to hence I propose yous bring together a comprehensive course of written report like reverse a String inward place, * without whatever additional buffer inward Java. * * @author WINDOWS 8 * */ public class StringReversal { /** * Java method to opposite a String inward house * @param str * @return opposite of String */ public static String reverse(String str) { if(str == null || str.isEmpty()){ return str; } char[] characters = str.toCharArray(); int i = 0; int j = characters.length - 1; while (i < j) { swap(characters, i, j); i++; j--; } return new String(characters); } /** * Java method to swap 2 numbers inward given array * @param str * @param i * @param j */ private static void swap(char[] str, int i, int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } @Test public void reverseEmptyString(){ Assert.assertEquals("", reverse("")); } @Test public void reverseString(){ Assert.assertEquals("cba", reverse("abc")); } @Test public void reverseNullString(){ Assert.assertEquals(null, reverse(null)); } @Test public void reversePalindromeString(){ Assert.assertEquals("aba", reverse("aba")); } @Test public void reverseSameCharacterString(){ Assert.assertEquals("aaa", reverse("aaa")); } @Test public void reverseAnagramString(){ Assert.assertEquals("mary", reverse("yram")); } }
You mightiness lead keep too noticed that this time, I lead keep non to purpose the main() method to seek the code, instead I lead keep written span of JUnit seek cases. It's truly ameliorate to write unit of measurement seek cases all the fourth dimension to seek your code instead of using main() method equally it pose unit of measurement testing inward your habit.
Btw, if yous experience reluctance on writing unit of measurement tests or non certain how to write tests, I propose yous read Test Driven, i of the best mass on Test drive evolution but fifty-fifty if yous don't follow TDD, it volition help yous to write ameliorate code in addition to unit of measurement tests.
I lead keep written next JUnit tests to banking corporation gibe whether our opposite method is working for dissimilar kinds of String or not, the JUnit seek outcome is too attached below:
- Unit seek to opposite an empty String
- Test to opposite a goose egg String
- Reverse a palindrome String
- Unit tests to opposite a i graphic symbol string
- JUnit seek to opposite a string amongst the same character
- Reverse a String amongst a dissimilar character
- Reverse an anagram String
And, hither is the outcome of running these JUnit tests:
You tin consider that all the unit of measurement tests are passing, which is good. You tin too add together to a greater extent than unit of measurement seek to farther seek our method of reversing String inward Java.
That's all nigh how to opposite String inward house inward Java. This is a mutual algorithm which uses 2 pointer approach. Since it requires us to traverse the array till middle, fourth dimension complexity is O(n/2) i.e. O(n). It doesn't purpose whatever external buffer instead simply purpose 2 variables to proceed runway of indices from start in addition to end.
Further Learning
Data Structures in addition to Algorithms: Deep Dive Using Java
solution)
Thanks for reading this article hence far. If yous similar this coding enquiry in addition to hence delight portion amongst your friends in addition to colleagues. If yous lead keep whatever uncertainty or feedback in addition to hence delight drib a note. You tin too follow me on Twitter (javinpaul) to larn updates nigh programming in addition to Java inward general.
No comments:
Post a Comment