akella.mahesh
BAN USER//This method will pre process first to make an array for each period and then goes through this array to find the interval with max discount.
Space and Time complexity is O(MaxEndPeriod - MinStartPeriod)
public class Interval {
public class DiscountPeriod{
int start;
int end;
double discount;
public DiscountPeriod(int start, int end, double discount){
this.start = start;
this.end = end;
this.discount = discount;
}
public DiscountPeriod(){
}
@Override
public String toString(){
StringBuffer sb = new StringBuffer();
sb.append(this.start + " - "+this.end + " = "+ this.discount);
return sb.toString();
}
}
public DiscountPeriod getMaxDiscountPeriod(List<DiscountPeriod> periods){
//preprocess
int minPeriod = Integer.MAX_VALUE;
int maxPeriod = Integer.MIN_VALUE;
for(int i=0;i< periods.size();i++){
DiscountPeriod currPeriod = periods.get(i);
if(currPeriod.start < minPeriod)
minPeriod = currPeriod.start;
if(currPeriod.end > maxPeriod)
maxPeriod = currPeriod.end;
}
int [] periodDiscounts = new int[maxPeriod-minPeriod+1];
for(int i=0;i < periods.size(); i++){
DiscountPeriod currPeriod = periods.get(i);
for(int j = currPeriod.start -minPeriod; j <= currPeriod.end - minPeriod;j++){
periodDiscounts[j]+=currPeriod.discount;
}
}
for(int i=0;i< periodDiscounts.length;i++){
System.out.print(periodDiscounts[i]+" ");
}
//find max
int maxDiscount = 0;
int maxStart = 0;
int maxEnd = 0;
int start = 0 ;
int end = 1;
while(end < periodDiscounts.length){
if(periodDiscounts[start] != periodDiscounts[end]){
if(periodDiscounts[end-1] > maxDiscount){
maxStart = start;
maxEnd = end-1;
maxDiscount = periodDiscounts[end-1];
start = end;
}
}
end++;
}
if(periodDiscounts[start] > maxDiscount){
maxStart = start;
maxEnd = end-1;
maxDiscount = periodDiscounts[end-1];
}
DiscountPeriod returnPeriod = new DiscountPeriod();
returnPeriod.start = minPeriod + maxStart;
returnPeriod.end = minPeriod + maxEnd;
returnPeriod.discount = maxDiscount;
return returnPeriod;
}
public static void main(String[] args) {
Interval i = new Interval();
ArrayList<DiscountPeriod> discounts = new ArrayList<DiscountPeriod>();
discounts.add(i.new DiscountPeriod(1,5,10));
discounts.add(i.new DiscountPeriod(2,8,5));
discounts.add(i.new DiscountPeriod(4,6,20));
System.out.println("\nGreatest discount found from "+i.getMaxDiscountPeriod(discounts));
}
}
public class CustomIterator<T> {
private Iterator<T> [] iterators;
private int currentIterator = 0;
private int size = 0;
public CustomIterator(Iterator<T> [] itrs){
this.iterators = itrs;
this.size = itrs.length;
}
public boolean hasNext(){
int incrementSize = 0;
while(incrementSize < this.size && !((Iterator<T>)iterators[currentIterator%size]).hasNext()){
currentIterator++;
incrementSize++;
}
if(incrementSize == size)
return false;
return ((Iterator<T>)iterators[currentIterator%size]).hasNext();
}
public T next(){
T currNode = null;
if(this.hasNext()){
currNode = ((Iterator<T>)iterators[currentIterator%size]).next();
currentIterator++;
}
return currNode;
}
}
public class Node{
int value;
Node(int value){
this.value = value;
}
}
public static void main(String [] args){
IteratorPractice ip = new IteratorPractice();
Set<Node> a = new LinkedHashSet<Node>();
a.add(ip.new Node(1));a.add(ip.new Node(6));
Set<Node> b = new LinkedHashSet<Node>();
b.add(ip.new Node(2));b.add(ip.new Node(7));b.add(ip.new Node(10));
Set<Node> c = new LinkedHashSet<Node>();
c.add(ip.new Node(3));c.add(ip.new Node(8));
Set<Node> d = new LinkedHashSet<Node>();
d.add(ip.new Node(4));
Set<Node> e = new LinkedHashSet<Node>();
e.add(ip.new Node(5));e.add(ip.new Node(9));e.add(ip.new Node(12));
Iterator<Node> [] itrs = new Iterator[5];
itrs[0] = a.iterator();
itrs[1] = b.iterator();
itrs[2] = c.iterator();
itrs[3] = d.iterator();
itrs[4] = e.iterator();
CustomIterator<Node> test = ip.new CustomIterator<Node>(itrs);
while(test.hasNext()){
System.out.println(test.next().value);
}
}
// O(n) run time O(1) space if only alphabets are used.
public boolean isPangram(String s){
s = s.toLowerCase();
int charMap = 0x03FFFFFF;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c != ' ' && isNthBitSet(charMap,(int)(c-'a'))){
charMap = resetNthBit(charMap,(int)(c-'a'));
}
}
return charMap==0;
}
private boolean isNthBitSet(int number,int n){
int flag = 0x02000000;
return (number&((flag)>>>n)) >0;
}
private int resetNthBit(int number,int n){
int flag = 0x02000000;
return number^((flag)>>>n);
}
QuickSort with findMedium to find the pivot. Use findMax on left side of pivot and findMin on right side of pivot until findMax > pivot and findMin < pivot ?
- akella.mahesh April 17, 2015public String printCrazy(int n){
if(n == 1){
System.out.println("1");
return "1";
}
if(n > 1){
String returnPrev = printCrazy(n-1);
String [] parts = returnPrev.split(" ");
StringBuffer returnCur = new StringBuffer();
for(int i=0;i<parts.length;i++){
if(i==0){
returnCur.append(parts[0]);
returnCur.append(" ");
}
if(i > 0 && i < parts.length){
int calculatedValue = Integer.parseInt(parts[i-1]) + Integer.parseInt(parts[i]);
returnCur.append(calculatedValue);
returnCur.append(" ");
}
if(i == parts.length-1){
returnCur.append(parts[parts.length-1]);
returnCur.append(" ");
}
}
System.out.println(returnCur.toString().trim());
return returnCur.toString().trim();
}else
return "";
}
- akella.mahesh July 24, 2015