## 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

## 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

*/

#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):

build file (jamroot.jam or Jamroot):

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

OROROR

Ensure you have a space between “hello_sree.cc” and “;” in the build file. Otherwise you will get the below error:

You will get this message at the successful run:You 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.

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.

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.

Output: 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.

Output:

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.

Output:

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.

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.

Output: 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.

Output:

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.

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.

Output:

A blank parameter list will raise a TypeError:

E.g. Output:

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.

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.

Output:

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.

Output:

Destructor:

E.g.

Output:

• __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.

Output: 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.

Apache hadoop gives you option to program your mapper and reducer in your favourite language.If you wonder about its possibility, you willknow it by yourself by going through this blog.
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'san alphabet, I print it to stdout in the format: "<character><tab-space>1". This means to reducer program that the character appeared one time. Herethe 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:
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

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.

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).

(in my case )

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

Unzip and un-tar the file there:

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:

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

You will find below lines in hadoop-env.sh

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

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”

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.

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:

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.

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

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: