Biswajit Sinha
BAN USER
I'm a MTech student of CS branch in IIT Roorkee
- 2of 2 votes
AnswersYou are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
- Biswajit Sinha in India
Now we create a signature of this array by comparing every consecutive pir of elements. If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI". The signature thus has a length of N-1. Now the question is given a signature, compute the lexicographically smallest permutation of [1,2,....n]. Write the below function in language of your choice.
vector* FindPermute(const string& signature);| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
Answerswe have an array, and a window of k elements
- Biswajit Sinha in United States
which slides over n elements of array A
k<n
we need to construct array B
such that B[i] = min (A[i], A[i+1]....A[i+k-1])
we don't have additional space at all
and we need to work on a solution better then O(nk)
say n = (1,1,2,3,4,5)
k =2
b would be (1,1,2,3,4)
if k=3
b would be (1,1,2,3)| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersSuppose you have given a 2D array having filled with "L" or "W" i.e. either land or water, using DP you have to find it largest land unit in this grid, each cell of land is considered as 1 unit and you can only consider up,down,left or right land units as contiguous to each other not diagonal unit.
- Biswajit Sinha in India
Example:
LLLL
LLWL
LWLW
WWLL
in the above mentioned grid the answer will be 8 units| Report Duplicate | Flag | PURGE
Flipkart Software Engineer / Developer Algorithm
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
- Biswajit Sinha October 31, 2012Showell ....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...
- Biswajit Sinha October 31, 2012But your algorithm doesn't work for DD,DDD,DDDD...........................
- Biswajit Sinha October 31, 2012@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
- Biswajit Sinha October 29, 2012I 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
- Biswajit Sinha October 29, 2012@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
- Biswajit Sinha September 10, 2012@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)
- Biswajit Sinha September 09, 2012cool
- Biswajit Sinha September 09, 2012worst idea..........take ur time buddy..........it's not that much easy
- Biswajit Sinha September 09, 2012can 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
- Biswajit Sinha September 09, 2012please explain....................
- Biswajit Sinha September 09, 2012@totallyred.... please explain it with code...thnk u
- Biswajit Sinha September 09, 2012how 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
- Biswajit Sinha September 09, 2012package 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));
}
}
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...
- Biswajit Sinha October 15, 2019