Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

First of all, if this string has an odd number of characters, we know already that it isn't valid.

class Solution(object):
    def isValid(self, s):
        if len(s) % 2 == 1:
            return False

Go through each character, and if they are open characters(open parens, open bracket, open curlies), push it onto a stack.

        openparens = []
        for i in range(len(s)):
            if s[i] == '(' or s[i] == '[' or s[i] == '{':
                openparens.append(s[i])

Then, if it is any closing character, pop one off of the stack and make sure it is the opening character is the corresponding type. If everything goes well we will pass through the string nicely and return True.

            elif s[i] == ')':
                if len(openparens) == 0 or openparens.pop() != '(':
                    return False
            elif s[i] == ']':
                if len(openparens) == 0 or openparens.pop() != '[':
                    return False
            else:
                if len(openparens) == 0 or openparens.pop() != '{':
                    return False
        return True

Read More

Remove Nth Node from End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

We are given the ListNode class

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

First, let's set two pointers to go through the linked list.

class Solution(object):
    def removeNthFromEnd(self, head, n):
        needle = head
        end = head

Then, we want to move the end pointer past the needle pointer by n steps. After that we move both pointers until end is the last node of the linked list.

        for i in range(n-1):
            end = end.next

        while end.next != None:
            needle = needle.next
            end = end.next

Notice that needle pointer will always be n steps behind the end pointer. Thus, when the end pointer is at the last node, the needle pointer is pointing at the (n+1)th last node. From there, we drop out the nth to last node by setting needle.next to the next next node.

        needle.next = needle.next.next
        return head

We can always change it return the value of the head through head.val. Now we can test it out using this:

numbers = ListNode(1)
numbers.next = ListNode(2)
numbers.next.next = ListNode(3)
numbers.next.next.next = ListNode(4)
n = 2
sol = Solution()
print sol.removeNthFromEnd(numbers, n)

This question is quite similar to this that I've done some time back. It's in a different language though(C).

Read More

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

P   A    H   N
A P L S  I  I  G
Y       I      R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        rows = ["" for x in range(numRows)]
        count = 0
        start = 0
        end = numRows
        inc = 1

        # while we dont run out of letters
        while count < len(s):
            # count from index 0 -> numRows -> numRows
            for i in range(start, end, inc):
                if count < len(s):
                    rows[i] += s[count]
                    count += 1

            if inc == 1:
                inc = -1
                start = numRows-2
                end = 0
            else:
                inc = 1
                start = 0
                end = numRows
        return "".join(rows)


sol = Solution()
s = "PAYPALISHIRING"
numRows = 3
print sol.convert(s, numRows)

This solution goes through the string once, using a loop that changes direction when it hits the number of rows. Then, this simply joins the separated rows of strings into one, which makes an O(n) complexity.

Read More

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.

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

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i!=j:
                    if nums[i] + nums[j] == target:
                        return [i, j]


nums = [2, 7, 11, 15]
target = 9
sol = Solution()
print sol.twoSum(nums, target)

This is simple since you can look through each element in the array and compare their sum with the target number. But, the complexity of this solution is O(n^2), since you are going through the list once every element in the list.

What about this?

class Solution(object):
    def twoSum(self, nums, target):
        dict = {}
        for i in range(len(nums)):
            if dict.has_key(target-nums[i]):
                return (dict[target-nums[i]][1], i)
            else:
                dict.setdefault(nums[i], (target-nums[i], i))

nums = [2, 7, 11, 15]
target = 9
sol = Solution()
print sol.twoSum(nums, target)

This is a lot simpler in terms of complexity. The pointer goes through the array once, picking out each element and seeing what number needs to be paired with it to sum up to the target number.
Then, we put that in a dictionary. For example, element in index 0 would be stored as a key and it's leftover and index as a tuple for a value dict[2]:(7, 0).

Every time we look at an element we figure out if we have a corresponding number already in the dictionary, and if we do, then we return the index stored as well as the index we are currently on.
This make for an O(n) complexity.

