kandarp2516
BAN USERcan you please explain the algorithm?
- kandarp2516 April 06, 2015can you please explain flatten graph procedure?
- kandarp2516 April 04, 2015difference=A[length-1]-A[0]+1
A[0+difference] or A[length-1-difference] will be local minima or maxima. I am not sure. But it worked for all my tests. I have written code in separate answer below
class GetMaximaMinima
{
static int getIt(int[] arr)
{
int diff=Math.abs(arr[arr.length-1]-arr[0]);
if(diff+1<arr.length)
{
int minus=arr.length-2-diff,plus=diff+1;
if(arr[minus]>arr[minus-1] && arr[minus]>arr[minus+1])
return arr[minus];
if(arr[minus]<arr[minus-1] && arr[minus]<arr[minus+1])
return arr[minus];
if(arr[plus]>arr[plus-1] && arr[plus]>arr[plus+1])
return arr[plus];
if(arr[plus]<arr[plus-1] && arr[plus]<arr[plus+1])
return arr[plus];
}
return Integer.MAX_VALUE;
}
public static void main(String[] st)
{
int[] arr={1,2,3,4,5,4};
System.out.println("local minima/maxima:"+getIt(arr));
}
}
import java.util.*;
class MaxDifference2Elem
{
static int maxDiff(int[] arr)
{
int min=0,max=0;
int[] diff=new int[arr.length-1];
for(int i=0;i<arr.length;++i)
{
//System.out.println("arr[i]: "+arr[i]+" arr[min]: "+arr[min]);
if(arr[i]<arr[min])
min=i;
if(arr[i]>arr[max])
max=i;
if(i+1<arr.length)
diff[i]=arr[i+1]-arr[i];
}
int res=0;
if(min>max)
{
int temp=min;
min=max;
max=temp;
}
//System.out.print(min+","+max);
for(int i=min;i<max;++i)
res+=diff[i];
return res;
}
public static void main(String[] st)
{
int[] elem={1,-2,6};
System.out.println("largest difference: "+maxDiff(elem));
}
}
import java.util.*;
class TimeSlot implements Comparable<TimeSlot>
{
int start,end;
TimeSlot(int start,int end)
{
this.start=start;
this.end=end;
}
//@Overrride
public int compareTo(TimeSlot elem)
{
if(this.start>elem.start)
return 1;
else if(this.start<elem.start)
return -1;
else
return 0;
}
}
class CountingRooms
{
static int noRooms(TimeSlot[] arr)
{
Arrays.sort(arr);
int maxOverlap=1;
int overlap=0;
for(int i=0;i<arr.length-1 && overlap+i<arr.length-1 ;++i)
{
int j=i+1;
TimeSlot temp=arr[j];
TimeSlot present=arr[i];
overlap=0;
while(temp.start<present.end && j<arr.length)
{
temp=arr[j];
overlap++;
++j;
System.out.println("in overlap");
}
if(overlap+1>maxOverlap)
{
maxOverlap=overlap+1;
}
}
return maxOverlap;
}
public static void main(String[] st)
{
TimeSlot[] arr={new TimeSlot(2,5),new TimeSlot(4,9)};
System.out.println("total no of rooms neede: "+noRooms(arr));
}
}
Can you please give complexity analysis?
As far as I can understand (nlogn+m) where m is largest number of overlapping time-slots.
Is it correct?
import java.util.*;
class LetterPalindrome
{
static boolean isPalindrome(String str)
{
int noChars=0;
for(int i=0;i<str.length();++i)
{
if(isOurChar(str.charAt(i)))
noChars++;
}
int lo=0,hi=str.length()-1;
for(int i=0;i<noChars/2;++i,++lo,--hi)
{
while(!isOurChar(str.charAt(lo)))
++lo;
while(!isOurChar(str.charAt(hi)))
--hi;
if(str.charAt(lo)!=str.charAt(hi))
return false;
//System.out.println("lo: "+str.charAt(lo)+" hi: "+str.charAt(hi));
}
return true;
}
static boolean isOurChar(char ch)
{
if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'))
return true;
return false;
}
public static void main(String[] st)
{
String str="A man, a plan, a canal, Panama!";
//System.out.println("is A our:"+isOurChar(' '));
System.out.println("str: "+str+" result: "+isPalindrome(str.toLowerCase()));
}
}
class TreeNode
{
int data;
TreeNode left=null,right=null;
TreeNode(int data)
{
this.data=data;
}
TreeNode rightMost()
{
TreeNode tra=this;
while(tra.right!=null)
tra=tra.right;
return tra;
}
}
class BTtoDTSorted
{
static TreeNode head=null,tail=null;
static void addToList(TreeNode node)
{
if(head==null)
{
head=node;
tail=head;
return;
}
if(head.data>node.data)
{
node.right=head;
head=node;
}
else if(tail.data<node.data)
{
tail.right=node;
tail=node;
}
else
{
TreeNode tra=head;
while(tra.right!=null)
{
if(tra.right.data>node.data)
{
TreeNode temp=tra.right;
tra.right=node;
node.right=temp;
}
}
}
}
static void DFS(TreeNode head)
{
if(head.left!=null)
DFS(head.left);
System.out.print(head.data+", ");
if(head.right!=null)
DFS(head.right);
}
static void TreetoList(TreeNode head)
{
TreeNode left,right=head.right;
if(head.left!=null)
TreetoList(head.left);
System.out.println("head,data "+head.data);
addToList(head);
head.left=null;
if(right!=null)
TreetoList(right);
}}
- kandarp2516 March 27, 2015class Position
{
int indexTest,no;
Position(int indexTest,int no)
{
this.indexTest=indexTest;
this.no=no;
}
}
class RandomWordCombo
{
static boolean isCombo(String[] dict,String test)
{
HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>();
Stack<Position> pos=new Stack<Position>();
for(String each:dict)
{
if(dic.containsKey(""+each.charAt(0)))
{
//System.out.println("=========it is here");
ArrayList<String> temp=dic.get(""+each.charAt(0));
temp.add(each);
dic.put(""+each.charAt(0),temp);
}
else
{
ArrayList<String> temp=new ArrayList<String>();
temp.add(each);
dic.put(""+each.charAt(0),temp);
}
}
Iterator it = dic.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry)it.next();
System.out.println("key: "+pair.getKey());
for(String str:(ArrayList<String>)pair.getValue())
{
System.out.print(str);
}
}
pos.push(new Position(0,0));
while(!pos.isEmpty())
{
Position position=pos.pop();
System.out.println("position index: "+position.indexTest+" no: "+position.no);
if(dic.containsKey(""+test.charAt(position.indexTest)))
{
ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest));
if(strings.size()>1&&position.no<strings.size()-1)
pos.push(new Position(position.indexTest,position.no+1));
String str=strings.get(position.no);
if(position.indexTest+str.length()==test.length())
return true;
pos.push(new Position(position.indexTest+str.length(),0));
}
}
return false;
}
public static void main(String[] st)
{
String[] dic={"world","hello","super","hell"};
System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman"));
}
}
Slightly modified in-order traversal can do it in O(n) complexity and O(1) space
}
- kandarp2516 October 13, 2015