Bitwise Algorithm 1: Clear Bit

0

Problem

Given an integer x, clear the kth bit from the right (the rightmost bit is the 0th bit).

For example, let's say x = 000100101110. Here the 1st, 2nd, 3rd, 5th, and 8th bit are set. So for k=1, the algorithm should return 00100101100, but for k=0, since the 0th bit is already clear, it should return the original value unchanged.

Algorithm

To solve this problem we need to do some bit masking. We want to mask one bit to 0, while leaving the other bits unchanged. To mask a bit to 0, we use a bitwise AND. We need to bitwise AND the integer x with a number containing bits all set to 1, except in the kth location set to 0. In boolean algebra a \& 1 = a whereas a \& 0 = 0, so we leave all the bits unchanged except in the kth location we clear it.

For example if x = 00100101110 and k=1, we want to do the operation 000100101110 \& 111111111101, which gives us our answer, 000100101100.

The question then is how do we compute the number 111111111101 where all bits are set except the kth bit. To do this, we can take the number 1 shift it to the left by k positions and negate the result.

Here is the code in java:

public static int clearBit(int x, int k) {
    return x & ~(1 << k);
}

Interesting Programming Puzzle

0

How many ways can you write a function such that f(1) = 2 and f(2) = 1. It doesn't matter what the function returns for other values. Here are the functions I came up with in c.

Using control flow:

int f1(int i) {
	if (i == 1) return 2;
	return 1;
}

Using bitwise xor:

int f2(int i) {
	return i^3;
}

Using subtraction:

int f3(int i) {
	return 3-i;
}

Using modulus:

int f4(int i) {
	return i%2 + 1;
}

Using an array:

int f5(int i) {
	static const int arr[] = {0, 2, 1};
	return arr[i];
}

Using logical not:

int f6(int i) {
	return !(i-1) + 1;
}

Can anyone think of more solutions?

Maximum Single Buy and Sell Profit Problem

0

Heres a pretty simple but interesting problem to solve.  Also a popular interview question!

Problem

Given a list of stock prices for a specific stock over time in chronological order, figure out what is the maximum profit that could have been made by making exactly one buy and one sell of this stock. Return 0 if it is not possible to make a profit.

For example, given the stock prices 10, 9, 8, 7, 5, it is not possible to make a profit so it should return 0. Given the stock prices 13, 3, 12, 1, 11, the maximum profit that can be made is 10 (by buying at 1 and selling at 11).

Algorithm

The optimal algorithm is actually fairly simple. Here it is coded in java:

public static double maxProfit(double[] prices) {
	if (prices.length <= 0) {
		return 0;	
	}

	double lowSoFar = prices[0];
	double maxProfitSoFar = 0.0;
	for (int i = 1; i < prices.length; i++) {
		// Keep track of the lowest price so far.
		if (lowSoFar > prices[i]) {
			lowSoFar = prices[i];
		}
	
	        // This is the maximum profit possible if we sell at i.
		double profit = prices[i] - lowSoFar;

		if (profit > maxProfitSoFar) {
			maxProfitSoFar = profit;
		}
	}

	return maxProfitSoFar;
}

The idea here is that as we loop through the array we keep track of the lowest value so far. If we subtract the lowest value so far from the current value we are at in the array, we find the maximum profit that can be made by selling at the current point in the array. Since we are calculating that value for every ending point, the maximum of all those values will be our solution!

Since we just need to loop through the prices array once, the time complexity is O(n) (where n is the size of the prices array).

The Maximum Sum Problem

0

Recently I have been solving algorithms problems for fun and thought it'd be a good idea to share some of my solutions here. So here's one called the Maxmimum Sum Problem.

Problem