Read More

Three in One - Part One

Describe how you could use a single array to implement three stacks.

Hint 1. A stack is simply a data structure in which the most recently added elements are removed first. Can you simulate a single stack using an array? Remember there are many possible solutions, and there are tradeoffs of each.

Hint 2. We could simulate three stacks in an array by just allocating the first third of the array to the first stack, the second third to the second stack, and the final third to the third stack. One might actually be much bigger than the others though. Can we be more flexible with the divisions?

Initialize a size holder, an array of each head of the stacks, and a stack array.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int total_size;
int stack_point[3];
int* stacks = NULL;

Then we make the push and pop functions. Push here is alittle different in where it takes a stack number, specifying which stack it is to be pushed to. Pop also takes an extra argument specifying which stack to pop from.

void push(int* stacks, int s_num, int element){
  if (s_num > 3 || s_num < 1) {
    printf("ERROR. invalid stack number");
    return;
  }
  if (stack_point[s_num-1] >= total_size || 
      (stack_point[s_num-1] >= (total_size/3) * s_num && s_num != 3)){
    printf("ERROR. Stack %i full\n", s_num);
    return;
  }
  stacks[stack_point[s_num-1]] = element;
  stack_point[s_num-1] += 1;
}

void pop(int* stacks, int s_num){
if (s_num > 3 || s_num < 1) {
    printf("ERROR. invalid stack number");
    return;
  }
  
  if (stack_point[s_num-1] < (total_size/3) * s_num-1){
    printf("ERROR. Stack empty");
    return;
  }  

  stacks[stack_point[s_num-1] - 1] = -1;
  stack_point[s_num - 1] -= 1;
}

The a simple print function to print all the stack numbers. This way we can see if things aren't quite working.

void print_stacks(int* stacks){
  int i;

  for(i=0; i= total_size/3 && i < stack_point[1]) printf("%i, ", stacks[i]);
    else if (i >= (total_size/3) * 2 && i < stack_point[2]) printf("%i, ", stacks[i]);
  }
  printf("\n");
}

Assuming that size input is not going to be invalid, we create a stack here and give it some push/pop tests.

void main(int argc, char* argv[]){
  if (argc != 2){ printf("ERROR. Insufficient arguments.\n"); return;}
  total_size = atoi(argv[1]); 

  stacks = malloc(sizeof(int) * total_size);
  stack_point[0] = 0;
  stack_point[1] = total_size / 3;
  stack_point[2] = (total_size / 3) * 2;

  push(stacks, 1, 1);
  push(stacks, 1, 3);

  push(stacks, 2, 2);
  push(stacks, 2, 4);

  push(stacks, 3, 1);
  push(stacks, 3, 2);
  push(stacks, 3, 3);

  pop(stacks, 3);
  push(stacks, 3, 4);

  print_stacks(stacks);
}

Let me know if there's any mistakes! I'm contemplating if I should post a better version since it would be longer, so I will post other questions as I work on it.

Read More

Return Kth to Last

Implement an algorithm to find the kth to last element of a singly linked list.

If we knew the length of the linked list, then we could just subtract k and we would move a pointer length-k times.

Here, I think the best way would be to just iterate through the linked list with two pointers. The two nodes start on the head of the linked list. The first pointer would go ahead k steps, and then both would move ahead until the first point touches the last node. The next node that the second node stops at will be out kth to last node.

This would take O(n) time since we have to go through all the elements of the linked list, and O(1) space.

Here's what I have:

We first create the structures for a linked list

#include <stdlib.h>
#include <stdio.h>

struct node{
  int data;
  struct node* next;
};

struct list{
  struct node* head;
};

Then we make some linked list making functions

struct node* create_node(int data){
  struct node* new_node = (struct node*)malloc(sizeof(struct node));
  new_node->data = data;
  new_node->next = NULL;

  return new_node;
}

