Saturday 31 March 2012

SQL breezer

Here is a short SQL breezer i made for revising SQL for interviews.

SQL SELECT command syntax :
SELECT select_list
[ INTO new_table ]
FROM table_source
[ WHERE search_condition ]
[ GROUP BY group_by_expression ]
[ HAVING search_condition ]
[ ORDER BY order_expression [ ASC | DESC ] ]

The WHERE clause is applied before the GROUP BY clause.
Because it acts on the results of the GROUP BY clause, aggregation functions can be used in the HAVING clause predicate.

Example Queries:
SELECT Book.title,
       count(*)
AS Authors
   
FROM  Book JOIN Book_author
      
ON Book.isbn = Book_author.isbn
   
GROUP BY Book.title;

  • INSERT adds rows (formally tuples) to an existing table, e.g.,:
INSERT INTO My_table
       (field1, field2, field3)
   
VALUES
       ('test', 'N',
NULL);
  • UPDATE modifies a set of existing table rows, e.g.,:
UPDATE My_table
   
SET field1 = 'updated value'
   
WHERE field2 = 'N';
  • DELETE removes existing rows from a table, e.g.,:
DELETE FROM My_table
   
WHERE field2 = 'N';

Data definition

The Data Definition Language (DDL) manages table and index structure. The most basic items of DDL are the CREATE, ALTER, RENAME, DROP and TRUNCATE statements:
  • CREATE creates an object (a table, for example) in the database, e.g.,:
CREATE TABLE My_table(
   my_field1   INT,
   my_field2   VARCHAR(50),
   my_field3   DATE         
NOT NULL,
   
PRIMARY KEY (my_field1, my_field2)
);
  • ALTER modifies the structure of an existing object in various ways, for example, adding a column to an existing table or a constraint, e.g.,:
ALTER TABLE My_table ADD my_field4 NUMBER(3) NOT NULL;
  • TRUNCATE deletes all data from a table in a very fast way, deleting the data inside the table and not the table itself. It usually implies a subsequent COMMIT operation, i.e., it cannot be rolled back.
TRUNCATE TABLE My_table;
  • DROP deletes an object in the database, usually irretrievably, i.e., it cannot be rolled back, e.g.,:
DROP TABLE My_table;

Null and three-valued logic (3VL)

The idea of Null was introduced into SQL to handle missing information in the relational model. The introduction of Null (or Unknown) along with True and False is the foundation of three-valued logic. Null does not have a value (and is not a member of any data domain) but is rather a placeholder or “mark” for missing information. Therefore comparisons with Null can never result in either True or False but always in the third logical result, Unknown.

p AND q
p
True
False
Unknown
q
True
True
False
Unknown
False
False
False
False
Unknown
Unknown
False
Unknown



Transaction controls

Transactions, if available, wrap DML operations:
  • START TRANSACTION (or BEGIN WORK, or BEGIN TRANSACTION, depending on SQL dialect) mark the start of a database transaction, which either completes entirely or not at all.
  • SAVE TRANSACTION (or SAVEPOINT ) save the state of the database at the current point in transaction
CREATE TABLE tbl_1(id int);
 
INSERT INTO tbl_1(id) value(1);
 
INSERT INTO tbl_1(id) value(2);
COMMIT;
 
UPDATE tbl_1 SET id=200 WHERE id=1;
SAVEPOINT id
-1upd;
 
UPDATE tbl_1 SET id=1000 WHERE id=2;
ROLLBACK
TO id-1upd;
 
SELECT id FROM tbl_1;
  • COMMIT causes all data changes in a transaction to be made permanent.
  • ROLLBACK causes all data changes since the last COMMIT or ROLLBACK to be discarded, leaving the state of the data as it was prior to those changes.
Once the COMMIT statement completes, the transaction's changes cannot be rolled back.

ACID properties
1. Atomicity - all operations in a txn fail or succeed as a whole
2. Consistency
3. Isolation - all txns run in isolation.
4. Durability - changes in the DB are permanent.

Data control

The Data Control Language (DCL) authorizes users and groups of users to access and manipulate data. Its two main statements are:
  • GRANT authorizes one or more users to perform an operation or a set of operations on an object.
  • REVOKE eliminates a grant, which may be the default grant.

Accessing windows shared disks from the linux systems

If you need to access windows shared directories on your local network from linux systems, you can use the following open source Java SMB client:

This client lets you access windows shared folders programmatically.
The following is an example client which you can use after downloading jar from the above location.

examples/AuthListFiles.java

SmbFile from = new SmbFile( "smb:// 192.168.1.4/7-Zip/7zCon.sfx" );
SmbFile to = new SmbFile( "smb://192.168.1.2/temp/7zCon.sfx" );
if(!to.exists())
     System.out.println(" Not found !!");
from.copyTo( to );

The full format for SMB url/links is as follows:
smb://domain\;user:pass@server/pub/

Setting up HTTP proxy in the linux shell


You can set the http_proxy environment variable using the command specific to your shell (e.g. set or export). 

To make this change persistent, add the command to the appropriate profile file for the shell. For example, in bash, add a line like the following to your .bash_profile or .bashrc file:

http_proxy=http://username:password@hostname:port;  
export http_proxy

Remote file copying in shell

You can use "scp" command to copy files between systems. This utility is based on "ssh" protocol.
Usage:
scp /home/* username@destinationMachine:/destination_path


The above command copied all files in home folder to destinationMachine's path.

Nice hacking lessons

The site security overrides is a good place to start learning about security exploits. the best part is it explains the exploits and gives you an arena to practice your skills as well  :)
Check this out:
http://securityoverride.net/challenges/index.php

Here is another one for practicing your SQL injection skills:
http://progzoo.net/hack/
http://sqlzoo.net/hack/12access.htm

Finding the open ports on a system

You can find the opened/used ports of the system using the netstat command.

netstat -an


Adding the additional switch "-b" to the above lists the process PID using each port.
If you want to search for any particular string in the output of netstat you can use the "find" command on windows system as follows:

netstat -an | find "97.107"

Relation between a polygon and a point

Given a point (a,b) and a polygon (in form of a list of vertices (x0,y0)(x1,y1)...(x0,y0)).

How to optimally find if the point lies inside in the polygon or outside it ?

This was asked to me in adobe 1st round of interview.

Find the kth permutation of the string

Print the kth permutation of the given string.
e.g.
5th permutation of "abc" is "cab", because its comes on 5th position in the ordered list of its permutations as shown below:
abc
acb
bac
bca
cab
cba

My Code:

import java.util.Arrays;




public class Main {


    public static String getStr(StringBuffer perm, int k){ // perm is not the original string it has the non repeating string chars
        String r = "";
        //System.out.println(perm);
        
        if(k<1)
            return perm.toString();
        int n = 0, t= 1, ctr = 1, k_n = 0;;
        for(int i=1;;i++){
            t *= i;
            if(t>k){
                break;
            }
            ctr = i;
            n = t;
        }
        k_n = k/n;
        // take care of this n, i.e. reverse upto position i
        int pos = perm.length()-ctr;
        if(pos<0){
            //System.out.println("ERROR !!");
        }
        //mov e bfor b
        int e = pos-1+k_n;
        int b = pos-1;
        if(b<0){
            return getStr(perm, k-(n*k_n));
        }
        String tmp = perm.substring(0,b)+ perm.charAt(e) + perm.substring(b,e) ;
        if(e+1<perm.length()){
            tmp += perm.substring(e+1);
        }
        
        /*System.out.println(perm);
        System.out.println("\n ** nxt level ***\n");*/
        return getStr(new StringBuffer(tmp), k-(n*k_n));
        //return r;
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
      System.out.println(getStr(new StringBuffer("abcd"),5));
    }
}

Find the Longest common sub sequence between two strings in java

My code:

static void LCS(String x, String y){
               int m = x.length();
               int n = y.length();
               int len[][] = new int[m+1][n+1]; // by default init. to zeros
               int b[][] = new int[m+1][n+1]; // by default init. to zeros
               for(int i=0;i<=m;i++){
                       for(int j=0;j<=n;j++){
                               if(i==0 || j==0){
                                       len[i][j] = 0;
                               }
                               else{
                                       if(x.charAt(i-1)==y.charAt(j-1)){
                                               len[i][j] = len[i-1][j-1] + 1;
                                               b[i][j] = -2;
                                       }
                                       else{
                                               if(len[i][j-1]>len[i-1][j]){
                                                       len[i][j] = len[i][j-1];
                                                       b[i][j] = -3;
                                               }else{
                                                       len[i][j] = len[i-1][j];
                                                       b[i][j] = -1;
                                               }

                                       }
                               }
                       }
               }
               System.out.println("length of LCS " + len[m][n]);
               int i=m,j=n;
               String res= "";
               while(true){

                       if(b[i][j] == -1){
                               i--;
                       }
                       if(b[i][j] == -2){
                               res = x.charAt(i-1)+ res;
                               i--;j--;
                       }
                       if(b[i][j] == -3){
                               j--;
                       }
                       if(res.length()==len[m][n])
                               break;
               }
               System.out.println("LCS " + res);
       }

Permutations of a string in java

Print all permutations of a string in java:


public static void permutate(String o, String t,boolean used[]){
               if(t.length()==o.length()){
                       System.out.println(t);return;
               }
               boolean used2[] = new boolean[o.length()];
               for(int i=0;i<o.length();i++){
                       if(used[i])continue;
                       System.arraycopy(used, 0, used2, 0, o.length());
                       used2[i] = true;
                       permutate(o,t+o.charAt(i),used2);
               }
       }

An Arithmetic interview puzzle


Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Example: With the list of numbers [2,3,5,7,11] we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!).

Any thoughts on how to solve this ?

Matrix rotate

GIven a 2D NxN matrix, visualize it as concentric circles. You have to find the rotated matrix where each element in the circle is rotated by 1 position layer by layer in an alternate clockwise and anticlockwise direction.

Sample Input:
4
2 3 4 5
1 6 7 8
4 2 1 9
5 3 2 4
Sample Output:
1 2 3 4 
4 7 1 5 
5 6 2 8 
3 2 4 9

My Code:


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.Math;


public class Solution {


public static void main(String[] args) {


int N =0;
int a[][],b[][];

BufferedReader br = 
         new BufferedReader(new InputStreamReader(System.in));
try {
String s = br.readLine();
N = Integer.parseInt(s);
a = new int[N][N];

for(int i=0;i<N;i++)
{
s = br.readLine();
String tmp[] =s.split(" ");
for(int j=0;j<N;j++){
a[i][j]= Integer.parseInt(tmp[j]);
//System.out.print(a[i][j]+" ");
}
//System.out.println();
}
int dist = 0;
int ii,jj;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dist = Math.min(Math.min(i,N-1-i),Math.min(j,N-1-j));
ii=i;jj=j;
if(dist%2==0){ // do clockwise rotation
if(dist==i){// top row
jj = j-1;
ii = i;
if(jj<dist){
jj = j;
ii = i+1;
}
}
else if(dist==j){// left col
jj = j;
ii = i+1;
if((N-1-ii)<dist){
jj = j+1;
ii = i;
}
}
else if(dist==(N-1-i)){// bottom row
jj = j+1;
ii = i;
if((N-1-jj)<dist){
jj = j;
ii = i-1;
}
}
else if(dist==(N-1-j)){// right col
jj = j;
ii = i-1;
if(ii<dist){
jj = j-1;
ii = i;
}
}
}
else{ // anti clockwise
if(dist==i){// top row
jj = j+1;
ii = i;
if((N-1-jj)<dist){
jj = j;
ii = i+1;
}
}
else if(dist==j){// left col
jj = j;
ii = i-1;
if(ii<dist){
jj = j+1;
ii = i;
}
}
else if(dist==(N-1-i)){// bottom row
jj = j-1;
ii = i;
if(jj<dist){
jj = j;
ii = i-1;
}
}
else if(dist==(N-1-j)){// right col
jj = j;
ii = i+1;
if((N-1-ii)<dist){
jj = j-1;
ii = i;
}
}
}
if(Math.min(ii,N-1-ii)<dist){
ii=i;
}
else if(Math.min(jj,N-1-jj)<dist){
jj=j;
}
System.out.print(a[ii][jj]+" ");
}
System.out.println();
}

} catch (IOException e) {
e.printStackTrace();
}


}


}