dereknheiley
BAN USERyou can edit this solution at ideone.com/iu9EEK
... don't mind the odd syntax highlighting, it's valid python that runs fine
i had initially used avg, then i found i needed to recalculate the avg, then i found that it wasn't able to find optimal solution if there was an extreme outlier in the array, median seems to work best
comments welcome!
#O(n)
def median(A):
#since we know universe of values in A
maxValue = 100
vals = [0]*(maxValue+1) #we'll ignore index 0
#build histogram of values
n = len(A)
for i in xrange(n):
vals[A[i]] += 1
#build sorted list from histogram
sorted = [0]*n
ptr = 0
for i in xrange(1,(maxValue+1)): #ignoring index 0
for j in xrange(vals[i]):
sorted[ptr] = i
ptr += 1
if n%2==0: #compute median value
return (sorted[n/2] + sorted[n/2 -1])/float(2)
else: #get median value
return sorted[n/2]
#O(n)
def adjust(A, target):
adj = 0
n = len(A)
if n>1:
med = median(A)
for i in xrange(n-1):
diff = abs(A[i] - A[i+1])
if diff>target:
first = abs(A[i]-med)
second = abs(A[i+1]-med)
if first > second:
newadj = diff-target
adj +=newadj
A[i] = A[i]+newadj if A[i]<med else A[i]-newadj
else: #second > first
newadj = diff-target
adj +=newadj
A[i+1] = A[i+1]+newadj if A[i+1]<med else A[i+1]-newadj
return adj
#test it
print adjust( [1,4,2,3] , 1) # 2
print adjust( [1,2,3,2,1] , 1) # 0
print adjust( [1,2,4,2,1] , 1) # 1
print adjust( [3,7,4,2,5,1] , 2) # 4
print adjust( [1,1,1,90] , 2) # 87
print adjust( [3,7,4,2,5,90], 2) # 86
this doesn't make sense to me, your foreign key O.Cust_id should never be null, that's violating referential integrity, furthermore, C.Cust_id should also never be null if it's the primary key of the customer table
- dereknheiley December 11, 2014you can't use -1 for the default max, what if your array only goes from -10 to -5?
- dereknheiley November 25, 2014yup, i forgot the base case entirely too, kind of an important part, but you also don't need to check both directions for the second if / elseif.... and you need to add start to your new mid in the else
- dereknheiley November 25, 2014good point, it's not logn, but it is dependent on the array and the search value, meaning that subsets of the array are skipped over, the tricky part is that it could be in both sides
- dereknheiley November 25, 2014// O(1) for every case except
// O(logn) finding max in increase-decrease case
n = a.Length
if (n > 1) {
front = ""
tail = ""
//compare first and second element
if (a[0] < a[1]) { front="increasing" }
if (a[0] > a[1]) { front="decreasing" }
//compare last and second last elements
if (a[n-1] < a[n-2]) { tail="decreasing" }
if (a[n-1] > a[n-2]) { tail="increasing" }
//where they the same
if (front == tail) {
print front
//max must be one of the ends
if (front == "increasing"){
print "max: " + a[n-1]
}
else {
print "max: " + a[0]
}
}
else {
print front +"-"+ tail
if (front=="decreasing" && tail=="increasing" ) {
//max must be one of the ends
if ( a[0] > a[n-1]) {
print "max: " + a[0]
}
else {
print "max: " + a[n-1]
}
}
else {
//max is somewhere in the middle at the inflextion point
max = a[1]
max = binaryMaxSearch(a, max, 1, (n-3)/2+1, n-2)
print "max: " + max
}
}
}
int binaryMaxSearch([] a, start, mid, end) {
//check for inflextion point
if (a[mid-1] < a[mid] && a[mid] > a[mid + 1]) {
return a[mid]
}
//not found so keep looking
if (a[mid] < a[mid + 1]) { //go right
return binaryMaxSearch(a, mid, (end-mid)/2+mid, end)
}
else { // go left
return binaryMaxSearch(a, start, (mid-start)/2+start, mid)
}
}
//Naive O(n)
int find(int value, int[] a) {
int n = a.Length;
for (int i=0; i<n; i++) {
if (value==a[i])
return i;
}
return -1;
}
//binary search ... ish
int find(value, a) {
int n = a.Length;
Queue q = new Queue();
q.Enqueue({ 0,n/2,n }); // START,MID,END of a subrange to search
while (q.Count > 0) {
int[] sub = q.Pop();
int start=sub[0], mid=sub[1], end=sub[2];
if (a[mid]==value) {
return mid;
}
int gap = mid - start;
int range = Math.Abs(a[mid]-value);
if (gap>=range) {
q.append( (mid-start)/2+start, start, mid);
}
gap = end-mid;
if (gap>=range) {
q.append( (mid-start)/2+mid, mid, end);
}
}
return -1;
}
//index 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18
int[] a = {7,8,9,8,8,7,6,5,4,5,5,4,3,3,2,2,4,5,6}
int i = find(2, a);
System.Console.WriteLine(i); //output 14
good counter example!
- dereknheiley December 18, 2014