Friday, 29 June 2012

Co-joined Linked lists

You have two linked lists: A and B. A and B are co-joined at some node 'c'.

(A)--------
           (c) |------- (common part of both linked lists)
(B)--------

Find the the node (c) at which both the linked lists meet / collide.

Solution:

  1. Traverse both the lists and find their lengths 'a' and 'b' respectively.
  2. calculate the difference between both lengths: d = |a-b|
  3. Make two pointers PA and PB for each list.
  4. Move the pointer of the longer list 'd' steps.
  5. Then move both the pointers simultaneously until both the pointers become equal, which happens at the node 'c'.

Sunday, 17 June 2012

Find similarity between two arrays

There are two arrays.
int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}
The arrays will be called similar if they contain same number of elements equally.
Write the pseudo code to check this ?
I was not allowed to use sorting and hashtable.
Solution:
I.
Pick a random number from the array and partition it using the quick sort partition function.
Then partition the second array using the same number. O(n) time.

Now recursively, do this until the counts on either side mis-matches.

II.
Make two min heaps in O(n) time.
Extract the mins from both and compare till either both heaps are empty or there is a mismatch.

Reference: http://www.careercup.com/question?id=11685824

Saturday, 9 June 2012

Using GDB to debug in linux

To debug a process: "./a.out arg1 arg2", run:

$ gdb ./a.out
(gdb) run arg1 arg2


Reading: http://cs.baylor.edu/~donahoo/tools/gdb/tutorial.html

Understanding the I/O redirection in linux

STDIN is FD 0, while STDOUT is FD 1, and STDERR is FD 2.


To redirect the errors to the output stream use this: 2>&1
Here '&' tells that it is a FD(file descriptor) and not an ordinary file named '1'.

There are lots of redirection symbols that you can use, and here are some of them:
filemeans open a file for reading and associate with STDIN.
<< tokenMeans use the current input stream as STDIN for the program until token is seen. We will ignore this one until we get to scripting.
filemeans open a file for writing and truncate it and associate it with STDOUT.
>> filemeans open a file for writing and seek to the end and associate it with STDOUT. This is how you append to a file using a redirect.
n>&mmeans redirect FD n to the same places as FD m. Eg, 2>&1 means send STDERR to the same place that STDOUT is going to.



Thursday, 7 June 2012

Find if number is a power of two, and returns it power

Solution:

'a' is power of two iff:  (a & (a-1) == 0).


To calculate the highest power 'a',

  • iteratively shift the bits of a number to right
  • increment a counter each time you shift right
  • repeat above 2 steps until number > 0.
  • 'counter' gives the value if the highest power.
  • No. of loops = 32 ( width of the number)
Better solution:
To find more optimally one can make a lookup table, of say size 4, which stores the power of 2/(number of set bits) and then run the loop 32/4 = 8 times. 

Optimal Solution:
To optimize this even further we can use divide and conquer, at each step find the half of the 32 bit number which contains the set bit. And do this recursively. We need just 5 (= log 32) iterations in this method.

Tuesday, 5 June 2012

Swap two numbers using bit operations

Two numbers a,b.

XOR based solution:
a = a^b
// now a contains the  'a xor b'

b = b^a
// now b contains 'a'

a = a^b
// now a contains 'b'

Monday, 4 June 2012

Print all interleavings of given two strings


Given two strings str1 and str2, write a function that prints all interleavings of the given two strings. You may assume that all characters in both strings are different
Example:
Input: str1 = "AB",  str2 = "CD"
Output:
    ABCD
    ACBD
    ACDB
    CABD
    CADB
    CDAB

Solution:

public static void interleavings(String x, String y, String r){
  if(x.length() >0){
   if(y.length() >0){
    interleavings(x.substring(1),y,r+x.charAt(0));
    interleavings(x,y.substring(1),r+y.charAt(0));
   }
   else{
    System.out.println(r+x);
   }
  }
  else{
   System.out.println(r+y);
  }
 }
http://www.geeksforgeeks.org/archives/17743

A Program to check if strings are rotations of each other or not

Solution:

If the two given strings are A,B;
concatenate A+A => S.
Now if S contains B, then A is a rotation of B, else not.

Using KMP this can be done in O(n).

http://www.geeksforgeeks.org/archives/429

Check whether two strings are anagram of each other

Solution:

I.) Sort both the strings O(m log m) and then compare each of the sorted strings O(m) => O(m log m).

II.) Create an array of size 26,  in which store the counts of each alphabet in A. As you process B, decrement the count. If any of the counts are not equal to 0, then it is NOT an anagram pair. => O(m)

http://www.geeksforgeeks.org/archives/18752

The celebrity problem

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.



In a group of N people, find out if there is a celebrity (who knows no one, but evry one knows him).
Use the func. doesAknowB(A,B) returns true if A knows B.


Solution:


Maintain a stack of celebrities(possibly). Take two ppl A,B out from the stack and check if they know each other.
If doesAknowB(A,B) returns true, then A is discarded as he cant be the celeb. If it returns false, B is discarded as B cant be celeb bcoz evryone knows a celeb.


Keep discarding all the ppl till one last person remains. now validate if this person is celeb or not.


http://www.geeksforgeeks.org/archives/19622

Reasoning: This solution uses the the fact that each comparison/question allows us to discard one of the person, who is not a celebrity for sure. So, after N comparisons we have 1 prospective celeb remaining, which we can confirm by asking another n-1 questions.

Find the two numbers with odd occurrences in an unsorted array

Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences in O(n) time complexity and O(1) extra space.


Solution:


XOR of all no.s which occur even no. of times is zero, so XOR of two odd numbers will be the output. Choose a bit at which they differ, and then XOR all elements which have that bit set to '1' gives one no. 
similarly find the other number.


http://www.geeksforgeeks.org/archives/19378

Friday, 1 June 2012

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.


Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found


Solution:

Since all numbers are positive so the sum, we can do this without needing a DP array/table.

Maintain a running sum, which adds all elements from start_pos to curr_pos, until the sum becomes greater than the given number. When sum > given number remove the starting elements until the sum becomes <= the given number.

http://www.geeksforgeeks.org/archives/19267

Find the minimum of two numbers without using relational operators

Solution:

1.) Run a loop in which u decrement each number till either of them becomes a zero, and keep incrementing a counter. Return this counter value.
int min(int x, int y){
  int ctr = 0;
  while(x & y){
    x--;y--;ctr++;
  }
  return ctr;
}

2.)
Minimum of x and y will be

y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))
This method shifts the subtraction of x and y by 31 (if size of integer is 32). If (x-y) is smaller than 0, then (x -y)>>31 will be 1. If (x-y) is greater than or equal to 0, then (x -y)>>31 will be 0.
So if x >= y, we get minimum as y + (x-y)&0 which is y.
If x < y, we get minimum as y + (x-y)&1 which is x.


http://www.geeksforgeeks.org/archives/14805

Thursday, 31 May 2012

Find the smallest positive number missing from an unsorted array

Solution:
I.) Order statistics, to find the min +ve number missing from the array. Divide the array into positive and negative numbers.
Take a random no.(r) from positive array and partition the array like we do in quick sort. After partitioning the random no. is placed at the correct sorted position(k) in the array. If the left side of position 'k' contains less than k number then the missing number lies in the left half. Or else the missing number lies in the right half. Partition and continue searching.
This can search in average O(n) time, and worst case O(nlogn) time.

II.) This solution uses the indexes of the array(i) to mark the element 'i' seen by making it negative. The first index with the non negative integer is the answer.
http://www.geeksforgeeks.org/archives/19419

Maximum_subarray_problem


Find continuous subsequence of an array of integers such that its sum is maximum positive sum.
Solution:
function maximumSumSubarray(arr){
    var sum=0,max=0,i;
    for(i=0;i<arr.length;i++){
        sum = sum + arr[i];
       if(sum<0){
           sum=0;
       }
       if(max<sum){
           max = sum;
       }
   }
   return max;
}



http://en.wikipedia.org/wiki/Maximum_subarray_problem

http://wuhrr.wordpress.com/category/interview/

http://www.geeksforgeeks.org/archives/19248

Tuesday, 29 May 2012

Without using a calculator, how many zeros are at the end of "100!"? (that's 100*99*98*...*3*2*1)

Answer: What you don't want to do is start multiplying it all out! The trick is
remembering that the number of zeros at the end of a number is equal to the
number of times "10" (or "2*5") appears when you factor the number. Therefore
think about the prime factorization of 100! and how many 2s and 5s there are.
There are a bunch more 2s than 5s, so the number of 5s is also the number of 10s in
the factorization. There is one 5 for every factor of 5 in our factorial multiplication
(1*2*...*5*...*10*...*15*...) and an extra 5 for 25, 50, 75, and 100. Therefore we have
20+4 = 24 zeros at the end of 100!.

You have some nuts and some bolts in random order. You cannot compare nuts with nuts and bolts with bolts. It is guaranteed that a nut will fit in one or more bolts. Now you have to sort both nuts and bolts separately in minimum complexity.

You have some nuts and some bolts in random order. You cannot compare nuts with nuts and bolts with bolts. It is guaranteed that a nut will fit in one or more bolts. Now you have to sort both nuts and bolts separately in minimum complexity.


I used quick sort approach and sorted both in n * log (n). (The exact solution I am not posting it, quick sort is a hint).
Take a bolt and use it as pivot to find the smaller, matching and the bigger nuts. Now using this nut as pivot, partially sort the bolts. Now continue with the left and right halves, recursively.

Ternary search

A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function (function that is either strictly increasing and then strictly decreasing or vice versa). A ternary search determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining two-thirds.



The function

Assume we are looking for a maximum of f(x) and that we know the maximum lies somewhere between A and B. For the algorithm to be applicable, there must be some value x such that
  • for all a,b with A ≤ a < bx, we have f(a) < f(b), and
  • for all a,b with xa < b ≤ B, we have f(a) > f(b).

Run Time Order

T(n) = T(n/3) + c
   Î˜(log n)



Recursive algorithm
def ternarySearch(f, left, right, absolutePrecision):
   
#left and right are the current bounds; the maximum is between them
   
if (right - left) < absolutePrecision:
       
return (left + right)/2

   leftThird = (2
*left + right)/3
   rightThird = (left + 2
*right)/3

   
if f(leftThird) < f(rightThird):
       
return ternarySearch(f, leftThird, right, absolutePrecision)

   
return ternarySearch(f, left, rightThird, absolutePrecision)

Negative base representation (Base -2)

The base -r expansion of a number can be found by repeated division by (-r),recording the non-negative remainders of  and concatenating those remainders, starting with the last. Note that if  remainder d, then  For example, in negaternary:


NOTE: remember to subtract the smaller number, e.g. -3*2 = -6 from -5 and not -3*1 = -3  from -5 as -3 > -5.

Find the duplicate in an array of numbers from 1 to 1000

I. Given an array of 1001 integers with number from 1..1000, and one of the numbers duplicated. How would you find the duplicate in the array.

Solution:
-> (Sum of Array)-(Sum of number from 1..1000) = duplicate number
-> XOR of all numbers from 1 to 1024 is zero. So, XOR all numbers in the array, plus the numbers from 1001..1024. The duplicate number is produced as the output.

II. What if the array has 1002 integers with two different numbers as duplicates. How would you find both the duplicates ?

-> This one is based on the lines of the XOR solution above. Find the XOR.
In this XOR value, each '1' bit represents the position where the two duplicates differ.
So make two sets of numbers, one in which this bit position is set and another with this bit unset.
Take the XORs separately for one set of elements in which a particular bit is set, this will give you one element. XORing the elements with the bit unset will give you the other element.

http://www.geeksforgeeks.org/archives/7953

code: qor:{((x&y)~:)&x|y}

Median of medians algorithm

  1. If n is small, for example n<6, just sort and return the k'th smallest number.( Bound time- 7)
  2. If n>5, then partition the numbers into groups of 5.(Bound time n/5). Sort the numbers within each group. Select the middle elements (the medians). (Bound time- 7n/5)
  3. Call your "Selection" routine recursively to find the median of n/5 medians and call it m. (Bound time-Tn/5)
  4. Compare all n-1 elements with the median of medians m and determine the sets L and R, where L contains all elements <m, and R contains all elements >m. Clearly, the rank of m is r=|L|+1 (|L| is the size or cardinality of L). (Bound time- n)
  5. If k=r, then return m
  6. If k<r, then return k th smallest of the set L .(Bound time T 7n/10)
  7. If k>r, then return k-r th smallest of the set R.
Source: ranger.uta.edu/~gdas/Courses/Fall2004/.../W6Presentation.ppt


This algorithm (O(n)) is used to improve the worst case performance of basic (partitioning) order selection algo used in quicksort (O(n^2)) .
 

Monday, 28 May 2012

Finding second largest element in the array with min. no. of comparisions

Solution:

To find the MAX element of the array, we need to rule out (n-1) no.s, which means that we require atleast (n-1) comparisons. If we try to find the 2nd largest element in a similar fashion, we would need another (n-2) comparisons.

If however, we use the tournament model, we can reduce the no. of comparisons for second largest to (n-1)+logn. This involves finding the MAX as above and then finding the second MAX from amongst all those who lost to the MAX. The elements which lost to MAX at each level can be found out by creating a heap like structure of the tournament.

An extension to this is to find the kth largest element in the array.
->This can be found out by conducting k/2 tournaments to find MAX and 2nd MAX as above.
->We can use order statistics algorithm to find the kth largest element in O(n).
->Create heap in O(n). Remove the MAX n times from the heap, in O(k logn) time.

Sunday, 27 May 2012

Boyer-Moore Majority Vote Algorithm

Given an array A[N] of integers, find the major element in the array or return -1 if no major element exists in the array. An element 'e' of an array is called major if it exists more than N/2 times in the array.
PS: Use O(1) space and time complexity should be O(N).

Solution:
->Initial thought is to find the median of the array in O(N) and check if the median exists more than N/2 times in the array. Important thing to understand is that, if the element is the major element of the array then it has to occur at the median position.

Another approach i found after searching is based on majority vote algorithm, called Boyer-Moore algorithm. This algorithm is faster than the above one.
->In the first pass of the array you start with the first element as the major element and its count set to 1. There on, major element is voted for (when same element occurs next time) and against (when any other element occurs at the next position). After the count reaches 'zero', major element is changed to the next element and count set to 1. If there is a majority element in the array, then it would remain set as the major element. If however, there is no major element i.e. no element occurs more than N/2 times in the array, then the value in the major element after first pass would be a false value.
-> So we need a second pass, in which we get the count of the major element found in the firs pass. This count tells if the element is a true majority or a false one.

This is easy to PROVE: If there is a majority element 'e', then e's count would be atleast N/2+1 and other elements can not bring this count to zero by voting against it. hence this would be set as the major element after the first pass.

This algorithm is explained very well using a simulation on the following link : http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html, and the original paper here: http://www.cs.rug.nl/~wim/pub/whh348.pdf

Friday, 25 May 2012

Getting an interview call from any company

Everyone knows it is difficult to get an interview call from a company unless you are from a top notch college or you know an insider. True, isn't it ?
Well there is a company called RoundOne which links you to an insider of almost all companies in India. It allows you to be that insider as well, so get going people.
I see almost all top notch comapnies like Google, Microsoft, Amazon ... up there. Is your company there, if not why not add it.

Go ahead and give it a try !! 
http://www.roundone.in/

Thursday, 10 May 2012

Longest palindrome

Write algo for longest palindrome?


http://www.careercup.com/question?id=12697674

Probability and the chessboard horse

A horse is in chessboard. given its x,y find the probability through program that it will remain in board after n moves.

http://www.careercup.com/question?id=12695674

Awk - with loops and regex

Awk built-in variables:

FNR         The input record number in the current input file.
NF          The number of fields in the current input record.
NR          The total number of input records seen so far.

// an awk command to match the regex "UST" in the line
cat matrace_20120430234915.dat | awk -F'[,]' '{print FNR; i=1;for(i=1;i<(NF);i++) { print i,$i, /UST/;} }'


// an awk command which finds the column matching the regular expression of date in format "yyyy-mm-dd" and splits the date and adds 1 to the date and then prints the same.
awk -F'[,]' '{print FNR; i=1;for(i=1;i<(NF);i++) { print i,$i; if(match($i,/(....)\-(..)\-(..)/)) { split($i,a,"-"); printf("%d-%d-%d",a[1],a[2],(a[3]+1));};} }'

// awk using sprintf
awk -F'[,]' '{x=sprintf("%s",$1); i=1; for(i=2;i<(NF);i++) {  if(match($i,/(....)\-(..)\-(..)/)) { split($i,a,"-"); x=sprintf("%s,%s-%s-%d",x,a[1],a[2],(a[3]+1));} else { x=sprintf("%s,%s",x,$i); } } x=sprintf("%s,%s",x,$(NF)); print x;}'

Regex - regular expressions

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=regularExpressions

A regular expression is a special string that describes a search pattern.

A regular expression(regex) is one or more non-empty branches, separated by '|'.
'|' - It matches one of the branches

A branch is one or more atoms, concatenated.

An atom is possibly followed by a '*', '+', '?', or bound.
* - 0 or more atom
+ - 1 or more atom
? - 0 or 1 atom
a{1,3} - atom a occurs between 1 to 3 times

An atom is a regular expression enclosed in '()' (matching a match for the regular expression), a bracket expression (see below),
'.' (matching any single character)
'^' (matching the null string at the beginning of a line)
'$' (matching the null string at the end of a line)
a `\' followed by one of the characters `^.[$()|*+?{\' (matching that character taken as an ordinary character) or a single character with no other significance (matching that character).
There is one more type of atom, the back reference: `\' followed by a non-zero decimal digit d matches the same sequence of characters matched by the d-th parenthesized subexpression (numbering subexpressions by the positions of their opening parentheses, left to right), so that (e.g.) `([bc])\1' matches `bb' or `cc' but not `bc'.

[0-9] or [a-z] for specify the character range
A bracket expression is a list of characters enclosed in '[]'. It normally matches any single character from the list.
If the list begins with '^', it matches any single character not from the rest of the list.
If two characters in the list are separated by `-', this is shorthand for the full range of characters between those two inclusive (e.g. '[0-9]' matches any decimal digit).
With the exception of ']','^','-' all other special characters, including `\', lose their special significance within a bracket expression.

Wednesday, 2 May 2012

MySQL commands



List all databases on the sql server.

mysql> show databases;



Creating a database:

mysql> CREATE DATABASE magento;



Deleting a database:

mysql> drop database magento;



To see all the tables in the db.


mysql> show tables;








Saturday, 21 April 2012

Java Data Objects (JDO)

Reading: http://java.sun.com/developer/technicalArticles/J2SE/jdo/
The JDO Programming Model
The Development Life Cycle: Using JDO in Your Applications


JDO as part of Google App Engine (GAE):
https://developers.google.com/appengine/docs/java/datastore/jdo/overview

Lifecycle of GAE datastore writes:
https://developers.google.com/appengine/articles/life_of_write



Spring Web MVC step by step tutorial


Steps to setup a Spring Web MVC project on eclipse Helios:

1. Create a new Dynamic Web Project name "SpringWebMVC".

2. Create a JSP, 'SpringWebMVC/WebContent/index.jsp' with contents:
<html>
  <head><title>Example :: Spring Application</title></head>
  <body>
    <h1>Example - Spring Application</h1>
    <p>This is my test.</p>
  </body>
</html>

3. Create 'SpringWebMVC/WebContent/WEB-INF/web.xml', with contents:

<?xml version="1.0" encoding="UTF-8"?>

<web-app version="2.4"
         xmlns="http://java.sun.com/xml/ns/j2ee"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://java.sun.com/xml/ns/j2ee
         http://java.sun.com/xml/ns/j2ee/web-app_2_4.xsd" >

  <welcome-file-list>
    <welcome-file>
      index.jsp
    </welcome-file>
  </welcome-file-list>

</web-app>

4. Run the web app on any server and access it through URL: "http://localhost:8080/SpringWebMVC/"

5. Modify 'web.xml' to add the spring's servlet  DispatcherServlet (also known as a 'Front Controller').
 It is going to control where all our requests are routed.

  <servlet>
    <servlet-name>springapp</servlet-name>
    <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
    <load-on-startup>1</load-on-startup>
  </servlet>

  <servlet-mapping>
    <servlet-name>springapp</servlet-name>
    <url-pattern>*.htm</url-pattern>
  </servlet-mapping>

We have decided to let any URL with an '.htm' extension be routed to the 'springapp' servlet (the DispatcherServlet).

6. Create a file called 'springapp-servlet.xml' in the 'SpringWebMVC/WebContent/WEB-INF' directory. This file contains the bean definitions (plain old Java objects) used by the DispatcherServlet. It is the WebApplicationContext where all web-related components go. The name of this file is determined by the value of the <servlet-name/> element from the 'web.xml', with '-servlet' appended to it (hence 'springapp-servlet.xml'). This is the standard naming convention used with Spring's Web MVC framework.

<?xml version="1.0" encoding="UTF-8"?>

<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xsi:schemaLocation="http://www.springframework.org/schema/beans
       http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

  <!-- the application context definition for the springapp DispatcherServlet -->

  <bean name="/hello.htm" class="springapp.web.HelloController"/>

</beans>

Added a bean entry named '/hello.htm' and specify the class as springapp.web.HelloController. This defines the controller that our application will be using to service a request with the corresponding URL mapping of '/hello.htm'. The Spring Web MVC framework uses an implementation class of the interface called HandlerMapping to define the mapping between a request URL and the object that is going to handle that request (the handler). Unlike the DispatcherServlet, the HelloController is responsible for handling a request for a particular page of the website and is also known as a 'Page Controller' (Fowler). The default HandlerMapping that the DispatcherServlet uses is the BeanNameUrlHandlerMapping; this class will use the bean name to map to the URL in the request so that the DispatcherServlet knows which controller must be invoked for handling different URLs.

7. Copy Spring libraries to the 'WEB-INF/lib' folder:
commons-logging.jar
org.springframework.asm-3.1.1.RELEASE.jar
org.springframework.beans-3.1.1.RELEASE.jar
org.springframework.context-3.1.1.RELEASE.jar
org.springframework.core-3.1.1.RELEASE.jar
org.springframework.expression-3.1.1.RELEASE.jar
org.springframework.web-3.1.1.RELEASE.jar
org.springframework.web.servlet-3.1.1.RELEASE.jar

8. Create the controller, 'src/springapp.web.HelloController'.

public class HelloController implements Controller {

    protected final Log logger = LogFactory.getLog(getClass());

    public ModelAndView handleRequest(HttpServletRequest request, HttpServletResponse response)
            throws ServletException, IOException {

        logger.info("Returning hello view");

        return new ModelAndView("hello.jsp");
    }

}

 In Spring Web MVC, the Controller handles the request and returns a ModelAndView - in this case, one named 'hello.jsp'/
 The model that this class returns is actually resolved via a ViewResolver. Since we have not explicitly defined a ViewResolver, we are going to be given a default one by Spring that simply forwards to a URL matching the name of the view specified.

Reading:
About using a view resolver and annotation based configuration.
http://blogs.sourceallies.com/2010/02/taking-advantage-of-spring-mvcs-default-behavior/