All complete until lesson 7

rimbener · Jul 4, 2020 · beccbca · beccbca
1 parent 8168dff
commit beccbca
Show file tree

Hide file tree

Showing 18 changed files with 982 additions and 0 deletions.
diff --git a/2-task.js b/2-task.js
@@ -0,0 +1,46 @@
+// you can write to stdout for debugging purposes, e.g.
+// console.log('this is a debug message');
+
+function solution(S) {
+    // write your code in JavaScript (Node.js 8.9.4)
+    const isValidSegment = segment => (!isNaN(segment) && segment < 256);
+    const extractSegment = (curS, topIndex) => parseInt(curS.substring(0, topIndex));
+    const extractRest = (curS, topIndex) => curS.substring(topIndex, curS.length);
+
+    const snapshotIp = (validIp, S, curIndex, path, segment) => {
+        if (segment === 4 && curIndex === S.length) {
+            validIp.push(path[0] + '.' + path[1] + '.' + path[2] + '.' + path[3]);
+            return;
+        } else if (segment === 4 || curIndex === S.length) {
+            return;
+        }
+        for (let len = 1; len <= 3 && curIndex + len <= S.length; len++) {
+            const snapshot = S.substring(curIndex, curIndex + len);
+            const value = parseInt(snapshot);
+            if (value > 255 || len >= 2 && S.charAt(curIndex) === '0') {
+                break;
+            }
+            path[segment] = value;
+            snapshotIp(validIp, S, curIndex + len, path, segment + 1);
+            path[segment] = -1;
+        }
+    }
+    const validIp = [];
+    snapshotIp(validIp, S, 0, [], 0);
+    return validIp.length;
+}
+
+function showResults(S, expected) {
+    const result = solution(S);
+    const resOK = isEqual(result, expected);
+    //    if (!resOK) {
+    console.log(resOK, result, expected);
+    //  }
+}
+showResults('4216712120', 2);
+showResults('255255255255', 1);
+showResults('188212', 8);
+
+function isEqual(a, b) {
+    return a === b;
+}
diff --git a/lesson-5/1-count-div.js b/lesson-5/1-count-div.js
@@ -0,0 +1,58 @@
+/*
+Write a function:
+
+    function solution(A, B, K);
+
+that, given three integers A, B and K, returns the number of integers within the 
+range [A..B] that are divisible by K, i.e.:
+
+    { i : A ≤ i ≤ B, i mod K = 0 }
+
+For example, for A = 6, B = 11 and K = 2, your function should return 3, 
+because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.
+
+Write an efficient algorithm for the following assumptions:
+
+        A and B are integers within the range [0..2,000,000,000];
+        K is an integer within the range [1..2,000,000,000];
+        A ≤ B.
+*/
+
+function solution(A, B, K) {
+    let firstDivisible;
+    for (let i = A; i < B + 1; i++) {
+        if ((i % K) === 0) {
+            firstDivisible = i;
+            i = B + 1;
+        }
+    }
+    if (firstDivisible === undefined) {
+        return 0;
+    }
+    const res = Math.trunc((B - firstDivisible) / K) + 1;
+    return res;
+}
+
+let allGood = true;
+function showResults(A, B, K, expected) {
+    const result = solution(A, B, K);
+    const resOK = isEqual(result, expected);
+    if (!resOK) {
+        allGood = false;
+        console.log(resOK, result, expected);
+    }
+}
+
+console.log('START');
+showResults(6, 11, 2, 3);
+showResults(6, 19, 6, 3);
+showResults(11, 11, 2, 0);
+showResults(6, 11, 20, 0);
+showResults(0, 2000000000, 1, 2000000001);
+
+function isEqual(a, b) {
+    return a === b;
+}
+if (allGood) {
+    console.log('ALL GOOD!!!')
+}
diff --git a/lesson-5/2-genomic-range-query.js b/lesson-5/2-genomic-range-query.js
@@ -0,0 +1,91 @@
+/*
+A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?
+
+The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).
+
+For example, consider string S = CAGCCTA and arrays P, Q such that:
+    P[0] = 2    Q[0] = 4
+    P[1] = 5    Q[1] = 5
+    P[2] = 0    Q[2] = 6
+
+The answers to these M = 3 queries are as follows:
+
+        The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
+        The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
+        The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.
+
+Write a function:
+
+    function solution(S, P, Q);
+
+that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.
+
+Result array should be returned as an array of integers.
+
+For example, given the string S = CAGCCTA and arrays P, Q such that:
+    P[0] = 2    Q[0] = 4
+    P[1] = 5    Q[1] = 5
+    P[2] = 0    Q[2] = 6
+
+the function should return the values [2, 4, 1], as explained above.
+
+Write an efficient algorithm for the following assumptions:
+
+        N is an integer within the range [1..100,000];
+        M is an integer within the range [1..50,000];
+        each element of arrays P, Q is an integer within the range [0..N − 1];
+        P[K] ≤ Q[K], where 0 ≤ K < M;
+        string S consists only of upper-case English letters A, C, G, T.
+*/
+
+/*
+A1
+C2
+G3
+T4
+*/
+function solution(S, P, Q) {
+  let returnList = [];
+  for (let i = 0; i < P.length; i++) {
+    const impactList = S.substring(P[i], Q[i] + 1);
+    if (impactList.search('A') !== -1) {
+      returnList.push(1);
+    } else if (impactList.search('C') !== -1) {
+      returnList.push(2);
+    } else if (impactList.search('G') !== -1) {
+      returnList.push(3);
+    } else if (impactList.search('T') !== -1) {
+      returnList.push(4);
+    }
+  }
+  return returnList;
+}
+
+let allGood = true;
+function showResults(A, B, K, expected) {
+  const result = solution(A, B, K);
+  const resOK = isEqual(result, expected);
+  if (!resOK) {
+    allGood = false;
+    console.log(resOK, result, expected);
+  }
+}
+
+console.log('START');
+
+showResults('CAGCCTA', [2, 5, 0], [4, 5, 6], [2, 4, 1]);
+
+function isEqual(a, b) {
+  if (a.length === 0 && b.length !== 0) {
+    return false;
+  }
+  let equal = true;
+  for (let i = 0; i < a.length; i++) {
+    if (a[i] !== b[i]) {
+      equal = false;
+    }
+  }
+  return equal;
+}
+if (allGood) console.log('ALL GOOD!!!')
+
diff --git a/lesson-5/3-PrefixSums.pdf b/lesson-5/3-PrefixSums.pdf
diff --git a/lesson-5/3-min-avg-two-slice.js b/lesson-5/3-min-avg-two-slice.js
@@ -0,0 +1,87 @@
+/*
+A non-empty array A consisting of N integers is given. 
+A pair of integers (P, Q), such that 0 ≤ P < Q < N, 
+is called a slice of array A (notice that the slice contains at least two elements). 
+The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. 
+To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).
+
+For example, array A such that:
+    A[0] = 4
+    A[1] = 2
+    A[2] = 2
+    A[3] = 5
+    A[4] = 1
+    A[5] = 5
+    A[6] = 8
+
+contains the following example slices:
+
+        slice (1, 2), whose average is (2 + 2) / 2 = 2;
+        slice (3, 4), whose average is (5 + 1) / 2 = 3;
+        slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
+
+The goal is to find the starting position of a slice whose average is minimal.
+
+Write a function:
+
+    function solution(A);
+
+that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.
+
+For example, given array A such that:
+    A[0] = 4
+    A[1] = 2
+    A[2] = 2
+    A[3] = 5
+    A[4] = 1
+    A[5] = 5
+    A[6] = 8
+
+the function should return 1, as explained above.
+
+Write an efficient algorithm for the following assumptions:
+
+        N is an integer within the range [2..100,000];
+        each element of array A is an integer within the range [−10,000..10,000].
+*/
+
+let positionOfMin = 0;
+let min = Number.MAX_VALUE;
+
+function solution(A) {
+  for (let a = 0; a < A.length - 2; a++) {
+    checkIfMin((A[a] + A[a + 1]) / 2, a);
+    checkIfMin((A[a] + A[a + 1] + A[a + 2]) / 3, a);
+  }
+
+  checkIfMin((A[A.length - 2] + A[A.length - 1]) / 2, A.length - 2);
+  return positionOfMin;
+}
+
+function checkIfMin(val, a) {
+  if (val < min) {
+    positionOfMin = a;
+    min = val;
+  }
+}
+
+
+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);
+  }
+}
+
+console.log('START');
+
+showResults([4, 2, 2, 5, 1, 5, 8], 1);
+
+function isEqual(a, b) {
+  return a === b;
+}
+if (allGood) console.log('ALL GOOD!!!')
+
diff --git a/lesson-5/4-passing-cars.js b/lesson-5/4-passing-cars.js
@@ -0,0 +1,80 @@
+/*
+A non-empty array A consisting of N integers is given. 
+The consecutive elements of array A represent consecutive cars on a road.
+
+Array A contains only 0s and/or 1s:
+
+        0 represents a car traveling east,
+        1 represents a car traveling west.
+
+The goal is to count passing cars. 
+We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, 
+is passing when P is traveling to the east and Q is traveling to the west.
+
+For example, consider array A such that:
+  A[0] = 0
+  A[1] = 1
+  A[2] = 0
+  A[3] = 1
+  A[4] = 1
+
+We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
+
+Write a function:
+
+    function solution(A);
+
+that, given a non-empty array A of N integers, returns the number of pairs of passing cars.
+
+The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.
+
+For example, given:
+  A[0] = 0
+  A[1] = 1
+  A[2] = 0
+  A[3] = 1
+  A[4] = 1
+
+the function should return 5, as explained above.
+
+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 that can have one of the following values: 0, 1.
+*/
+
+function solution(A) {
+  const east = 0;
+  const firstEast = A.indexOf(east);
+
+  let count = 0;
+  for (let i = firstEast; i < A.length; i++) {
+    const direction = A[i];
+    if (direction === east) {
+      const passingCars = A.slice(i + 1, A.length).filter(el => el !== direction).length;
+      count += passingCars;
+    }
+  }
+  return count;
+}
+
+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);
+  }
+}
+
+console.log('START');
+
+showResults([0, 1, 0, 1, 1], 5);
+showResults([1, 0], 0);
+
+function isEqual(a, b) {
+  return a === b;
+}
+if (allGood) console.log('ALL GOOD!!!')
+