Two Sum: Improving Time Complexity

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9.
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0,1]

Implementation

var twoSum = function(nums, target) {
     for (let i = 0; i < nums.length; i++) {
         for(let j = i + 1; j < nums.length; j++) {
             if (nums[j] === (target - nums[i])) {
                 return [i, j]; 
             }
         }
     }
 }

In this first example the time complexity is quadratic O(n^2). I made one loop inside of a loop to search for all possible pairs of numbers.

Time complexity: O(n^2). For each element, we try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2).

var twoSum = function(nums, target) {
    const numbers = {}
    for (let i = 0; i < nums.length; i++) {
        if(numbers[target - nums[i]] !== undefined ) {
            return [numbers[target - nums[i]], i];
        }
        numbers[nums[i]] = i;
    }
};

In this example, I do two things at once. I iterate and insert elements into the table (numbers).

Time complexity: O(n). We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.

References
Example Coding/Engineering Interview

Comming soon

** New blog Post comming soon **

Javascript: Floating Point Arithmetic

Javascript case

• Why the numbers below don’t add up to a nice round 0.3?

	> 0.1 + 0.2
	0.30000000000000004
	>

You got a unexpected result:

0.30000000000000004

Maybe you asked for help on some forum and got pointed to a long article with lots of formulas that didn’t see to help with your problem. Today I’m here to:

1 . Explain concisely why you get that unexpected result
2 . Tell you know to deal with this problem
3 . If you’re interested, provide in-depth explanations of why floating point number have to work like that and what other problems can arise. You must look at this site

Internally, computers use a format (binary, floating-point) that can not accurately represent a number like 0.1, 0.2 or 0.3 at all.

When the code is compiled or interpreted, your “0.1” is already rounded to the nearest number in that format, which results in a small rounding error even before the calculation happens.

Why do computers use such a stupid system?

It’s not stupid, just different. Decimal numbers cannot accurately represent a number like 1/3, so you have to round to something like 0.33 - and you don’t expect 0.33 + 0.33 + 0.33 to add up to 1, either - do you?

Computers use binary numbers because they’re faster at dealing with those, and because for most calculations, a tiny error in the 17th decimal place doesn’t matter at all since the numbers you work with aren’t round (or that precise) anyway.

What can I do to avoid this problem?

That depends on what kind of calculations you’re doing.

• If you really need your results to add up exactly, especially when you work with money: use a special decimal datatype.
• If you just don’t want to see all those extra decimal places: simply format your result rounded to a fixed number of decimal places when displaying it.
• If you have no decimal datatype available, an alternative is to work with integers, e.g. do money calculations entirely in cents. But this is more work and has some drawbacks.

Why do other calculations like 0.1 + 0.4 work correctly?

In that case, the result (0.5) can be represented exactly as a floating-point number, and it’s possible for rounding errors in the input numbers to cancel each other out - But that can’t necessarily be relied upon (e.g. when those two numbers were stored in differently sized floating point representations first, the rounding errors might not offset each other).

In other cases like 0.1 + 0.3, the result actually isn’t really 0.4, but close enough that 0.4 is the shortest number that is closer to the result than to any other floating-point number. Many languages then display that number instead of converting the actual result back to the closest decimal fraction.

Floating-Point Cheat Sheets for Javascript

Round Types

> var num = 0.1 + 0.2
 0.30000000000000004
> Math.round(num)
 0
> Math.round(num * 10000000) / 10000000
 0.3

Math.round

The round method rounds to the nearest integer: 3.1 becomes 3, 3.6 becomes 4 and -1.1 becomes -1.

> Math.ceil(num)
 1
> Math.floor(num)
 0

Math.ceil() rounds up: 3.1 becomes 4, and -1.1 becomes -1. Math.floor() rounds down: 3.1 becomes 3, and -1.1 becomes -2.

If you want to decide how many values after comman, there is a toPrecise() method to do it. The toPrecision() method returns a string representing the Number object to the specified precision. The toFixed() method formats a number using fixed-point notation.

> num.toPrecision(2)
'0.3'
> +num.toPrecision(2)
0.3
> parseFloat(num.toPrecision(2))
0.3

> +num.toFixed(2)
0.3

