DSA Day -1 : Strings

When we talk about data structures, a lot of people forget about strings. It’s not a tough topic, but an important one. I got one question of string manipulation in my first online round for Amazon.

Basic Concepts

• int length(): Returns the number of characters in the String
• char charAt(int i): Returns the character at i index
• String substring (int i): Return the substring from the ith index character to end.
• String substring (int i, int j): Returns the substring from i to j-1 index.
• String concat( String str): Concatenates specified string to the end of this string.
• int indexOf (String s): Returns the index within the string of the first occurrence of the specified string.
• int compareTo( String anotherString): Compares two string lexicographically.
• String toLowerCase(): Converts all the characters in the String to lower case.
• String toUpperCase(): Converts all the characters in the String to upper case.

Important Questions for practice

1. Verify if a string is palindrome, anagram
2. Reverse a string
3. Given an input string and ordering string, need to return true if the ordering string is present in Input string.

input = “hello world!”
ordering = “hlo!”
result = FALSE (all Ls are not before all Os)

input = “hello world!”
ordering = “!od”
result = FALSE (the input has ‘!’ coming after ‘o’ and after ‘d’, but the pattern needs it to come before ‘o’ and ‘d’)

input = “hello world!”
ordering = “he!”
result = TRUE

input = “aaaabbbcccc”
ordering = “ac”
result = TRUE

4. Different permutations of a string

5. Given a two strings, determine if one is a circular permutation of the other or not. For example abcd, cdab are circular permutations

6. Longest palindromic substring (involves Dynamic programming too, so add this question in to do list if you’ve not studied DP yet)

7. Valid Paretheses (String, Stacks)

Interview Questions

1. Difference between Character Constant and String Constant in java ?

Ans. Character constant is enclosed in single quotes. String constants are enclosed in double quotes. Character constants are single digit or character. String Constants are collection of characters.
Ex :’2’, ‘A’
Ex : “Hello World”

2. Why Char array is preferred over String for storing password?

Ans. String is immutable in Java and stored in String pool. Once it’s created it stays in the pool until unless garbage collected, so even though we are done with password it’s available in memory for longer duration and there is no way to avoid it. It’s a security risk because anyone having access to memory dump can find the password as clear text.
If we use a char array to store password, we can set it to blank once we are done with it. So we can control for how long it’s available in memory that avoids the security threat with String.

3. What is the output of below code snippet?

String s1 = new String("abc");

String s2 = new String("abc");

System.out.println(s1 == s2);

Ans. It will print false because we are using new operator to create String, so it will be created in the heap memory and both s1, s2 will have different reference. If we create them using double quotes, then they will be part of string pool and it will print true.

4. What will be output of below code snippet?

String s1 = "abc";

StringBuffer s2 = new StringBuffer(s1);

System.out.println(s1.equals(s2));

Ans. It will print false because s2 is not of type String. If you will look at the equals method implementation in the String class, you will find a check using instanceof operator to check if the type of passed object is String? If not, then return false.

5. How many String objects got created in below code snippet?

String s1 = new String("Hello");

String s2 = new String("Hello");

Ans. The answer is 3.
First — line 1, “Hello” object in the string pool.
Second — line 1, new String with value “Hello” in the heap memory.
Third — line 2, new String with value “Hello” in the heap memory. Here “Hello” string from string pool is reused.

After a detailed research on questions related to strings, I concluded that most of the questions revolve around the concepts of above questions only.

Since, this initiative is to help everyone including the beginners, I have kept the difficulty level very low in the beginning and would be increasing it in the days to come.

Tips to Start practicing

1. I used leetcode for practice. You can use hackerrank, geeksforgeeks or any other platform you’re comfortable with.
2. If you’re new to a topic, don’t rush to hard questions right away, solve at least 10 easy, 5- 7 medium questions before going for hard questions.
3. Don’t skip to typing the code right away, use pen and paper to form an approach to the solution.
4. Give yourself 20–30 minutes to solve a question, if you cannot, then only move to solution. If you skip to solution part, you might understand the solution but won’t be developing intuition to solve questions on your own.
5. When you’re seeing solution, don’t just look at the code and understand it, rather, solve each step of the solution for 2–3 inputs on a piece of paper and then write the code on your own for the same solution.

I understand that exams are starting for a lot of people out there, that is why I’m covering very basic concepts first. So, keep solving at least 5 questions daily and you’ll start feeling confident yourself.

Do leave comments on how I can improve the posts or the topics you want me to address.

All the best!

Upcoming posts: Microsoft Summer internship and PPO selection procedure, DSA Day 2