theclish
BAN USERMaintain a heap for each cost so you don't have to keep re-heapifying to figure out which F(t, c) to remove. You'll still have to scan through the heap tops to find the next one to remove. This obviously only works if you have cost categories. If every item has a unique cost then this becomes a list.
- theclish August 13, 2015public static int[] revSort(int...values) {
int idxMax;
boolean sorted = false;
for(int flips=0; flips < values.length; flips++) {
idxMax = 0;
sorted = true;
for(int idx=0; idx < values.length - flips; idx++) {
if(values[idxMax] < values[idx]) {
idxMax = idx;
}
else if(values[idxMax] > values[idx]) {
sorted = false;
}
}
if(sorted) {
break;
}
while(idxMax < values.length-1-flips && values[idxMax] == values[values.length-1-flips]) {
flips++;
}
if(idxMax == values.length-1-flips) {
continue;
}
rev(values, idxMax);
rev(values, values.length-1-flips);
}
return values;
}
static void rev(int[] values, int upper) {
int lower=0;
while(lower < upper) {
swap(values, lower++, upper--);
}
}
static void swap(int[] values, int idx1, int idx2) {
int tmp = values[idx1];
values[idx1] = values[idx2];
values[idx2] = tmp;
}
I don't see anything that beats a simple combinatoric approach.
/**
* @param max indices of the maximum list of disjoint sets
* @param disjoint the union of all used sets
* @param used indices of the sets included in the disjoint set. HashSet isn't necessarily efficient, but it's simple
* @return indices of the maximum number of disjoint sets
*/
public Set<Integer> getDisjointSets(Set<Integer> max,
Set<Integer> disjoint,
Set<Integer> used,
int idx,
List<Set<Integer>> sets) {
if(max.size() < used.size()) {
max.clear();
max.addAll(used);
}
// while used has a chance to beat max
for(; idx < sets.size() && max.size() < used.size() + (sets.size()-idx); idx++) {
Set<Integer> set = sets.get(idx);
if(!set.stream().anyMatch(item->disjoint.contains(item))) {
disjoint.addAll(set);
used.add(idx);
getDisjointSets(max, disjoint, used, idx+1, sets);
used.remove(idx);
disjoint.removeAll(set);
}
}
return max;
}
It can be a set cover problem if our universe={P1, P2, ..., Pn} and we turn the product/seller mappings over so that 1={P1}, 2={P1, P2}, ... Then we can find the minimum sellers to cover the product universe.
Not many products and sellers so probably just make it a simple combinatoric problem saving only the minimum set of sellers.
Maybe this is actually the answer they were looking for. It definitely finds the minimum number of swaps to sort the array. They didn't ask to sort the array in the minimum number of swaps.
My current algorithm sorts most arrays in the fewest swaps but fails miserably on some contrived arrays (specifically the two examples you list).
Maybe they're being cute and want you to realize that 'null' is a valid delimiter...
str3 = str1 + null + str2 + null +null
You can contrive two scenarios: str1="a", str2="" and str1="", str2="a". Without a delimiter there is no way to tell the difference between the resulting str3's.
- theclish August 08, 2015It seems you can just add 1 and walk from right to left and every time you encounter two 1's together shift right, add 1, and shift back left.
public static int getNextSparse(int in) {
int num = in + 1;
int mask = 0b11;
int shift = 0;
while(0 <= Integer.compareUnsigned(num, mask)) {
if((num & mask) == mask) {
num = ((num >> shift) + 1) << shift;
}
mask <<= 1;
shift++;
}
return num;
}
If you happen not to remember your Taylor series during the interview you can always fall back on a binary search.
public static double sqrt(double val) {
double sqrt = val/Math.log(val);
while(Math.abs(val - sqrt*sqrt) > TOLERANCE) {
sqrt = (sqrt + val/sqrt)/2;
}
return Math.abs(sqrt);
}
- theclish August 14, 2015