CodeJunkey
BAN USERWhat if 1,2 3,4 are characters themselves. Can you convert
aebfcgdh to abcdefgh in O(n) time and O(1) complexity. I think it should be possible.
Yes, you may have a valid point but it won't happen if you override the compare operator for comparing two integers by joining them as string and reconverting to long number. You can check Long.MAX_VALUE is bigger two Intger.MAX_VALUE joined side by side. After all you just need a boolean value in the end.
However, if you are still not satisfied, there is a very simple technique to override compare operator without getting into problems like you mentioned. Just compare the integers as strings, character by character. With this logic any string that begins with a higher order number gets preference. For. eg.
'9'> '81' (because second string begins with 8)or '76'>'597' (because second string begins with 5). I don't think this is something very difficult to implement.
It is just an simple sorting question with a little twist by changing the elementary compare operator so I don't think there is one answer to this problem. Any algorithm would work but O(n log n) type algorithms like mergesort and quicksort should be a good answer. Any comparison based sorting algorithms would do. Here I have implemented both in java for random arrays. Have a look those interested but there is absolutely no change in these basic algorithms except for the change in compare operator:
import java.util.Arrays;
import java.util.Random;
public class AnyClass
{
private final static int MAX_SIZE = 10 ;
private final static int MAX = 20;
public static void mergeSort(int a[])
{
if(a.length <= 1)
return;
int first[] = new int[a.length / 2];
int second[] = new int[a.length - first.length];
for(int x = 0; x < first.length; x++)
first[x] = a[x];
for(int x = first.length, y = 0; x < a.length; x++, y++)
second[y] = a[x];
//Split the array again
mergeSort(first);
mergeSort(second);
merge(first, second, a);
}
private static int[] merge(int first[], int second[], int[] a)
{
int x = 0;
int y = 0;
int z = 0;
while(x < first.length && y < second.length){
if(compareInt(first[x],second[y])){
a[z] = first[x];
x++;
}
else{
a[z] = second[y];
y++;
}
z++;
}
//copy remaining elements to the tail of a[];
for(int i = x; i < first.length; i++){
a[z] = first[i];
z++;
}
for(int i = y; i < second.length; i++){
a[z] = second[i];
z++;
}
return a;
}
public static boolean compareInt(int x, int y){
return (Integer.parseInt(Integer.toString(x)+Integer.toString(y))>
Integer.parseInt(Integer.toString(y)+Integer.toString(x)));
}
public static void quickSort(int[] a, int p, int r)
{
if(p<r)
{
int q=partition(a,p,r);
quickSort(a,p,q);
quickSort(a,q+1,r);
}
}
private static int partition(int[] a, int p, int r) {
int x = a[p];
int i = p-1 ;
int j = r+1 ;
while (true) {
i++;
while ( i< r && compareInt(x,a[i]))
i++;
j--;
while (j>p && compareInt(x,a[j]))
j--;
if (i < j)
swap(a, i, j);
else
return j;
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String args[]){
Random generator = new Random();
int[] numbers = new int[generator.nextInt(MAX_SIZE)];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = generator.nextInt(MAX);
}
//int[] numbers = {4, 94, 9, 14, 1};
System.out.println("Unsorted Array:"+Arrays.toString(numbers));
mergeSort(numbers);
System.out.println("Sorted Array via Mergesort:"+Arrays.toString(numbers));
for (int i = 0; i < numbers.length; i++) {
numbers[i] = generator.nextInt(MAX);
}
System.out.println("Unsorted Array:"+Arrays.toString(numbers));
quickSort(numbers, 0, numbers.length - 1);
System.out.println("Sorted Array via QuickSort:"+Arrays.toString(numbers));
}
}
Please ignore the classname and excuse my english. I wrote it very fast
- CodeJunkey October 03, 2012oh.. great.. Thank you. my bad.
- CodeJunkey September 08, 2012This seems like brute force search. However, there are only two loops. It seems to me that complexity will be O(N^2), assuming we do constant O(1) work for each if statements. Can someone explain what I am doing wrong here?
- CodeJunkey September 07, 2012This Java code works for me. Let me know if you spot an error or have a comment. The program spots any consecutive substrings. Starts with 0th character and checks all the consecutive substrings possible starting here. Then increment one character and repeat the process.
import java.util.Scanner;
public class StringCompare {
public static void main(String[] args){
Scanner myinput = new Scanner( System.in );
String inputstring;
System.out.print("Enter your string(no spaces and no capital letters): ");
inputstring = myinput.next();
for (int i=0;i<inputstring.length()-1;i++)
{
for(int s=1;s<=(inputstring.length()-i)/2;s++)
{
if(inputstring.substring(i,i+s).equals(inputstring.substring(i+s,i+s+s)))
{
System.out.println("Match Found: "+inputstring.substring(i,i+s)+" "+inputstring.substring(i+s,i+s+s));
}
}
}
System.out.print("Finished :-)");
}
}
How about use a HashSet to track already seen friends so that you don't print a friend twice. And use two indices to track levels just like level tree order print. Let me know if this is wrong, I will really appreciate
- CodeJunkey October 19, 2013