michaelchen101
BAN USERSort the set by start, if start values are equivalent, sort in descending end order
Iterate over the sorted array and add to result array entries where the value of end exceeds the current max. Update max in this case.
Time Complexity: O(n log n) due to sorting
Sorting is not stable, and I was not sure if this was supposed to modify the original array or return a different array.
var Tuple = function(start, end) {
this.start = start;
this.end = end;
}
function removeRange(set) {
var endMax = 0;
var result = [];
if (set.length < 2) { return set; }
set.sort(function (a,b) {
if (a.start === b.start) {
return b.end - a.end;
} else {
return a.start - b.start;
}
});
endMax = set[0].end;
result.push(set[0]);
for (var i = 1; i < set.length; i++){
if (set[i].end > endMax) {
result.push(set[i]);
endMax = set[i].end;
}
}
return result;
}
// Execute
var set1 = [ new Tuple(2,6), new Tuple(3,5), new Tuple(7,21), new Tuple(20,21) ];
var set2 = [ new Tuple(1,5), new Tuple(1,3), new Tuple(1,7), new Tuple(2,3) ,
new Tuple(3,5), new Tuple(8,9), new Tuple(9,17), new Tuple(5,6)];
var set3 = [ new Tuple(1,10), new Tuple(3,3), new Tuple(4,7), new Tuple(10,30) ,
new Tuple(16,19), new Tuple(-1,9), new Tuple(9,31), new Tuple(9,29)];
console.log(removeRange(set1)); // Expected: [(2,6), (7,21)]
console.log(removeRange(set2)); // Expected: [(1,7), (8,9), (9,17)]
console.log(removeRange(set3)); // Expected: [(-1,9), (1,10), (9,31)]
I don't think so since the sample OUTPUT would've been [(2,21)]
- michaelchen101 October 19, 2015I looked at this problem like a simple but unreliable string compression. Basically, each compressible word is divided into 3 parts:
1. The header
2. The body, aka the number
3. The footer
So this solution finds what I called the middle word and then finds all substrings of that middle word possible. And then for each of those, builds a possible result.
var simplifyWord = function(word){
var middleWord = word.substring(1, word.length-1);
var max = middleWord.length;
var possibleCompressions = [];
var currentWordHeader = "";
// Check if length is > 3
if(word.length < 3)
return possibleCompressions;
for(var i = 0; i < middleWord.length; i++){
var sub = "";
currentWordHeader += word[i];
for(var k = 0; k < max; k++){
sub += middleWord[i+k];
var currentWordFooter = word.substring(currentWordHeader.length + sub.length);
possibleCompressions.push(currentWordHeader + sub.length + currentWordFooter);
}
max--;
}
return possibleCompressions;
}
Repirenedpisano, Blockchain Developer at ABC TECH SUPPORT
Hello, I am Irene and I live in Pittsburgh, USA. I am working as A production worker and my duty ...
RepLisaTQuinn, Analyst at A9
I have a passion for reading and creative writing and attend many workshops and conventions surrounding love spell that work ...
Repevelynleary0, Consultant at Arista Networks
Hi, I am Evelyn from Los Angeles, USA. I have been a Marketing Manager in Veramons Digital Company from last ...
Repjbacklit, abc at 247quickbookshelp
I am working as a news anchor and i love my job i an working from last 4 years under ...
Repkylieblindner, abc at ASAPInfosystemsPvtLtd
Hello, I am Kylie. I am working in a store as Supply chain managers promote the design, development, and implementation ...
Repjuanitajboon, Applications Developer at 247quickbookshelp
Hi everyone, I am from Pelham. I currently work in the Hechinger as Cashier.I like to do creative things ...
Repjacksssones433, Apple Phone Number available 24/7 for our Customers at A9
Proficient and creative WordPress developer with a strong history in website management and development. Experienced in SEO and PPC campaign ...
Repharoldjmaloney, Accountant at ASU
Hi, I am a Computer systems administrator from texas. Experienced in running a wide variety of software development Company. Looking ...
Repshawt146, Applications Developer at ADP
I love Exploring and photography. I want to fill my life with happiness and beautiful mammaries. I also like to ...
Repman254183, Project Leader at GoDaddy
I am working as Human Resources Associates, and my duties are for obtaining, recording, and interpreting human resources information within ...
RepRobin has more than 26 years of experience working for state, city, university, and public entities as a fisheries ecologist ...
Repteresawells858, Java Developer at 247quickbookshelp
I am Teresa. I work as a Software engineer at Asian Fusion Company. I was born in the US and ...
So my approach is instead of going to each cell and then looking around the cell for mines, since I have a map of all the mines, find each mine and then bump up the value of some other grid that is a 2-D array of 0's.
Implementation in Javascript. Basically no error handling in this code for bad input and such but this is the general idea.
- michaelchen101 October 21, 2015