Given a string of length N, output “Correct” if brackets close in correct order else output “Incorrect”

Question:

Given a string of length N, output “Correct” if brackets close in correct order else output “Incorrect”

Input     :   ({}[((({{}})[{()}]))])

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Given a string of length N, output "Correct" if brackets close in correct order else output "Incorrect"
    #                         Input     : ({}[((({{}})[{()}]))])
    #                         

#!/usr/bin/python
def validString(input1):
    stk = []
    flag = True
    for x in input1:
        if x in ['{', '(', '[']:
            stk.append(x)
        else:
            if  len(stk)==0:
                flag = False
            elif x == '}' and not stk[len(stk)-1]=='{' :
                flag = False    
            elif x == ')' and not stk[len(stk)-1]=='(' :
                flag = False 
            elif x == '}' and not stk[len(stk)-1]=='{' :
                flag = False    
            if not flag:
                return "Incorrect"
            else:
                stk.pop()
    return "Correct"
 

input1 = '({}[((({{}})[{()}]))])'
input2 = '({}((({{}})[{()}]))])'
print validString(input1)    
print validString(input2)

Count Inversions in an array

This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.

 

Tips:

If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Eg: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

 

 

You can get working program from here

Input files :     Input1            Input2

 

Answer for input1 :

Answer for input 2: 25

Google Code jam Solutions: Problem A. Minimum Scalar Product

Problem