Given an n * n matrix of integers, find the sum of sub-rectangular (doesn't have to be a square) matrix with the largest sum.

For example, given this matrix:

 \begin{array}{ccc} 1 & -2 & 2 \\ 5 & -3 & 5 \\ 2 & 4 & -6 \end{array}

The sub-matrix with the largest sum is:

 \begin{array}{ccc} 5 & -3 \\ 2 & 4 \end{array}

So the solution is the sum of this matrix, which is 8.

NOTE: There are actually three more sub-matrices in this example that sum to 8. Can you find them?

Algorithm

    1. Compute an n*n matrix of the partial vertical sums of the input matrix. Such that sums_{i,j} = \sum_{n=0}^{j} input_{i,n}. For our example above, that will give us a matrix that looks like this:

       \begin{array}{ccc} 1 & -2 & 2 \\ 6 & -5 & 7 \\ 8 & -1 & 1 \end{array}

      This matrix can be computed in O(n^2) time by adding the new row to the results of the previous row.
    2. Now we can use the sums we computed to find all the possible rectangles of width 1 in another matrix by subtracting rows:
      Matrices of height 1:
      sums_1
      sums_2 - sums_1
      ...
      sums_{n-1} - sums_{n-2}
      sums_n - sums_{n-1}

      Matrices of height 2:
      sums_2
      ...
      sums_{n-1} - sums_{n-3}
      sums_n - sums_{n-2}

      ...

      Matrices of height n-1:
      sums_{n-1}
      sums_n - sums_{1}

      Matrices of height n:
      sums_n

      After doing each of these calculations we will have a bunch of resulting rows. In the case of our example we will end up with the following rows:

       \begin{array}{ccc} 1 & -2 & 2 \\ 5 & -3 & 5 \\ 2 & 4 & -6 \\ 6 & -5 & 7 \\ 7 & 1 & -1 \\ 8 & -1 & 1 \end{array}

      These rows can all be found in O(n^2) time.

    3. The numbers in the rows from step 2 represent the sums of all the possible rectangles of width 1. To find the sum of rectangles with other widths, we can sum horizontally. So we are left with a problem of finding the maximum sum consecutive sub-sequence in each row. The greatest of each of these results is the answer to the problem.The maximum sum subarray for each row can be found in O(n) time by calculating the maximum sub-array that ends at each position in the row as follows:
      max_0 = row_0
      max_i = max(row_i, max_{i-1} + row_i)
      The max-sum of the row is now the maximum value in max.

      For example, the first row \begin{array}{ccc} 1 & -2 & 2 \end{array} would produce a max array of \begin{array}{ccc} 1 & -1 & 2 \end{array}. The maximum number in this row is 2.

      And the second row \begin{array}{ccc} 5 & -3 & 5 \end{array} would produce a max array of \begin{array}{ccc} 5 & 2 & 7 \end{array}. The maximum number in this row is 7.

      After we do this for all the rows we are left with 2, 7, 6, 8, 8, 8.

      Since there are O(n^2) rows and the maximum sum within each row can be computed in O(n) time, the complexity of this step is O(n^3).

      The maximum of all those values is the maximum sum of the original matrix. In our example, the largest number was 8, suggesting that the sum of the maximum-sum submatrix is 8.

The complexity of all the steps together is then O(n^2+n^2+n^3), giving us a total complexity of O(n^3) for the entire algorithm.

Intro to SASS - Variables and Mixins

0

This tutorial is split into two sections. The first section which can be found here is for the non-programmers or those who are new to programming languages such as JavaScript, PHP, Python, and/or Ruby and have little to no experience dealing with logic, arrays, or functions. For those who have programming experience in dealing with arrays, functions, and simple logic (i.e. if-else), please read the programmer's approach to SASS.

Non-Programmer's Approach to SASS

SASS is a great alternative to writing conventional style sheets as we saw in the first tutorial. SASS provides a programmatic approach to writing CSS. We can use variables to hold values (that can be changed if we want), mixins which contain reusable pieces of code, and functions which are mostly the same as mixins except they return only a single value.

Variables

Variables can be thought of as placeholders for a value. Let's look at a basic math problem as an example:

Given the equation x + 5 = z and x = 5, what is the value of z?
x = 5 therefore, 5 + 5 = z
5 + 5 = 10 therefore, 10 = z
z = 10.

This seems like something we would see out of a math book; however, it shows how variables contain known values. Thankfully, we know the values of our variables in SASS because we must set them.

We set variables in SASS by using a dollar symbol($), the name of the variable, a colon(:), then a value, and then we close the statement with a semi-colon(;). Here are some examples examples:

$foo: 'bar';
$variable: bold;
$link_color: #ff9300;
$link_hcolor: rgba(0,0,0,0.25);


When naming variables, we need to use only certain characters when naming variables. Here are the pitfalls to avoid:

  • Do not use spaces $this is: bad;
  • Replace spaces with hyphens(-), underscores(_) $i_am: okay;, or capitalize the first letter of each new word $iAmL okay.
  • Do not use special characters $i'm: bad;
  • Do not begin variable names with numbers $3i_am: bad
  • To recap, here are the proper ways to name variables:
    • Best practice says to stick with one method, do not mix any of the three naming methods
    • $this_is_a_variable: 'foo';
    • $this-is-a-variable: 'foo';
    • $thisIsAVariable: 'foo';

SASS variables can only contain certain types of data—these are commonly referred to as data types. Here are the following types of values we can store in a SASS variable. Continue reading to find a more detailed example of each type.

  • Strings
  • Numbers
  • Colors
  • Lists
  • Booleans
Strings

Strings are something we see every day. SASS allows us to set variables to strings without quotes, single quotes, or with double quotes. Strings are multiple characters that are pieced together to form a word or phrase. These values could technically be anything we need them to be; however, we will set them to values that can be used later on.

$string: bold;
$font: 'My Font';
$fancyFont: "My Fancy Font";
Numbers

Numbers are any character 0-9 without using a comma to separate numbers. SASS is very friendly when handling numbers. We can add units to the end of values in SASS and we can still perform arithmetic operations on those values. Every unit we need to use in CSS (e.g. px, pt, em, %, etc) can be appended to the end of a number in a SASS variable. This will not impact how SASS changes the value later on. Here are some examples:

$number: 1;
$font_size: 12px;
$title_1: 2.3em;
$title2: 1.9pt;
$title-3: 150%;
Colors

Although color is not a real data type in any programming language, SASS treats them as a special type of data. In CSS 2.1, we define colors using the hex color space, rgb color space, or by using entity values (color names). In CSS 3 we introduced the rgba color space, hsl color space, hsla color space, and opacity (alpha transparency). We simply write the colors as we would normally in CSS, here are examples of each:

  • $red: red;
  • $red: #f00;
  • $red: #ff0000;
  • $red: rgb(255,0,0);
  • $red: rgba(255,0,0,0.25);
  • $red: hsl(0deg,100%,50%);
  • $red: hsla(0deg,100%,50%,0.25);

Lists

Lists in SASS are nothing more than a sequence of numbers or characters separates by commas or spaces. Common uses of lists are rgba(), rgb(), hsl(), hsla() values as well as font-family values. Here are a few examples of lists in SASS:

  • $var: 10px 0 12px 4px;
  • $var: 'My Font', Arial, Verdana, Tahmoa, sans-serif;
  • $var: 255,255,255;
  • $var: 0deg, 100%, 50%;
Booleans

Booleans are an essential part of logic in computing. Booleans are simply TRUE or FALSE. Boolean values in a vairables are not typically something we would print out, but it would be something we would test for. We would check to see if a value of a variable is true or false.

$var: TRUE;
$var: FALSE;

We will touch more on booleans in a later tutorial.

Altering Variable Values

In SASS, we can use basic arithmetic operations to change the values of our variables. This is well beyond the scope of conventional CSS and adds dynamic capabilities and a distinct advantage to SASS over CSS. By 'basic arithmetic operations' we simply mean addition, subtraction, division, and multiplication. Here is a very practical example of using basic arithmetic operations to alter values:

$font_size: 12px;
$heading_one: $font_size * 2;
.title { font-size: $heading_one - 4; }

Remember: SASS will perform arithmetic operations even with units!

As part of being able to perform arithmetic operations, we can include the value from one variable and store it in another variable as we see can fron the second statement in the example above. Calculating the numbers out, we would know the value of $heading_one is 24px. SASS would output the following CSS code once rendered:

 .title { font-size: 20px; } 

Mixins

Mixins are similar to functions as we might see them in a programming language like JavaScript, PHP, Python, or Ruby. Mixins are reusable pieces of code that contain and/or alter values based on user input. This might seem confusing at first; however, with a little explanation mixins will become second nature!

Defining Mixins

We can define our own mixins by using the @mixin directive. To define a mixin, we must write the directive first, the name of the mixin followed by a set of parenthesis and a pair or curly braces. Here is an example:

@mixin mixin_name() {
     property: value(s);
}

Note: the naming conventions we touched on regarding variables applies to mixins as well! To review these rules, click here.
Remember that mixins are reusable pieces of code. Mixins can include things like if-else logic statements and loops.

@mixin my_mixin() {
	font-family: 'My Font', Arial, Tahmoa, sans-serif;
	font-weight: normal;
	font-size: 12px;
	font-style: normal;
}

body {
	margin: 0 auto;
	@include my_mixin();
}

The CSS output is:

body {
	margin: 0 auto;
	font-family: 'My Font', Arial, Tahmoa, sans-serif;
	font-weight: normal;
	font-size: 12px;
	font-style: normal;
}

The above is a very basic use of mixins. The mixin contains predefined values not based on user input. We can include these values within any selector without an error being thrown by SASS.

Passing in Variables into Mixins

Passing variables into mixins (and functions) is essential to effectively using and mastering mixins. The best way to learn this is through example:

@mixin my_mixin($color) {
	background: $color;
}

Looking at the mixin we just made, we see something different inside our parenthesis. We added a variable into the parenthesis. We call this passing a variable into a mixin. From here, we have a background property where the value is the same as the variable passed into the mixin. We call the passed in variable, $color in our case, an argument or parameter. If we called this mixin, for instance:

body { @include my_mixin(#000); }
div { @include my_mixin(yellow); }
pre { @include my_mixin(rgb(237,237,237)); }
/* Our result would be */
body { background: #000; }
div { background: yellow; }
pre { background: rgb(237,237,237); }

Given the examples above we can see the direct relationship between the values passed into the mixin and the values rendered by SASS into CSS. However, there are some principles we much understand. One very important part of using parameters is that the name of the parameter(s) must be consistent with the variable names in the body of the mixin. For instance:

/* This is correct */
@mixin my_mixin($color) {
	background: $color;
}
/* This is INCORRECT */
@mixin my_mixin_revised($color) {
	background: $color2;
}

my_mixin_revised is incorrect because the variable we pass into the mixin is $color but we call $color2 inside the context of the mixin. This is inconsistent and will cause an error when SASS renders to CSS.

With programming languages such as JavaScript, PHP, Python, and Ruby, there exists what we call variable scope which refers to the context (or scope) within a SASS script which a variable may be accessed and used. Setting aside the smoke and mirrors, let us see an example we can break apart:

$color1: red;
$color2: blue;
@mixin my-mix($color1, $color2) {
    background: mix($color1, $color2);
}
body { @include my-mix(); }

We have two variables defined here $color1: red; and $color2: blue;. We created a mixin called my-mix which takes in two parameters into the mixin. We know this mixin will work because our parameters are consistent. Our implementation seems to be reasonable. Perhaps we would predict our outcome to be the following:

body { background: #7f007f; }

Our result is a purple color that has no green value. Is this what we can expect? No, we cannot expect this because of variable scope issues. When we have a variable defined inside the context of a mixin, if-else statement, loop, function(s), or any type of branching statement (that is one who has curly braces), that variable takes precedence over any variable defined out of the branching statement. For our example, this means that despite the fact that we have predefined values for $color1 and $color2, they will not be inherited by the $color1 and $color2 variables inside the mixin.

The correct was to implementation this mixin is the following:

body { @include my-mix($color1, $color2); }

This is because we have two set values which are are passing into the mixin. We know that despite whatever values we have defined outside of functions, branching statements, and mixins, they will not be inherited by SASS. Try these examples for yourself and test the output http://sass-lang.com/try.html!

How to include Mixins

We understand how to correctly pass variables into our mixins but now we need to know how to include them in our SASS scripts. You've probably seen @include directive in the examples above. This is exactly how you include mixins inside our selectors. Here is an example:

selector { @include mixin_name(); }

All we need to do in order to include a mixin is use the @include directive followed by the name of the mixin and any parameters we need so SASS can render to CSS without any errors.

Passing Variables into Mixins Continued

We learned the fundamentals about passing variables into mixins and functions in SASS; however, we need to touch base on one last topic before we learn about control structures in SASS. Unlike languages such as python, ruby, PHP, and JavaScript, in SASS we can have an undefined number of parameters or an uncertain amount of parameters as in a list. Here is an example:

@mixin font($size, $weight, $family...) {
    font: $size $weight $family;
}

In a normal font definition we might see something like:

font: 12px normal 'Arial', Tahmoa, Verdana, sans-serif;

If we were to break apart this we would see:

font-size: 12px;
font-weight: normal;
font-family: 'Arial', Tahmoa, Verdana, sans-serif;

By looking at these properties we see that font-family is a list and can contain and uncertain number of values depending on our needs when we use this mixin. SASS calls these variable arguments which are arguments at the end of a mixin declaration that take all leftover arguments and package them up as a list. Variable arguments are best used when we have an uncertain number of arguments we need to pass into a mixin such as for font-family properties, box-shadows, text-shadows, etc. Note: variable arguments always come at the end of all mixin parameters, failure to do so will result in an error! A live example of this can be seen here http://codepen.io/atomicpages/pen/zEvKl.

Programmer's Approach to SASS

For all those programmers out there, we will be covered four languages to relate SASS to. These are all web-based languages and we will NOT be covering languages such as Java/JSP, C, Objective-C, C#, C++, etc. Here are the languages we will be using:

  • JavaScript
  • PHP
  • Python
  • Ruby

We will be covering:

Setting Variables in SASS

Possessing the ability to set variables is the absolute basics of programming. SASS-flavored variables appear to be a cross between PHP and CSS. Review your individual language for setting variables if you need a refresh:

JavaScript PHP Python Ruby SASS

JavaScript

For JavaScript developers we declare variables like the following:

var variable = 3;

PHP

In PHP we declare variables like:

$variable = 3;

Python
variable = 3

Ruby
variable = 3


In SASS, the syntax is as follows:

$variable: 3;

We use the dollar symbol (as we would in PHP or Perl) and instead of a conventional equals sign, we use a colon instead. Note: for python and ruby developers, do not forget the semi-colon after each statement! Like JavaScript and PHP, SASS relies on these semicolons to know when the statement ends! SASS does offer an indented-style syntax as an alternative to SCSS-style syntax. We will cover this in later tutorials.

Acceptable Data Types in SASS

We can have the following data types when using SASS:

Numbers

SASS supports all numeric data types be it int, double, float, long, short, etc. The main selling point of SASS is that we can KEEP our units when doing arithmetic operations. Let's compare a simple script and a SASS script:

JavaScript PHP Python Ruby SASS

JavaScript
var size = 12;
var unit = 'px';
document.write( (size * 2) + unit ); // outputs 24px

PHP
$size = 12;
$unit = 'px';
echo ($size * 2) . $unit; // outputs 24px

Python
size = 12
unit = 'px'
print(str(size * 2) + unit) # outputs 24px

Ruby
size = 12
unit = 'px'
puts " #{(size * 2)}#{unit}" # outputs 24px

$size: 12px;
body { font-size: $size * 2; } // outputs 24px

In SASS we can see that there is no need to omit the units when doing arithmetic operations. SASS understands that it needs to only run calculations on numbers and not letters.

Creating Mixins in SASS

In most programming languages, there are functions that take parts of code and package them into reusable functions. JavaScript, PHP, Python, and Ruby are no exception to this.

JavaScript PHP Python Ruby SASS

JavaScript

In JavaScript we define functions as such:

function name(name) {
	return name.length;
}
document.write( name(&quot;Dennis&quot;) );

PHP

In PHP we define function like this:

function name($name) {
	return strlen($name);
}
echo name(&quot;Dennis&quot;);

Python
def name(name):
	return len(name)
name(&quot;Dennis&quot;);

Ruby
def name(name)
	name.length
end
name(&quot;Dennis&quot;)


Mixins are different than normal functions. Functions usually return or print a value where mixins do not return any values or print any values. Mixins in SASS are a way to bundle together reusable pieces of CSS with or without parameters.

To begin writing mixins, we need to become acquainted with the @mixin directive. Normally function or def would be our starting keyword, in SASS it's @mixin. Here is an example:

@mixin my_mixin() {
	property: value;
}

SASS expects mixins to have a property and value since we are including pieces of packaged CSS which makes mixins so helpful. Below are additional examples of mixins:

@mixin reset() {
    html, body, div, span, applet, object, iframe,
    h1, h2, h3, h4, h5, h6, p, blockquote, pre,
    a, abbr, acronym, address, big, cite, code,
    del, dfn, em, img, ins, kbd, q, s, samp,
    small, strike, strong, sub, sup, tt, var,
    b, u, i, center,
    dl, dt, dd, ol, ul, li,
    fieldset, form, label, legend,
    table, caption, tbody, tfoot, thead, tr, th, td,
    article, aside, canvas, details, embed, 
    figure, figcaption, footer, header, hgroup, 
    menu, nav, output, ruby, section, summary,
    time, mark, audio, video {
        margin: 0;
    	padding: 0;
    	border: 0;
    	font-size: 100%;
    	font: inherit;
    	vertical-align: baseline;
    }
    /* HTML5 display-role reset for older browsers */
    article, aside, details, figcaption, figure, 
    footer, header, hgroup, menu, nav, section {
    	display: block;
    }
    body {
    	line-height: 1;
    }
    ol, ul {
    	list-style: none;
    }
    blockquote, q {
    	quotes: none;
    }
    blockquote:before, blockquote:after,
    q:before, q:after {
    	content: '';
    	content: none;
    }
    table {
    	border-collapse: collapse;
    	border-spacing: 0;
    }
}

Above is a mixin containing Eric Meyer's lovely CSS reset script which is helpful for building web site from the ground up. Notice how this mixin has selectors, properties, and values. Selectors for mixins are not mandatory when defining mixins. Let's see more examples:

@mixin default_font() {
	font-size: 12px;
	font-weight: normal;
	font-family: Arial, Helvetica, sans-serif;
	font-size: normal;
}

This mixin does not contain any selectors and is still a valid mixin. We can see that we need not have any selectors inside of a mixin in order for it to be valid.

Using Mixins

Unlike a function/method call in one of our web languages where we simply call the function/method such as:

print my_function()

We need an @include directive before SASS will render our mixin. Here are examples of how to include the two mixins we created above:

@include reset();
body { @include default_font(); }

Our result would look like the following:

Mixin Parameters & Variable Arguments

Parameters are essential to any function/method definition. They allow us to alter values inside of functions and methods without editing the the code itself. Mixins allow us to pass in variables into the mixin just like functions or methods (see here for a refresh).

Let's add some configuration options to the mixin we created earlier. We want to be able to edit the font size, weight, and style right off the bat:

@mixin default_font($size, $weight, $style) {
	font-size: $size;
	font-weight: $weight;
	font-family: Arial, Helvetica, sans-serif;
	font-size: $style;
}

As a programmer, this is nothing you haven't seen before. If you're not familiar with passing values into functions then please read more here.

Like most languages, SASS will take in arguments separated by commas. Note: the same variable scope rules apply to SASS scripts as they do in JavaScript, PHP, Ruby, Python, and many other languages! Let's check out an implementation of this mixin:

body { @include default_font(12px, 700, italic); }

Results in:

body {
	font-size: 12px;
	font-weight: 700;
	font-family: Arial, Helvetica, sans-serif;
	font-size: italic;
}

Variable Arguments

Variable arguments is where SASS's list data type comes into play. Lists are not arrays or lists, they are simply strings of text separated by a space or a comma in SASS. SASS supports lists by using variable arguments. We can tell SASS we want a variable argument by a variable followed by three periods (...):

@mixin mixin($variable...) { /* no definition */ }

Variable mixins must be the last parameter in a series of multiple parameters otherwise SASS will show an error at the time of rendering. Let's alter our default_font mixin to allow for font-family configuration:

@mixin default_font($size, $weight, $style, $family...) {
	font-size: $size;
	font-weight: $weight;
	font-family: $family;
	font-size: $style;
}
body { @include default_font(12px, 700, italic, Arial, Helvetica, sans-serif); }

SASS understands that our fourth parameter is a list and not a series of individual parameters because we stated the fourth parameter will be having a list passed in.

Our result will be:

body {
	font-size: 12px;
	font-weight: 700;
	font-family: Arial, Helvetica, sans-serif;
	font-size: italic;
}

Failure to specify variable arguments will result in an error resembling Sass Error: Mixin default_font takes 4 arguments but 6 were passed.

To review all of the concepts we covered in this tutorial please see a live demo here: http://codepen.io/atomicpages/pen/zEvKl.

Go to Top