Git Product home page Git Product logo

cc_algos's Introduction

Hi!

For my 4 solutions, I wrote 2 in JavaScript (one optimized for time, and one for storage) and 2 in Ruby (one optimized for time, one for storage).

###Time 1: Ruby Solution - Mergesort and binary search. I chose to use mergesort to sort the array because it's fast, O(n log(n)). It makes some sacrifices space-wise though, due to the stack that the recursion produces and the additional arrays (left, right, result) that is uses. I used binary search to find the missing value because it's fast ( O(log(n)) ), which is due to the fact that each iteration halves the number of items to be searched through.

To use this code call

low_time_1(array_with_missing_val)

Ex:

hundo = gen_array(8)  
missing = low_time_1(hundo)  
puts "missing: #{missing}"

###Time 2: JavaScript Solution - Quicksort and binary search. Here I use quicksort to sort the array, and a binary search like algorithm to find the missing value. Both of these algorithms are fast. Quicksort is O(n log(n)), and binary search is O(log (n)).

To use it, call the function

lowTimeTwo(arrayWithMissingVal)

Ex:

var hunds = genArray(3);
var valMissing = lowTimeTwo(hunds);
console.log('valMissing', valMissing);

###Storage 1: Ruby Solution - Insertion sort and Iteration

For this one, I used insertion sort to sort the array. It's very low storage [O(1)], because the only data structure that it uses is the passed in array. Time-wise, though, it's inefficient.

To find the missing number in the sorted array, I used a method that also iterates through the passed in array without generating any additional data structures, making it low storage as well.

To use this code call

low_storage_1(array_with_missing_val) 

Ex:

hundy = gen_array(80)
missing = low_storage_1(hundy)
puts "missing: #{missing}"

###Storage 2: JavaScript Solution - Bubble sort and Iteration

I chose to sort via bubble sort, because it doesn't create any data structures and will be very low storage. This makes it O(1). The function that I use to then find the missing values will be low storage for the same reason.

To use it, call the function

lowStorageTwo(arrayWithMissingVal)

Ex:

var hunds = genArray(3);
var valMissing = lowStorageTwo(hunds);
console.log('valMissing', valMissing);

cc_algos's People

Contributors

johnh4 avatar

Watchers

 avatar  avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.