You are given two vectors v1=(x1,x2,…,xn) and v2=(y1,y2,…,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+…+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Input

The first line of the input file contains integer number T – the number of test cases. For each test case, the first line contains integer number n. The next two lines contain n integers each, giving the coordinates of v1 and v2 respectively.

Output

For each test case, output a line

Case #X: Y

where X is the test case number, starting from 1, and Y is the minimum scalar product of all permutations of the two given vectors.

Limits

 

Small dataset

T = 1000
1 ≤ n ≤ 8
-1000 ≤ xi, yi ≤ 1000

Large dataset

T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000

Sample

Input Output
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1
Case #1: -25
Case #2: 6

C++ Solution:

/*
    Author      :   Sreejith Sreekantan
    Description :   Problem A. Minimum Scalar Product
                    (https://code.google.com/codejam/contest/32016/dashboard#s=p0)

*/

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int main(int argc, char const *argv[])
{
    // freopen("as.in", "rt", stdin);
    // freopen("as.out", "wt", stdout);
    int n;
    cin >> n;
    int c;
    int tmp;
    vector v1, v2;
    int a, b;
    for(int a=0; a<n; a++)=""    ="" {=""        ="" v1.clear();="" v2.clear();="" cin="">> c;
        for(int b=0; b<c; b++)=""        ="" {=""            ="" cin="">> tmp;
            v1.push_back(tmp);
        }
        for(int b=0; b<c; b++)=""        ="" {=""            ="" cin="">> tmp;
            v2.push_back(tmp);
        }
        sort(v1.begin(),v1.end());
        sort(v2.rbegin, v2.rend());

        long long sumofprod = inner_product(v1.begin(), v1.end(), v2.begin(), (long long)0);
        cout << "Case #" << a + 1 << ": " << sumofprod << endl;
    }
    return 0;
}


C++ build tool: boost bjam intro

Reference Material : HERE

Source code (hello_sree.cc):

Screen Shot 2014-02-26 at 2.56.26 PM

build file (jamroot.jam or Jamroot): Screen Shot 2014-02-26 at 7.00.22 PM

Now in terminal, change the present working directory to the folder where the code and build-file resides. Run any of the below commands:

Screen Shot 2014-02-26 at 7.01.05 PMORScreen Shot 2014-02-26 at 7.00.45 PMORScreen Shot 2014-02-26 at 7.01.52 PMORScreen Shot 2014-02-26 at 7.03.09 PM

Ensure you have a space between “hello_sree.cc” and “;” in the build file. Otherwise you will get the below error:Screen Shot 2014-02-26 at 7.03.23 PM

Screen Shot 2014-02-26 at 7.03.33 PM

You will get this message at the successful run:Screen Shot 2014-02-26 at 7.04.01 PMYou will see a bin folder with a hierarchy of folders and executable file created as part of successful build of our program

Pythonize : Classes in Python

This series of articles, “Pythonize” will serve as an aid for python beginners. In this chapter I will try to explain all about python classes. In this series I will let python code talk to you more than me.

A few interesting things about python for you: Internet giants, Google and Yahoo, maintain a large code-base in python and promotes python to a large extent. Google apps can now be developed in python using the python APIs provided by Google. Python is famous for more functionality in less time being a scripting language and at the same time enabling OOP(Object Oriented Programming). It’s rich with libraries and online help. You can access

 

Python Class:

Class is a template or prototype that defines the fields and methods common to all objects created with this class. Classes in python starts with the keyword ‘class’ followed by the class name and then an optional set of classes separated with comma inside parenthesis, which will be inherited into your class depth-first and left-to-right order. It is then ended with a full-colon and all the indented block of statements just after that forms the body of the class. Note: Python keywords are case-sensitive. Stick with small letters. Below code won’t compile.

E.g.

Image FYI: pass is the keyword used to avoid error and it represents an empty block here. Variables: Data type of python variables is set based on the value assigned to it. Some valid variable assigning:
E.g.

Image

Hope you noted that I have reassigned ‘variable1’ from number to string without any extra code and the program worked fine. That is the extent of freedom python gives you. There is no keyword to define the scope of variables in class and all your usual variables declared inside class will be publicly accessible. Let try this with an example.

E.g.

6a Output: 6 Recent python versions came up with a solution to declare private variables. You just need to precede your variables with two underscores (__) and magic: it became private. Such private attributes are declared outside __init__ function for data hiding. Lets experiment this with a few lines of code.

E.g.

7a Output:

7

You may doubt that this is because I tried to print the variable ‘name’ where the class variable is “__name”. Lets clear your doubt.

E.g.

8a Output: 8

Here we tried to print the same variable name. Since preceding class-variables with two underscores make it private, we got an ‘AttributeError’. Python protects such private members internally by altering its name to contain the class name and we can access such members by following the template:

<objectName>._<className>__<attributeName>

Here our object name is prs, class name is Person and the variable is __name, so as per our assumption we should get the variable value by printing ‘prs._Person__name’

E.g.

8-1a Output: Note: Use “self.” with variable names to refer to instance variables and class-name followed by period (.) and then variable name to refer to class variables. Otherwise python will consider it as a global name and raise an error or give unpredictable outputs if a global variable with similar name exists. Lets have one example of class variables and then go to next topic:

E.g.

Image Output: 10 Here, you can see that by changing company name of emp2, it got reflected in emp1 as well i.e. emp1 and emp2 points to a single memory and such variables are technically called as class variables; one single memory for all the classes.

 

Class functions:

Functions of class decide the behavior of the class. They act as an interface to the outside world. Take a look at a sample class with a function ‘print_emp_details’.

E.g.

9a

Output: 4

Constructor:

Object Oriented Programmers might already know the role of constructor in a class. For those who don’t, let me explain. Constructor is the function that gets automatically invoked at the time of object-creation which is usually made use of for resource allocation. Python differs a bit from other OOP languages like java or C++ in constructor-name and it’s invocation. In python,

  • constructor of parent classes will not get invoked at the class of object creation of child class.
  • constructor function in python is always __init__().

E.g.

Image

You might be wondering about ‘self’ in __init__ function. In python, you will see this variable as the first argument in all the class functions without which the execution will fail. ‘self’ is not a keyword but instance of a class. You can use any other name for this parameter but it’s part of coding standard, which makes your code readable and easy to understand for other programmers. Lets stick to that standard.

E.g.

Image

Output: 1

A blank parameter list will raise a TypeError:

E.g. Image Output:

3

We have seen only constructors that don’t take any parameters so far. Now lets take a peek into parameterized constructors. As you guessed, the parameters of the constructor follow ‘self’.

E.g. 4a

Here name and hobby are the arguments and during object-creation we passed the arguments string “Sreejith” and “programming” as name and hobby to the constructor. One thing to note is that, with this class you won’t be able to create an object without any parameters. You will get the following error:

E.g.

4b

Output:

4c

Lets see a work around for that. Here we will assign a default value for the constructor variables and thereby the constructor assumes the default value if not explicitly specified at the time of object creation.

E.g.

4d Output: 4e

 

Destructor:

E.g.

11

Output: 11

 

Other base methods you can overload in your class:

  • __repr__(self)
    • To represent the object in evaluatable string
    • E.g.: repr(obj)
  • __str__(self)
    • To represent the object in string
    • E.g.: str(obj)
  • __cmp__(self, obj1)
    • For comparing with another object
    • E.g.: cmp(obj, obj1)

Inheritance:

Lets straight away get into a python code that successfully uses inheritance to reuse code and at the same time overrides needed functions.

E.g.

Image Output: 12 Here we override the print_name() function in Child and GrandChild class but uses the same smile() function as such. Functions are searched in the following hierarchy:

  1. Derived class
  2. Base class in the order of depth first and then left-to-right.

There are two functions which comes handy with class inheritance:

  • issubclass()
    • Returns a boolean value based on if the first parameter is a sub-class of the second parameter.
    • E.g.: issubclass( subclass1, superclass1 )
  • isinstance
    • Returns a boolean value based on if the first parameter is an object of second parameter.
    • E.g.: isinstance( object1, class1 )

Thus we have come to the end of this chapter. Lets recall what we have learned from this chapter. We learned

  1. Basic syntax of class
  2. Variables; How to make variables private; Class variables and Instance variables
  3. Class Functions/Methods
  4. Inheritance; Function overriding

Meet you next time..

Big Data Series; Part 2: Program hadoop mapreduce in your favourite language.

Image

Apache hadoop gives you option to program your mapper and reducer in 
your favourite language.If you wonder about its possibility, you will
know it by yourself by going through this blog. Since python got into my favourite-language list recently,
let me try with it. Python already has a module: pydoop which
provides you with API to program map reduce. But this time,
we will program without using pydoop, thereby you will get
an idea how you can achieve the same in your preferred programming
language. Apache hadoop comes with a streaming jar which takes as
parameters: your mapper program, your reducer program, input file and
output file. It then streams the data, in your input file, to the
stdin (if I am going a bit too technical here, refer standard streams)
of mapper program. Your mapper program is supposed to read from stdin,
process the data and write to stdout as key-value pairs; its completely
upto you to choose the separator for key and value, since you are
going to get back those key-value data. The stdout of mapper is then
taken by the hadoop-streaming-jar, sorts the data from all mapper's
execution(fyi: mapper program is executed in all the data nodes, the
input file is chunked and stored), sorts that data based on key and
writes to the stdin of reducer program. Your reducer program should be
in such a way that it should read from stdin a key-value pair per line
and do the necessary processing to print out the final processed data.
Now, I will give you a feel of how things are going to work-out with a
character-count program, implemented in python, which will give your
the count of all alphabets in the input data.

Now let me show you my mapper and reducer code:
charcount_mapper.py:
Image


In charcount_mapper.py, I read line by line from stdin and go through
each line character by character and check if it's an alphabet. If it's
an alphabet, I print it to stdout in the format: "<character><tab-space>1". This
means to reducer program that the character appeared one time. Here
the key is <character> and value is '1'(one). There can be multiple
occurrence of same "<character><tab-space>1" depending on the input data.

charcount_reducer.py:
Image
Now lets analyze charcount_reducer.py. In this, I read line by line
from stdin, since its what I wrote into stdout from mapper program, I
can foretell that every line will be of the form:
"<character><tab-space>1". The only difference between what I wrote
into stdout from mapper program and what I get from stdin in reducer
program is that input will be sorted based on keys when I read in
reducer program. This will be helpful for me to construct logic for
reducer program. Now I just need to see if a new key is encountered.
Till then I keep on incrementing the counter. Once a new key is found,
the old key along with the counter value is printed out and counter is
reset. In the for loop, key along with counter value is printed out
only when a new key is encountered. Therefore I add one more print
statement at the end of the program to print out the last key and count.
(In case you are confused about the use of last print statement outside
the for-loop).
Since it will be hard to debug programs in hadoop I will ensure the
functionality of my program locally. I will use a sample input:
Image
You can easily predict the output our program should give out. Lets
see if we can get the same from the program.
Keep eyes on the command used in each screen-shot.
I will use the 'cat' command to print out the contents of the input file.
Image
It is then piped to mapper program.
Image
As I said this will the output of mapper program and to feed into
reducer program, for now, we will have to explicitly sort it.
Image
Now its ready to be fed to the reducer program:
Image
The output is as expected, isn't it!
Now lets run the same program in hadoop setup to see its success.
For that, start the hadoop running the start-all.sh script. (Refer the
part 1 of Big Data series in case of any confusion)
Then we need to copy our sample input file into HDFS file system. Know
the command to do it? Let me help you..
Before that I will create a directory for our use:
Image
Now we have a directory "charcount" in the path /user/thinker/ in the
Hadoop file-system. Lets copy our input file from my local file-system
to hadoop file-system.
Image
Lets ensure that the file's existence and its content:
Image
Image
Now we are sure about our input. Lets further with the execution.
For that, the command is:
Image

To ensure the availability of the hadoop-streaming jar, run the command:
Image
This is the jar which does the job of read the contents of input file
and feeding it to mapper program and ... (rest you already know)
the "-file" says the files which has your programs. The programs need
not be copies to HDFS. I used two "-file" to mention my mapper and
reducer files. "-mapper" mentions the mapper program's file name(only
file-name and not entire path). "-reducer" mentions the reducer program's
file-name. "-input" is used to mention the hdfs-absolute-path of input
file and "-output" mentions the output directory to which the output will
be written to.
Lets see the output of successful execution of the above command:
Image
Listing the contents of /user/thinker/charcount/:
Image
We can see a new directory with the name: sample_output.
Note: The command will fail to execute if you give an already existing
file/folder name with '-output' option.
Lets list the sample_output:
Image
Our output will be in 'part-*' files. Since the output size is very
small in this particular case, we have only one file. The number of
files increases with increase in output size.
Lets print the generated output for final verification.
Image
Even though the output differs in order, the counts are correct. You
can run the program with some other input by changing the file given
with '-input' option. You can use any language to
program your mapper and reducer. Points to be noted are:
Scripting languages with its jvm/interpreter installed in all the datanodes is a must.
In case of compiled languages like C or C++, you will have to compile it first and
the executable file need to be mentioned with '-file', '-mapper' and '-reducer'.
With that, I think I covered almost everything needed for you to kickstart your mapreduce
programming in your preferred language. See you in next part..