References
Math.round() MDN
toPrecision()MDN
toFixed() MDN
Numbers - Javascript Info

Algorithms: Merge Sort and Recursion

Merge Sort

Merge Sort is on of the most efficient sorting algorithms. It works on the principle of Divide and Conquer. Merge sort repeatedly breaks down a list into several sublist until each sublist consist of a single element and merging those sublist in a manner that results into a sorted list.

Implementation in Pseudo Code

	 - Sort the left half of the array (assuming n > 1)      
	 - Sort the right half of the array (assuming n >1)  
	 - Merge the two halves together

Time Complexity

Worst-case scenario: We have to split n elements up and then recombine them, effectively doubling the sorted subarrays as we build them up. (Combining sorted 1-element arrays into 2-element array, combining sorted 2-element arrays into 4-element arrays…) ( O (n log n) )

Best-case scenario: The array is already perfectly sorted. But we still have to split and recombine it back together with this algorithm. ( Ω (n log n) )

Merge sort uses something called recursion. Recursion is an extremely useful technique. Let’s quickly review what it is.

Recursion

The definition of recursive functions is one that, as part of its execution, invokes itself. Every recursive function has two cases that could apply, given any input.

The Base Case

The base case is a problem that you either already know the answer to, or can solve using some other method. Note that a recursive algorithm may have more than one base case, but they are all lumped together under this heading.

The Recursive Case

The recursive case is a problem that can be broken down into “smaller” pieces which can be solved individually. The solutions are then combined into the answer for the whole problem.

Note that the recursive case must move towards the base, by reducing the ``size’’ of the problem. If it doesn’t, then the base case will never be reached, and the algorithm will not terminate.

Note again that a recursive algorithm may have more than one recursive case (i.e. it may recurse more than once, binary tree traversal algorithms are a good example of this).

Code Example

	const factorial = (n) => {
		if ( n === 1 ) {
			return 1;
		} else { 
			return n * factorial ( n - 1 );
		}
	}

In general, recursive functions replace loops in non-recursive functions.

References
Recursion by CS50
CS50 Algorithm Review Notes
Merge Sort by CS50
Merge Sort by InterviewBit

Time Complexity Analisys: From Linear to Binary Search

During the CS50x Introduction to Computer Science on Edx (Havardx) I was exposed with many types of algorithms to solve problems to search and sort. With so many ways to solve the same problem it is important to find the most efficient algorithms to do the job. That ’s when time complexity comes in.

Time complexity is the number of operations an algorithm performs to complete its task. The algorithm that performs the task in the smallest number of operations is considered the most efficient one in terms of the complexity. It is important to point out that the time complexity are also affected by factors such as your operations system and hardware.

Linear Search

Linear search is used on a collection of items. It relies on the technique of traversing a list from start to end trying to find the target element.

Implementation in pseudo code

	- Repeat, starting at the first element:
		- if the first element is what you’re looking for (the target), stop.
		- Otherwise, move to the next element.

Time complexity of Linear Search

Worst-case scenario: I have to look through the entire array of n elements, either because the target element is the last element of the array or doesn’t exist in the array at all. O(n)

Best-case scenario: The target element is the first element of the array, and so I can stop looking immediately after we start.

Binary Search

Binary search is the most popular Search algorithm. It is efficient and also one of the most commonly used techniques that is used to solve problems. The collection must first be sorted, else I can not make assumptions about the array’s contents.

Fun fact: A study from 1988 showed that only one in four textbooks has a correct implementation of binary search (that might be much better now) but it shows that it’s very easy to make a mistake during implementation.

In binary search, the idea is divide and conquer, reducing the search area by half each time, trying to find the target.

Implementation in pseudo code:

	- Repeat until the (sub)array is of size 0:
		- calculate the middle point of the current (sub)array.
		- if the target is at the middle, stop
		- otherwise, if the target is less than what’s at the middle, repeat, changing the end point to be just to the left of the middle
		- otherwise, if the target is greater than what’s at the middle, repeat, changing the start point to be just to the right of the middle. 

Most implementations calculate the middle point using the formula m = (start + end)/2. The issue here is that the sum of start plus end might overflow. That’s can happen because, for example, in C++ and Java, int types fits values up to around 2 billion (2^31). If you add two such values, the sum will overflow and you might have some mistake because of that. It will not compute the average correctly.

The best formula to get the middle would be m = start + (end - start/2). Assuming that start and end are non-negative number.

Time complexity of Binary Search

Wort-case scenario: I have to divide a list of elements in half repeatedly to find the target element, either because the target element will be found at the end of the last division or doesn’t exist in the array at all. (O(log n) ).

Best-case scenario: The target element is at the midpoint of the full array, and so I can stop looking immediately after I start.

Algorithms Summary

References
Linear Search by CS50
Linear Search Algorithms by HackerEarth
Binary Search lecture (C++ and Python) by Errichto
Binary Search by CS50

Code Challenge @Leetcode - Single-Row Keybord

I was doing some code challenges at Leetcode using Javascript language, and surprisingly converting the string into array improved the runtime then accessing the character directly via index.

Let me explain in code therms:

First

Accessing string directly via index srt[i] or str.charAt() takes at least 60ms.

let str = 'leetcode';
for (let i = 0; i < str; j++) {                  	
		let w = str[i]; // same as str.charAt(i)
		// do some with w
}

Second

Converting a string to array improved the runtime to approximately 40ms. Why? Shouldn’t this method be more time consuming since I’m converting data types?

let arr = 'leetcode'.split(''); 
for (let i = 0; i < arr; i++) {                  
		let w = arr[i];   //
		// do some with w
}

The same happens when using the spread operator.

let word = [...'leetcode’];
// ['l', 'e', 'e','t', 'c', 'o','d', 'e'] //

I’m still looking for an answer to this question. Let me know if you have a clue. ;)

Interview Question: What was your most challenging project?

At the Flatiron Bootcamp Software Engineering program, I had to do as many labs as possible to really get the content. At the end of each section of the curriculum, I had to prove myself and build an application that became the foundation of my programming portfolio: CLI (Command Line Interface) Gem (ruby), Sinatra, Rails, Javascript and React/Redux.

After finalizing all the projects and graduating from the program, another journey started: the job search. I prepared to answer many types of questions, but then I got one which I wasn’t expecting. What was your most challenging project? Thinking about it made me realize that although my first project was very challeging, it was not the most difficult.

The first project was like a blank canvas. I did no know what to do. To make this enjoyable, I decided to combine my hobby with coding. As an anime fan, I decided to rate the best animes of the season. Unfortunately, I had my first technical issue; the API was in GraphQL, and at that time, I was not comfortable in using it.

After doing some more research, I decided to use the Studio Ghibli RESTfull API.. I had to read a lot, ask questions, and interact with the Flatiron community on Slack. I had a lot of fun building it, and after that, I realized I could build anything, I felt powerful. ;)

I believe every challenge, independent of how big it is, can be overcome if I keep learning, iteracting with the community, and improving myself.

You can check my CLI Gem here.

React: Understanding setState()

A React class component has an internal state, which like props, affects how the component renders and behaves. Unlike accessories, the state is local to the component and can only be initialized and updated within it.

Remember that state is similar to props, but it is private and fully controlled by the component.

Three things to know about setState()

Do not modify state directly

Modifying State directly will not re-render a component

State Updates May Be Asynchronous

React may batch multiple setState() calls at once for performance. That’s the reason why we can’t rely on their values for calculating the next state.

State Updates are Merged

Calling setState() merges the object you provide into the current state.

• The merging process is kicking off what is called in React reconciliation. The reconciliation process is the way React updates the DOM, by making changes to the component based on the change in state. When the request to setState() is triggered, React creates a new tree containing the reactive elements in the component (along with the updated state). React knows which changes to implement and will only update the parts of the DOM where necessary. That’s the reason why React is fast.

The most important thing to know about setState is the fact that it is a function in React that works asynchronous. That is why state are not immediately available after the update.

Here a link to the official documentation to learn more about State and Lifecyle

Accessibility: Chrome DevTools

Did you know that roughly 15% of the world’s population has some form of disability? I am talking about over 1 billion people.

As a person who believes in diversity and inclusion, I always have this in mind when developing a new tool. For reference, W3 has a great guideline for web content accessibility, and google DevTools can audit a website for accessibility either. More information about it here.

How to audit

Accessibility Reference and Tools for Web Developers are a guideline made from Google on how to audit your application step by step.

Pratical Example

I used the audits on DevTools to verify my Find Daycare application and where I could improve to make it more accessible.

My background and foreground colors do not have a sufficient contrast ratio. I decided to change the colors and make the button text bold.

Changing the style of my application increased my accessibility rate to 82. This tool doesn’t only show you what to improve; it has links to websites teaching you how to do it and why it is so important.

There is an excellent YouTubecasts with Rob Dodson teaching accessibility fundamentals and how to audit applications.

A11ycasts is short for AccessibilityCasts (a11y is a common shortening of the term accessibility because there are 11 letters in between the “”A”” and the “”Y””). The goal of A11ycasts is to teach developers how accessibility works all the way down at the platform level, while also demonstrating real world accessibility problems and solutions to fix them.

React Redux Project: Single Page Application

How exciting is to get at the end of the curriculum. I have learned so much and could build many cool projects. The projects have helped me understand the sections and how to apply all the knowledge I have acquired, and go even further exploring different libraries.

As a mother, I discovery it can be very challenge to find daycare for my daughter. I had decided to build a tool to help parents to get track of daycares they have visit, keep notes, schedule visits, and finally choose the one that best fits the needs of their kids.

In my application I used Yelp Fusion API to search for daycares by zip code. I called two endpoints to get the businesses and reviews. For my backend I built a Rails API to handle the data persistence. To serializer fast I choosed the Netflix/fast_jsonapi: A lightning fast JSON:API. API as a serializer for Ruby Objects, since it has a better benchmark times for 250 records than Active Model Serializer.

My front-end was built using React and Redux to manage state. Understanding the redux flow is very important to manage state properly. Bellow is a simple graphic to understand the redux cycle.

This time to design my application I decided to use the framework Material-UI.It is very well documented with tons of usage examples.

You can see my frontend and backend repository on github.

Rails JavaScript Project: Introduction to Single Page Application

Last week at my coding Bootcamp, I was asked to implement a project for the section “Rails with Javascript.” It required adding dynamic features using Javascript and an API based on JSON.

Quick Intro

Previously, I had created a Maintenance Management System for Laboratories (CMMS). It is supposed to help technicians to keep track of all records and assets that they are responsible for in a laboratory. That is, it includes features like schedules, maintenance records, tasks, and a long history of all work these technicians performed. In a chemical lab, for example, many pieces of equipment require periodic maintenance, such as corrective and preventive types.

The project was primarily built to render ERB views on the server-side. It did not include any JSON endpoints.

Hybrid Approach: Moving from Server to Client

Previously, by the time I created my Rails app, I had implemented a few basic functionalities, including the basic models, a couple of controllers and views. These were all server rendered, using Views and ERB templates. This time I would like to move from server to client rendered pages. That’s when the concept of single-page apps comes in handy.

To expand the app, I’d decided to use a hybrid approach. Instead of migrating the current code, only the new features should support AJAX requests and JSON responses. Like in the Equipment Controller

The Idea: Simulate a Single-Page Application (SPA)

SPA is a web application or web site that interacts with the user by dynamically rewriting the current page rather than loading entire new pages from a server. This approach avoids interruption of the user experience between successive pages, making the application behave more like a desktop application.

In a SPA, it is common that all the necessary code - HTML, Javascript, and CSS - is retrieved in a single page load.

The most prominent technique used to load dynamic content is AJAX. It allows rendering of fluid web views without constant page reloads.

Sending the app data in JSON creates a separation between static from dynamic content. The presentation layer - HTML, CSS - is treated as static, and the application logic - AJAX, JSON - dynamic. This separation makes the app easier to maintain. In a well-architected SPA, you can change the whole presentation in HTML (static) without touching the code that implements the business logic (dynamic).

Practical Example

In theory, this hybrid approach is supposed to make my application more scalable and easier to maintain. Next, I should be able to replace all server rendered forms by a full SPA like Angular or React.

Reference

Source Code: https://github.com/ludaires/maintenance-rails-js-project

