JSFiddle - React, Tailwind, and code Playground

by Tim Ko

JavaScript

sorted array rotated k positions.

5 6 7 8 1 2 3 4


5 6 7 8 9 10 11 1 2 3 4 

12 1 2 3 4 5 6 7 8 9 10 11

check 9 and 10

k = 4

function findRotation(a) {

    if (a.length == 0) {
        return 0;
    }
    
    var i = 0;
    var j = a.length-1;
    var first = a[0];
    
    while(i <= j) {
        var mid = parseInt((i + j) / 2); // check this later
        if (mid+1 <= a.length-1 && a[mid] > a[mid+1]) {
            return mid + 1;
        }
        
        if (first > a[mid]) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }

    return 0;
}


// input: string 
// return: most frequently used words in the string

bat cat dog owl cat dog cat

k = 2

cat dog 


{
   bat: 1,
   cat: 2, 
   dog: 2,
   owl: 1
}

var occurrences = {
   1: [bat, owl],
   2: [cat, dog],
   3: ...  (50 words)
   ...
   50: ... (4 words)
}

k = 52
n = k;

Object.keys(occurrences);
keys = [1,2,3,50]

k = 30
50: 4 words
1: 50 words
2: 3 words
3: 10 words

var size = 0; var top;
for (var i = 0, ln = keys.length; i < ln; i++) {
    heap.push(keys[i]); // to a min heap
    size += occurrences[keys[i]].length;
    top = heap.top();
    
    while (size > k && size - occurrences[top].length > k) {
        heap.pop();
        top = heap.top();
    }
}