Finding the beginning of a loop in a link list.

Let's jump right into it.

I uploaded the drawings I made while trying to understand the algorithm. Just some rough sketches, thought it'd be handy.

4 steps.

Step 1: Assign two pointer to the head of the link list.

Slowpointer-Traverse 1 step at a time

Fastpointer- Traverse 2 steps at a time.

As you see here, both the f and s pointer are at the head of the link list.

Step 2: By the time the slow pointer has entered the loop, the fast pointer will be at k steps into the loop.

As you see here, s is at the beginning of the loop (position 0) and f is at k steps into the loop (3)

Step 3: Now both the pointers will collide at a single location after (length of loop-k) steps

Here the length of the loop is 5. And k was 3. So after traversing the s and f pointers 2 more times with their respective speeds they'll collide at the point show in figure. This point is k steps away from the head of the loop.

Step 4: Move your slow pointer to the head of the link list and start traversing both pointers with a speed of 1. The next time they'll collide, will be at the head of the loop. Ta-da! you're done.

Here, after f and s move 3 more times with a speed of 1, they'll collide at the head of the loop!

Kadane's Algorithm

So kadane's algorithm is to find the maximum sum of continuous numbers in a 1D array (i.e you're finding a subarray).

What's special about this you ask?

Well its complexity is of O(n)

Here's a simple pseudocode.

Kadane’s Algorithm: 
First: max = 0 
max_end = 0 
For each element of the array: 
(a) max_end = max_end + a[i]
(b) if(max_end < 0) max_end = 0 
(c) if(max < max_end) max = max_end return max

So basically we're looking for a list of positive numbers. 

If a negative number appears when max_end==0, we don't need to start counting the sum as the negative number will be less than zero, and we're trying to maximize the sum.

Otherwise if the max_end is greater than max, update the new value of max to max_end. 

Check this example. 
Eg -3,2,4,-3,6 
Firstly -3 appears, so since max_end now equals -3, we make max_end=0. 
Next 2 comes up, so max_end=2 and since max_end>max make max=2. 
Next 4 comes up, so max_end=2+4=6 and since max_end>max make max=6. 
Next -3 comes up, so max_end=6-3=3 and since max_end<max retain max=6. 
Next 6 comes up, so max_end=3+6=9 and since max_end>max make max=9. 
Hence our maximum sum of numbers in the subarray is from i=1 to i=4 which totals upto 9. 

This algorithm can be used in a variety of programming problems.

Query of products and stock

This is a java program to print out the quantity and stock when asked by a user. The index value is then sent to the server and the corresponding product and quantity is returned.
This is just a basic outline for people with doubts. You'll have to refine it for your own personal purposes.

CLIENT

import java.io.*;
import java.net.*;
import java.util.*;
import java.awt.*;
public class cli implements Runnable{
Thread th1;
String str1;
int str2;
PrintWriter pw;
int a=0;
BufferedReader br,br1;
String[] prod=new String[100];
int[] quan=new int[100];
public static void main(String args[])
{
cli sup=new cli();
sup.th1=new Thread(sup);
sup.th1.start();
}
public cli()
{
try{
Socket s=new Socket("localhost",3000);
br=new BufferedReader(new InputStreamReader(System.in));
br1=new BufferedReader(new InputStreamReader(s.getInputStream()));
pw=new PrintWriter(s.getOutputStream(),true);
}catch(IOException e){}
}
public void run()
{
int str;
String ans;
try{
while(true)
{
if(a==1)
{
ans=(br1.readLine());
System.out.println(ans);
}
a=1;
str=Integer.parseInt(br.readLine());
pw.println(str);
System.out.println("Sent");
}}catch(IOException e){}
}
public void prinnt()
{
pw.println(str1+str2);
}
}


SERVER


import java.io.*;
import java.net.*;
import java.util.*;
import java.awt.*;
public class serv implements Runnable{
Thread th1;
String str1;
int str2;
PrintWriter pw;
BufferedReader br;
String[] prod=new String[100];
int[] quan=new int[100];
public static void main(String args[])
{
serv sup=new serv();
sup.th1=new Thread(sup);
sup.th1.start();
}
public serv()
{
try{
ServerSocket ss=new ServerSocket(3000);
Socket s=ss.accept();

prod[0]="Carrot";
quan[0]=5;
br=new BufferedReader(new InputStreamReader(s.getInputStream()));
pw=new PrintWriter(s.getOutputStream(),true);
}catch(IOException e){}
}
public void run()
{
int str;
try{
while(true)
{
str=Integer.parseInt(br.readLine());
str1=prod[str];
str2=quan[str];
prinnt();
}}catch(IOException e){}
}
public void prinnt()
{
pw.println(str1+str2);
}
}

Teacher Student Chat (With BroadCast and Multicast)

Here's a program to implement Broadcast and Multicast Query System Between a student and a teacher.
You'll have to change the IP address per student logged in.
Just a basic outline for those who have doubts. UI isn't great.

TEACHER


import javax.swing.*;
import java.util.*;
import java.awt.*;
import java.io.*;
import java.net.*;
import java.awt.event.*;

public class teacher extends Frame implements ActionListener{
TextField tf2;
TextArea ta;
Button b1,b2;
TextField tf1;
public static void main(String args[])
{
teacher teach=new teacher();
}

public teacher()
{
Frame f1=new Frame();
Panel p1=new Panel();
Panel p2=new Panel();
GridLayout gl=new GridLayout(2,2);
FlowLayout fl=new FlowLayout();
p1.setLayout(gl);
tf1=new TextField();
b1=new Button("MULTICAST");
tf2=new TextField();
b2=new Button("BROADCAST");
b2.addActionListener(this);
b1.addActionListener(this);
p1.add(tf1);
p1.add(tf2);
p1.add(b1);
p1.add(b2);
ta=new TextArea();
p2.add(ta);
f1.setLayout(fl);
f1.add(p1,BorderLayout.NORTH);
f1.add(p2,BorderLayout.SOUTH);
f1.setSize(600,600);
f1.setVisible(true);
receiverfunc();


}

public void itsbroadcast()
{
try{
MulticastSocket ms=new MulticastSocket(3000);
InetAddress iads=InetAddress.getByName("255.255.255.255");
System.out.println("HI");
String str=tf2.getText().toString();
byte[] b=str.getBytes();
DatagramPacket dp=new DatagramPacket(b,str.length(),iads,3000);
ms.send(dp);
}catch(IOException e){}
}

public void itsmulticast()
{
try{
MulticastSocket ms=new MulticastSocket(3000);
InetAddress iads=InetAddress.getByName("231.4.2.3");
System.out.println("HI");
String str=tf1.getText().toString();
byte[] b=str.getBytes();
DatagramPacket dp=new DatagramPacket(b,str.length(),iads,3000);
ms.send(dp);
}catch(IOException e){}
}

public void receiverfunc()
{
try{
System.out.println("hi");
MulticastSocket ms=new MulticastSocket(3000);
InetAddress iads=InetAddress.getByName("231.4.2.2");
ms.joinGroup(iads);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
byte[] b=new byte[100];
DatagramPacket dp=new DatagramPacket(b,b.length);
ms.receive(dp);
String str=new String(dp.getData());
ta.append(str+"\n");
receiverfunc();
}catch(IOException e){}

}

public void actionPerformed(ActionEvent e)
{
if(e.getSource()==b2)
itsbroadcast();
else if(e.getSource()==b1)
itsmulticast();
}
}




STUDENT

import javax.swing.*;
import java.util.*;
import java.awt.*;
import java.io.*;
import java.net.*;
import java.awt.event.*;

public class student1 extends Frame implements ActionListener{
TextArea ta;
TextField tf1;
public static void main(String args[])
{
student1 teach=new student1();
}

public student1()
{
Frame f1=new Frame();
Panel p1=new Panel();
Panel p2=new Panel();
GridLayout gl=new GridLayout(2,2);
FlowLayout fl=new FlowLayout();
p1.setLayout(gl);
tf1=new TextField();
Button b1=new Button("SEND");
p1.add(tf1);
p1.add(b1);
b1.addActionListener(this);
ta=new TextArea();
p2.add(ta);
f1.setLayout(fl);
f1.add(p1,BorderLayout.NORTH);
f1.add(p2,BorderLayout.SOUTH);
f1.setSize(600,600);
f1.setVisible(true);
itsbroadcast();

}
public void itsbroadcast()
{
try{
System.out.println("hi");
MulticastSocket ms=new MulticastSocket(3000);
InetAddress iads=InetAddress.getByName("231.4.2.3");
ms.joinGroup(iads);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
byte[] b=new byte[100];
DatagramPacket dp=new DatagramPacket(b,b.length);
ms.receive(dp);
String str=new String(dp.getData());
ta.append(str+"\n");
itsbroadcast();
}catch(IOException e){}

}

public void itssent()
{
try{
MulticastSocket ms=new MulticastSocket(3000);
InetAddress iads=InetAddress.getByName("231.4.2.2");
System.out.println("HI");
String str=tf1.getText().toString();
byte[] b=str.getBytes();
DatagramPacket dp=new DatagramPacket(b,str.length(),iads,3000);
ms.send(dp);
}catch(IOException e){}
}

public void actionPerformed(ActionEvent e)
{
itssent();
}
}

Optimization hashing into arrays

So I came across this problem of basically finding n(n+1)/2 of numbers in an array where n is the frequency of the number.

Eg. 1 2 3 4
would equate to 1+1+1+1=4

Eg. 1 2 1

would equate to 3+1=4   (since 1 occurs twice , n(n+1)/2=3)

Now the input can range from -1000001 and 1000001.

My original method of doing this caused me to time out, even though I was coding it in python.

I finally found a way to organize my data. I simply hashed the numbers present in the input into 2 arrays, one for positive numbers and another for negative numbers.

Then I simply ordered them in ascending order (I'll explain the benefits of arranging your numbers in a sorted order and then working on it in another blog post. But apparently, it can improve the running time up to 6 times!)

Every time a number occurs, I simply incremented the occurrence since my array/list was initialized to 0 for every item.

If 2 occurred thrice then list[2]++ would occur thrice causing its value to be 3

Then I ran a for loop, and checked if the occurrence was greater than 0. If so, I applied the formula and kept adding.

If you have any doubts let me know.




def read():
isum=0
fisum=0
freq=0
lex=[0]*1000001
lexneg=[0]*1000001
s=raw_input("")
numbers = map(int, s.split())
for y in numbers:
if(y>=0):
lex[y]+=1
else:
y=abs(y)
lexneg[y]+=1
for y in xrange(0,1000001):
if(lex[y]>0):
isum=(lex[y]*(lex[y]+1))/2
fisum=fisum+isum
if(lexneg[y]>0):
isum=(lexneg[y]*(lexneg[y]+1))/2
fisum=fisum+isum

print fisum


n=raw_input("")
n=int(n)
for z in xrange(0,n):
x=raw_input("")
read()

Finding nth prime number (large number) (Optimization)

This was something handy I learned. Actually the problem is pretty easy, but when finding the nth prime where n>1000000 it takes way to long in the conventional way youre thinking. Here is an optimized solution to it, that reduces the time complexity. If you have any doubts, ask!

I think you can even optimize it further by doing p=p+2 and num=num+2. Try it out and see

def prime(chk):
if(chk%2==0):
return False
else:
p=3
while(p<chk**0.5+1):
if(chk%p==0):
return False
p=p+1
return True



def is_prime(x):
count=2
num=4
while(count<x):
if prime(num):
count+=1
num1=num
num=num+1
return num1

result=is_prime("Enter the nth term here")
print result

Largest Palindrome of 3 Numbers

If you have any doubts, let me know
#include <stdio.h>
#include <string.h>
#include<limits.h>

main()
{
    int i=999,j=999,sum=0,r=0,y,x,sum1=0,a[3000],k=0,temp;
    for(i=999;i>100;i--)
    {
        for(j=999;j>100;j--)
        {
            sum=i*j;
            x=sum;
            while(sum>0)
            {
             sum1=sum1*10;
             sum1=sum1+sum%10;
             sum=sum/10;
            }
            if(sum1==x)
         {
             a[k]=x;
             k++;
         }
            sum1=0;
        }
    }
   
    for(i=0;i<k;i++)
    for(j=0;j<k;j++)
    {
        if(a[i]<a[j])
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
printf("%d",a[k-1]);

}