CareerCup

This one is related to finding cycles in your graph...The strategy would be if a move-out request came to, check that whether there is an opposite path present in graph or not...means check using dfs whether 'to' to 'from' is possible or not...if possible then try to find a cycle or add that edge in the graph...

import java.util.*;

class Request {
    String name;
    int from;
    int to;

    public Request(String n, int from, int to) {
        this.name = n;
        this.to = to;
        this.from = from;
    }
}

public class EmployeeMovingPlan {

    boolean findMovingPlanWrapper(Set<Set<String>> plan, Map<Integer, Map<Integer, List<String>>> g, Set<String> p, int src, int dst, String name) {

        if (src == dst) {
            p.add(name);
            plan.add(new HashSet<>(p));
            return true;
        } else {
            Map<Integer, List<String>> neighbors = g.getOrDefault(src, new HashMap<>());
            for (int i : neighbors.keySet()) {
                List<String> l = neighbors.get(i);
                if (l.size() == 0) continue;
                String n = l.get(l.size() - 1);
                l.remove(l.size() - 1);
                p.add(n);
                if(!findMovingPlanWrapper(plan, g, /*v,*/ p, i, dst, name)) {
                    p.remove(n);
                    l.add(n);
                }else{
                    break;
                }
            }
            return false;
        }
    }


    List<List<String>> findMovingPlans(List<Request> requests) {
        Set<Set<String>> finalPlan = new HashSet<>();
        Map<Integer, Map<Integer, List<String>>> graph = new HashMap<>();
        for (Request r : requests) {
            if (!graph.containsKey(r.to)) {
                Map<Integer, List<String>> neighbors = graph.getOrDefault(r.from, new HashMap<>());
                List<String> l = neighbors.getOrDefault(r.to, new ArrayList<>());
                l.add(r.name);
                neighbors.put(r.to, l);
                graph.put(r.from, neighbors);
            } else {
                Set<String> names = new HashSet<>();
                findMovingPlanWrapper(finalPlan, graph, names, r.to, r.from, r.name);
            }
        }
        List<List<String>> l = new ArrayList<>();
        for (Set<String> s : finalPlan) {
            l.add(new ArrayList<>(s));
        }
        return l;
    }

    public static void main(String[] args) {
        List<Request> l = new ArrayList<>() {{
            add(new Request("Alex", 1, 2));
            add(new Request("Ben", 2, 1));
            add(new Request("Chris", 1, 2));
            add(new Request("David", 2, 3));
            add(new Request("Ellen", 3, 1));
            add(new Request("Frank", 4, 5));
        }};
        System.out.println(new EmployeeMovingPlan().findMovingPlans(l));
    }

}

Little bit modification

int lasti=1
For i = 0...siglen-1
If signature[i] == 'I'
print reverse(lasti, i+1)
lasti=i+2
print reverse(lasti, siglen+1)
I think it'll work now perfectly

Nice Implementation................best code so far

Showell ....you are right........I skipped that one...anyways I loved your code....that's why I want to be sure that it's perfect....anyways thanks to clarify...

But your algorithm doesn't work for DD,DDD,DDDD...........................

@johnny...........could you please explain the data structure you will use for it....or explain thru some pseudo code or code.......because using conventional topological sorting it's difficult to implement

I think this code will add repeated number.........see for a signature DDIIDI, it will create a list efficiently upto 3,2,1 and after that it will add again 2 for 'I' and so on..........i think you need to keep some check to exclude those number which already included....because every time the start variable starts from 0 may cause some problem here

@totallyred
@cerberuz.............I think my code met your requirement........please check and comment

#include<stdio.h>
#include<conio.h>
static char A[4][4] ={{'L','L','L','L'},{'L','L','W','L'},{'L','W','L','W'},{'W','W','L','L'}};

struct Graph
{
    int v;
    int e;
    int **Adj;
};
int visited[20]={0};
int count = 0;
int max = 0;
struct Graph* createAdjMatrix(int n,int l,int t[][4])
{
    struct Graph *G = (struct Graph*)malloc(sizeof(struct Graph));
    int i,j;
    if(!G)
    {
	printf("memory error\n");
        return NULL;
    }
    G->v=G->e=l;
    G->Adj = (int**)malloc(sizeof(int*)*G->v);
    for(j=0;j<G->v;j++)
    {
            G->Adj[j] = (int*)malloc(sizeof(int)*G->v);
    }
    for(i=0;i<G->v;i++)
    {
            for(j=0;j<G->v;j++)
            {
                    G->Adj[i][j]=0;
            }
    }
    for(i=0;i<n;i++)
    {
            for(j=0;j<n;j++)
            {
                    if(t[i][j]!=-1)
                    {
                                  int x=t[i][j];
                                  if(((i-1)>=0&&(i-1)<n)&&(j>=0&&j<n)&&(t[i-1][j]!=-1))
                                  {
                                                                                      G->Adj[x][t[i-1][j]]=1;
                                                                                      G->Adj[t[i-1][j]][x]=1;
                                  }
                                  if(((i+1)>=0&&(i+1)<n)&&(j>=0&&j<n)&&(t[i+1][j]!=-1))
                                  {
                                                                                      G->Adj[x][t[i+1][j]]=1;
                                                                                      G->Adj[t[i+1][j]][x]=1;
                                  }
                                  if((i>=0&&i<n)&&((j-1)>=0&&(j-1)<n)&&(t[i][j-1]!=-1))
                                  {
                                                                                      G->Adj[x][t[i][j-1]]=1;
                                                                                      G->Adj[t[i][j-1]][x]=1;
                                  }
                                  if((i>=0&&i<n)&&((j+1)>=0&&(j+1)<n)&&(t[i][j+1]!=-1))
                                  {
                                                                                      G->Adj[x][t[i][j+1]]=1;
                                                                                      G->Adj[t[i][j+1]][x]=1;
                                  }
                    }
            }
    }
    return G;
}

void DFS(struct Graph *G,int u)
{
     visited[u]=1;
     int i;
     for(i=0;i<G->v;i++)
     {
                        if(!visited[i]&& G->Adj[u][i]==1)
                        {
                                         count++;
                                         DFS(G,i);
                        }
     }
}

void DFStraversal(struct Graph *G)
{
     int i;
     for(i=0;i<G->v;i++)
     {
                        visited[i]=0;
     }
     for(i=0;i<G->v;i++)
     {
                        if(!visited[i])
                        {
                                       //printf("next ")
                                       count=1;
                                       DFS(G,i);
                                       if(count>max)
                                       {
                                                    max=count;count=0;
                                       }
                                       else
                                           count = 0;
                        }
     }
}

int main()
{
    int i,j,temp[4][4] ={0};
    int c=0;
    for(i=0;i<4;i++)
    {
                    for(j=0;j<4;j++)
                    {
                                    if(A[i][j]=='L')
                                    {
                                                    temp[i][j]=c;
                                                    c++;
                                    }
                                    else
                                    {
                                                    temp[i][j]=-1;
                                    }
                                    
                    }
    }
    struct Graph *gh =  createAdjMatrix(4,c,temp);
    DFStraversal(gh);
    printf("maximum land= %d\n",max);
    getch();
    return 0;
}

cerberuz i need comment of you on this code

@totallyRed hi buddy.........your solution is nice.........i got it.....but the solution which was stated above is not exponential..... as we are not visiting those cells which we have already visited...in this way the solution is restricted to O(n^2)

cool

worst idea..........take ur time buddy..........it's not that much easy

can u please explain how O(n) solution does exist with extra memory of size k........as per my thought in any case you need the complexity of ((n-k)+1)*k

please explain....................

@totallyred.... please explain it with code...thnk u

how would you do a DFS or BFS search on it because the given 2D array is not an adjacency matrix.......to make it adjacency you need to create a 16by16 matrix which would be higher when the value of n is higher

