eknowledger’s Technical Log

Statistical Modeling : Simple Linear Regression

2020-01-31T00:00:00+00:00

Statistical Modeling

Statistical modeling is the practice of summarizing observation and create inferences from it. observation represented in data points includes lots of details. for example, if we observe house sales information in a certain location, we could collect information on the size of the house, price, location, etc.. for now let’s assume that we are concerned only with price and square footage of the house. we observed 100 house sales. there is going to be a lot of information in this data set that we don’t necessarily want to keep track of. imagine now we have 1000 observations (data points). Statistical modeling enables us to create summaries from data, to describe the general trend or overall shape of the data without keeping all track of all observation and data points. Statisticians sometimes refer to this idea by data compress.

%matplotlib inline
import matplotlib as mpl
import matplotlib.pyplot as plt
mpl.rc('axes', labelsize=14)
mpl.rc('xtick', labelsize=12)
mpl.rc('ytick', labelsize=12)

import numpy as np
np.random.seed(56)
X = 2 * np.random.rand(100,1)
y = 8 + 5 * X  + np.random.randn(100 ,1)

plt.plot(X,y, "b.")
plt.xlabel("X", fontsize=12)
plt.ylabel("y", rotation=0,fontsize=12)
plt.show()

The first task of statistical modeling is to summarize or compress this information through a representative model describing correlations in the data. but it does not stop there. Modeling enables us to enter the realm of inference - if we are trying to extend our knowledge from the data we have already, to other variables we have not to measure or didn’t measure directly - essentially extrapolating from sample data to a larger population is an inference based on modeling.

But more importantly, observations are prone to measurement errors, whether this has to do with mistakes, deliberate lies, possibly incorrect assumptions made at various stages, accidents,etc.. some of these sources for error are systematic where it will distort data in predictable, repeatable ways. but some other sources of errors are statistical it is directionless, do not repeat itself yet the distribution of errors in data is still predictable and stable (probability theory helps us to handle such errors).

Simple Linear Regression Model

The most basic of all statistical models and a foundation of most predictions in the world of machine learning is Simple Linear Regression. The model of two random variables, $y$, and $X$ , where we are trying to predict $y$ from $X$. and like any good statistical model, it has a few key assumptions:

$X$ distribution is unspecified, possibly even deterministic.
$y \mid X = \beta_0 + \beta_1x + \epsilon$ , where $\epsilon$ is a noise variable.
$\epsilon$ has mean 0, a constant variance $\sigma^2$, and is uncorrelated with $X$ and uncorrelated across observations.

the model assumes a noise $\epsilon$ normally distributed Gaussian to represent measurement error or fluctuations in $y$, or both. The coefficient $\beta_0$ represents and intercept or initial state. where the coefficient $\beta_1$ represent weights added to variable $X$ to predict $y$.

We could plot a simple regression model on the above dataset to compress and summarize the description of the data.

X_b = np.c_[np.ones((100, 1)), X]
beta_1 = np.linalg.inv(X_b.T.dot(X_b)).dot(X_b.T).dot(y)
X_new_b = np.c_[np.ones((100,1)), X]
y_predict = X_new_b.dot(beta_1)

# Plot model predictions
plt.plot(X, y_predict, "r-")
plt.plot(X, y, "b.")
plt.show()

As you can see from the plot, the regression model line compresses the 100 data points into a simpler linear upward trend that is easy for humans to remember and reason about. even better it helps us predict other data points that obey the same assumptions of the simple linear regression model.

Linear Regression probably the most basic simplest and popular tool in regression modeling. dating back to the late 19th century. its basic assumption a linear relationship between input random variable $x$ and target random variable $y$. This linear relationship can is represented by the algebraic formula $y \mid X = \beta_0 + \beta_1x + \epsilon$ . In simple terms, $y$ can be expressed as a weighted sum of the inputs $X$, with additive noise $\epsilon$ to the observations. and as we described earlier the assumption is this noise is well behaved following a Gaussian distribution. In our introductory example, we can describe the price of a house given an input of the area of the house using a linear model as $price = \beta_0 + w_{area} \cdot area$ .