void add_node(struct list* llist,int data){
  struct node* new_node = create_node(data);
  new_node->next = llist->head;
  llist->head = new_node;
}

The star method of this question! Assuming a valid k and linked list, we get two pointers, move the first k times, and then move both pointers until the first pointer reaches the end of the linked list.

int kth_to_last(struct list* llist, int k){
  struct node* tmp1 = llist->head;
  struct node* tmp2 = llist->head;

  int i;
  for (i=0;i<k+1;i++){
    tmp2 = tmp2->next;
  }
  while(tmp2->next != NULL){
    tmp1 = tmp1->next;
    tmp2 = tmp2->next;
  }
  
  return tmp1->data;

}

Then we create a linked list for some testingggg

int main(int argc, char* argv[]){
  struct list* new_list = (struct list*)malloc(sizeof(struct list));
  new_list->head = NULL;

  int i;
  for (i=20;i>0;i--){
  add_node(new_list, i*2);
  }

  for(i=0;i<19;i++){
    printf("%ith item: %i\n", i+1, kth_to_last(new_list, i));
  }
}

Read More

Binary Search

Binary search is one the simplest search algorithms(most are pretty simple) to implement. However, first it assumes an important property of an array that isn't always true; the array is sorted. This search is based on the number of elements(length), and we fold the array in half each time, which makes search time logarithmic.

First, you see in the diagram above that the list is already sorted. Next, we label the first index as the lowest number(LO), the last index as the highest number(HI), and the middle index as the index between lowest and highest(MID). Keep in mind that these are just markers for indices and we aren't moving any of the array elements around.

In the diagram that's searching for the number 16 and we realize that the number 16 is smaller than the number in index MID. As a result, we move the high index right before the mid index, and we reorganize the mid index as the middle of lo and hi again. This is what cuts the array in half, and in another half every time it checks MID. The resulting indices is represented in the second row of the diagram.

The last row of the diagram, just shows that when we check MID again here we find that it matches our search number, and thus re return the MID index and we are doneeeeee!!!!

In the case that the number we are searching for is higher than MID, then we'd move LO right after MID and re-position MID. Also, in the case that we don't find any numbers, we'd just return -1.

We repeat these steps several times, folding HI and LO in halves until we've either found our number or we've looked through all the possible index elements.

Here's how it would look in java:

import java.util.Arrays;

class BinarySearch{
.
.
.
    public static int rankIndices(int key, int[] a){
        //assume here that the array is sorted already
        int lo = 0; //index 0 is lowest
        int hi = a.length - 1;                      //and the last index is highest
        while(lo <= hi){                         //stop when hi and lo have become the same index number
            int mid = lo + (hi - lo) / 2;           //find the middle of hi and lo
            if (key < a[mid]) hi = mid - 1;      //key is between mid and lo, move hi before mid
            else if (key > a[mid]) lo = mid + 1; //key is between mid and hi, move low after mid
            else return mid;                        //The middle number is the number we look for
        }
        return -1;
    }
}

And here's some python:

def binarySearch(key, a):
    ## assume that the array is already sorted
    lo = 0
    hi = len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  ##postion mid, integer division
        if key < a[mid]:
            hi = mid - 1           ##key is between mid and low, move hi before mid
        elif key > a[mid]:
            lo = mid + 1           ##key is between mid and hi, move lo after mid
        else:
            return mid             ##mid is where our number resides
    return -1                      ##number is not found


print binarySearch(2, [0, 1, 2, 3, 4, 5, 6, 7]) ##just a test

Read More

Relational Algebra - An Intro of it's Use and Operators

Consider the following database scenario:
You are planning a high school graduation party for the school. You keep data on those who have registered to be present on that day. We have students(S), teachers(T), staff members(SM), parents(P), and siblings(C) of the students, followed by relatives(F), and a list of registered people for the party(R). We also have information about food allergies(A). If we were asked to find out the group of people who is a 25 years old or older and a parent of a student who has a peanut allergy, what would you query?

SELECT S.name
FROM S
WHERE S.allergy='peanut' and S.parent=
               (SELECT P.name
                FROM P
                WHERE P.age >= 25)

As we can see here this is not the simplest query. Imagine if we had to query for something way more complex than this. Would you sit there and try things out until you got the right query? Would a database always have someone behind it entering queries? Not always(Probably not). It can be done of course, but there's a better solution for this.

Relational Algebra: relational algebra is a way of expressing relations. Just like algebra is a way of expressing numbers and their relations, relational algebra is a way of expressing things in a database with their set of operators. It can also be used to describe constraints of a database, though we'll elaborate on that in another post.


Relational Operators: relational operators are analogous to arithmetic operators; they operate on a certain operand and describes the operands' relationship to each other. Below we will jump into some of the basic operators.

1. Selection(σ): Like in SQL queries we are selecting a subset of rows from a relation(operand)
2. Projection(π): Keeps certain column(s) of a relation, I don't think this has an SQL counterpart
3. Cross-product(×): Also called Cartesian product. This takes relations and combines them
4. Join(⋈): Connects two relations with some sort of condition
5. Set-difference(−): an existing tuple(s) in one relation but nonexistent in another relation
6. Union(∪): Tuples that exist in one relation OR another relation. Realize that the "or" I'm talking about is logical or.
7. Intersection(∩): Tuples that exist in both of two relations
8. Renaming(): renames a relation or an attribute.

Operator Examples:
1. Selection(σ) & Projection(π): All of those who have a peanut allergy from the student list(S)
π_S.name(σ _{allergy='peanut'}(S))

3. Cross-product(×): All of those who have peanut allergy and are a student or teacher
π_S.name(σ _{allergy='peanut'}(S × T))

4. Join(⋈) All of those who have peanut allergy and are a student or teacher
π_S.name(σ _{allergy='peanut'}(S ⋈ T))

5. Set-difference(−): find the students who have an allergy but did not reserve a place for the party
π_S.name(σ _{allergy='peanut'}(S)) - π_S.name(R)

6. Union(∪) & Renaming(): The list of students and teachers that have a name of "Sara"
π_R.name(σ _{R.name='sara'}((R , (S ∪ T))))

7. Intersection(∩) & Renaming(): The list of people who's name is "sara" and is both a parent and a teacher
π_R.name(σ _{R.name='sara'} ((R , (P ∪ T))))

Read More

MySQL Queries and commands

In this post I hope to go through some MySQL commands that would help users get started and used to using it. Remember that semicolons are default used to show end of command/queries.

Creation/Deletion Commands

USE <database name>:
This is used to enter an existing database.

CREATE DATABASE <database name>:
This is used to create a database.

CREATE TABLE <table name> <name of variable, variable type>:
This is really similar to database creation, although it has many more entries for each attribute. Here are some commonly used ones:

• CHAR(N), where N is length between 1-255. Default is 1
• VARCHAR(N), where N is length between 1-255. Unlike CHAR, you must define a length.
• INT, an integer entry. The number should be between -2147483648 and 2147483648. If you need a bigger number, you can use
• BIGINT the integer max depends on signed or unsigned.

SHOW TABLES:

Shows all available tables in a database

SHOW DATABASES:

Shows all existing databases in MySQL

DESCRIBE <table name>:

This shows how you've defined the table, what variables and types.

DROP TABLE <table name>:

This totally deletes the table, if it exists of course.

DROP DATABASE <database name>:

This deletes an existing database

Query Commands

SELECT * FROM <table name> WHERE <some condition>:
Select *  means it finds some table and return everything. If you want to find something specific you would do SELECT <attribute name> FROM <table name>  and if you want to return pairs of things you can specifiy the attributes with commas.
Ex.  SELECT name, age FROM attendees WHERE age > 20;

FROM describes where you are searching/querying.
WHERE is specifying conditions, you can specify several conditions in separated AND or OR.

