divm01986
BAN USERpublic class KRankService
{
public static void kRank(int[] arr, int k)throws NullPointerException, IllegalArgumentException
{
if(arr==null)
{
throw new NullPointerException(“input array cannot be null”);
}
if(k<0||k>arr.length)
{
throw new IllegalArgumentException(“k cannot be less than zero or greater than array length”);
}
MinHeap mh=new MinHeap(k);
HashMap<Integer,Boolean> inHeap=new HashMap<Integer,Boolean>(k);
for(int i=0; i< arr.length;i++)
{
if(!inHeap.contains(arr[i]))
{
if(mh.isFull())
{
if(arr[i]>mh.getMin())
{
mh.extractMin();
}
}
mh.insert(arr[i]);
inHeap.put(arr[i],true);
}
}
System.out.println(“kth rank: “ + mh.getMin());
System.out.println(“k highest values: “ );
while(!mh.isEmpty())
{
System.out.print(mh.extractMin() + “ “);
}
}
private static int[] getInputArray(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(n);
}
return arr;
}
public static void main(String[] args)
{
Random rnd=new Random();
int n=rnd.nextInt(1001);
int k=rnd.nextInt(51);
int[] input=KRankService.getInputArray(n);
KRankService.kRank(input,k);
}
}
public class Node implements Iterable<Node>
{
private int value;
private Node left;
private Node right;
private Iterator<Node> bti;
public Node(int v)
{
this.value=v;
}
public Iterator<Node> iterator()
{
bti=new BinaryTreeIterator(this);
return bti;
}
public static void main(String[] args)
{
//code to create tree
Node n=new Node(6)
Iterator<Node> treeIt=n.iterator();
while(treeIt.hasNext())
{
System.out.println(treeIt.getNext().value);
}
}
public class BinaryTreeIterator implements Iterator<Node>
{
private Node n;=
public BinaryTreeIterator(Node rt)
{
n=rt;
}
public boolean hasNext()
{
return(n!=null);
}
public Node getNext() throws NoSuchElementException
{
if(hasNext())
{
Node ret=n;
n=n.left!=null?n.left:n.right;
return ret;
}
throw new NoSuchElementException();
}
public void remove() throws UnsupportedOperationException
{
throw new UnsupportedOperationException();
}
}
}
public class SumData//Helper class that will store largest sum and its length
{
private int sum;
private int length;
}
public class LisSumFinder
{
public int findLisSum(int[] a)
{
if(a==null)
{
throw new InvalidInputException("input array cannot be null");
}
ArrayList<SumData> allSums=new ArrayList<SumData>();
findLisAndSums(allSums,0,a);
SumData max=allSums.get(0);
for(SumData x:allSums)
{
max=x.length>=max.length?x:max;
}
return max.sum;
}
public void findLisAndSums(ArrayList<SumData> allSums,int idx,int[] a)
{
SumData curr;
if(idx==a.length)
{
return;
}
if(idx==0)
{
curr=new SumData();
}else
{
for(int i=0; i<idx;i++)
{
if(a[i]<a[idx])
{
curr=findLongestSum(curr,allSums.get(i));
}
}
}
curr.length++;
curr.sum+=a[idx];
findLisAndSums(allSums,idx+1,a)
}
public SumData findLongestSum(SumData x,SumData y)
{
if(x==null)
{
return y;
}
if(x.length>y.length)
{
return x;
}
return y;
}
}
public class Node
{
private int value;
private ArrayList<Node> children;
}
public class CheckSumProperty
{
public boolean hasSumProperty(Node n)
{
if(n==null)
{
return true;
}
Queue<Node> q=new Queue<Node>();
q.enqueue(n);
while(!q.isEmpty())
{
Node top=q.dequeue();
ArrayList<Node> c=top.children();
int sum=0;
for(Node x: c)
{
sum+=x.value;
q.enqueue(x);
}
if(sum!=top.value)
{
return false;
}
}
return true;
}
}
O(nm) time complexity and I think O(n) space
public class IntersectFinder
{
public ArrayList<ArrayList<Integer>> findIntersect(ArrayList<LinkedList<Integr>> allLists) throws InvalidInputException
{
if(allLists==null||allLists.size()==0)
{
throw new InvalidInputException();
}
Map<Integer,ArrayList<Integer>> setsMap=findIntersectingSets(alllists);
//Iterate through the map and store all sets into a single array list
ArrayList<ArrayList<Integer>> intersectingLists=new ArrayList<ArrayList<Integer>>();
for(Map.Entry<Integer,ArrayList<Integer>> me:setsMap.entrySet())
{
intersectingLists.add(me.getValue());
}
return intersectingLists;
}
private Map<Integer,ArrayList<Integer>> findIntersectingSets(ArrayList<LinkedList<Integer>> lists)
{
Map<Integer,ArrayList<Integer>> sets=new HashMap<Integer,ArrayList<Integer>>();
for(LinkedList<Integer> ls:lists)
{
//Navigate to the last entry of the current list
Integer m=ls.size()-1;
ArrayList<Integer> set;
//check if this last alue exists in the map(Is there another list we've already seen that intersects with this one?)
if(sets.contains(m))
{
set=sets.get(m);//If tail value exists in the map, get the corresponding value(Array list of head values from other lists that have the same tail)
set.add(ls.get(0));
sets.put(m,set);
}else{
set=new ArrayList<Integer>(1);
set.add(m);
sets.put(m,set);
}
}
return sets;
}
}
public class ZeroCounter
{
public int countZeros(int[] arr)
{
if(arr==null||arr.length==0)
{
throw new InvalidInputException("The input array cannot be null or empty");
}
int start=0
int end=arr.length-1;
while(start<=end)
{
int mid=(start+end)/2;
if(arr[mid]==0)
{
return mid+1;
}
end=mid-1;
}
}
public class CountZeroTester
{
ZeroCounter zc=new ZeroCounter();
int numZeros=zc.countZeros(input);//where input is an int array of 0s and 1s
}
public class FindElement
{
public int findValue(int[] input, int v) throws InvalidInputException
{
if(input==null||input.length==0)
{
throw new InvalidInputException(“The input array cannot be empty or null”);
}
int searchResult=searchValue(input, (v,0+v.length()-1)/2,0,v.length()-1);
return searchResult;
}
private int searchValue(int[] input, int idx,int value,int start, int end)
{
if(idx<start||idx>end)
{
return -1;
}
if(input[idx]==value)
{
return idx;
}
int diff=Math.abs(input[idx]-value);
int leftSearchResult=searchValue(input,idx-diff,value,start,idx-1);
if(leftSearchResult!=-1)
{
return leftSearchResult;
}
return (searchValue(input,idx+diff,value);
}
}
//Driver class
FindElement fe=new FindElement();
int elemIdx=fe.findValue(arr)//arr is an input array.
public TreeNode getTree(int[] a, int[][] arr,int i, int j){
return buildTree(i,j,a);
}
private TreeNode buildTree(int start,int end, int[] values){
if(start>end){
return null;
}
int mid=(start+end)/2;
Node n=new Node(values[mid]);
n.left=buildTree(start,mid-1,values);
n.right=buildTree(mid+1,end,values);
return n;
}
Assumptions made in my solution:
-- A[] from i to j all values in the tree rooted at a[i][j] INCLUDING a[i][j] itself.
--A[] is sorted.
Steps:
1) Find a[i][j] in A[]--this index will be called idx
2) Everything from i to idx-1 is the left subtree of a tree rooted at a[i][j].
3)Everything from idx+1 to j is the right subtree of a tree rooted at a[i][j]
public class Solution
{
public int makeP(String s,int start,int end)
{
if(end<=start)//if the string has length less than or equal to 1
{
return 0;
}
//If the characters at 'start' and 'end' are the same increase 'start' by 1,
//decrease 'end' by 1, and make a recursive call.
if(s.charAt(start)==s.charAt(end))
{
return(makeP(s,++start,--end));
}
//If a mismatch between char at 'start' and char at 'end' occurrs at the terminal
//ends of the string (0 and s.length()-1).
if(start==0)
{
//Remove the character at s.length()-1
s=s.substring(start,end);
//Add 1 to the total count of characters to be replaced.
///make a recursive call with 'start'=0 and 'end'=s.length()-1
return 1 + makeP(s,0,s.length()-1);
}
//If character mismatch occurrs somewhere in the middle of the string
//(not at terminal ends).
//The number of characters to add is defined as:
// 1 Less than The number of characters before 'start'-- (start-1) +
//The number of characters from 'start' to the end of the string (s.length()-start)
return ((start-1)+(s.length()-start));
}
}
Class FreeTimeFinder{
public static List<Interval> findFreeTimes(Interval[] per1, Interval[] per2){
if((per1==null)||(per2==null)||(per1.length==0)|| (per2.length==0)){
return null;
}
List<Interval> freeTimesPer1=findFreeTimes(per1);
Interval[] freeTimesPer2=findFreeTimes(per2).toArray();
List<Interval> mutualTimes=new ArrayList<Interval>();//contains mutually available times for person 1 and person 2
Iterator<Interval> it= freeTimesPer1.iterator();
while(it.hasNext()){
Interval p1Interval=it.next();
int overlapIdx=Arrays.binarySearch(p1Interval,freeTimesPer2);
if(overlapIdx!=-1){
Interval p2Interval=freeTimesPer2[overlapIdx];
if(p1Interval.end-p1.Interval.start <= p2Interval.end-p2Interval.start){
mutualTimes.add(p1Interval);
}else{
mutualTimes.add(p2Interval);
}
}
}
return mutualTimes;
}
private List<Interval> findFreeTimes(Interval[] busyTimes){
List<Interval> freeTimes=new ArrayList<Interval>();
for(int i=1; i<busyTimes.length;i++){
Interval first=busyTimes[i-1];
Interval sec=busyTimes[i];
if(first.end - sec.start => 1){
freeTimes.add(new Interval(first.end+1,sec.start-1));
}
}
return freeTimes;
}
class IntervalComparator implements Comparable{
public int compare(Interval i1,Interval i2){
if(i1.end<=i2.start){
return -1;//Indicates that interval i1 occurrs before interval i2
}else if(i1.start>=i2.end){
return 1;//Indicates that interval i1 occurrs after interval i2
}
return 0;//Indicates that interval i1 overlaps with interval i2
}
}
public static void main(String[] args){
Interval[] per1={new Interval(2,3),new Interval(4,7),new Interval(27,30)};
Interval[] per2={new Interval(1,2),new Interval(6,7),new Interval(22,25), new Interval(27,29)};
FreeTimeFinder() ft=new FreeTimeFinder();
List<Interval> mutualTimes=ft.findFreeTimes(per1,per2);
}
}
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 ...
//O(n) time and O(n) space--where n is the rank of the element we are interested in finding.
- divm01986 July 14, 2015