Skip to content

Instantly share code, notes, and snippets.

@theredpea

theredpea/code_challenges_cf.js

Last active October 27, 2023 18:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save theredpea/023219c63ca134612891c171c75878a8 to your computer and use it in GitHub Desktop.
Save theredpea/023219c63ca134612891c171c75878a8 to your computer and use it in GitHub Desktop.
Download ZIP
Code Challenges
Raw
code_challenges_cf.js
/*
Write a function solution that, given a string S consisting of N letters 'a' and/or 'b' returns true when all occurrences of letter 'a' are before all occurrences of letter 'b' and returns false otherwise.
Examples:
1. Given S = "aabbb", the function should return true.
2. Given S = "ba", the function should return false.
3. Given S = "aaa", the function should return true. Note that 'b' does not need to occur in S.
4. Given S = "b", the function should return true. Note that 'a' does not need to occur in S.
5. Given S = "abba", the function should return false.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..300,000];
string S is made only of the characters 'a' and/or 'b'.
*/
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(S) {
// Implement your solution here
var aAfterB = false;
var foundB = false;
var backwardsString = S.split('').reverse();
var latestB = backwardsString.indexOf('b')
var latestA = backwardsString.indexOf('a');
// in case any more efficient:
return latestA == -1 || !(latestA < latestB);
// Array.from(S || '').forEach(function(s){
for (let i= 0; i<S.length; i++) {
s = S[i];
if (s=='b'){
foundB = true;
} else if (s=='a' && foundB) {
aAfterB = true;
// if you find the condition, don't waste time looking for it:
break;
}
}
// });
return !aAfterB;
}
/*
You are given an array A of N integers. You can delete some (possibly zero) of its elements. Then the remaining elements in even positions are added and elements in odd positions are subtracted:
S = A[0] − A[1] + A[2] − A[3] + ...
What is the maximum possible value of S that could be obtained by performing such deletions? As the result may be large, return its last nine digits without leading zeros (in other words, return the result modulo 1,000,000,000).
Write a function:
function solution(A);
that, given an array A of length N, returns the maximum value of S (modulo 1,000,000,000).
Examples:
1. Given A = [4, 1, 2, 3], the function should return 6, because we could delete the third value in A and obtain A = [4, 1, 3]. Then S = 4 − 1 + 3 = 6, which is the maximum possible value of S.
2. Given A = [1, 2, 3, 3, 2, 1, 5], the function should return 7, because for A = [3, 1, 5] we could obtain S = 3 − 1 + 5 = 7.
3. Given A = [1000000000, 1, 2, 2, 1000000000, 1, 1000000000], the function should return 999999998, because for A = [1000000000, 1, 1000000000, 1, 1000000000] we could obtain S = 1000000000 − 1 + 1000000000 − 1 − 1000000000 = 2999999998. That is the maximum possible value of S, but it should be returned modulo 1000000000.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..200,000];
each element of array A is an integer within the range [0..1,000,000,000].
*/
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
window.examples = [
{
input: [4, 1, 2, 3],
output: { remaining: [4, 1, 3], reduction: 6 }
},
{
input: [1, 2, 3, 3, 2, 1, 5],
output: { remaining: [3, 1, 5], reduction: 7 }
},
{
input: [1000000000, 1, 2, 2, 1000000000, 1, 1000000000],
output: { remaining: [1000000000, 1, 1000000000, 1, 1000000000], reduction: 999999998 }
}
];
function get_best(arr) {
var remaining = [];
arr.forEach((current_item, i) => {
var is_would_add = remaining.length % 2 == 0;
var last_taken_item = remaining[remaining.length - 1];
var next_item = arr[i + 1];
if (is_would_add) {
console.log(`add: the current item ${current_item} will be added (net positive); taking the current item`);
remaining.push(current_item);
} else {
if (last_taken_item < current_item) {
console.log(`subtract: last item ${last_taken_item} added *less* than the current item ${current_item} would subtract (net negative); taking the current item instead`);
remaining.pop();
remaining.push(current_item);
} else if (next_item < current_item) {
console.log(`subtract: the next item ${next_item} would be a smaller negative than the current item ${current_item}, ignoring the current item`);
} else {
console.log(`subtract: the current item ${current_item} wont contribute to net negative, nor would the next item be a smaller choice; taking the current item`);
remaining.push(current_item);
}
}
});
return {
remaining,
reduction: remaining.reduce((accumulator, cv, ci) => accumulator + ((ci % 2 == 0) ? cv : -cv), 0) % 1000000000
}
}
window.examples.forEach((example, example_index) => {
var best_output = get_best(example.input);
if (best_output.reduction !== example.output.reduction) {
console.warn(`example ${example_index + 1} failed, expected value is ${example.output.reduction} actual value is ${best_output.reduction}`);
} else {
console.log(`example ${example_index + 1} produced the expected result`);
}
});
/*
Task description
Your task is to provide a suite of tests for an invert function, using Jest framework, covering all the requirements below.
Description of the invert function
invert function accepts a string and returns a string.
When the string is empty it returns empty string.
When the argument passed to the method is null or undefined it returns an empty string
When the string has exactly one character the same string is returned
When the string is longer then 1 character its inverted version is returned.
Examples of invert function usage
const { invert } = require("./inverter");
invert("a"); // returns "a"
invert(null); // returns ""
invert("abcd"); // return "dcba"
Requirements
Your task is to implement a suite of tests in Jest that will test all the possible behaviours of the invert function, as described above.
Your suite of tests will be run against multiple (wrong and correct) implementations of invert function.
All tests must pass for correct implementation. Otherwise you will receive 0%, so make sure that all tests pass for the correct one before submitting the task.
For a wrong implementation of the invert function, at least one of the test cases should fail.
*/
const { invert } = require("./inverter");
describe("invert", () => {
it("returns a single character when given a single character", () => {
expect(invert('a')).toBe('a')
});
it("returns an empty string when given a null value", () => {
expect(invert(null)).toBe('')
});
it("returns an empty string when given an empty string", () => {
expect(invert('')).toBe('')
});
it("returns 'dcba' when given 'abcd", () => {
expect(invert('abcd')).toBe('dcba');
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment