Steve Breese

Count the number of occurrences for each charater in a string and sort the results

In this coding problem, you are given a list of values (can be strings, numbers, etc.) and you are asked to determine most frequently occoring item in the list, the second most frequently occuring item, and so on. Here are 5 possible solutions, ordered from least to highest performant.

ES3 - Nested for loops

                     
const list = [3, 'a', 'a', 'a', 2, 3, 'a', 3, 'a', 2, 4, 9, 3];
const countArray = [];
const uniqueList = [];
let matchCount;
for (let i = 0; i < list.length; i++) {
    matchCount = 1;
    item = list[i];

    if (uniqueList.includes(item)) {
    continue;
    }

    uniqueList.push(item);
    for (let j = i + 1; j < list.length; j++) {      
      if (item == list[j]) {
        matchCount++;
      }
    }
    countArray.push({name: item, count: matchCount});
}

countArray.sort((a, b) => {
    return b.count - a.count;
});

console.log(countArray);
                            

ES5 - conditional (ternary) operator

 
const list = [3, 'a', 'a', 'a', 2, 3, 'a', 3, 'a', 2, 4, 9, 3];
const counts = {};

for (let i = 0; i < list.length; i++) {
    let item = list[i];
    counts[item] = counts[item] ? {name: item, count: counts[item].count + 1 } : {name: item, count: 1};
}

const countArray = Object.values(counts);

countArray.sort((a, b) => {
    return b.count - a.count;
});

console.log(countArray);

ES6 - forEach

const string = "Can you count how many or each character?"

// 1 - split / spread the string
const charArray = [...string] // string.split('')

// 2 - iterate over each character
const counts = {}
charArray.forEach(char => {
  counts[char] = counts[char] ? ++counts[char] : 1
})

// 3 - Sort the array
const sortable = Object.entries(counts)

sortable.sort((a,b) => a[1] - b[1])

// 4 - Restore to the object
const sortedObject = {}
sortable.forEach(charEntry => {
  sortedObject[charEntry[0]] = charEntry[1]
})

console.log(sortedObject)

ES7 - reduce

const string = "Can you count how many or each character?"

// 1 - iterate over each character
const counts = [...string].reduce((accum, char) => {
accum[char] = accum[char] ? ++accum[char] : 1
  return accum
}, {})


// 2 - Sort the array
const sortable = Object.entries(counts)

sortable.sort((a,b) => a[1] - b[1])

// 3 - Restore to the object
const sortedObject = {}
sortable.forEach(charEntry => {
  sortedObject[charEntry[0]] = charEntry[1]
})

console.log(sortedObject)

Flood Fill

Problem: Given a grid, location of a pixel in the screen and a color, replace color of the given pixel and all adjacent same colored pixels with the given color.

Solution

const matrix = [
    [{color: 'green'},{color: 'green'}, {color: 'green'}],
    [{color: 'blue'}, {color: 'blue'}, {color: 'green'}],
    [{color: 'blue'}, {color: 'green'}, {color: 'green'}]
];

const floodfill = (x, y, oldColor, newColor) => {
    let theStack = [{x, y}]

    while (theStack.length > 0) {
        let {x, y} = theStack.pop();

        if (!matrix[x] || !matrix[x][y] || matrix[x][y].color != oldColor) {
            continue;
        }
        matrix[x][y].color = newColor;

        theStack.push( { x: x + 1, y } );  // right
        theStack.push( { x: x - 1, y } );  // left
        theStack.push( { x, y: y + 1 } );  // down
        theStack.push( { x, y: y - 1 } );  // up   
    }        
}
        
floodfill(0, 0, 'green', 'red');

console.log("Matrix green is now red:");
console.log(matrix);

Maximum Number of Connected Colors

Problem: Given a grid, find the maximum number of connected colors.

Solution

  
const matrix = [
    [{color: 'green'},{color: 'green'}, {color: 'green'}],
    [{color: 'blue'}, {color: 'blue'}, {color: 'green'}],
    [{color: 'blue'}, {color: 'green'}, {color: 'green'}]
];


const floodFillCount = (x, y, color) => {
    let cnt = 0;
    const stack = [{x, y}];

    while (stack.length > 0) {
        const {x, y} = stack.pop();

        if (!matrix[x] || !matrix[x][y] || matrix[x][y].color !== color || matrix[x][y].counted) {
        continue;
        }
        cnt++;

        matrix[x][y].counted = true;

        stack.push({x: x - 1, y});
        stack.push({x: x + 1, y});
        stack.push({x, y: y - 1});
        stack.push({x, y: y + 1});
    }
    return cnt;
}

console.log(floodFillCount(0, 0, 'green'));