Ruby on Rails Project: Using a Third-Party Authentication (OAuth)

It is exciting to see how far and how many things we can build at the end of the Rails section. For my Rails project, I kept working in the same domain from my Sinatra project. I continued my CMMS app for a chemical laboratory. It tracks all the equipment maintenances.

The main difference from the Sinatra to Rails implementation can be seen not only in the UI but in the fairly amount of logic in the backend. As I learned more about best practices and software design principles, I was able to come up with a much cleaner version. I could refactor it using helpers, partials with locals, and nested forms.

As the title suggests, one of the requirements for this project was to use a third-party authentication solution. For that, I found OmniAuth as a great library to handle different authentication providers like Google.

Google Authentication Setup

Here is a quick step-by-step, demonstrating how I set up my application. In addition to OmniAuth, I used another library called OmniAuth Google OAuth2. You can find the documentation here.

Gemfile

gem 'omniauth-google-oauth2'
gem 'dotenv-rails'

Google API Setup

Go to console developers and select your project if you have already set up one. Go to Credentials, then select the “OAuth consent screen” tab on top, and provide an ‘EMAIL ADDRESS’ and a ‘PRODUCT NAME’.

Because I didn’t know all details for creating a new project in Google Console, I followed this excellent blog post explaining how to create a Google API Console project and OAuth2 Client ID.

OmniAuth with Google

Create a file at config/initializers/omniauth.rb with the following code:

Rails.application.config.middleware.use OmniAuth::Builder do
    provider :google_oauth2, ENV['GOOGLE_CLIENT_ID'], ENV['GOOGLE_CLIENT_SECRET']
end 

Environment Variables

Create a .env file in your root application and include the ‘dotenv-rails’ library to load the config into the ENV hash. Don’t forget to add the .env file to your .gitignore to ensure you don’t commit your credentials. You don’t want to expose your credentials to strangers, right?

GOOGLE_CLIENT_ID="<paste your client_id keys here>"
GOOGLE_CLIENT_SECRET="<paste your client_secret here>"

Link to Login

If you have a navigation bar, create a link to login. In my case, I included the following link at app/views/layouts/application.html.erb:

<%= link_to "Log in via Google", '/auth/google_oauth2', class: "btn btn-outline-secondary" %>

Routing OAuth Flow in Your Application

In my config/routes.rb file:

get '/auth/google_oauth2/callback', to: 'sessions#create_from_omniauth'

User Sessions

In my app/models/user.rb file, I included a method that finds or create new users from Google Authentication. It assigns them a random password if new.

def self.create_from_google(auth)
    User.find_or_create_by(email: auth[:info][:email]) do |user|
        user.username = auth[:info][:name]
        user.password = SecureRandom.hex
    end
end

In my app/controllers/sessions_controller.rb:

def create_from_omniauth
    @user = User.create_from_google(auth)
    set_session
    if logged_in?
        flash[:message] = "Successfully authenticated via Google!"
        redirect_to user_path(@user)
    else
        flash[:message] = "Something went wrong. Try again"
        redirect_to root_path
    end
end

private
def auth
    request.env['omniauth.auth']
end

You can find the source code at maintenance_management_rails_app.

Sinatra Project: CMMS with UML

As a former industrial chemist who decided to learn how to code, I wanted to create a project which could combine the two things I love the most: Chemistry and Coding.

A chemical lab has a lot of equipment that needs periodic maintenance: corrective and preventive. I developed an app to help technicians to keep a record of all assets they are responsible for, including scheduling, track maintenance, tasks, and keeping a record of the work they perform.

The web application was built in Ruby, using MVC architecture, and Sinatra. Here is a class diagram I put together in UML Unified Modeling Language. I used Lucidchart to design the schema and set up everything beforehand. My primary goal was to make this app very simple and functional.

A class diagram is a type of static structure diagram that describes the structures of a system by showing the system’s classes, their attributes, methods and the relationships among objects.

In the diagram, classes are represented with boxes that contain up to three compartments: The top compartment contains the name of the class The middle compartment contains the attributes of the class The bottom compartment contains the operations the class can execute.

You can learn more about it here and how to create a class diagram is this great Youtube video.

You can see the full application on my GitHub account or live here.