divm01986
BAN USER//For positive numbers.
public void printConsecNums(int n)throws InvalidInputException
{
if(n<=0)
{
throw new InvalidInputException();
}
Queue<Integer> consecSums=new LinkedList<Integer>();
int sum=0;
for(int i=1;sum<n;i++)
{
sum+=i;
consecSums.enqueue(sum);
}
int start=1;
//if sum is larger then n, try removing values from the queue until you get a value less than or equal to n.
while(sum>n)
{
int top=consecSums.dequeue().intValue();
sum=sum-top<=n?sum-top:sum;
start++;
}
sum==n?printConsecValues(start,n):System.out.println( n + " cannot be expressed as the sum of consecutive values ");
}
private void printConsecValues(int s,int target)
{
int sum=0;
for(int i=s; i+sum<=target;i++)
{
System.out.print(i + " ");
sum+=i;
}
}
/**Time complexity is O(m+k) where m is the number of operations needed to get a sum>=n, k is the number of values to be removed from the queue to get the sum
to be less than or equal to n.**/
//For negative integers, we have to change the loops and the start variable (ie. for (int i=-1; sum>n;i--), while (sum<n), start=-1).
public void computeMatches(int teams, int days)throws InvalidInputException
{
if(teams%2!=0||days<=0)
{
throw new InvalidInputException();
}
int teamMatchesPerDay=(teams/days)+(teams%days);
int maxRotation=teams-1;
int rot=0;
int dayIdx=1;
int[] teamArr=new int[teams];
for(int i=0;i<teamArr.length;i++)
{
teamArr[i]=i+1;
}
while(rot<maxRotation)
{
for(int i=0;i<teamMatchesPerDay && rot<maxRotation;i++)
{
rotate(1,teams-1,teamArr);
rotate(2,teams-1,teamArr);
rot++;
System.out.println("day " + dayIx+":" + Arrays.toString(teamArr));//Neighboring values represent teams playing one another.
}
dayIdx++;
}
}
private void rotate(int start,int end,int[] arr)
{
int i=start;
int j=end;
while(i<j)
{
int tmp=arr[i];
arr[i++]=arr[j];
arr[j--]=tmp;
}
}
//Time: O(n^2) where n is the number of teams. Space is O(n) where n is the number of teams.
public void printTeamPlays()
{
int[][] m=new int[2][2];
//teams 1,2,3,4
m[0][0]=1;
m[1][0]=2;
m[0][1]=3;
m[1][1]=4;
System.out.println ("day 1: " + m[0][0] + "vs" + m[1][0] + "," + m[0][1] + "vs" + m[1][1]);
System. out.println("day 2:" + m[0][0] + "vs" + m[0][1] +", " + m[1][0] + "vs" + m[1][1]);
System.out.println("day 3:" + m[0][0] + "vs" m[1][1] + "," + m[0][1] + "vs" + m[1][0]);
}
//My earlier solution stops as soon as it finds two strings with mismatching characters, even if these two strings aren't necessarily the ones which yield the max product of their lengths.
Here is my updated solution.
public int getMaxLengthProduct(String[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
if(arr.length==0)
{
return -1;
}
Array.sort(a);
return findMaxLength(arr);
}
private int findMaxLength(String[] arr)
{
int maxMatch=-1;
for(int i=0;i<arr.length;i++)
{
boolean[] b=setValues(arr[i]);
for(int j=i+1;j<arr.length;j++)
{
boolean hasMatches=(b,arr[j]);
if(!hasMatches)
{
maxMatch=Math.max(maxMatch,arr[i].length()*arr[j].length())
}
}
}
return maxMatch;
}
private boolean[] setValues(String s)
{
boolean[] b=new boolean[27];
for(int i=0;i<b.length;i++)
{
b[i]=false;
}
for(int i=0;i<s.length();i++)
{
b[s.charAt(i)-'A']=true;
}
return b;
}
private boolean hasMatches(boolean[] b, String s)
{
for(int i=0;i<s.length();i++)
{
if(b[s.charAt(i)-'A'])
{
return true;
}
}
return false;
}
//Running time complexity (O((n^2m^2))
public int getMaxLengthProduct(String[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
if(arr.length==0)
{
return -1;
}
Array.sort(a);
return findMaxLength(arr);
}
private int findMaxLength(String[] arr)
{
for(int i=0;i<arr.length;i++)
{
boolean[] b=setValues(arr[i]);
for(int j=i+1;j<arr.length;j++)
{
boolean hasMatches=(b,arr[j]);
if(!hasMatches)
{
return (arr[i].length() * arr[j].length());
}
}
}
return -1;
}
private boolean[] setValues(String s)
{
boolean[] b=new boolean[27];
for(int i=0;i<b.length;i++)
{
b[i]=false;
}
for(int i=0;i<s.length();i++)
{
b[s.charAt(i)-'A']=true;
}
return b;
}
private boolean hasMatches(boolean[] b, String s)
{
for(int i=0;i<s.length();i++)
{
if(b[s.charAt(i)-'a'])
{
return true;
}
}
return false;
}
//Running time complexity (O((n^2m^2)), Space is O(1)
public class MovingAvgSvc
{
private float[] values
private float avg;
int rplc;
int size;
MovingAvgSvc(int k)
{
values=new float[k];
avg=0.0;
size=0;
rplc=0;
}
public void addValue(float f)
{
float sum=avg * size;
if(size<k)
{
size++;
}else
{
rplc=0;
}
sum-=values[rplc];
values[rplc++]=f;
sum+=f;
avg=sum/size;
}
public float getAvg()
{
return avg;
}
///O(K) Space, O(1) time.
- divm01986 November 16, 2015public class ObjIterator<Object> implements Iterator<Object>{
private ArrayList<Object> ls;
int pos=0;
ObjIterator(int count,Object toRepeat)throws NullPointerException, IllegalArgumentException
{
if(toRepeat==null)
{
throw new NullPointerException();
}
if(count<0)
{
throw new IllegalArgumentException
}
ls=new ArrayList<Object>(count);
for(int i=0;i<count;i++)
{
ls.add(toRepeat);
}
}
public boolean hasNext()
{
return (pos<ls.size());
}
public Object next()
{
return ls.get(pos++);
}
public Object remove()
{
return ls.remove(pos);
}
}
public ObjectIterator<Object> repeat(Object e, int n)
{
ObjectIterator it=new ObjectIterator(e,n);
return it;
}
public class Node
{
int value;
int count;
Node left;
Node right;
Node(int v,int c)
{
value=v;
count=c;
}
}
public Node insert(int v,Node n)
{
if(n==null)
{
n=new Node(v,1);
return n;
}
Node rt=n;
Node p=rt;
while(n!=null)
{
if(v<=n.value)
{
p=n;
n=n.left;
}
else
{
n.count++;
p=n;
n=n.right;
}
}
if(v>p.value)
{
p.right=new Node(v,1);
}else
{
p.left=new Node(v,1);
}
return rt;
}
public int getCount(Node n, int v)
{
while(n!=null && n.value<=v)
{
n=n.right;
}
if(n==null)
{
return 0;
}
if(n.value>v)
{
return n.count;
}
}
public int[] getCounts(int[] a)throws NullPointerException
{
if(a==null)
{
throw new NullPointerException();
}
Node rt=null;
for(int i=a.length-1;i>=0;i--)
{
int count=getCount(rt,a[i]);
rt=insert(a[i],rt);
a[i]=count;
}
return a;
}
//Uses a BST. O(n log n) running time with O(n) space.
public int[] findMissing(int[] arr)
{
int tmp=0;
int start=0;
int fillIdx=0;
if(arr[0]!=0)
{
int end=arr[0];
for(int i=0;i<end;i++)
{
tmp=arr[i];
arr[i]=i;
start++;
}
}else
{
start++;
tmp=arr[0];
}
while(start<=arr.length-1 && fillIdx<arr.length-1)
{
if(arr[start]-tmp>1)
{
for(int i=tmp+1;i<arr[start];i++)
{
arr[fillIdx++]=i;
}
tmp=arr[start++];
}else
{
tmp=arr[start++];
}
}
for(int i=tmp+1; i<2*arr.length && fillIdx<arr.length)
{
arr[fillIdx++]=tmp
}
return arr;
}
//Assumption: The word which is 1 character different from the query string may not have its characters in the same order as that of the query string.
public boolean hasSimilarWord(String[] arr,String s)throws NullPointerException;
{
if(arr==null||s==null)
{
throw new NullPointerException();
}
return isOneCharDiff(s,arr);
}
private boolean isOneCharDiff(String s,String[] words)
{
//Examine each word and see if there's one which only differs by 1 character
for(int i=0;i<words.length;i++)
{
String x=words[i].length();
if(x==s.length())
{
//Create a HashMap of all the characters in this string
HashMap<Character,Integer> mp=new HashMap<Character,Integer>();
for(int i=0;i<x.length();i++)
{
if(!mp.containsKey(x.charAt(i)))
{
mp.put(x.charAt(i),1);
}else
{
int currCount=mp.get(x.charAt(i)).intValue();
mp.put(x.charAt(i),++currCount);
}
}
//Check query word against characters in hash map
for(int j=0;j<s.length();j++)
{
if(mp.containsKey(s.charAt(j))
{
int currCount=mp.get(s.charAt(j)).intValue();
--currCount;
if(currCount==0)
{
mp.remove(s.charAt(j));
}else
{
mp.put(s.charAt(j),currCount);
}
}
}
if(mp.size()==1)
{
return true;//If we find a string that differs by just one character, return true.
}
}
}
return false;
}
//Time complexity: O(kn)--From comparing whether each string has matching characters with the query string (k is the number of strings whose length matches the query string, n is the number of characters in the query string).Space complexity O(k+n)--From the list of words with the same length as the query string and the hash map of characters.
//When using the hashmap. Have two pointers (one at the right end of the string(j), the other at the left end of the string(i)). On, the left end, if you encounter a '(','<','[' ,look up the matching key for i in the hashmap and retreive the corresponding value. See if the character at j matches the retrieved value.
- divm01986 October 02, 2015public class Node
{
int value;
Node left;
Node right;
}
public class BinaryTreeSvc
{
public boolean hasSameValues(Node a,Node b) throws NullPointerException
{
if(a==null||b==null)
{
throw new NullPointerException();
}
HashMap<Integer,Boolean> values=new HashMap<Integer,Boolean>();
fillMap(a,values);
//Check if all of the values in the hash map are present in the second tree.
return values.isEmpty();
}
public void fillMap(Node n,HashMap<Integer,Boolean> mp)
{
if(n==null)
{
return;
}
mp.put(n.value,true);
fillMap(n.left,mp);
fillMap(n.right,mp);
}
private void checkMap(HashMap<Integer,Boolean> mp,Node s)
{
if(s==null)
{
return;
}
if(mp.containsKey(s.value()))
{
mp.remove(s.value());
}
checkMap(mp,s.left);
checkMap(mp,s.right);
}
}
//Time complexity: O(n), Space complexity O(n).
public int getHourMax(String[] logs)
{
int[] usageData=new int[123100-10100+1];///123100 represents 12/31 at hour 00 10100 represents 01/01/ hour 00
int maxUsage=Integer.MIN_VALUE();
int maxUsageHour=0;
for(String s:logs)
{
int[] arr=s.split();//Split the log entry into three elements (start date and time, end date and time, usage)
//get start
int start=Integer.parseInt(arr[0]).intValue();
//get end
int end=Integer.parseInt(arr[1]).intValue();
//get usage
int usage=Integer.parseInt(arr[2]).intValue();
//find the indices in the array corresponding to start and end. Add usage to each of the values in these positions. Keep track of the maximum
//usage amount encountered at each update to the array
int i=start-10100;
int j=end-10100;
while(i<=j)
{
usageData[i] += usage;
if(usageData[i]>maxUsage)
{
maxUsage=usageData[i];
maxUsageHour=i+10100;
}
}
}
return maxUsageHour;
}
//Worst time complexity O(n). Space complexity is O(1)
public int removeDups(ArrayList<Integer> input) throws NullPointerException
{
if(input==null)
{
throw new NullPointerException();
}
if(input.isEmpty())
{
return 0;
}
HashMap<Integer,Boolean> mp=new HashMap<Integer,Boolean>();
int size=mp.size();
for(Integer x:input)
{
if(!mp.contains(x))
{
mp.put(x,true);
}else
{
input.remove(x);
size--;
}
}
return size;
}
//O(n) time complexity, O(n) space complexity.
public class MinThreeDifferences
{
public Class MinValues implements Comparable<MinValues>
{
int value;
char arrayId;
int idx;
MinValues(int v,int index, char id)
{
value=v;
idx=index;
arrayId=id;
}
public int compareTo(MinValues mv)
{
return value-mv.value;
}
}
public static MinValues[] findMinDifferences(int[] a, int [] b, int[] c) throws NullPointerException
{
if(a==null ||b==null||c==null)
{
throw new NullPointerException();
}
//Sort the three arrays from which we will be pulling our values.
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
MinValues[] minDiffThree=new MinValues[3];//Array to store 3 values with min difference across a, b, and c
//Store the minimum value from each of the three arrays (a,b,c)
minDiffThree[0]=new MinValues(a[0],0,'a');
minDiffThree[1]=new MinValues(b[0],0,'b');
minDiffThree[2]=new MinValues(c[0],0,'c');
int minDiff=Integer.MAX_VALUE();
do
{
Arrays.sort(mindDiffThree);//Sort the array of values from a,b,c
minDiff=Math.min(minDiff,minDiffThree[2].value-minDiffThree[0].value);//Find the minimum difference between the maximum and minimum value across all 3(a,b,c) arrays.If it's less then the current min difference, update minDiff.
minDiffThree[0].idx++;//Point to the next highest value in the array containing the minimum value across all 3 arrays.
int[] minArray=null;//Reference that will point to the array containing the min value.
switch(minDiffThree[0].arrayId)//Identify the array containing the minimum value element.
{
case'a':
minArray=a;
break;
case 'b':
minArray=b;
break;
case 'c':
minArray=c;
break;
case deafult:
break;
}
}while(minDiffThree[0].idx<minArray.length)//If there are no more elements left in the minimum element array, stop.
return minDiffThree;
}
//Create an array of random integers of size n
private static int[] getArray(int n)
{
if(n<=0)
{
return null;
}
Random rnd=new Random();
int[] arr=new int[n];
for(int i=0;i<arr.length;i++)
{
arr[i]=rnd.nextInt(101);
}
}
public static void main(String[] args)
{
Random rnd=new Random();
int[] a=MinThreeDifferences.getArray(rnd.nextInt(101));
int[] b=MinThreeDifferences.getArray(rnd.nextInt(101));
int[] c=MinThreeDifferences.getArray(rnd.nextInt(101));
MinValues[] m= MinThreeDifferences.findMinDifferences(a,b,c);
System.out.println(m[0].value, m[1].value,m[2].value);
}
}
//Time complexity is O(nlogn), where this is the time taken to sort the largest array of the three. Space Complexity is O(1).
public class Range
{
int start;
int end;
Range(int s, int e)
{
start=s;
end=e;
}
}
public class ArraySvc
{
public static ArrayList<Range> findConsecSegments(int[] a) throws NullPointerException, InvalidInputException
{
if(a==null)
{
throw new NullPointerException();
}
if(a.length==0)
{
throw InvalidInputException();
}
ArrayList<Range> results=new ArrayList<Range>();
Range r=new Range(a[0],a[0]);
for(int i=1;i<a.length;i++)
{
if(a[i]-a[i-1]!=1)
{
r.end=a[i-1];
results.add(r);
r=new Range(a[i],a[i]);
}
}
results.insert(r);
return results;
}
private static int[] getTestArray(int n)
{
if(n<=0)
{
return null;
}
Random rnd=new Random();
int[] arr=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=rnd.nextInt(arr.length()*20);
}
Arrays.sort(arr);
return arr;
}
public static void main(String[] args)
{
Random rnd=new Random();
int[] arr=ArraySvc.getTestArray(rnd.nextInt(1001));
System.out.println(Arrays.toString(arr));
ArrayList<Integer> results=ArraySvc.findConsecSegments(arr);
for(Range r: results)
{
System.out.println("start: " + r.start + "end: " + r.end);
}
}
}
O(n) time complexity, O(n) space complexity (worst case is when none of the integers are consecutive).
public int countIslands(char[][] arr)
{
int count=0;
for(int i=0;i<arr.length;i++)
{
for(int j=0;j<arr[i].length;j++)
{
if(arr[i][j]=='X')
{
count += checkForIsland(arr,i,j);
}
}
}
return count;
}
public int checkForIsland(char[][] m,int r, int c)
{
int xcount=1;
//check above
for(int k=r-1;k>=0 && k<r-4;k--)
{
if(m[k][c]=='X')
{
xcount++;
if(xcount==4)
{
return 1;
}
}else
{
break;
}
}
//check right
for(int k=c+1;k<m.length && k<c+4;k++)
{
if(m[r][k]=='X')
{
xcount++;
if(xcount==4)
{
return 1;
}
}else
{
break;
}
}
return 0;
}
//Time complexity: O(MN) Space complexity: O(1)
True.Consider an array sorted by rows and columns. Min entries of columns would occur in the first row. The maximum of these values would be (0,matrix[0].length-1). However, this value would also be the smallest entries across the maximum entries in each row (these entries would occur in column mat.length-1).
- divm01986 September 15, 2015public class Node
{
int value;
Node left;
Node right;
Node next;
}
public void connectNodes(Node n)
{
if(n==null)
{
return;
}
Node rightSibling=getNextSiblingChild(n.next);//Iteratively visit the right sibling of n until we find a node that has at least one child.
if(n.left!=null && n.left!=null)
{
n.left.next=n.right;
n.right.next=rightSibling;
}else if (n.left!=null && n.right==null)
{
n.left.next=rightSibling;
}else if (n.right!=null && n.left==null)
{
n.right.next=rightSibling;
}
connectNodes(n.left);
connectNodes(n.right);
}
private Node getNextSiblingChild(Node n)
{
while(n!=null)
{
if(n.left!=null)
{
return n.left;
}else if(n.right!=null)
{
return n.right;
}
n=n.next;
}
}
//O(n) time. O(1) space.
- divm01986 September 14, 2015public void printPostOrder(Node n) throws NullPointerException
{
if(n==null)
{
throw new NullPointerException();
}
Queue<Node> toVisit=new LinkedList<Node>();
Stack<Node> toPrint=new LinkedList<Node>();
toVisit.enqueue(n);
while(!toVisit.isEmpty())
{
Node top=toVisit.dequeue();
toPrint.push(top)
for(int i=top.children().size()-1;i>=0;i--)
{
toVisit.enqueue(top.children.get(i));
}
}
while(!toPrint.isEmpty())
{
System.out.print(toPrint.pop().value);
}
}
//O(n) time complexity, O(n) space complexity where n is the number of nodes in the graph.
public ArrayList<Integer> merged(int[] a, int[] b) throws NullPointerException
{
if(a==null||b==null)
{
throw new NullPointerException();
}
if(a.length==0||b.length==0)
{
throw new InvalidInputException();
}
ArrayList<Integer> results=new ArrayList<Integer>();
int j=a.length-1;
int i=b.length-1;
while(j>=0 && i>=0)
{
if(a[i]==b[j])
{
results.insert(a[i]);
i--;
j--;
}
else if(a[i]>b[j])
{
i--;
}else
{
j--;
}
}
return results;
}
O(n+m) time complexity, O(k) space complexity (k is the number of similar elements).
- divm01986 September 10, 2015public class StringSvc
{
public String shortestLexicoString(String s)
{
//If the string has all unique characters then it is already in shortest lexicographically ordered form.
HashMap<Character,Boolean> charsFound=new HashMap<Character,Boolean>();
boolean isUnique=true;
for(int i=0;i<s.length() && isUnique;i++)
{
if(charsFound.contains(s.charAt(i)))
{
isUnique=false;
}else
{
charsFound.put(s.charAt(i),true);
}
}
if(isUnique)
{
return s;
}
//If the string has duplicate characters, find the smallest lexicographically ordered string with all characters
String result=""+s.charAt(0);
char earliest=s.charAt(0);//lexicographically earliest character.
String curr=""+s.charAt(0);
HashMap<Character,Boolean> existsInResult=new HashMap<Character,Boolean>();
existsInResult.put(existsInResult.charAt(0));
for(int i=1;i<s.length();i++)
{
if(s.charAt(i)-earliest>0)//If current character occurs after the earliest character
{
if(!existsInResult.contains(s.charAt(i))//If the current character hasn't been added to the curretn string
{
curr+=s.charAt(i);//add the character to the string
existsInResult.put(s.charAt(i),true));
if(curr.length()>=result.length())//If the length of the current string is greater then or equal to the maximum length string seen so far
{
result=curr;
}
}
}else
{
if(s.charAt(i)-earliest<0)//If the current character isn't lexicographically after the earliest character, then it is the new earliest character.
{
curr=""+s.charAt(i);//Start a new string
existsInResult=new HashMap<Character,Boolean>()//Create a new hash map to store characters to be added to the new string.
earliest=s.charAt(i);//Set earliest character to the current character.
existsInResult.put(s.charAt(i),true);//Store current character into hash map.
}
}
}
return result;
}
}
Worst case Time complexity O(n).Space O(n)--assuming input string is all unique characters.
- divm01986 September 09, 2015public int solvePostFix(String s)
{
Stack<Integer> values=new LinkedList<Integer>();
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)>='0' && s.charAt(i)<='9')
{
values.push(Integer.parseInt(s.charAt(i));
}else
{
int sol=solveExprsn(values.pop().intValue(),values.pop().intValue(),s.charAt(i));
values.push(sol);
}
}
return values.pop().intValue();
}
private int solveExprsn(int first,int sec,char symbol)
{
switch (symbol){
case '+':
return first+sec;
case '*':
return first * sec;
case '-':
return first - sec;
case '/':
return first / sec;
default:
break;
}
return 0;
}
public class ArrayAdditionSvc
{
public static int[] incrementByOne(int[] arr) throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
int i=arr.length-1;
int carry=1;
while(i>=0)
{
int sum=carry+arr[i];
carry=sum/10;
arr[i--]=sum%10;
}
if(carry>0)
{
int newArr=new int[arr.length+1];
newArr[0]=carry;
System.arrayCopy(arr,newArry,0,1,arr.length);
arr=newArr;
}
return arr;
}
public static int[] getTestInput(int n)
{
if(n<=0)
{
return null;
}
int[] a=new int[n];
Random rnd=new Random();
for(int i=0;i<a.length;i++)
{
a[i]=rnd.nextInt(101);
}
return a;
}
public static void main(String[] args)
{
Random rnd=new Random();
int[] arr=ArrayAdditionSvc.getTestInput(rnd.nextInt(1001));
System.out.println("start: "+Arrays.toString(arr));
arr=ArrayAdditionSvc.incrementByOne(arr);
System.out.println("result: " +Arrays.toString(arr));
}
//Worst case analysis: O(N) time and O(N) space
}
public class SquareSumSvc
{
public static int findNumSquareTerms(int n)throws InvalidInputException
{
if(n<0)
{
throw new InvalidInputException();
}
int[] sumTermCounts=new int[n+1];
for(int i=0;i<=n;i++)
{
int sqrProd=i*i;
if(sqrProd<=n)
{
sumTermCounts[sqrProd]=1;//if i is a perfect square we only need 1 term.
}else
{
for(int j=0;j*j<=i;j++)
{
sumTermCounts[i]=Math.min(sumTermCounts[i],(sumTermCounts[j*j]+sumTermCounts[i-(j*j)]));
}
}
}
return sumTermCounts[n];
}
public static void main(String[] args)
{
int n=5;//expecting 2.
System.out.println(assertEquals(2,findNumSquareTerms(n,2)));
n=6;//expecting 3.
System.out.println(assertEquals(2,findNumSquareTerms(n,3)));
}
}
Could you clarify a little more about jumping between the two staircases-is the penalty higher then just moving upwards on one staircase? Also, when moving across does the destination step have to be the same level as the origin step or can it be higher (ie. can you move from step 1 of staircase A to step 3 of staircase B?)
- divm01986 August 06, 2015public class MaxDifferenceSvc
{
public static int findMaxDifference(int[] a) throws NullPointerException
{
if(a==null)
{
throw new NullPointerException();
}
int maxDiff=0;
int max=a[0];
for(int i=1;i<a.length;i++)
{
if(a[i]<=max)
{
maxDiff=Math.max(maxDiff,max-a[i]);
}else
{
max=a[i];
}
}
return maxDiff;
}
public static getTestArray(int n)
{
if(n<=0)
{
return null;
}
int[] arr=new int[n];
Random rnd=new Random();
for(int i=0;i<arr.length;i++)
{
arr[i]=rnd.nextInt(1001);
}
}
public static void main(String[] args)
{
Random rnd=new Random();
int[] inputArr=MaximumDifferenceSvc.getTestArray(rnd.nextInt(1001));
System.out.println("input: " + Arrays.toString(inputArr));
int maxDiff=MaximimumDifferenceSvc.findMaxDifference(inputArr);
System.out.println("max difference: " + maxDiff);
}
}
//O(N) time.
- divm01986 August 05, 2015public class Node implements Comparable<Node>
{
private String name;
private int phoneNo;
private String address;
public int compareTo(Node n)
{
if(n==null || !n instanceOf Node)
{
return -1;
}
if(name.equals(n.name)&&phoneNo.equals(n.phoneNo))
{
return 0;
}
return -1;
}
}
public class ListService
{
public static Node mergeWithoutDuplicates(Node l1,Node l2) throws NullPointerException
{
if(l1==null||l2==null)
{
throw new NullPointerException();
}
Node p=l1;
while(p.next!=null)
{
p=p.next;
}
p.next=l2;
return(removeDuplicates(l1));
}
private Node removeDuplicates(Node ls)
{
HashMap<Node,Boolean> mp=new HashMap<Node,Boolean>();
Node s=null;
Node f=ls;
while(f!=null)
{
if(!mp.containsKey(f))
{
mp.put(f,true);
}else
{
s.next=f.next;
f.next=null;
f=s.next;
}
}
return ls;
}
}
//O(n+m) space and O(n+m) time.
- divm01986 August 04, 2015public class DishAssignSvc
{
public static int getMinDifferentDishes(int[][] mat)throws NullPointerException
{
if(mat==null)
{
throw new NullPointerException();
}
boolean[] dishes=new boolean[mat[0].length];
for(int i=0;i<mat.length;i++)
{
for(int j=0;j<mat[i].length;j++)
{
if(mat[i][j]==1 && dishes[j])
{
break;
}else if(mat[i][j]==1 && !dishes[j])
{
dishes[j]=true;
}
}
}
int numDiffDishes=0;
for(int i=0;i<dishes.length;i++)
{
numDiffDishes++;
}
return numDiffDishes;
}
}
O(NM) time and O(M) space
//Ignore previous solution, I misread the question.
public class StringSvc
{
public String reverse(String s)
{
if(s==null)
{
throw new NullPointerException("input string cannot be null");
}
StringBuilder sb=new StringBuilder();
int i=0;
int j=a.length()-1;
while(i<a.length() && j>=0)
{
if(s.charAt(i)==' ')
{
sb.append(' ');
}else{
while(s.charAt(j)==' ')
{
j--;
}
sb.append(s.charAt(j--));
}
i++;
}
return sb.toString();
}
}
public static void main(String[] args)
{
String s= " a b "//should return " b a "
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
s=" a"//should return " a"
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
s= " ab c"//should return (" cb a")
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
}
}
public class StringSvc
{
public String reverse(String s)
{
if(s==null)
{
throw new NullPointerException("input string cannot be null");
}
StringBuilder sb=new StringBuilder();
int i=0;
int j=a.length()-1;
while(i<a.length() && j>=0)
{
if(s.charAt(i)==' ')
{
sb.append(' ');
}else{
while(s.charAt(j)==' ')
{
j--;
}
sb.append(s.charAt(j--));
}
i++;
}
return sb.toString();
}
}
public static void main(String[] args)
{
String s= " a b "//should return " b a "
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
s=" a"//should return " a"
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
s= " ab c"//should return (" cb a")
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
}
}
if the target node("node") doesn't have a right child don't we have to return the first node whose value is greater than the target node? So if "node" is a left child we return its immediate parent. Otherwise, if "node" is a right child we return the first node in the path from root to "node" whose value is greater than that of "node".
- divm01986 July 20, 2015Time:O(n) space O(logn)-->in terms of stack frame(s).
public class Node
{
int value;
Node left;
Node right;
}
public class BSTService
{
public Node findInOrderSuccessor(Node n,Node key)
{
if(n==null)
{
throw new NullPointerException("input tree cannot be null");
}
if(n.value==key.value)
{
Node succesor=getLeftMostChild(n.right);
if(successor!=null)
{
return successor;
}
return n;
}
Node result;
if(key.value<n.value)
{
result=findInOrderSuccessor(n.left,key);
}else
{
result=findInOrderSuccessor(n.right,key);
}
if(result==null)
{
return null;
}
if(result.value==key.value)
{
result=n.value>key.value?n:result;
}
return result;
}
private Node getLeftMostChild(Node r)
{
if(r==null)
{
return null;
}
while(r.left!=null)
{
r=r.left;
}
return r;
}
}
}
//Used an inorder traversal to visit the nodes in the tree. When visited, a node's left child is removed and the node is added to a stack
//O(n) time O(1) Space
public class Node
{
int value;
Node left;
Node right;
public Node(int v)
{
value=v;
}
}
public class BSTService
{
public static Node flattenTree(Node n) throws NullPointerException
{
if(n==null)
{
throw new NullPointerException("input tree cannot be null");
}
Stack s=new Stack();
flatten(s,n);
}
private void flatten(Stack s,Node r)
{
if(r==null)
{
return void;
}
flatten(s,r.left);
if(s.isEmpty())
{
r.left=null;
s.push(r);
}else
{
r.left=null;
s.peek.right=r;
s.push(r);
}
flatten(s,r.right);
}
public static void main(String[] args)
{
Node n=new Node(24);
Node l1=new Node(18);
n.left=l1;
l1.left=new Node(16);
l1=l1.left;
l1.right=new Node(17);
Node r1=new Node(30);
n.right=r1;
r1.left=(26);
r1.right=(34);
r1=r1.right;
r1.right=new Node(35);
Node n=BSTService.flattenTree(n);
}
}
public class IncrementSvc
{
public int[] increment(int[] a) throws NullPointerException
{
if(a==null)
{
throw new NullPointerException("input cannot be null");
}
int carry=1;
for(int i=a.length-1;i>0;i--)
{
int total=a[i]+carry;
carry=total/10;
a[i]=total%10;
}
if(a[0]>9)
{
int[] result=new int[a.length+1];
result[0]=a[0]/10;
result[1]=a[0]%10;
for(int i=2; i< result.length;i++)
{
result[i]=a[i-1];
}
a=result;
}
return a;
}
//Time:O(n) , Space: O(n).
- divm01986 July 19, 2015//Use two stacks O(n) time and O(2^h) space if we have a perfect tree
public class Node
{
private int value;
private Node left;
private Node right;
}
public class ZigZagService
{
public void ZigZagTraverse(Node n)
{
if(n==null)
{
System.out.println("error input is null");
}
Stack<Node> lr=new Stack<Node>();//Will print nodes from left to right
Stack<Node> rl=new Stack<Node>();//Will print nodes from right to left
rl.push(n);
while(true)
{
if(lr.isEmpty() && rl.isEmpty())
{
break;
}
while(!lr.isEmpty())
{
Node x=lr.pop();
System.out.print(x.value);
if(x.left!=null)
{
rl.push(x.left);
}
if(x.right!=null)
{
rl.push(x.right);
}
}
while(!rl.isEmpty())
{
Node x=rl.pop();
System.out.print(x.value);
if(x.right!=null)
{
lr.push(x.right);
}
if(x.left!=null)
{
lr.push(x.left);
}
}
}
}
public class CarData
{
private int checkOutHour;
private int returnHour;
}
public class Interval
{
private int start;
private int end;
private int cars;
}
public class RentalService
{
public int getMaxRentalPeriod(ArrayList<CarData> cd)throws IllegalArgumentException
{
if(cd==null||cd.isEmpty())
{
throw new IllegalArgumentException("input list cannot be null or empty");
}
int[] timeSlots=new int[24];//each index represents a time period from hour 0 to hour 24 (on a 24 hour clock) and the number of cars Checked out at a specific hour.
for(CarData c:cd)
{
timeSlots[checkOutHour]++;//If a car was checked out add 1 to the number at index checkOutHour
timeSlots[returnHour]--;//If a car was returned subtract 1 to the number of cars taken out at returnHour;
}
//find the contiguous LIS in the array
Interval maxTime=new Interval();
Interval currTime=new interval();
for(int i=1;i<timeSlots.length;i++)
{
if(timeSlots[i]>timeSlots[i-1])
{
currTime.cars+=timeSlots[i];
currTime.end++;
if(currTime.cars>timeSlots[i])
{
maxTime.end=currTime.end;
maxTime.cars=currTime.cars;
}else{
maxTime.start=i;
currTime.start=i;
maxTime.end=i;
currTime.end=i;
maxTime.cars=timeSlots[i];
currTime.cars=timeSlots[i];
}
}else{
currTime.start=i;
currTime.end=i;
currTime.cars=timeSlots[i];
}
}
return maxTime;
}
//Time: O(n) space: O(1)
- divm01986 July 16, 2015//Assuming that the integers in the array are unsorted. If more then one integer is found that doesn't repeat 3 times, only the first occurrence will be returned.
public class DuplicateService
{
public int findNonRepeat(int[] arr)
{
if(arr==null)
{
throw new NullPointerException("input array cannot be null");
}
if(arr.length<3)
{
return(arr[0]);
}
HashMap<Integer,Integer> counts=new HashMap<Integer,Integer>();
for(int i=0;i<arr.length;i++)
{
if(!counts.contains(arr[i]))
{
counts.put(arr[i],1);
}else
{
int count=counts.get(arr[i]).intValue();
count++;
counts.put(arr[i],count);
}
}
int result=0;
for(Map.Entry<Integer,Integer> e:counts)
{
int x=e.getValue();
if(x<3)
{
result=e.getKey().intValue();
}
return result;
}
}
}
- divm01986 July 15, 2015public class AnagramService
{
public boolean isAnagram(String a,String b)
{
if(a==null||b==null||a.trim().equals("")||b.trim().equals("")||a.length()!=b.length())
{
return false;
}
HashMap<Character,Integer> mp=new HashMap<Character,Integer>();
for(Character c: a)
{
if(!mp.contains(c))
{
mp.put(c,1);
}else{
int count=mp.get(c);
mp.put(c,count++);
}
}
for(Character c:b)
{
if(!mp.contains(c))
{
return false;
}
else
{
int count=mp.get(c);
count--;
if(count<0)
{
return false;
}
else if(count==0)
{
mp.remove(c);
}else
{
mp.put(c,count);
}
}
}
return(mp.isEmpty());
}
}
public class Node
{
private int value;
private Node left;
private Node right;
}
public class BSTService
{
public Node findClosestValue(Node n,int x)
{
if(n.value==x)
{
return n;
}
Node result=findClosestValue(n.left,x);
if(result==null)
{
result=findClosestValue(n.right,x);
}
if(result.left==null && result.right==null)//If target node is a leaf, closet value will be its parent
{
return n;
}
//if target node is not a leaf, either its left child or right child will have the closest value.
if(result.left!=null && result.right==null)
{
return result.left;
}
if(result.right==null && result.left!=null)
{
return result.right;
}
result=Math.abs(result.value-result.left.value)<Math.abs(result.value-result.right.value)?result.left:result.right;
return result;
}
}
RepDiscover the cheapest packers and movers in Gurgaon at best price with smooth and hassle free relocation. We provide truck ...
Repjacksonbetty625, Accountant at 247quickbookshelp
My work is specialized help, regardless of whether on the telephone, face to face, or distantly, identified with PC frameworks ...
Rephoychrista, Blockchain Developer at ASU
Worked with Clients to guide them through the event details about copier leasing companies and served as their personal coordinator ...
Repannehbell8, Quality Assurance Engineer at Globaltech Research
Build and maintain relationships with convention vendors. Resolve issues throughout meeting event timelines.Plan room layouts and event programs, schedule ...
RepAmmoBoard, Employee at A9
The best online ammo shop to buy ammunition for your rifles, handguns & shotguns from top brands you like.
RepGet powerful wazifa to know who did black magic. Guru Ji is the master of black magic totke, kala jadu ...
- divm01986 January 17, 2016