package programs;
import java.util.Scanner;
import java.util.ArrayList;
public class program5 {
    public static String [] days={"","31","28","31","30","31","30","31","31","30","31","30","31"};
    public static ArrayList<String> dates = new ArrayList<String>();
    public static int dateGenerator(String s, String e,int ind)
    {
        String temp1,temp2,temp3;
        int i=ind;
        temp1 = s;
        System.out.println("Start date is "+temp1);
        temp2 = e;
        System.out.println("End date is "+temp2);
        dates.add(i,temp1);
        while(!(dates.get(i).equals(temp2)))
        {
            String day,month,year;
            int dayi,monthi,yeari;
            day=month=year=temp3="";
            month = month+dates.get(i).substring(0,2);
            day = day+dates.get(i).substring(2,4);
            year = year+dates.get(i).substring(4,dates.get(i).length());
            dayi = Integer.parseInt(day);
            monthi = Integer.parseInt(month);
            yeari = Integer.parseInt(year);
            if((yeari%400!=0)||(yeari%4!=0))
            {
                if(dayi<(Integer.parseInt(days[monthi])))
                {
                    dayi++;
                    i++;
                    if(monthi<10)
                    {
                        month = "0"+Integer.toString(monthi);
                    }
                    else
                    {
                        month =""+Integer.toString(monthi);
                        
                    }
                    if(dayi<10)
                    {
                        day="0"+Integer.toString(dayi);
                    }
                    else
                    {
                        day=""+Integer.toString(dayi);
                    }
                    dates.add(i,temp3+month+day+Integer.toString(yeari));
                    
                }
                else
                {
                    if(monthi<12)
                    {
                        day = "01";
                        monthi++;
                        i++;
                        if(monthi<10)
                        {
                           month = "0"+Integer.toString(monthi);
                        }
                        else
                        {
                           month =""+Integer.toString(monthi);
                        }
                        dates.add(i,temp3+month+day+Integer.toString(yeari));
                    }
                    else
                    {
                        day = "01";
                        month = "01";
                        yeari++;
                        i++;
                        dates.add(i,temp3+month+day+Integer.toString(yeari));
                    }
                }
            }
            else
            {
                if(dayi<(Integer.parseInt(days[monthi])))
                {
                    dayi++;
                    i++;
                    if(monthi<10)
                    {
                        month = "0"+Integer.toString(monthi);
                    }
                    else
                    {
                        month =""+Integer.toString(monthi);
                    }
                    if(dayi<10)
                    {
                        day="0"+Integer.toString(dayi);
                    }
                    else
                    {
                        day=""+Integer.toString(dayi);
                    }
                    dates.add(i,temp3+month+day+Integer.toString(yeari));
                }
                else
                {
                    if(monthi<12 && monthi!=2)
                    {
                        day = "01";
                        monthi++;
                        i++;
                        if(monthi<10)
                        {
                           month = "0"+Integer.toString(monthi);
                        }
                        else
                        {
                           month =""+Integer.toString(monthi);
                        }
                        dates.add(i,temp3+month+day+Integer.toString(yeari));
                    }
                    else if(monthi==2)
                    {
                        day = "29";
                        //monthi++;
                        i++;
                        month = "0"+Integer.toString(monthi);
                        dates.add(i,temp3+month+day+Integer.toString(yeari));
                    }
                    else
                    {
                        day = "01";
                        month = "01";
                        yeari++;
                        i++;
                        dates.add(i,temp3+month+day+Integer.toString(yeari));
                    }
                }                
            }
        }
        return i+1;
    }
    public static boolean palindrome(String a)
    {
        String temp = new String();
        temp="";
        int i=a.length()-1;
        while(i>=0)
        {
            temp=temp+a.charAt(i);
            i--;
        }
        if(temp.equals(a))
        {
            System.out.println("Palindrome found");
            return true;
        }
        else
            return false;
    }
    public static boolean validation(String b)
    {
        if(b.length()==8 && (Integer.parseInt(b.substring(0,2))>0 && Integer.parseInt(b.substring(0,2))<=12) && (Integer.parseInt(b.substring(2,4))>0 && Integer.parseInt(b.substring(0,2))<=31))
        {
            if(Integer.parseInt(b.substring(0,2))==2 && Integer.parseInt(b.substring(2,4))==29)
            {
                if((Integer.parseInt(b.substring(4,b.length()))%400==0) && (Integer.parseInt(b.substring(4,b.length()))%400==0))
                {
                    return true;
                }
                else
                    return false;
            }
            else if(Integer.parseInt(b.substring(0,2))==2 && Integer.parseInt(b.substring(2,4))>29)
            {
                return false;
            }
            else
                return true;
        }
        else
            return false;
    }
    public static boolean validation(String a,String b)
    {
        if((Integer.parseInt(a.substring(4,a.length()))<=Integer.parseInt(b.substring(4,b.length())))&&(Integer.parseInt(a.substring(2,4))<=Integer.parseInt(b.substring(2,4))) && (Integer.parseInt(a.substring(0,4))<=Integer.parseInt(b.substring(0,4))))
            return true;
        else
            return false;
    }
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        int ind=0;
        while(true)
        {
            String start,end,temp[];
            System.out.print("Enter a start date in MMDDYYYY format: ");
            start = in.next();
            System.out.println();
            System.out.print("Enter a end date in MMDDYYYY format: ");
            end = in.next();
            if(!validation(start))
            {
                System.out.println("Enter a valid start date!!!!");
                continue;
            }
            if(!validation(end))
            {
               System.out.println("Enter a valid end date!!!!");
               continue; 
            }
            if(!validation(start,end))
            {
                System.out.println("Enter a end date either equal to start date or bigger than start date!!!!");
                continue;
            }
            int index = dateGenerator(start,end,ind);
            for(int i=ind;i<index;i++)
            {
                if(palindrome(dates.get(i)))
                {
                    System.out.println(dates.get(i)+" is a palindrome!!!!!!!!!!!!");
                }
                else
                {
                    System.out.println(dates.get(i)+" is not a palindrome");
                }
            }
            String c;
            System.out.print("Do you execute this application again?(y/n):");
            c = in.next();
            System.out.println(c);
            if(c.equals("yes".toString()))
            {
                ind = index;
                continue;
            }
            else
            {
                break;
            }
                
        }
        
    }

}

