svarvel
BAN USERA simple solution in java. Worst case is O(n). Logic is the same of merge in MergeSort: we have two index i,j that move in the two arrays as minimum element is found respectively. We need an additional check for duplicate elements. This is a simple loop to move pointers to an element which is bigger than current minimum.
private static int findKSmallest(int[] arr1, int[] arr2, int k) {
int i = 0;
int j = 0;
int min = -1;
while (k > 0){
while (arr1[i] <= min)
i++;
while (arr2[j] <= min)
j++;
if (arr1[i] < arr2[j]){
min = arr1[i];
i++;
}else{
min = arr2[j];
j++;
}
k--;
}
return min;
}
A very simple idea would be to use an hashset, i.e., O(1) for both insertion and lookup. Time slotting need to be predefined, or it can be hard to nadle collision between a meeting starting at 9:01 vs a meeting starting at 9. So, if we decide resolution is half an hour, meeting 9-->10 would occupy two entries in hashSet (9_930 and 930_10).
Example in java below (well, not really much to do)
// slots are represented as string "tStart_tEnd"
private static void meetingSchedule(List<String> l ){
Set<String> calendar = new HashSet<String>();
for (String str: l){
if (calendar.contains(str))
System.out.println("Meeting already scheduled");
else
calendar.add(str);
}
}
A solution in Java making two assumptions: 1) characters are [a-z], 2) no letter repetition. Extending from 1 is easy: just use larger freq and location arrays. Extending from 2 requires location to be an array of list since for each character there might be multiple possible location candidates. It then also requires modification to the algorithm to explore the different possible path, whereas with assumption 1 there is only a single path.
// assumption, [a-z]
private static boolean anaStrStr (String needle, String haystack){
if (haystack.length() < needle.length())
return false;
int [] freq = new int[26];
int [] location = new int[26];
for (int i = 0; i < haystack.length(); i++){
freq[(int)haystack.charAt(i)-'a'] ++;
location[(int)haystack.charAt(i)-'a'] = i;
}
int s = Integer.MAX_VALUE;
int e = 0;
for (int i = 0; i < needle.length(); i++){
if ( freq[(int)needle.charAt(i)-'a'] == 0)
return false;
freq[(int)needle.charAt(i)-'a']--;
int loc = location[(int)needle.charAt(i)-'a'];
if ( loc == (s-1) || location[(int)needle.charAt(i)-'a'] == (e+1) || s == Integer.MAX_VALUE || e == 0){
s = Math.min(s, location[(int)needle.charAt(i)-'a']);
e = Math.max(e, location[(int)needle.charAt(i)-'a']);
} else {
return false;
}
}
return true;
}
A simple solution in Java
- svarvel February 26, 2014