AND:
The and keyword is used to specify that the combined conditions must all be satisfied.
Ex.  SELECT name, age FROM attendees WHERE age > 20 AND age < 30;

OR:
The or keyword is used to specify that one of the combined conditions must be satisfied.
Ex.  SELECT name, age FROM attendees WHERE age > 20 OR age < 10;

These are just the few basic commands/queries that you can do, and I hope that this helps you get started with building a database! I also plan to publish a post that goes into more queries, since most database management concepts are about these queries.

Read More

Breadth-First Search

Breadth-first search is a search algorithm to find something in an tree. This search algorithm utilizes a queue to keep track of all the nodes that the algorithm will explore. If you're not sure what a queue is then you should take a look at it here.

What basically happens:
The search algorithm starts at the root node(A), and looks at each node of its children before going on.

What specifically happens:
Let's say that the goal is to find E.
The search tree starts at the root node(A) added into the queue then popped, and adds it's children into the queue. If the node it is at is not a goal, it enqueues its children into the queue. If it is the goal then the algorithm returns and stops. Here are some of the steps:

1. We start with A dequeued from the queue. Since A is not the goal and it has children, A's children are enqueued. Queue = [B, C]

2. B is dequeued from the queue and its children are enqueued. Queue = [C, D, E]

3. C is dequeued from the queue and its children are enqueued. Queue = [D, E, F, G]

4. D is dequeued from the queue and its children are enqueued. Queue = [E, F, G, H, I]

5. E is dequeued from the queue and it is our goal, so we stop.

Think about if we are searching for M. What would our path be and what would happen?

Why don't we need an explored list compared to Depth-first algorithm?
Because we search everything level by level, there is no need to keep track of explored nodes, whereas Depth-first has to go back up the tree.

Read More

Depth-First Search

Depth-first search is a search algorithm to find something in an tree. This search algorithm utilizes a stack to keep track of all the nodes that the algorithm will explore. If you're not sure what a stack is then you can read about it here.

What basically happens:
The search starts at the root node(A), and continues to travel down until it reaches a leaf node. Once it hits a leaf node, it goes a step until it can travel downwards again. This continues until it has either found what it was looking for, or until it has explored all of the nodes and found nothing. The path happens this way: (A, B, D, H, I, E, J, K, C, F, L, G)


What specifically happens:
Let's say our goal is to find G.
The search starts with the root node(A) and pushed into the stack, and continues to travel down until it reaches a leaf node. A leaf node is a node that does not have any children. At every step it checks to see if the node has already been explored. If it has been explored, it is simply ignored and continues looking in the stack. If the node has not been explored, it adds any children(that have not been explored) into the stack and adds itself to the explored list. If it hasn't found the goal, then it continues to search until it has found the goal or that the tree is all explored. Here are some of the steps:

1. A goes down B, D, and stops at H.  Explored list = [A, B, D, H]  Stack = [C, E, I]

2. H is a leaf so it doesn't add any children to the stack, I is popped off and added to the explored list.
    Explored list = [A, B, D, H, I]  Stack = [C, E]

3. I also doesn't have any children to add to stack, E gets popped off. It's added to explored and its children added to the stack.
    Explored list = [A, B, D, H, I, E]  Stack = [C, K, J]

4. J is popped off the stack. Because it is a leaf no children are added to the stack. Same thing happens with K.
    Explored list = [A, B, D, H, I, E, J, K]   Stack = [C]

5. C is popped off the stack and any of its unexplored children are added to the stack.
    Explored list = [A, B, D, H, I, E, J, K, C]  Stack = [G, F]

6. F is popped off the stack and, any unexplored children added.
    Explored list = [A, B, D, H, I, E, J, K, C, F]   Stack = [G, L]

7. L is popped off the stack and there are no children to add to the stack.
    Explored list = [A, B, D, H, I, E, J, K, C, F, L]   Stack = [G]

8. G is popped off the stack and because our goal was to find G, we stop our search.

