Buzz Lightyear
BAN USER- 1of 1 vote
AnswersThere are two gates , one to hell and the other to heaven.
- Buzz Lightyear in India
Two gatekeepers , one for each gate.
One of them always speaks the truth and the other always lies but you don't know which one s guarding which gate.
You are allowed only one question and you need to find out the gate to heaven.
What is the question you will ask and remember , you do not know which one speaks the truth and which one lies.| Report Duplicate | Flag | PURGE
Brain Teasers
1. Use a boolean/integer array to check if character is already present in the substring .
2. Append if its the first occurence , if not , break and check for max length !
import javax.swing.JOptionPane;
public class LongestSubString {
public static void main(String []args)
{
new LongestSubString().displayLongestSubString(JOptionPane.showInputDialog("Enter input String :"));
}
public void displayLongestSubString(String main)
{
StringBuffer sub = new StringBuffer();
StringBuffer max = sub;
for(int i = 0;i < main.length();i++)
{
int []bool = new int[256];
for(int k = 0;k < 256;k++)
bool[k] = 0;
for(int j = i;j < main.length();j++)
{
if(bool[main.charAt(j)] == 0)
{
sub.append(main.charAt(j));
bool[main.charAt(j)]++;
}
else
{
break;
}
}
if(sub.length() > max.length())
max = sub;
sub = new StringBuffer();
}
System.out.println("Longest sub string : " + max);
}
}
Use Quick Sort instead of bubble sort.
Also, Instead of concat and check , just check the significant digits and get the order !
public class SortMaxValue {
public static void main(String []args)
{
int []input = {13,54,56,745,45,76,879,12,91,8,9,99,989,543,887};
new SortMaxValue().sortMaxValue(input);
new SortMaxValue().displayArray(input);
}
public void displayArray(int [] input)
{
for(int i = 0;i < input.length;i++)
System.out.print(input[i] + " ");
}
public void sortMaxValue(int []input)
{
for(int i = 0;i < input.length;i++)
{
for(int j = 0;j < input.length - i - 1;j++)
{
if(!compareElements(input[j],input[j+1]))
swap(input,j,j+1);
}
}
}
public boolean compareElements(int input1,int input2) // returns true if input1 has higher precedence over input2(eg . 9 over 83)
{
if(input1 == input2)
return false;
int l1 = noOfDigits(input1);
int l2 = noOfDigits(input2);
int l1copy = l1;
int l2copy = l2;
int i1copy = input1;
int i2copy = input2;
boolean flag;
int n;
if(l1 < l2)
{
n = l1;
flag = true;
}
else
{
n = l2;
flag = false;
}
while(input1 / (int)Math.pow(10,l1-1) == input2 / (int)Math.pow(10,l2-1) && n > 1)
{
input1 %= Math.pow(10,l1-1);
input2 %= Math.pow(10,l2-1);
l1--;
l2--;
n--;
}
if(input1 / (int) Math.pow(10,l1-1) > input2 / (int)Math.pow(10,l2-1))
return true;
else if(input1 / (int) Math.pow(10,l1-1) < input2 / (int)Math.pow(10,l2-1))
return false;
else
{
if(flag)
{
input2 %= Math.pow(10,l2-1);
if(input2 / (int) Math.pow(10,l2-2) >= i2copy / (int) Math.pow(10,l2copy-1))
return false;
else
return true;
}
else
{
input1 %= Math.pow(10,l1-1);
if(input1 / (int) Math.pow(10,l1-2) >= i1copy / (int) Math.pow(10,l1copy-1))
return true;
else
return false;
}
}
}
public int noOfDigits(int n)
{
int digits;
for(digits = 0;n > 0;digits++)
{
n /= 10;
}
return digits;
}
public void swap(int []a,int x,int y)
{
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}
Ya , typing error , its 56*3 + 21*1 , not 23 !
- Buzz Lightyear November 15, 2012You can use a StringBuffer to append if character isn't a duplicate but the above method does'nt use an extra data structure and does it in-place.
- Buzz Lightyear November 15, 2012You are only checking if the previous character and the current character are not same !
What if I give an input like abcda ??
You ll only check if 'a' is different from 'd' before appending to builder !!
This method won't work !
Whats GC intensive ?
- Buzz Lightyear November 15, 2012
JAVA CODE :-
- Buzz Lightyear November 22, 2012