ishitajuneja's blog
In this tutorial we are going to discuss the technicalities attached with the concept of longest substring without repeating the characters!
As string is touted as the most crucial coding interview concept, there are high chances you will encounter the questions on this topic.
From longest palindromic substring to reversing a string, you will come across several string concepts.
In this blog we have discussed the topic of substrings that exist without non-repeating characters.
Read it in detail and strengthen your knowledge!
Counting longest substring without repeating all the characters
A string str is given to you which consists of all the lowercase alphabets. Your task would be to find all the possible substrings which only consist of distinct characters.
For example:
The input is Str = gffg
The output in this case is 6.
From a given string, you will get the possible strings as g, gf,gff, gffg,f, ff, ffg, f, fg and g.
Among all these strings, the highlighted strings will only consist of the distinct characters.
Analysis
To find the longest substring without repeating the character,you will get the input as a string which contains the characters that may not be repeated. Your task would be to find the longest substring with distinct characters.
One feature of a substring is that it contains all the contiguous characters. In the given string, s =requark, the substrings would be edq, red, ar, quar.
Though, the substring rd and qur are not valid ones as they contain the characters from its source string or which are not contagious.
There can be several substrings as the output so as to only return the longest among them.
Sliding window algorithm
The sliding window algorithm would be quite useful to find substring with distinct characters. From an input, we can gather the information as:
A data structure is given which will be a linear data structure
The output would be a substring that is the part of a string
There will be a naive solution for checking if you will get the combination of the each character in a string
The steps to follow in this case are:
You are given two pointers which would define a start index with the start and an ending index as end in a current window. They will be 0 in the beginning.
Declare the set of variables to unique characters that you will encounter with
Declare the variable called maxlength to keep track of the required length of the longest substring
Scan a required string from its left to right as one character at a given time
If the characters are not encountered before, they will not be present as a set in the string to get the increment at the end of an index. The maxlength in this case would be as set.size[]with the existing maxlength
Though, if there are characters that have been encountered before which are present in a given set, we will increment it as start to remove all characters at the start of an index
Repeat the steps to move it till the window
After a loop terminates, return it maxlength
As you can see, the strings will be scanned only once from left to right, the time complexity in this case would be O[n].
As you will be using the set of data structure for computations, the space complexity in this case would be the O[n]
Since, the set will only contain unique characters, you will not get the size of characters more than what is required.
Brute Force Approach
This is a simple method to check all required substrings from a given string with that of a nested for loop to check if the substrings would have any duplicate characters.
Create all variables to track longest_len of the substring encountered.
Create the required loop in order to traverse all the substring characters. Then create variables to keep the track of all substrings encountered
Create some other loop in order to traverse the characters of a substring. Compare the string length by using the max()function and assign the greater value
Use if nested statement to check the length of a previous string with the length of a current string with the lonest_str variable.
Print the longest substring with its length
Considering in this case, the string as only substring, the runtime will be O [n ^ 2] the space complexity in the best or worst case would be o [1]
Using Hashmap
It takes less time in the dictionary type. Firstly, create a required empty dictionary for tracking all the characters as a key with their respective indexes as a kind of dictionary value.
Keep the longest substring length in mind with the start of an index for each substring in the loop to determine the length at the end of a loop.
First create the empty dictionary with longest_len to keep the track of variables. Then keep the track of the starting indexes with the longest_str
Create the required for loop for all string characters. Create the if statement to check if it is in the dictionary or not. Check if it has the value greater than that of start variable or the value equal to that character
By using if statement, you can check current substring length as i = start for the previous length of a required substring
Set the longest_len variable for storing the value length in the current substring with that of the previous substring. See if it is greater than the max() function
Print the length of a longest substring with that of the substring itself
The time complexity in this case would be O [n] because you may need to traverse all characters. Though, the space complexity would be O[1] for both best and worst case.
Wrapping Up
From longest palindrome substringto longest palindromic superstring to longest substring without repeating characters, you will come across the much wider concept of substring.
Keep this blog as your mentor to find the non repeating characters that exist in a longest substring.
Java is arguably one of the most popular programming languages since the past 25 years. This is mainly because it is not only flexible in nature but also user friendly.
It is commonly used for developing various software applications such as web applications, mobile gaming softwares and several educational platforms as well.
This is one of the main reasons why Java is one of the top choices for the interviewers to conduct coding interviews.
The string class in Java is specifically one of the most popular. String in Java allows the programmers to store data in the form of objects that can be used within a program.
If you are interested in becoming a Java developer, then one of the major prerequisites is to solve the string interview questions in java.
Find the top string questions that are important from the interview perspective in this blog.
Top 20 Java String Interview Questions and how to solve them
There are certainly different levels to the types of string interview questionsthat one can expect within their technical interview rounds.
From freshers to experienced professionals, the string questions differ in terms of their complexities.
With that said, this section offers a segment view of each level of string questions that you will be asked to complete during your interview process. Let's have a look!
Fresher level string interview questions
Q. What is the process of declaring a string in Java?
Q. Would you consider string to be a derived or a primitive class in Java?
Q. What are the differences between the string class in C programming and in Java programming?
Q. How would you create a string pool using Java?
Q. Would you consider string to be immutable or constant in Java? What would you consider are the benefits for string being mutable in Java?
These are some of the fresher level questions that you can expect to encounter in the first round of your string interview. In order to answer these questions you will have to clear the basics of string.
The string is essentially a mutable class in Java that can be declared by using the String str= class function. You can create a string pool in the memory using the same string class function.
Make sure to clear your basics in order to answer the fresher level string interview questions. With that said, the next section will focus on the intermediate level questions for string.
Intermediate level string interview questions
Q. What is the purpose of using the string intern() function in Java?
Q. What are the differences between the string and Stringbuffer in Java?
Q. What are the differences between StringBuffer and StringBuilder in the programming language of Java?
Q. How would you compare two different strings in Java?
Q. What is the main difference between the functions: str1 == str2 and str1.equals(str2)?
As you might have noticed, the intermediate level string interview questionsare related to the different methods and functions that are available for string in Java.
All of these methods are essentially related to manipulating the objects contained within a string.
Even if you forget the function of any of these methods, it is suggested to frame your answers based on how these functions make it easier for the string class to change or add objects within the program.
Some of these methods are also used for comparing different string classes in Java.
For instance, you have the string equals method that is one of the top classes used for making comparisons between two different values in a string.
With that, it's time to move onto the advanced level string interview questions.
Advanced Level String Interview Questions
Q. What are the types of risks involved in comparing the strings using == operator?
Q. How do you consider the substring() class used in Java?
Q. Can you use a switch case for string in Java?
Q. Describe the different forms of string methods that are available in Java?
Q. Would you consider the string thread to be safe for Java?
These forms of advanced level string questions are often asked in the technical interview of various multinational companies.
For instance, you can check out theDE Shaw interview experienceto find out how the candidates have tried to approach these questions.
For starters, it is suggested that you practice using string in real time in order to learn all about the different methods of string.
On the other hand, if you have been practicing string for a while, then you might certainly be able to answer the experienced level string interview questions as mentioned in our final section.
Experienced level string interview questions
Q. Why do you think string is used as a key for HashMap in Java?
Q. If you were to divide a string, how would you achieve that in Java?
Q. Why do most of the programmers use the char array instead of string for storing the passwords?
Q. What is the process for converting a string into an integer in Java?
Q. How would you convert a given string into a StringBuilder in Java?
Now, these are some of the more advanced level questions for string that require coding. This is mainly the reason why this section can only be cleared by people who have a significant amount of experience in Java as well as in creating string objects.
In order to ace this section, we would suggest practicing coding in Java so that you would have a certain level of knowledge of how the string class works in Java.
Start with the basics, and move onto the different class functions to make sure to thoroughly prepare for the experienced level coding questions for string.
Wrapping Up
Strings, arrays and linked lists are some of the top data structures that are extremely essential for Java programmers.
If you are a Java interview aspirant, you should definitely check out the technical interview experiences of different companies such as Microsoft, Infosys, Amazon and DB Shaw interview experience.
These tech interview experiences will guide you through all sorts of questions for string interview.
Data structure is among the most critical concepts asked in coding interview assessments at tech companies. This includes product-based companies like Amazon and Microsoft to service companies like TCS and Accenture.
And within data structure, you’re bound to get the ‘Reverse a Linked List in Groups’ question. How you reverse a linked list is critical to cracking the interview round.
The reason why applicants have a hard time solving this problem is because they don’t know what a linked list is and how to reverse it. Well, that’s what this article is about.
Here learn how you can reverse a linked list in groups of given sizeeasily in a few steps while learning the different approaches used to reverse the list.
Linked lists are an important concept in data structure. As per their technical definition, linked lists are defined as linear data structures with interconnected nodes. Each node contains the information (data) and the address to the next node.
Think of linked lists as the game of Treasure Hunt. In this popular game, the clue in a current scenario leads to the next clue and so on. Likewise, each node in the linked list leads to the next node. The links between the two nodes are called pointers.
Also, note that there are different types of linked lists. These are:
Singly linked- Each node is joined to another node a single pointer
Doubly linked- The nodes are joined to one another double pointers. Thus, you can proceed in both directions, forward and backward
Circular- Here the last node is linked to the first node in addition to a single pointers
The importance of linked lists in programming is immense. They are often employed for the implementation of queues, stacks, or other abstract data types. Doubly linked and circular linked lists are used for more complex problems in data structure like Fibonacci Heap.
Their efficient insertion and deletion is what makes linked lists so popular among programmers. They are used in many mainstream languages like C, C++, Java, and Python.
Don’t confuse linked lists with arrays, even though both are used for storing the elements. Understanding the difference between the two is crucial to solving the problem.
Arrays are used for storing elements in a contiguous memory location, whereas in linked lists, the elements aren’t held at contiguous memory locations.
In other words, linked lists are less rigid when it comes to the storage structure. That’s why they contain information to the next node, thereby giving a reference.
So what does reversing a linked list in groups mean?
Since all technical rounds are time-based, many applicants don’t put enough time in understanding the question. This, as hiring managers would tell, is a mistake. You should also read and understand the problem before attempting. You can also look at the reverse level order traversal.
When you get a “reversing a linked list” type of query, there are two similar questions. These are:
Reverse a linked list in groups
Reverse a linked list
The solution to both of these questions is different. One wouldn’t substitute for another. Therefore, it’s really crucial to read and understand the query before attempting.
For the second question, you just have to reverse the linked list. More specifically, you have to reverse the pointers. So for ( 3→2→1), the reverse list would be (1→2→3). You can either follow the iterative or recursive approach.
The point of focus for this article is how to reverse a linked list in groups of given size. So instead of simply reversing the linked list, you need to reverse it in groups. Here’s what the input looks like:
Input: 1->2->3->4->5->6->7->8->NULL (k=3)
K is always a positive integer and here serves as an input to the function. It also defines the size of the group. The output of this would be:
Output: 3->2->1->6->5->4->8->7->NULL
Noticed the difference?
Here, the linked list was reversed in groups of 3. So there are 3 nodes in each group. Nodes 1, 2, 3 are one group, nodes 5, 6, 7 are the next group and so on. The last group (7, 8) is incomplete. So they need to stay the same.
You need to produce the same result when asked to reverse a linked list in groups of given size. Also, you don’t have to change the value of the nodes in the list.
Now let’s see how to solve this problem.
The best approach to reversing a linked list in groups of given size is the following:
Reverse the first sub-list with size equal to K. You need to keep track of the next and previous node when reversing.
Define the pointer leading to the next node as ‘next’ and the one pointing to the previous node as ‘prev’
Then, you have to recursively call the remaining list. Then link the two sub-lists.
Finally, return ‘prev’. Here, the nodes defined as prev become the head in the new list.
You can apply this approach to solve this problem. In the end, you should get a reversed linked list in groups of k.
Reversing the linked list in a group of given sizeproblems will help you crack the interview. Yes, there will be other questions as well, but this will create a good first impression.
For the best chances of clearing the technical round, practise other similar linked list data structure problems. Some of them are:
Detect loop in a linked list
Remove duplicates from a sorted linked list
Reverse level order traversal
Convert a Binary Tree to Circular Doubly Linked list
Swap the nth node in the beginning with the nth node in the end in this linked list
You can find more similar questions in online mock tests. Do take them up to boost your chances of success.
