Lesson 4 Counting Elements

rimbener · Jun 22, 2020 · 8168dff · 8168dff
1 parent 4c8080d
commit 8168dff
Show file tree

Hide file tree

Showing 8 changed files with 371 additions and 3 deletions.
diff --git a/lesson-3/1-frog-jmp.js b/lesson-3/1-frog-jmp.js
@@ -39,10 +39,12 @@ function solution(X, Y, D) {
     return steps;
 }
 
+let allGood = true;
 function showResults(X, Y, D, expected) {
     const result = solution(X, Y, D);
     const resOK = isEqual(result, expected);
     if (!resOK) {
+        allGood = false;
         console.log(resOK, result, expected);
     }
 }
@@ -51,4 +53,7 @@ showResults(1, 5, 2, 2);
 
 function isEqual(a, b) {
     return a === b;
-}
+}
+if (allGood) {
+    console.log('ALL GOOD!!!')
+}
diff --git a/lesson-3/2-perm-missing-elem.js b/lesson-3/2-perm-missing-elem.js
@@ -75,10 +75,12 @@ function splitArray(array) {
     return resp;
 }
 
+let allGood = true;
 function showResults(A, expected) {
     const result = solution(A);
     const resOK = isEqual(result, expected);
     if (!resOK) {
+        allGood = false;
         console.log(resOK, result, expected);
     }
 }
@@ -116,4 +118,7 @@ function createTestArray(length, missing) {
 
 function isEqual(a, b) {
     return a === b;
-}
+}
+if (allGood) {
+    console.log('ALL GOOD!!!')
+}
diff --git a/lesson-3/3-tape-equilibrium.js b/lesson-3/3-tape-equilibrium.js
@@ -65,10 +65,12 @@ function sum(A) {
     return A.reduce((a, b) => a + b, 0);
 }
 
+let allGood = true;
 function showResults(A, expected) {
     const result = solution(A);
     const resOK = isEqual(result, expected);
     if (!resOK) {
+        allGood = false;
         console.log(resOK, result, expected);
     }
 }
