simplysou
BAN USER- 0of 0 votes
AnswersGiven an array of positive, unique, increasingly sorted numbers A, e.g. A = [1, 2, 3, 5, 6, 8, 9, 11, 12, 13]. Given a positive value K, e.g. K = 3. Output all pairs in A that differ exactly by K.
- simplysou in United States
e.g. 2, 5
3, 6
5, 8
6, 9
8, 11
9, 12
what is the runtime for your code?| Report Duplicate | Flag | PURGE
Facebook Software Developer
//Run time = O(N)
public void findDiff(int[] a, int k){
if(a.length < 2 ){
return; //No result
}
int lPtr = 0;
int rPtr = 1;
while(lPtr < a.length-1 && rPtr < a.length){
if(a[rPtr] - a[lPtr] < k){
rPtr++;
}else if(a[rPtr] - a[lPtr] > k){
lPtr++;
rPtr = lPtr + 1;
}else{
System.out.println(a[lPtr] + ", " + a[rPtr]);
lPtr++;
rPtr = lPtr + 1;
}
}
}
/*
* runtime = 2N
*/
public void findPairs(int[] a, int k){
if(a.length < 2 ){
return; //No result
}
int previous= 1;
for(int i = 0; i < a.length; i++){
for(int j = previous; j < a.length; j++){
previous = j;
if(a[j] - a[i] > k ){
break;
}else if(a[j] - a[i] == k){
System.out.println(a[i] +", "+a[j]);
break;
}
}
}
}
- simplysou October 06, 2015
This is the DP solution using memorized Map with recursion. Assuming we given a dictionary of words.
- simplysou November 06, 2015public class SegmentString {
Map<String, String> memorized = new HashMap<String, String>();
public String segmentString(String input, Set<String> dictonary){
if(dictonary.contains(input))return input;
if(memorized.get(input) != null){
return memorized.get(input);
}
int length = input.length();
for(int i = 1; i < length; i++){
String prefix = input.substring(0,i);
if(dictonary.contains(prefix)){
String suffix = input.substring(i, length);
String segmentString = segmentString(suffix, dictonary);
if(segmentString!=null){
memorized.put(input, prefix + " " + segmentString);
return prefix+" "+segmentString;
}
}
}
memorized.put(input, null);
return null;
}
public static void main(String[] args){
SegmentString seg = new SegmentString();
Set<String> dictonary = new HashSet<String>();
dictonary.add("hello");
dictonary.add("ate");
dictonary.add("a");
dictonary.add("an");
dictonary.add("ant");
dictonary.add("i");
System.out.println(seg.segmentString("iateanant", dictonary));
}
}