Big Data is a Big Deal.. :)

Big Data Series; Part 1: Set up Hadoop in ubuntu

Image

The reference given at the bottom most of this page can give you a detailed description on setup of Hadoop. I will take you through my experience in setting it up in Ubuntu.

You should have a linux/unix system with jvm installed and password-less ssh enabled.

Download the latest release of hadoop FROM

I prefer *.tar.gz to other installable packages because once you setup hadoop with installable packages, it will be hard for you to find the configuration files for any editing(from my experience; I removed it and installed with *.tar.gz).

Assuming that your browser downloaded the hadoop tar file to Downloads folder.

(in my case Image)

I chose /app folder to setup hadoop. So move the tar file to /app

Image

Unzip and un-tar the file there:

Image

You will need to edit the hadoop-env.sh file to set the JAVA_HOME environment variable.

If you try to start hadoop without this modification, hadoop will fail to start throwing the below error:

Image

gedit is a text editor I am using. You can prefer your favourite(vi/vim/textedit/…)

location of hadoop-env.sh (hadoop<version>/conf)

Image

You will find below lines in hadoop-env.sh

Image

Either edit the already existing line of add a new line as I did:

Image

You can know about your specific location with following commands:

Image

As you can see, I highlighted /usr/lib/jvm/java-7-oracle/jre/bin/java. hadoop expects us to specify the path till java-7-oracle ie. “/usr/lib/jvm/java-7-oracle”

This will be enough to kick-start your hadoop in stand-alone mode.

Since I plan to install Apache Pig for scripting, I will setup hadoop in pseudo Distributed mode. For that I need to edit three files: core-site.xml, hdfs-site.xml and mapred-site.xml which can be found in “hadoop<version>/conf/” directory. The same information can be found in the reference as well.

ImageImageImage

 

 

Now the recipe is ready. Before I can start hadoop there is this one final thing to be done: formatting of name-node. Assuming that you are in the hadoop main directory, run the command: “bin/hadoop namenode -format”

And you will see logs like below:Image

 

Done with the waiting part. Run the command “bin/start-all.sh” to run NameNode, Secondary NameNode, Data Node, Task Tracker and Job Tracker as back-end processes.

Image

To ensure that all five services are running, use jps command. If you see the below output, “ALL IS WELL..”

 

Image

Out of my experience in setting it up in different linux and unix variants including Mac, I can say, the same steps can be repeated in any *nix variants.

Big Data is a Big Deal.. 🙂

Reference:

http://hadoop.apache.org/docs/r1.1.1/single_node_setup.html