fenghanlu
BAN USER- 1of 1 vote
AnswersThe third question is a brain teaser: if 1000 couples are to give birth to male and female babies(50% change each), and they would keep giving birth until they have a girl, what's the boy to girl ratio in 20 years
- fenghanlu in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer
import java.util.HashMap;
/*Given a string (1-d array) , find if there is any sub-sequence that repeats itself.
Here, sub-sequence can be a non-contiguous pattern, with the same relative order.
Eg:
1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice */
public class SubReaptArray {
public static void main(String[] args) {
String test ="abddabc";
// System.out.println(test.indexOf("a",1));
SubReaptArray mSbucheck = new SubReaptArray();
System.out.println(mSbucheck.checkSubArray(test));
}
boolean checkSubArray(String input){
if(input.length()==1)
return false;
for(int i =0;i<input.length();i++){
char startValue = input.charAt(0);
int second = input.indexOf(startValue, i+1);
if(second == -1)
continue;
int third = input.indexOf(startValue, input.length()-1>second?second+1:second);
boolean value = checkRepeat(input,i,second, (third==-1)?input.length()-1:third);
if(value)
return true;
}
return false;
}
public boolean checkRepeat(String input, int start, int second, int third){
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(++start;start<second;start++){
map.put(input.charAt(start), 1);
}
for(++second;second<third;second++){
char mvalue = input.charAt(second);
if(map.containsKey(mvalue))
return true;
}
return false;
}
}
import java.util.HashMap;
/*Given a string (1-d array) , find if there is any sub-sequence that repeats itself.
Here, sub-sequence can be a non-contiguous pattern, with the same relative order.
Eg:
1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice */
public class SubReaptArray {
public static void main(String[] args) {
String test ="abddabc";
// System.out.println(test.indexOf("a",1));
SubReaptArray mSbucheck = new SubReaptArray();
System.out.println(mSbucheck.checkSubArray(test));
}
boolean checkSubArray(String input){
if(input.length()==1)
return false;
for(int i =0;i<input.length();i++){
char startValue = input.charAt(0);
int second = input.indexOf(startValue, i+1);
if(second == -1)
continue;
int third = input.indexOf(startValue, input.length()-1>second?second+1:second);
boolean value = checkRepeat(input,i,second, (third==-1)?input.length()-1:third);
if(value)
return true;
}
return false;
}
public boolean checkRepeat(String input, int start, int second, int third){
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(++start;start<second;start++){
map.put(input.charAt(start), 1);
}
for(++second;second<third;second++){
char mvalue = input.charAt(second);
if(map.containsKey(mvalue))
return true;
}
return false;
}
}
i think just like this for example "1234976" find the biggest continous two digits(if both of them are bigger than the first digit ,we beleve it is continous: 9>1,7>1) and then swap it with the first,
The result is: 97 23416
The left part(23416) recursive using the above method.
If we find the digit that is not continous, we just swap it with the first (6>1),
The result is 97 (6 3412)
Time is O(n^2)
Find the appear postion "First", "second" and "third".
And compare the value between ("First", "second") and ("second", "third"). Do they repeat or not!
- fenghanlu November 11, 2014