@@ -91,4 +93,7 @@ function createTestArray(length, from, to) {
 
 function isEqual(a, b) {
     return a === b;
-}
+}
+if (allGood) {
+    console.log('ALL GOOD!!!')
+}
diff --git a/lesson-4/1-frog-river-one.js b/lesson-4/1-frog-river-one.js
@@ -0,0 +1,91 @@
+/*
+A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.
+
+You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.
+
+The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.
+
+For example, you are given integer X = 5 and array A such that:
+  A[0] = 1
+  A[1] = 3
+  A[2] = 1
+  A[3] = 4
+  A[4] = 2
+  A[5] = 3
+  A[6] = 5
+  A[7] = 4
+
+In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.
+
+Write a function:
+
+    function solution(X, A);
+
+that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.
+
+If the frog is never able to jump to the other side of the river, the function should return −1.
+
+For example, given X = 5 and array A such that:
+  A[0] = 1
+  A[1] = 3
+  A[2] = 1
+  A[3] = 4
+  A[4] = 2
+  A[5] = 3
+  A[6] = 5
+  A[7] = 4
+
+the function should return 6, as explained above.
+
+Write an efficient algorithm for the following assumptions:
+
+        N and X are integers within the range [1..100,000];
+        each element of array A is an integer within the range [1..X].
+*/
+
+function solution(X, A) {
+    const breakReduce = () => A.splice(1);
+    let sumToEnd = X * (X + 1) / 2;
+    const checkA = new Array(X).fill(false);
+
+    const reducedX = A.reduce((prev, curr, i) => {
+        if (!checkA[curr - 1]) {
+            checkA[curr - 1] = true;
+            sumToEnd -= curr;
+        }
+        if (sumToEnd === 0) {
+            prev = i;
+            breakReduce();
+        }
+        return prev;
+    }, -1)
+    return reducedX;
+}
+
+let allGood = true;
+function showResults(X, A, expected) {
+    const result = solution(X, A);
+    const resOK = isEqual(result, expected);
+    if (!resOK) {
+        allGood = false;
+        console.log(resOK, result, expected);
+    }
+}
+
+showResults(5, [1, 3, 1, 4, 2, 3, 5, 4], 6);
+showResults(3, [1, 3, 1, 3, 2, 1, 3], 4);
+showResults(5, [1, 3, 5, 4, 5, 3, 5, 4, 2], 8);
+showResults(7, [1, 3, 1, 4, 2, 3, 5, 4], -1);
+showResults(5, [], -1);
+showResults(1, [1], 0);
+showResults(2, [1, 2], 1);
+showResults(2, [2, 1], 1);
+showResults(2, [2, 2, 2, 2, 2], -1);
+
+function isEqual(a, b) {
+    return a === b;
+}
+
+if (allGood) {
+    console.log('ALL GOOD!!!')
+}
diff --git a/lesson-4/2-CountingElements.pdf b/lesson-4/2-CountingElements.pdf
diff --git a/lesson-4/2-max-counters.js b/lesson-4/2-max-counters.js
@@ -0,0 +1,114 @@
+/*
+You are given N counters, initially set to 0, and you have two possible operations on them:
+
+        increase(X) − counter X is increased by 1,
+        max counter − all counters are set to the maximum value of any counter.
+
+A non-empty array A of M integers is given. This array represents consecutive operations:
+
+        if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
+        if A[K] = N + 1 then operation K is max counter.
+
+For example, given integer N = 5 and array A such that:
+    A[0] = 3
+    A[1] = 4
+    A[2] = 4
+    A[3] = 6
+    A[4] = 1
+    A[5] = 4
+    A[6] = 4
+
+the values of the counters after each consecutive operation will be:
+    (0, 0, 1, 0, 0)
+    (0, 0, 1, 1, 0)
+    (0, 0, 1, 2, 0)
+    (2, 2, 2, 2, 2)
+    (3, 2, 2, 2, 2)
+    (3, 2, 2, 3, 2)
+    (3, 2, 2, 4, 2)
+
+The goal is to calculate the value of every counter after all operations.
+
+Write a function:
+
+    function solution(N, A);
+
+that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.
+
+Result array should be returned as an array of integers.
+
+For example, given:
+    A[0] = 3
+    A[1] = 4
+    A[2] = 4
+    A[3] = 6
+    A[4] = 1
+    A[5] = 4
+    A[6] = 4
+
+the function should return [3, 2, 2, 4, 2], as explained above.
+
+Write an efficient algorithm for the following assumptions:
+
+        N and M are integers within the range [1..100,000];
+        each element of array A is an integer within the range [1..N + 1].
+*/
+
+function solution(N, A) {
+    /*
+    const resA = new Array(N).fill(0);
+    let max = 0;
+    for (let i = 0; i < A.length; i++) {
+        if (A[i] <= N) {
+            resA[A[i] - 1]++;
+            max = Math.max(max, resA[A[i] - 1]);
+        } else {
+            resA.fill(max);
+        }
+    }
+    return resA;
+*/
+    let max = 0;
+    const resu = A.reduce((acc, cur) => {
+        if (cur < N + 1) {
+            acc[cur - 1] = acc[cur - 1] === undefined ? 1 : acc[cur - 1] + 1;
+            max = Math.max(max, acc[cur - 1]);
+        } else {
+            if (acc.length < N) {
+                acc = new Array(N).fill(max);
+            }
+            else {
+                acc.fill(max);
+            }
+        }
+        return acc
+    }, []);
+    return resu;
+}
+
+let allGood = true;
+function showResults(N, A, expected) {
+    const result = solution(N, A);
+    const resOK = isEqual(result, expected);
+    if (!resOK) {
+        allGood = false;
+        console.log(result, expected);
+    }
+}
+
+showResults(5, [3, 4, 4, 6, 1, 4, 4], [3, 2, 2, 4, 2]);
+showResults(1, [1], [1]);
+
+function isEqual(a, b) {
+    if (a.length != b.length)
+        return false;
+    else {
+        for (var i = 0; i < a.length; i++)
+            if (a[i] != b[i]) return false;
+        return true;
+    }
+}
+
+if (allGood) {
+    console.log('ALL GOOD!!!')
+}
diff --git a/lesson-4/3-missing-integer.js b/lesson-4/3-missing-integer.js
@@ -0,0 +1,59 @@
+/*
+This is a demo task.
+
+Write a function:
+
+    function solution(A);
+
+that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
+
+For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
+
+Given A = [1, 2, 3], the function should return 4.
+
+Given A = [−1, −3], the function should return 1.
+
+Write an efficient algorithm for the following assumptions:
+
+        N is an integer within the range [1..100,000];
+        each element of array A is an integer within the range [−1,000,000..1,000,000].
+
+*/
+
+function solution(A) {
+    aSize = A.length;
+    const auxA = new Array(aSize).fill(false);
+    for (let i = 0; i < A.length; i++) {
+        if (A[i] > 0) {
+            auxA[A[i] - 1] = true;
+        }
+    }
+    let resu = auxA.indexOf(false);
+    if (resu === -1) resu = aSize;
+    return resu + 1;
+}
+
+let allGood = true;
+function showResults(A, expected) {
+    const result = solution(A);
+    const resOK = isEqual(result, expected);
+    if (!resOK) {
+        allGood = false;
+        console.log(resOK, result, expected);
+    }
+}
+
+showResults([2, 3], 1);
+showResults([], 1);
+showResults([1], 2);
+showResults([1, 3, 6, 4, 1, 2], 5);
+showResults([1, 3, 6, 4, 1, 7], 2);
+showResults([1, 2, 3], 4);
+showResults([-1, -3], 1);
+
+function isEqual(a, b) {
+    return a === b;
+}
+if (allGood) {
+    console.log('ALL GOOD!!!')
+}