Where:

$\beta_0$: is bias (sometimes called intercept or offest).
$w_{area}$: are weights determine the influence of the area on the target (house price)

We can generalize this model for more than one input or feature to describe a linear relationship between inputs to a target variable. for example, we can describe the relationship between house prices with respect to house area and the number of rooms. $price = \beta_0 + w_{area} \cdot area + w_{rooms} \cdot rooms$

The goal in designing a linear model in the machine learning world is to build a model from a training dataset to help us predict future target $y$ values. for example, predicting house prices given area and number of rooms. So if we have an input observations dataset $X$ the goals become to choose weights $w$ and a bias $\beta_0$ such that on average, the predictions made with this model are as close as possible (fit) the true house prices we observed in the data.

The predicted $y$ values is referred to in mathematical notation using the hat symbol $\hat{y}$

$\hat{y} = \beta_0 + w_1 \cdot x_1 + ... + w_d \cdot x_d$ In high dimentionality suitations we collect all input features in a vector $\mathbf{X}$ and all weights into a vactor $\mathbf{w}$. then the model can be expressed concisely using dot product.

$\hat{y} = \beta_0 + \mathbf{w}^T \mathbf{X}$

but before we start finding the best parameters $w$ and $\beta_0$ for our model we will need first to have a quality measure for the given model. that is how do we know that our model was able to predict $y$ correctly. and once we can measure model performance we will need a procedure to improve the model’s prediction quality.

Measure of Quality

Measuring the quality of linear model prediction is key to improve model prediction quality. that is we need a measure of fitness before we start fitting the model to data. Loss Function quantify the distance between the real and predicted value of the target variable. The loss will usually be a non-negative number where smaller values are better and perfect predictions incur a loss of $0$.

Sum of Squared Errors

This is the most popular loss function in regression problems. for a data point $i$, and real target $y_i$ and predict value $\hat{y_i}$. the squared erros is given by:

$l_i(\mathbf{w}, \beta_0) = \frac{1}{2} \left(\hat{y}_i - y_i\right)^2$

To measure the quality of a model on the entire dataset, we simply average (or equivalently, sum) the losses on the training set.

$L(\mathbf{w}, \beta_0) =\frac{1}{n}\sum_{i=1}^n l_i(\mathbf{w}, \beta_0) =\frac{1}{n} \sum_{i=1}^n \frac{1}{2}\left(\mathbf{w}^\top \mathbf{x}_i + b - y_i\right)^2$

When training the model, we want to find parameters ($\mathbf{w}^, \beta_0^$) that minimize the total loss across all training samples:

$\mathbf{w}^*, \beta_0^* = \operatorname*{argmin}_{\mathbf{w}, \beta_0}\ L(\mathbf{w}, \beta_0).$

Linear Regression happens to be one of the models that have an analytical solution to the optimization problem. other more complicated models don’t have a solution that can be solved analytically by a simple formula yielding the global optimum; in which case a numerical solution can be used to optimize the model like Gradient Decent algorithm. I’m not going in the mathematical details for how to optimize Linear Regression analytically, we can subsume the bias $\beta_0$ into the weight parameter $w$ and the final formula for computing optimum w would be:

$\mathbf{w}^* = (\mathbf X^T \mathbf X)^{-1}\mathbf X^T y.$

you can easily implement the above formula using NumPy to compute the weights for linear regression. but don’t get used to this easy life, mathematical analysis is not always easy to compute.

w = np.linalg.inv(X.T.dot(X)).dot(X.T).dot(y)
print(w)

Gradient Descent to the Rescue!

For high-dimensionality and nonconvex loss surfaces (surfaces with more than single minima), the Gradient Descent algorithm is an effective model in practice to optimize the model. the key idea behind the algorithm is to iteratively reduce the error by updating parameters in the direction that incrementally lowers the loss function. On convex loss surface (Single Global Minima) it will converge to the minima; the same can’t be said for nonconvex surfaces but at least it will lead towards a local minimum.

Real World Example

Let’s try Linear Regression out on a real dataset. Below I’m going to load in a dataset of Seattle housing prices from here It has the following features:

id: a notation for a house
date: Date house was sold
price: Price is the prediction target
bedrooms: Number of Bedrooms/House
bathrooms: Number of bathrooms/House
sqft_living: square footage of the home
sqft_lot: square footage of the lot
floors: Total floors (levels) in house
waterfront: House which has a view to a waterfront
view: Has been viewed
condition: How good the condition is ( Overall )
grade: overall grade given to the housing unit, based on King County grading system
sqft_above: square footage of house apart from the basement
sqft_basement: square footage of the basement
yr_built: Built Year
yr_renovated: Year when the house was renovated
zipcode: zip
lat: Latitude coordinate
long: Longitude coordinate
sqft_living15: Living room area in 2015(implies– some renovations) This might or might not have affected the lot size area
sqft_lot15: lotSize area in 2015(implies– some renovations)

We minimally process the data to make it amenable to analysis as follows:

fill in any missing data with the average value for that column
delete the date and the value sqft_basement

We don’t have to reinvent the wheel, so we will use the most common implementation of linear regression, found in sklearn library. sklearn is the standard package used for the majority of (non-neural network based) machine learning techniques. It contains nice implementations with a common interface for the majority of commonly encountered techniques.

from sklearn.linear_model import LinearRegression

# kc_house_data
# https://www.kaggle.com/shivachandel/kc-house-data
# House sales in King County, Washington State


data = pd.read_csv('kc_house_data.csv')
data = data.drop(['date','sqft_basement'],axis = 1)
data = data.fillna(data.mean())

model = LinearRegression()
model.fit(data.drop('price',axis=1),data['price'])
print("R squared of full model is: {}".format(model.score(data.drop('price',axis=1),data['price'])))

Ruelle, David (1991). Chance and Chaos. Princeton, New Jersey: Princeton University Press.
Smith, Leonard (2007). Chaos: Avery Short Introduction. Oxford: Oxford University Press.

XPress: Simple Truth Expression Language

2019-07-14T00:00:00+00:00

Background

How many times you needed a quick, simple method to create expressions in a Json or XML element value. and you wished there were an easy wy to create dynamic expressions at compile time as a literal string to be compiled and evaluated at runtime using the same powerful CLR. Well, I have!

The need for string expressions that can be simply expressed at compile time by engineers or non-engineering business or support team, has been a recurring theme through out my career. Whether its is business rules, business teams needs to modify it and change it frequently at runtime. or operation rules that devops team would like to control at runtime without the need to make a new deployment.

Goals

So, I rolled up my sleeves and created XPress. It came handy in many situations and i used it in different product and solution. I had a few goals in mind when I designed XPress:

Simple, yet powerful.
Contained as possible, as little dependencies as possible.
few to zero configurations.
Purely written in C# and .net.
Fast, and efficient.
Generates an optimized cacheable .net expressions .
Support all truth operators (Binary, Unary, Relational, and Conditional).
Support basic data types int32, string, boolean, float.
Support variable binding at runtime.
Ability to check on null-ability.

How it works?

PM> Install-Package XPress

XPress is simple, all you have to do after installing XPress package using nuget manager, is instantiating XpressCompiler, author XPress expressions, compile it, and execute it. here is a simple XPress sample code:

XpressCompiler _compiler = XpressCompiler.Default;

// Create and Compile Expression
var expression = "x gt y*2";
var compilationResult = _compiler.Compile(code);

// Create XpressRuntimeContext object with variable names and values
XpressRuntimeContext runtimeCtx = new XpressRuntimeContext() { { "x", "10" }, { "y", "9" } };

// Call compiled Func with runtime context
var result = compilationResult.Code(runtimeCtx);

As you can see, XPress language doesn’t need much. very little configuration to start and you’re good to go. If you notice I used XpressCompiler.Default a singleton compiler instance can be used quickly to compile expressions. But a compiler instance can be always instantiated through constructor.

XpressCompiler _compiler = new XpressCompiler();

The compiler class offers a single method Compile(string) taking an xpress expression and return a compilation result. The XpressCompilationResult object offers a boolean flag Compiled to indicate the success or failure of the compilation process, and a Log object of type ILogReader which can be used to get status on compilation process and debug the result. a particularly useful pattern after compilation process is to check the HasErrors fla, if true GetErrorMessages() and print it or log it.

if (compilationResult.Log.HasErrors)
{
    var errors = compilationResult.Log.GetErrorMessages();
    foreach(var error in errors)
    {
        Console.WriteLine(error);
    }
}

Finally, the compilation result object, will have a Code predicate of type Func<XpressRuntimeContext, bool> that is the optimized compiled .net expression tree for your string expression. it accepts XpressRuntimeContext which is simply a strongly typed dictionary of <string,string> to bind expression’s variables to runtime values. use the XpressRuntimeContext object to pass values to your variables. Code predicate jsut like any other .net Func can be cached and executed multiple time. the result of execution is a boolean.

Language Features

Variables

Variables literals can be used anywhere within an expression The variable name follows same C# variable literals naming constraints. It Must start with a letter, or _, and it may contain Unicode letter characters, decimal digit characters, Unicode connecting characters, Unicode combining characters, or Unicode formatting characters.

var e = "y eq x+2*2-4/2";

Operands

XPress supports boolean literals of true and false values, numerical operands of int32 and float decimal values, and string operands. notice how the operand values are defined in the next sample code:

var e1 = "true";
var e2 = "false";
var e3 = "9 gt 10";
var e4 = " 'Ahmed' eq 'ahmed'";

a null operands can also be expressed to compare a string with nothing

var e = " 'Ahmed' ne null";

Binary Expressions

+, -, *, /, % is supported on numerical operands

var e = "x eq (1+2)";

If + or - operators applied to a string operands it will act as String.concat()

var e = "x eq ('ahmed '+'elmalt')";

Note: Binary operators can’t be applied to mixed types of operands.

Unary Expressions

At the moment only unary logical operators are supported. not can onyl be applied to boolean operands or expressions.

// boolean operands
var e1 = "not false";
        
// boolean variables, the value of x must be set to a boolean value at runtime or runtime error
var e2 = "not x";
        
// boolean expression
var e3 = "not ('a' eq 'b' and 9 gt 10)";

Notice i applied not to variable x in the previous example. which is acceptable by XPress compiler. it will assume that value of x will be boolean at runtime otherwise it will throw a runtime exception.

Relational Expressions

The following relational expressions are supported:

eq Equal
ne Not Equal
gt Greater Than
lt Less Than
ge Greater Than or Equal
le Less Than or Equal

var e = "1 eq 4";

Conditional Expressions

The real power of XPress is composition, you can compose powerful expressions using conditional logical and and or

or Logical OR
and Logical AND

var e = "false or x lt 2";

Operator Precedence

Parentheses: ()
Unary Logial Operators: not
Binary Multiplicative Operators: *, / , %
Binary Additive Operators: +, -
Equality Operators: eq, ne
Logical Operators: gt, lt, ge, le
Conditional Operators: and, or
XPress is very powerful and can be used to compose sophisticated boolean expressions as strings.

var e = "(x ne null and x+1 gt 10) or (y ne null and (y*(5+1)-2) lt 5)";

What about performance?

XPress is built to be fast and optimized to generated very efficient .net lambda expressions. the most expensive part of the process as you can expect is the compilation of expressions, but this phase needs to occur once, and the result can be cached for the lifetime of the application. on average Xpress compilation phase takes about ~120ms.

Find more information about XPress on project github repository. I will be blogging more in the future about the internals implementation of the language and its compiler.

XPress is distributed under MIT license. What are you waiting, give it a try and let me know what you think!

Happy Coding!

Implement a Queue

2017-12-13T00:00:00+00:00

Problem

Write an efficient Queue<T> a FIFO datastructure offers Enqueue and Dequeue operations.

Example

var q = new Queue<int>();
q.Enqueue(10);
q.Enqueue(3);
q.Dequeue();
q.Enqueue(4);
q.Enqueue(5);

Analysis

Queue is a FIFO data structure; items added and removed in first-in0first-out order. In different word insertion and deletion happens on two different ends.

