Andrey Yeliseyev
BAN USERYour solution does not work. Here is code.
It does not count mat[3][2] & mat[1][6] items.
And it does not return items of result area as well.
var mat = [];
mat[0] = [1, 1, 0, 0, 0, 0, 0, 0, 0];
mat[1] = [1, 1, 0, 1, 1, 1, 1, 0, 1];
mat[2] = [0, 0, 0, 0, 0, 1, 0, 0, 1];
mat[3] = [1, 1, 1, 0, 0, 1, 1, 0, 1];
mat[4] = [1, 1, 0, 0, 1, 1, 1, 0, 1];
mat[5] = [1, 1, 1, 0, 0, 0, 0, 0, 1];
function findMaxArea(mat) {
var result = null;
var mat2 = [];
for (var row = 0; row < mat.length; row += 1) {
mat2[row] = [];
for(var column =0; column < mat[row].length; column+=1) {
if (mat[row][column] == 1) {
mat2[row][column] = 1 + (row - 1 >= 0 ? mat2[row - 1][column] : 0) + (column - 1 >= 0 ? mat2[row][column - 1] : 0);
if (result == null || result < mat2[row][column]) {
result = mat2[row][column];
}
}
}
}
return result;
}
var result = findMaxArea(mat);
JavaScript implementation
1. sort array
2. find the best split of array into 2 intervals. Split second interval recursively in order to find the best split for K groups
//var items = [1, 1, 2, 3, 4, 4, 5, 6, 7, 9, 15];
var items = [1, 2, 5, 7];
var k = 2;
var mins = [];
for(var index =0; index < items.length; index+=1) {
mins[index] = {};
}
function getDistance(items, start, end) {
var result = 0;
var total = 0;
for (var index = start; index <= end; index += 1) {
var item = items[index];
total += item;
}
var mean = total / (end - start + 1);
/* it is better to use binary search here */
var bestPosition = null;
var bestOffset = null;
for (var index = start; index <= end; index += 1) {
var item = items[index];
if (bestPosition == null || bestOffset > Math.abs(item - mean)) {
bestOffset = Math.abs(item - mean);
bestPosition = index;
}
}
for (var index = start; index <= end; index += 1) {
var item = items[index];
result += Math.abs(items[bestPosition] - item);
}
return result;
};
function getMinDistance(items, pos, k) {
var result = null;
if (pos >= items.length - k) {
return 0;
}
if (k == 1) {
result = getDistance(items, pos, items.length - k);
} else {
for (var end = pos; end < items.length - k; end += 1) {
/* var distance = getDistance(items, pos, end) + getMinDistance(items, end + 1, k - 1); */
var posDistance = null;
if (!mins[end + 1].hasOwnProperty(k - 1)) {
posDistance = getMinDistance(items, end + 1, k - 1);
mins[end + 1][k - 1] = posDistance;
} else {
posDistance = mins[end + 1][k - 1];
}
var distance = getDistance(items, pos, end) + posDistance;
result = (result == null) ? distance : Math.min(result, distance);
}
}
return result;
}
var result = getMinDistance(items, 0, k);
Iterate through items of matrix: row * column
If point is not part of any visited area then start searching for new area
Create margin collection having single starting point. Mark starting point as visited in matrix.
Iterate through margin points.
Populate new margin with points accessible from current margin points, in order to avoid duplicates, mark new margin points as visited in matrix immediately.
Search for new margins till no accessible points exist.
JavaScript Implementation.
//Given a matrix consisting of 0's and 1's, find the largest connected component consisting of 1's.
var mat = [];
mat[0] = [1, 1, 0, 0, 0, 0, 0, 0, 0];
mat[1] = [1, 1, 0, 1, 1, 1, 1, 0, 1];
mat[2] = [0, 0, 0, 0, 0, 1, 0, 0, 1];
mat[3] = [1, 1, 1, 0, 0, 1, 1, 0, 1];
mat[4] = [1, 1, 0, 0, 1, 1, 1, 0, 1];
mat[5] = [1, 1, 1, 0, 0, 0, 0, 0, 1];
function findMaxArea(mat) {
var visited = [];
var directions = [
{ horizontal: -1, vertical: 0 },
{ horizontal: 0, vertical: -1 },
{ horizontal: 1, vertical: 0 },
{ horizontal: 0, vertical: 1 }
];
for (var row = 0; row < mat.length; row += 1) {
visited[row] = [];
}
var bestArea = null;
var bestSize = null;
for (var row = 0; row < mat.length; row += 1) {
for (var column = 0; column < mat[row].length; column += 1) {
if (mat[row][column] == 1 && visited[row][column] != true) {
var area = getArea(mat, visited, directions, { row: row, column: column });
if (bestSize == null || area.length > bestSize) {
bestArea = area;
bestSize = area.length;
}
}
}
}
return bestArea;
}
function getArea(mat, visited, directions, point) {
var result = [];
var margin = [point];
visited[point.row][point.column] = true;
while (margin.length > 0) {
var newMargin = [];
for (var mIndex = 0; mIndex < margin.length; mIndex += 1) {
point = margin[mIndex];
for (var dIndex = 0; dIndex < directions.length; dIndex += 1) {
var direction = directions[dIndex];
var row = point.row + direction.horizontal;
var column = point.column + direction.vertical;
if (row >= 0 && row < mat.length && column >= 0 && column < mat[0].length) {
if (visited[row][column] != true) {
if (mat[row][column] == 1) {
newMargin.push({ row: row, column: column });
visited[row][column] = true;
}
}
}
}
}
result = result.concat(margin);
margin = newMargin;
}
return result;
}
var result = findMaxArea(mat);
This algorithmic problem is called
Jenks natural Breaks for coloring, see following post
"Oren Gal GIS Blog: Calculating Jenks Natural Breaks"
And it has name of its creator :-)
Clone linked list having random references between nodes
Random references don't loop nodes. This solution is in JavaScript for Demo Purposes only. It is unacceptable JavaScript structure since it creates loops between objects in memory and JavaScript is not capable to GC it.
var d = { value: "D", next: null, random: null };
var c = { value: "C", next: d, random: null };
var f = { value: "F", next: c, random: null };
var b = { value: "B", next: f, random: null };
var e = { value: "E", next: b, random: null };
var a = { value: "A", next: e, random: null };
a.random = c;
c.random = e;
b.random = d;
e.random = d;
f.random = a;
d.random = f;
function cloneLL(currentItem) {
var result = null;
var prevItem = null;
var itemsHash = {};
var itemsReferences = {};
while (currentItem != null) {
var newItem = { value: currentItem.value, next: null, random: null, newItem: true };
if (prevItem != null) {
prevItem.next = newItem;
}
itemsHash[newItem.value] = newItem;
if (itemsHash.hasOwnProperty(currentItem.random.value)) {
newItem.random = itemsHash[currentItem.random.value];
} else {
if (!itemsReferences.hasOwnProperty(currentItem.random.value)) {
itemsReferences[currentItem.random.value] = [currentItem.value];
} else {
itemsReferences[currentItem.random.value].push(currentItem.value);
}
}
if (itemsReferences.hasOwnProperty(newItem.value)) {
var items = itemsReferences[newItem.value];
for (var index = 0; index < items.length; index += 1) {
var reference = items[index];
itemsHash[reference].random = newItem;
}
}
if (result == null) {
result = newItem;
}
prevItem = newItem;
currentItem = currentItem.next;
}
return result;
}
var newLL = cloneLL(a);
We can split maximum integer into ranges and sum integers in every range, in order to avoid overflow we have to subtract from every number the range start value. At the end all buckets must contain the same value. If value in bucket is different that is our searched range. Then we have to add all possible numbers of that range to bucket again and if total amount matches total amount of other buckets that is our missing number. But it works only if all integers are unique.
- Andrey Yeliseyev March 01, 2014I'll program my bots to access my server at random time of the day, so I'll distribute instructions about planned coordinated attack during a day to all my bots, so the next day at some scheduled time they all at once start to read Wikipedia, I would prefer to make donation to Wikipedia actually.
- Andrey Yeliseyev March 01, 2014Hash should limit selected items. The global hash of values can be used only for algorithm verification.
// Printing all possible sub sets, only unique solutions
var items = ["A", "B", "C", "A", "B", "D"];
var results = [];
function print(prefix, position) {
var hash = {};
for (var index = position + 1; index < items.length; index += 1) {
var item = items[index];
if (!hash.hasOwnProperty(item)) {
hash[item] = true;
var newItem = prefix.slice();
newItem.push(item);
results.push(newItem);
print(newItem, index);
}
}
}
print([], -1);
results;
JavaScript implementation
// Printing all possible sub sets having only 3 elements out of 5
var items = [];
for (var index = 0; index < 5; index += 1) {
items.push(index);
}
var results = [];
function print(prefix, position, len) {
for (var index = position + 1; index < items.length; index += 1) {
var newItem = prefix.slice();
newItem.push(items[index]);
if (newItem.length == len) {
results.push(newItem);
}
if (newItem.length <= len - 1) {
print(newItem, index, len);
}
}
}
print([], -1, 3);
Here is JavaScript implementation. Can you explain what they actually test here?
Writing binary number string to number converter?
Imitating bit-wise operations?
What?
(parseInt("100011", 2) + parseInt("100100", 2)).toString(2);
Another solution in javaScript
1. Build hash out of needle characters keeping total count of them
2. Count unique characters number
3. Function works only when needle length is greater than haystack length
4. Slide range equal to needle length along haystack and check for characters inside. If character goes out of range we decrement its count, if character comes into range we increment its count. If number of characters matches their number in needle we increment total number of matches, if number of characters does not match anymore we decrement number of matches. When number of matches equals number of unique characters in needle we exit with success.
function anaStrStr(needle, haystack) {
if (haystack.length >= needle.length) {
var needleLen = needle.length;
var needleArray = needle.split('');
// Create hash for needle characters with value equal to their total count
var needleHash = {};
var dueMatches = 0;
for (var index = 0; index < needleLen; index += 1) {
var needleChar = needleArray[index];
if (needleHash.hasOwnProperty(needleChar)) {
needleHash[needleChar] -= 1;
} else {
needleHash[needleChar] = -1;
dueMatches += 1;
}
}
// Initialize hash
var matches = 0;
for (var index = 0; index < needleLen; index += 1) {
var haystackChar = haystack.substr(index, 1);
if (needleHash.hasOwnProperty(haystackChar)) {
if (needleHash[haystackChar] == 0) {
matches -= 1
}
needleHash[haystackChar] += 1;
if (needleHash[haystackChar] == 0) {
matches += 1
}
}
}
if (matches == dueMatches) {
return true;
} else {
for (var index = needleLen; index < haystack.length; index += 1) {
/* remove first character from account */
var prevHaystackChar = haystack.substr(index - needleLen, 1);
if (needleHash.hasOwnProperty(prevHaystackChar)) {
if (needleHash[prevHaystackChar] == 0) {
matches -= 1
}
needleHash[prevHaystackChar] -= 1;
if (needleHash[prevHaystackChar] == 0) {
matches += 1
}
}
/* add new character into account */
var haystackChar = haystack.substr(index, 1);
if (needleHash.hasOwnProperty(haystackChar)) {
if (needleHash[haystackChar] == 0) {
matches -= 1
}
needleHash[haystackChar] += 1;
if (needleHash[haystackChar] == 0) {
matches += 1
}
}
if (matches == dueMatches) {
return true;
}
}
}
}
return false;
}
var haystack = "somelongteexthavinganagrams";
var anagram = "xett";
var exists = anaStrStr(anagram, haystack);
exists;
JavaScript implementation
1. Find anagram of all words merged together O(n * log(k))
2. Check that anagram is actually combination of searched words
- Andrey Yeliseyev March 04, 2014