Imagine that there is a search for M. What would happen? The algorithm should return something that signifies nothing was found.

Why do we need an Explored list?
The reason that we would need an explored list is to prevent already traversed nodes from being rechecked, and prevent its children from being added back into the stack. Without the explored list the algorithm would end up in a loop forever.
Just like looking for something in the grocery store, you wouldn't want to go back to an aisle you already looked in, because you remember that you've looked there already.

I hope this clears up any muddy ideas you have about this search algorithm. Feel free to let me know if I've made any errors, grave or not.

Read More

Database Concepts - A Short Post about the Relational Database Model

via Wikipedia

Relational Database Model:
The relational database model, different from the entity relation model, shows specific data and information about a database table. A relational database model contains two parts: An instance, and a Schema.

Schema:
The schema is specific name of the relation, or the name of each column. If you think back to the Entity-Relationship Diagrams, there are names that have relationships to each other, these names would be the part of the schema. In the above picture, the schema would be the part that says "login", "first", and "last."

Instance:
The instance are the rows of data that pairs with the schema. In the above picture, the instance would be the rows of names.

Relations:
As you can see from the image above, the specific row of information for "Mark" is linked to another table that contains the specific key's phone number. This, is what the Entity Relationship Diagram has drawn out; the connection between one login key to a foreign key.

Usage:
With the Relational Database, we can use query language to query for data. Although our queries can be efficient, the DBMS is mostly responsible for making queries efficient.

Read More

Setting Up MySQL

Hi Everyone!

I know I haven't been posting much these past few months, I was busy with many other things and I decided to take a breather with blogging. However, things have cleared out of my way now, and I will start again with posts.

Installing:

For Linux users, type the following into your command line:

shell>sudo apt-get install mysql-server
shell>sudo apt-get install mysql-client

For Mac and Windows users, you have to download the installer here. Make sure you check 32 or 64 bit! Follow the steps that the install gives, and you should be fine!

Using MySQL:
To start up MySQL:  type the following commands in the terminal:
shell>mysql -u root -p
It would ask you for your password, since you need to be the root user. The installation should ask for you to set a password for MySQL, which is optional. If you do not wish to set a password, you can just click enter when it prompts you to type in a password.

If you did not set a password for MySQL, you can disregard the "-p" part. You can also just type it and click enter when it asks for a password. If you get in, you should see something like this:
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.6.27 MySQL Community Server (GPL)
Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved.
Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.
Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.
mysql>

For Windows users, here's the way to start it up. I haven't tried this but I hope it helps.

To create a database: type the following in the MySQL command line:

mysql>create database database_name;

Notice here that you need a semicolon to show that you're done talking. We'll see later how that semicolon can be changed to something else.

To go into a database: type the following in the MySQL command line:

mysql>use database_name;

type in "mysql --help" in you're computer terminal to see many, many other commands.

Changing MySQL Password:

In order to change your MySQL password you will need to log onto MySQL first. After that you type the following:

mysql>grant all privileges on *.* to root@localhost identified by "new_password";

Here, the new_password should be in the quotes.

Changing the Terminator Symbol:

The semicolon at the end of each command is usually called the terminator, which tells MySQL that you're done with a statement. But what if you wanted to paste a big chunk of commands? Or paste in a function? You can change the terminator symbol before you paste code, and change it back to semicolon afterwards. Here's how to change it:

mysql>DELIMITER YOUR_TERMINATOR

example: mysql>DELIMITER done

In this example, assuming you don't have the word "done" in your code, will end your set of commands when it find the word "done." To change it back to semicolon you would do the same except with a ";"

That's it! Pretty Simple huh? If you have any problems look it up, many people may have the same problem. You can also feel free to post a comment here, and please do so if my post here helped you! I really appreciate knowing that I have helped! 'Til next time.

*It also seems that the spacing of this post is really odd, I'm trying to fix it but I haven't figured out the cause so far.

Read More