There are several methods to implement queues, each with different Time and Space Complexity. assuming that the data structure will support two main operations Enqueue and Dequeue

    public interface IQueue<T>
    {
        void Enqueue(T item);
        T Dequeue();
    }

Method 1 - Array based Queue

In this approach, we will use a fixed length array to store the queue elements, and two pointers, head to point at the first item in queue to be removed on calling Dequeue and tail pointing at the next empty position in the queue. with Every enqueue operation we will move the tail pointer to next empty position, and with every dequeue we will decrement the head pointor to point at the next item in line. we will also keep a size varible to assist in determinig if the queue is full by comparing to initial capacity.

Operation	Time Complexity
Enqueue	O(1)
Dequeue	O(1)
Remove	n/a

Note Arrays are fixed length data structure, dequeuing items from the queue will leave empty spots in the array not utilized which will lead to wasted space, a more efficient approach is to build a circular array, wraps around to the first position. The Size variable will be key in this approach since it will be used to determine if there are space left in the array to wrap around .

Method 2 - LinkedList based Queue

Linked List is a very efficient and flexiable data structure, it will gives time complexity of O(1) for both adding and removing just like arrays. and also will enable us to change the queue items in the middle (although not usually needed operation).

Note Theoritically Arrays and LinkedLists will give you `O(1) head and tail inserts and deletes which in turns works very well for implementing a queue. But practically the overhead of an array is much less than linkedlist. Array is much more efficient data structure in memroy than a linkedlist.

Notice using LinkedList to store data internally for the queue, enabled me to implmement Remove(T item) method, the method will run in O(K) where k number of elements iterated until match found.

Operation	Time Complexity
Enqueue	O(1)
Dequeue	O(1)
Remove	O(k)

Bouns - Implement a Queue using two stacks

This is not a usual method to implement queues since it’s not efficent for both Time and Space Complexity! but it’s a fun problem to play with. if we are given two Stack<T> how can we implement a queue. Stack is the oppsite data strucuture of queue. Last-in-First-Out or LIFO

We will use one Stack for Enqueue operation, which will be very fast operation O(1) , and we will use the other stack to handle Dequeue this will make the operation more costly in terms of time complexity. here are the steps:

If enqueue and dequeue stacks are emtpy then queue is empty return default(T)
If dequeue stack has values then pop value from dequeue stack and return it.
if dequeue stack has no values
- while enqueue stack is not empty, pop items from enqueue stack and push to dequeue stack
pop item from dequeue stack

Operation	Time Complexity
Enqueue	O(1)
Dequeue	O(k)
Remove	n/a

Happy Coding!

Is a Palindrome String?

2017-12-11T00:00:00+00:00

Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example

Input : "Red rum, sir, is murder" is a palindrome, while"
Output: true

Input : "Ahmed is Engineer"
Output: false

Input : ""
Output: true

Input : "a"
Output: true

Analysis

A usual palindrome problem is a little easier, since the assumption is all sort of charachters are included, for instance “abba” is a simple palindrome. we can use two indcies to traverse forward and backward and compare values for matching, an algorithm of time compliexity O(n/2)

    public static bool IsPalindrome(string str)
    {
        if (string.IsNullOrEmpty(str) || str.Length == 1)
            return true;

        int i = 0; int j = str.Length - 1;
        while(i < j)
        {
            if (str[i++] != str[j--]) return false;
        }


        return true;
    }

But in this case we want to only consider alphanumeric characters and ignoring cases , we still run a forward and backward traverse , for each charachter we will check is letter is letter or digit using framework helper methdo Char.IsLetterOrDigit() , if not then we move get next charachter until we get an alphanumeric char.

CSharp Solution

Happy Coding!

Search For Range

2017-12-08T00:00:00+00:00

Problem

Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n) . If the target is not found in the array, return [-1, -1] .

Example

Input : [0,1,3,3,3,3,3,3,3,3,10] , value = 3
Output: [2,9]

Input : [5,7,7,8,8,10] , value = 8
Output: [3,4]

Input : [] , value = 7
Output: [-1,-1]

Input : [1,3,5,6] , value = 5
Output: [2,2]

Analysis

The problem forces us to think in BinarySearch algorithm’s term, since the time complexity myst be in order of O(log n) . We can design an algorithm using Binary search to get to the first occurance of element, if found we can traverse teh array backward and forward to find the start and end of the range which will add another O(m+k)

CSharp Solution

Happy Coding!

Search Insert Position

2017-12-07T00:00:00+00:00

Problem

Given a sorted array and a value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.

Example

Input : [1,3,5,6] , value = 5
Output: 2

Input : [1,3,5,6] , value = 2
Output: 1

Input : [1,3,5,6] , value = 7
Output: 4

Input : [1,3,5,6] , value = 0
Output: 0

Analysis

An easy method to solve the problem is to iterate through the array comparing target with value if found return, if greater return index since this will be the location of insertion. Time Complexity: O(n)

But we can do better! The problem is a search problem, and as we know BinarySearch is better algorithm for searching it will give us Time Complexity = O(log(n))

Solution 1 - Using Recursion

    public static int SearchInsert(int[] array, int value)
    {
        var median = array.Length / 2;

        if (array == null || array.Length == 0) return 0;

        return BinarySearch(array, 0, array.Length - 1, value);

    }

    private static int BinarySearch(int[] array, int min, int max, int value)
    {
        var mid = (min + max) / 2;

        if (value == array[mid])
            return mid;

        if (value < array[mid])
            return (min<mid)? BinarySearch(array, min, mid-1, value) : min;
        else
            return (max>mid)? BinarySearch(array, mid+1, max, value) : max+1;
    }

Solution 2 - Using a loop

    public static int SearchInsert(int[] array, int value)
    {
        if (array == null || array.Length == 0) return 0;

        int i = 0;
        int j = array.Length - 1;

        while(i <= j)
        {
            var mid = (i + j) / 2;

            if (value < array[mid])
                j = mid - 1;
            else if (value > array[mid])
                i = mid + 1;
            else return mid;
        }

        return i;
    }

Time Complexity : O(log(n)) Space Complexity : O(1)

Happy Coding!

Intersection of Two Arrays

2017-12-06T00:00:00+00:00

Problem

Given two arrays, write a function to compute intersection of arrays

Example

Input : array1 = [7, 1, 5, 2, 3, 6] , array2 = [3, 8, 6, 20, 7]
Output: [3,6]

Find Intersection of Unsorted arrays using Hash

Assuming that arrays doesn’t have duplicates, and arrays are not sorted, we can design a solution use an efficient data structure HashSet to compute the intersection, the benefit of using HashSet add and find operation has O(1) time complexity.

Initialize empty HashSet
Iterate first array and put elements in set
Iterate second array, and for each element search element in set, if present then its part of intersection.

Solution - CSharp

    public static int[] Intesect(int[] a, int[] b)
    {
        HashSet<int> map = new HashSet<int>();
        List<int> result = new List<int>();

        for (int i = 0; i < a.Length; i++) // o(n)
            map.Add(a[i]); // o(1)

        for (int i = 0; i < b.Length; i++) //o(m)
            if (!map.Contains(b[i])) // o(1)
                result.Add(b[i]);

        return result.ToArray();
    }

Time Complexity : O(m+n) Space Complexity : O(n)

Note I omitted List<int> data strucuture size used to capture results from Space Complexity, as well as .ToArray() method call used to convert list ot array, from Time Complexity to simplify, in reality these function are not a constant operations.

Find Intersection of sorted arrays

If we assume arrays are sorted and doesn’t contain duplicates, this will simplify things a bit and give us a chance to optimize the algorithm further. We can use BinarySearch to compary arrays.

Iterate through two array
Compary element in first array with element from second array
If less advance first array pointer, if greater advance second array pointer, otherwise its an intersection element

Solution - CSharp

    public static int[] Intesect(int[] a, int[] b)
    {
        int i = 0;
        int j = 0;
        List<int> result = new List<int>();

        while(i < a.Length && j < b.Length)
        {
            if(a[i] < b[j])
                i++;
            else if (a[i] > b[j])
                j++;
            else
            {
                result.Add(a[i]);
                i++;
                j++;
            }
        }

        return result.ToArray();
    }

Time Complexity : O(nlog(n)) Space Complexity : O(1)

Happy Coding!

Remove Element from Array

2017-12-05T00:00:00+00:00

Problem

Given an array and a value, remove all instances of that value in place and return the new arary.

Example

Input : [1,10,5,3,4,5,2,5,7,3,7,5] , value = 5
Output: [1,10,3,4,2,7,3,7]

Input : [2] , Value =2
Output: []

Input : [1,2]  , value = 4
Output: [1,2]

Analysis

The problem can be solved easily by using two indices, one pointing at current element, another to point at location to copy elements. The solution will traverse the array, matching with element value, if matched it will skip ahead, if not matched it will copy to j location and increament the location counter.

Note Arrays are fixed length data structure, changing the length of an array in place is usually done by copying elements; We will use built in Array.Resize() apis to resize in place, and assume operation runs in O(1). But in reality this is not the case.

Solution - CSharp

        public static int[] RemoveElement(int[] array, int e)
        {
            int j = 0;
            for (int i = 0; i < array.Length; i++)
                if (array[i] != e)
                    array[j++] = array[i];

            Array.Resize(ref array, j);
            return array;
        }

Time Complexity : O(n) Space Complexity : O(1)

Bouns

Given an array of numbers, write a function to move all 0’s to the end of it, while maintaining the relative order of non-zero elements.

Example

Input : [0,1,0,3,10] 
Output: [1,3,10,0,0]

Solution

We can use the same method as before, where we maintain two index, j pointing at copy location where we will move elements. and i to traverse the array. We traverse the array forward coparing each element with 0 if not equal we copy element to j and zero out its location i.

Solution - CSharp

    public static int[] MoveZeros(int[] array)
    {
        int j = 0;
        for (int i = 0; i < array.Length; i++)
        {
            if(array[i] != 0)
            {
                var temp = array[i];
                array[i] = 0;
                array[j++] = temp;
            }
        }

        return array;
    }

Time Complexity : O(n) Space Complexity : O(1)

Happy Coding!

Remove Duplicates from Sorted Array

2017-12-04T00:00:00+00:00

Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return array.

Example

Input : [1,1,2,2,3,4,4]
Output: [1,2,3,4]

Input : [1,1,1]
Output: [1]

Input : [1,2]
Output: [1,2] ## Analysis

The problem can be solved easily by using an extra temp array and copy the unique elements to the temp array. Or with a little more work to do all work in place, if we have memory constraints.

Either case solution should run in O(n) speed.

Solution 1 - Using Temporary Array

This solution will create a temporary auxiliary array to store unique numbers.

The algorithm will traverse the original array, comparing each element with next, if not duplicate, it will copy the unique element to temporary.

        public static int[] RemoveDuplicates(int[] array)
        {
            if (array.Length < 2)
                return array;

            int[] tempArray = new int[array.Length];

            int j = 0; // unique nubmer index
            for(int i = 0; i < array.Length-1; i++)
                if (array[i] != array[i + 1])
                    tempArray[j++] = array[i]; // tempArray[j] = array[i]; j = j+1;

            // Copy last element in main array duplicate or not
            // since it will not get copied as part of the loop
            tempArray[j++] = array[array.Length -1];

            // There are no better method to resize arrays
            Array.Resize(ref tempArray, j);
            return tempArray;
        }

Time Complexity : O(n) Space Complexity : O(n)

Solution 2 - Using Constant Space

This solution will utilize the same array to sort out the duplicates. It will only use an extra index to keep track of the last unique nubmer in the array.

The algorithm will traverse the array forward, comparing element with next element; if not equal elements it will copy the current element to last unique index location. Then array will be reseized at last unique index.

        public static int[] RemoveDuplicates(int[] array)
        {
            if (array.Length < 2)
                return array;
            // unique number index
            int j = 0;
            for (int i = 0; i < array.Length - 1; i++)
                if (array[i] != array[i + 1])
                    array[j++] = array[i]; // array[j] = array[i]; j = j+1;

            array[j++] = array[array.Length - 1];

            Array.Resize(ref array, j);
            return array;

        }

Time Complexity : O(n) Space Complexity : O(1)

Bouns

What if duplicates are allowed at most twice ?

Example

Input : [1,2,2,2,3,3,3,3,4,5,5,5]
Output: [1,2,2,3,3,4,5]

The solution still straightforward, we will use a counter for duplicates and check for how many duplicates desired

        public static int[] RemoveDuplicates5(int[] array)
        {
            if (array.Length < 2)
                return array;
            // unique number index
            int j = 0;
            int k = 0; // count for how many duplicates allowed
            for (int i = 0; i < array.Length - 1; i++)
                if (array[i] != array[i + 1])
                {
                    array[j++] = array[i]; // array[j] = array[i]; j = j+1;
                    k = 0;
                }
                else
                {
                    if (k < 1)
                    {
                        array[j++] = array[i];
                        k = k + 1;
                    }
                }

            array[j++] = array[array.Length - 1];

            Array.Resize(ref array, j);
            return array;
        }

Time Complexity : O(n) Space Complexity : O(1)

Happy Coding!

Configure 1&1 domain for GitHub Pages Site

2017-12-03T00:00:00+00:00

The process of setting up a custom domain name for a GitHub Pages website is straight forward, but it could be confusing if you haven’t setup a domain before. I will use 1&1 a domain name register to setup GitHub Pages website domain. The process should be similar using other domain registers such as GoDaddy.

Configure domain on GitHub

First we start by setting up the domain name on GitHub Pages repository. Under your GitHub repository settings, find GitHub Pages section then set Custom domain to your domain name and hit save.

Configure Subdomain CNAME

At this point your GitHub website is configured and ready to receive traffic from your domain register dns! The next step is to configure a subdomain for your website. Follow these steps:

Login to your 1&1 account.
Click Domains from left side menu.

Click Manage Subdomains under your domain settings
Click Add subdomain on the right side menu.
Choose a name for your subdomain

If you would like to to redirect all traffic from root domain to your website, use www as your subdomain name.

Click edit domain settings on the newly created subdomain.
To setup a CNAME or a traget for DNS to forward traffic to, choose CNAME in A/AAAA and CNAME Records section
Then enter your GitHub pages URL under Alias username.github.io

Forward All Traffic

The last step before you’re all done, is to setup the main root domain to redirect to subdomain. In order to do that:

Go to 1&1 domain control panel.
Click on your root domain name
Click on Forward to under settings
Choose Redirect type to HTTP redirect
Set your Redirect to destination to your subdomain name http://www.yourdomain.com

Great! You’are all done.

eknowledger’s Technical Log

Statistical Modeling : Simple Linear Regression

Statistical Modeling

Simple Linear Regression Model

Measure of Quality

Sum of Squared Errors

Gradient Descent to the Rescue!

Real World Example

Read More:

XPress: Simple Truth Expression Language

Background

Goals

How it works?

Language Features

Variables

Operands

Binary Expressions

Unary Expressions

Relational Expressions

Conditional Expressions

Operator Precedence

What about performance?

Implement a Queue

Problem

Example

Analysis

Method 1 - Array based Queue

Method 2 - LinkedList based Queue

Bouns - Implement a Queue using two stacks

Is a Palindrome String?

Problem

Example

Analysis

CSharp Solution

Search For Range

Problem

Example

Analysis

CSharp Solution

Search Insert Position

Problem

Example

Analysis

Solution 1 - Using Recursion

Solution 2 - Using a loop

Intersection of Two Arrays

Problem

Example

Find Intersection of Unsorted arrays using Hash

Solution - CSharp

Find Intersection of sorted arrays

Solution - CSharp

Remove Element from Array

Problem

Example

Analysis

Solution - CSharp

Bouns

Example

Solution

Solution - CSharp

Remove Duplicates from Sorted Array

Problem

Example

Solution 1 - Using Temporary Array

Solution 2 - Using Constant Space

Bouns

Example

Configure 1&1 domain for GitHub Pages Site

Configure domain on GitHub

Configure Subdomain CNAME

Forward All Traffic

More Info