Cracking the coding interview
Arrays and String question solutions
Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.
Question 1Implement an algorithm to determine if a string has all unique characters.Think what you can do if you cannot use additional data structures? means that all the characters in the string must be for one time only.
Solution
You can find the solution for this problem here
Here i am providing solutions for this question using different data structures to give to the knowledge about the them and to let you know that same problem can be solved in many different ways using different approaches that might be helpful to remember in your interviews.
If you find this code hard to understand then please start writing your own code and use pen n paper for that so then you can keep track what is your code all about and what it is calculating.
This problem is one of the most asked question in the interviews so try ti understand this thoroughly and try similar problems like it.
Solution 1 using hash map java (Worst case Complexity N)
This solution provides you the knowledge about using the hash map and functions of the hash map. Hash map is a data structure that has special key value mapping and used in many problems to reduce the complexity of the algorithm.
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(unique());
}
public static boolean unique()
{
String str ="asdfjgh";
HashMap < Character,Integer > map = new HashMap < Character,Integer > ();
for(int i=0;i < str.length();i++)
{
if(map.containsKey(str.charAt(i)))
{
return false;
}
map.put(str.charAt(i),1);
System.out.println(map.get('a'));
}
return true;
}
}
Solution 2 using array java(Worst case Complexity N).This method uses Boolean array to represent all the character and the value of the Boolean if the particular alphabet occurs one time in the string and that how this solution works checks if the particular alphabet has occur twice or not if yes the return false as the answer
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(unique());
}
public static boolean unique()
{
String str ="asdfghj";
boolean arr[] = new boolean[256];
for(int i=0;i < str.length();i++)
{
if(arr[i])
{
return false;
}
arr[i]=true;
}
return true;
}
}
Solution 3 using array java(Worst case Complexity N2).This is a simple iteration method that checks every alphabet with all the alphabet in the string to check if they match or not. If they matches then string is not unique.
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(unique());
}
public static boolean unique()
{
String str ="asdfghj";
for(int i=0;i < str.length();i++)
{
char c = str.charAt(i);
for(int j=i+1;j < str.length();j++)
{
if(c==str.charAt(j))
{
return false;
}
}
}
return true;
}
}
Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.