public class program6 {
    public static String g = "123456789";
    public static void Combination(String source,int len,int index,String generator)
    {
        if(source.length()==len)
        {
            System.out.println(source);
        }
        else
        {
            if(index<generator.length())
            {
                for(int i=0;i<=(generator.length()-index);i++)
                {
                    Combination(source+generator.charAt(i),len,index-1,generator.substring(i+1));
                }
            }
            else
            {
                for(int i=0;i<generator.length();i++)
                {
                    Combination(source+generator.charAt(i),len,index-1,generator.substring(i+1));
                }
            }
        }
        
    }
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        System.out.println("Enter the length of password: ");
        int len = in.nextInt();
        String s ="";
        Combination(s,len,len,g);        
    }

}

package programs;
import java.util.Scanner;

public class dynamicprogram2 {
static int[] sequence;
static int[] memory;
public static int MaxSum(int[] x)
{
int len = x.length;
int max=0;
int status = 0;
int temp;
memory[0]=sequence[0];
//int temp;
for (int i=0;i<len;i++)
{
if(sequence[i]>0)
{
status =1;
break;
}
}
if(status == 1)
{
for (int i=1;i<len;i++)
{
temp=memory[i-1]+sequence[i];
if(temp>0)
{
memory[i] = temp;
if(max<memory[i])
max = memory[i];

}
else
memory[i]=0;
}

}
else
{
max = sequence[0];
for (int i=1;i<len;i++)
{
if(sequence[i]>max)
max = sequence[i];
}

}
return max;
}
public static void main(String[] args)
{
int length = 0;
Scanner a = new Scanner(System.in);
System.out.println("Enter the length of your sequence: ");
length = a.nextInt();
sequence = new int[length];
memory = new int[length];
for(int i=0;i<sequence.length;i++)
{
memory[i] = 0;
}
System.out.println("Enter the element of your sequence one by one: ");
for(int i=0;i<sequence.length;i++)
{
sequence[i] = a.nextInt();
}
System.out.println("Maximum contiguous sub-sequence sum of the given sequence is : "+ MaxSum(sequence));
}

}