Created
March 27, 2014 05:33
-
-
Save zahid/9800989 to your computer and use it in GitHub Desktop.
Sevenify Problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* This is my implementation of the problem regarding replacing the element in the row and column of each instance of a 7 with 7s. I did this without allocating extra memory by just keeping track of the rows and columns that needed to be 'sevenified' and I did it in the end in one pass, therefore not having to rewrite 7s over and over again. My efficiency for sevenify's element reassignment, at the worst case, is O(m+n) or O((m+n) + (m*n)) if you include the cycles to create the locations hash. | |
I would test this by checking that: | |
- clone works properly (I tested to check for deep copying) | |
- test fillRow (and fillColumn) work on a single row (and column) with no 7s present | |
- test fillRow (and fillColumn) work on a single row (and column) with one 7 present | |
- test fillRow (and fillColumn) work on a single row (and column) with all elements set to 7 | |
zahid mahir | |
*/ | |
var cloneMatrix = function (matrixx) { | |
var clonedMatrix = []; | |
for (var i = 0; i < matrixx.length; i++) { | |
clonedMatrix[i] = matrixx[i].slice(0); | |
} | |
return clonedMatrix; | |
}; | |
var fillRow = function (arr, row) { | |
for (var i = 0; i < arr[0].length; i++) { | |
arr[row][i] = 7; | |
} | |
}; | |
var fillColumn = function (arr, column) { | |
for (var i = 0; i < arr.length; i++) { | |
arr[i][column] = 7; | |
} | |
}; | |
var matrixToString = function (matrixx) { | |
var dump = ''; | |
matrixx.forEach(function (col) { | |
col.forEach(function (element) { | |
dump += element + ' '; | |
}); | |
dump += '\n'; | |
}); | |
return dump; | |
}; | |
var sevenify = function (matrixx) { | |
var clonedMatrix = cloneMatrix(matrixx); | |
var locations = { | |
rows : {}, | |
columns : {} | |
}; | |
for (var i = 0; i < matrixx.length; i++) { | |
for (var j = 0; j < matrixx[0].length; j++) { | |
if(matrixx[i][j] == 7) { | |
locations.rows[i] = true; | |
locations.columns[j] = true; | |
} | |
} | |
} | |
for (var row in locations.rows) { | |
fillRow(clonedMatrix, row); | |
} | |
for (var column in locations.columns) { | |
fillColumn(clonedMatrix, column); | |
} | |
return clonedMatrix; | |
}; | |
// assume standard n x m matrix | |
var testMatrix = [ | |
[1, 8, 1, 4, -1], | |
[2, 3, 8, 2, 1], | |
[8, 3, 1, 7, 7] | |
]; | |
console.log('original'); | |
console.log(matrixToString(testMatrix)); | |
var sevenifiedMatrix = sevenify(testMatrix); | |
console.log('sevenified'); | |
console.log(matrixToString(sevenifiedMatrix)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment