AlexMcD-git

Posted on

# Algorithms Part 2 : A Beginner's Attempt (at improvement and translation)

As mentioned in my last post, I wanted to revisit the same problem after learning some ruby. Not only did I want to "translate" from one language to another, I wanted to attempt at optimization. Here is my javascript solution. The full question is both in the repl and previous blog.

The TL;DR is starting from an array of all false values, act upon it from an array of queries. First value of a query determines SET(1) or GET(2). SET means you turn the value in the starting array true, GET means you determine the position (indexing starts at 1) of the next true from the given starting position. SET has no output. If there are no ouputs for the GET, output is -1.

``````testArray = [false, false, false, false, false]
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
expectedOutput = output = [-1, 2, -1, 2]
``````

I tried to recreate my javascript solution as similarly as possible using ruby methods as such.

``````testArray = [false, false, false, false, false]
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
outputArray =[]

queries.each {|q|
if q[0]==1
testArray[q[1]-1]=true
elsif q[0]==2
found = false
i=q[1]-1
until found || i>testArray.length do
if testArray[i]
outputArray<<i+1
found = true
end
i=i+1
end
if found == false
outputArray<<-1
end
end
}
print outputArray
``````

As mentioned before, this could run very long if the GET were to have to search a very long "testArray" only to return -1. What if setting also stored the value to an array of everything that has been set? I also had the idea to store the max value separately in case the "memoryArray" get large. First step is to chop down the "if GET" and store the SETs.

``````testArray = [false, false, false, false, false]
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
outputArray =[]
memoryArr=[]
memoryArrMax= 0

queries.each {|q|
if q[0]==1
testArray[q[1]-1]=true
memoryArr<<q[1]
if q[1]>memoryArrMax
memoryArrMax=q[1]
end
elsif q[0]==2
if q[1] > memoryArrMax
outputArray<<-1
else
puts 'i should be here 2 times'
end
end
}
print memoryArr
puts
print outputArray
``````

console:

``````i should be here 2 times
i should be here 2 times
[2]
[-1, -1]
``````

So we see the output array is properly getting -1 twice, like before, but without even searching the the testArray. (I stored the max as a separate variable because the memoryArray could get pretty big, so in the worst case the .max built in method would take longer to recalculate every time there is a GET, I'm guessing, as opposed to a single comparison with each SET).

Next we add what to do if we have a GET where we know the return should not be -1. We need to find the first VALUE in memoryArray (which corresponds to indexes of true values in testArray) that is greater than or equal to the index provided with our GET request. This requires the array to be sorted. To cut down on sorting, we can opt to only sort on a GET request, instead of after every SET. Additionally, this can further be reduced by not sorting with consecutive GETs. I will add a boolean to track if our last query was a GET. This brings our final solution to:

``````testArray = [false, false, false, false, false]
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
outputArray =[]
memoryArr=[]
memoryArrMax= 0
lastWasGet=false

queries.each {|q|
if q[0]==1
testArray[q[1]-1]=true
lastWasGet=false
memoryArr<<q[1]
if q[1]>memoryArrMax
memoryArrMax=q[1]
end
elsif q[0]==2
if q[1] > memoryArrMax
outputArray<<-1
else
if !lastWasGet
memoryArr=memoryArr.sort
lastWasGet=true
end
for index in memoryArr do
if index>=q[1]
outputArray<<index
end
break if index>=q[1]
end
end
end
}
``````

Repl here

I understand that there may be some limitations of the .sort method that may make this solution also sub-optimal. I still don't think it could be worse than the worst case of the previous brute-force-y solution. If you made it this far, let me know what your think, and how you would approach this!