chavandp7
BAN USERSolution to this problem must solve 3 criteria efficiently:-
1. Memory wastage
2. should dynamically grow or shrink as per need
3, addition/removal/query of a person's data should be optimal
Technically we can think of 3 ways to solve this problem:
1. Arrays (Not Possible)
Addition/Removal/Searching of a person's data is efficient in this way. But can you think of array size equal to population of India. If there are less records, then lot of memory will be wasted. Also the size of array can't grow when there is need for it.
2. Linked List (Not Efficient)
We can implement Linked list for this as the records can be added dynamically when there is need for it. Memory wastage problem is solved as the record is created only when a new member appears. But addition/Removal/searching of a person's data with specific phone no becomes tedious. Imagine you have someones phone no in the last node. Then we have to iterate whole linked list to get to that node. So not Efficient.
3. Indexing/Hashing (Solution)
Indexing/Hashing gives us the way to store data efficiently. It grows with space requirement so memory wastage is taken care of. The best thing about this approach is that Addition/Removal/Searching of a person's data is very efficient. When we query for a person's phone no like 98********. First all nos starting from 9 only are taken into account. Then nos starting with 8 and hence forth. So this is an optimal solution.
import java.util.Scanner;
class SubStringOccurrence {
public static void main(String[] args) {
String str;
int flag = 0;
int i, j, k, l;
Scanner s = new Scanner(System.in);
str = s.next();
System.out.println("input String : "+str+ "\n");
// Rotate over array
for(i = 0; i < str.length()-1; i++){
for(j = i+1; j < str.length(); j++){
// first character out of 2 characters is found
if(j != str.length()-1 && str.charAt(i) == str.charAt(j)){
// Now search for second character from first half
// into second half
for(k = i+1; k < j; k++){
for(l = j+1; l < str.length(); l++){
if(str.charAt(k) == str.charAt(l)){
System.out.println(" "+str.charAt(i)+""+str.charAt(k)+ " is repeated");
flag = 1;
}
}
}
}
else{
continue;
}
}
}
if(flag == 0){
System.out.println("No substring found");
}
}
}
- chavandp7 November 18, 2014