Interview Question
Country: India
Interview Type: In-Person
Solution in Java:
String text = "Myunite@#$%%^^12334";
Pattern pattern = Pattern.compile("\\d"); // only digits
Matcher matcher = pattern.matcher(text);
System.out.println("\n\nprinting Digits only\n------------------------\n");
while (matcher.find()) {
System.out.print("Start index: " + matcher.start());
System.out.print(" End index: " + matcher.end() + " ");
System.out.println(matcher.group());
}
pattern = Pattern.compile("[a-zA-Z0-9]"); // only alphanumeric
matcher = pattern.matcher(text);
System.out.println("\n\nprinting Alphanumeric characters only\n------------------------\n");
while (matcher.find()) {
System.out.print("Start index: " + matcher.start());
System.out.print(" End index: " + matcher.end() + " ");
System.out.println(matcher.group());
}
pattern = Pattern.compile("\\W"); // only symbols
matcher = pattern.matcher(text);
System.out.println("\n\nprinting symbols only\n------------------------\n");
while (matcher.find()) {
System.out.print("Start index: " + matcher.start());
System.out.print(" End index: " + matcher.end() + " ");
System.out.println(matcher.group());
}
OUTPUT:
printing Digits only
------------------------
Start index: 14 End index: 15 1
Start index: 15 End index: 16 2
Start index: 16 End index: 17 3
Start index: 17 End index: 18 3
Start index: 18 End index: 19 4
printing Alphanumeric characters only
------------------------
Start index: 0 End index: 1 M
Start index: 1 End index: 2 y
Start index: 2 End index: 3 u
Start index: 3 End index: 4 n
Start index: 4 End index: 5 i
Start index: 5 End index: 6 t
Start index: 6 End index: 7 e
Start index: 14 End index: 15 1
Start index: 15 End index: 16 2
Start index: 16 End index: 17 3
Start index: 17 End index: 18 3
Start index: 18 End index: 19 4
printing symbols only
------------------------
Start index: 7 End index: 8 @
Start index: 8 End index: 9 #
Start index: 9 End index: 10 $
Start index: 10 End index: 11 %
Start index: 11 End index: 12 %
Start index: 12 End index: 13 ^
Start index: 13 End index: 14 ^
class separatecharacter{
public static void main(String args[]){
String s1="",s2="",s3="";
int i=0,j=0;
char c1;
String s="Myunite@#$%%^^12334";
char c[]=s.toCharArray();
for(i=0;i<c.length;i++){
c1=c[i];
j=c1;
if((j>=0 && j<=47)||(j>=91 && j<=96)||(j>=123 && j<=255)||(j>=58 && j<=64))
s1=s1+c1;
else if(j>=48 && j<=57)
s2=s2+c1;
else if((j>=65 && j<=90)||(j>=97 && j<=122))
s3=s3+c1;
}
System.out.println("the symbols are "+s1);
System.out.println("the numbers are "+s2);
System.out.println("the alphabets are "+s3);
}
}
Are you sure you understood the question correctly?
Because the way it's stated, you can use Auxillary space and just do a linear sweep filtering through if-elseif-elseif ranges into separate linked lists(with tail pointers), then append the lists.
This will be O(n) because appending linked lists is easy when they have tail pointers.
I think they probably said do this in-place (that is, use at most O(1) extra space). Only then is the problem "hard" and interesting.
[BTW, the way to do it in place is to use the partition subrouting on quicksort bit with the change that YOU CHOOSE the value to partition on]
Say the ranges for the different type of characters are like:
Type 1: [0,K1)
Type 2: [K1, K2)
..
Type m: [K(m-1), Km]
Say your array, A, is indexed [0,...,n-1]
Call t=Partition(A, 0, n-1, K1) to partition the array into things < K1 and >= K1
The t= returned from Partition is the position of first element > K1.
So we know the array A[0..t-1] is done with.
Call partitoin again like t= Partitoin(A, t, n-1, K2)
...
So in general you have a repeated process:
t=0;
for val iterated over {K1, K2, ...}
t=Partition(A,t,n,val)
So to this question I would have to clarify what the difference in Numberics and Numbers really means. This could just be a knowledge gap on my part. That being said, let's get into the appropriate way to establish a filter on an alphanumeric string.
- masterjaso September 11, 20131. Convert string to char array
2. Determine character set ( i will assume ASCII)
3. On each character evaluate the ASCII value by range. For instance
0-47: special characters (carriage return, newline, Space, etc...)
48-57: Numbers (0-9)
58-64: Special Symbols
65-90: Capital Alphabet (letters)
91-96: More Special Symbols
97-122: Lower Case Alphabet (letters)
123-255: more Special Characters
4. Apply filter rule: either keep or remove based on the type of filter and character present.
Note that there are many character sets and different ways to set these ranges. I picked these ranges for simplicity sake. I would also utilize a StringBuilder data structure to keep the characters that aren't filtered out and return the value of my StringBuilder when the algorithm completed. Should be O(n) time complexity for the filter, and require O(n) additional space for the char array and StringBuilder.