divm01986
BAN USER
//O(n) time where N is the size of the linked list. O(n) space.
public class Node
{
int value;
Node next;
}
private Node stripZeros(Node n)//Assuming nodes with value 0 should be removed.
{
Node s=n;
Node f=s.next;
while(f!=null)
{
if(f.value==0)
{
s.next=f.next;
}else
{
s=f;
}
f=f.next;
}
return n;
}
public Node removeZeroSum(Node n)
{
if(n==null||n.value==0)
{
return null;
}
n=stripZeros(n);
Deque<Integer> stack=new LinkedList<Integer>();
HashMap<Integer,Node> mp=new HashMap<Integer,Node>();
int sum=0;
Node v=n;
while(v!=null)
{
sum+=v.value;
if(mp.containsKey(sum))
{
while(stack.peekLast()!=sum)
{
int top=stack.removeLast();
mp.remove(top);
}
mp.get(sum).next=v;
}else if (sum==0)
{
n=v.next;
mp=new HashMap<Integer,Node>();
stack=new LinkedList<Integer>();
}else
{
stack.addLast(sum);
mp.put(sum,v);
}
v=v.next;
}
return n;
}
//Time Complexity: O(N) where N is the size of the input string.Space is O(N).
public class Solution
{
public static String constructPalindrome(String str)
{
if(str==null||str.length()==0)
{
return str;
}
if(str.length()==1)
{
return str;
}
if(isPalindrome(str))
{
return str;
}
return getLongestPalindrome(str);
}
private static boolean isPalindrome(String str) {
int i=0;
int j=str.length()-1;
while(i<j)
{
if(str.charAt(i)!=str.charAt(j))
{
return false;
}else
{
i++;
j--;
}
}
return true;
}
private static String getLongestPalindrome(String str) {
int[] c=new int[26];
for(int i=0;i<str.length();i++)
{
c[(int)str.charAt(i)-'a']++;
}
int oddCounts=0;
for(int i=0;i<c.length;i++)
{
if(c[i]%2!=0)
{
oddCounts++;
}
}
int i=0;
while(oddCounts>1 && i<c.length)
{
if(c[i]%2!=0)
{
c[i]--;
oddCounts--;
}
i++;
}
return buildString(c,str);
}
private static String buildString(int[] c,String s) {
StringBuilder sb=new StringBuilder(s);
int oddIdx=-1;
int a=0;
int b=sb.length()-1;
for(int i=0;i<c.length;i++)
{
if(c[i]%2!=0)
{
oddIdx=i;
}else
{
while(c[i]>0)
{
char v=(char)(i+'a');
sb.setCharAt(a, v);
sb.setCharAt(b, v);
a++;
b--;
c[i]-=2;
}
}
}
if(oddIdx!=-1)
{
while(c[oddIdx]>0)
{
char x=(char)(oddIdx+'a');
sb.setCharAt(a,x );
sb.setCharAt(b, x);
a++;
b--;
c[oddIdx]-=2;
}
}
return sb.toString();
}
}
//Time Complexity: O(MN) where M is the number of rows and N is the number of columns. Space is O(MN).
class Data
{
int row;
int col;
int idx;
public Data(int r, int c, int i)
{
row=r;
col=c;
idx=i;
}
public int hashCode()
{
return Objects.hash(new Integer(r), new Integer(c), new Integer(idx));
}
public boolean equals(Object obj)
{
if(obj==null || !(obj instanceof Data))
{
return false;
}
Data d=(Data)obj;
return d.row==row && d.col==col && d.idx==idx;
}
}
public boolean countOccurs(String str, char[][] m)
{
if(s==null||m==null||str.length()==0||m.length==0||m[0].length==0)
{
return false;
}
int ct=0;
for(int i=0;i<m.length;i++)
{
for(int c=0;c<m[0].length;c++)
{
if(m[i][c]==str.charAt(0))
{
ct=ct+dfs(new Data(0,i,c),str,m,new HashSet<Data>());
}
}
}
return ct;
}
private int dfs(Data d,String str, int[][] mat,HashSet<Data> set)
{
if(d.idx==str.length())
{
return 1;
}
if((d.row<0||d.row==mat.length||d.col==0||d.col==mat[0].length)||(mat[d.row][d.col]!=str.charAt(d.idx))||set.containsKey(d))
{
return 0;
}
int[] r={-1,0,1};
int[] c={-1,0,1};
int ct=0;
for(int i=0;i<r.length;i++)
{
for(int i=0;i<c.length;i++)
{
if(i!=d.row || c!=d.col)
{
ct=ct+dfs(new Data(d.idx+1,d.row+r[i],d.col+c[i]),str,mat,set);
}
}
}
if(ct==0)
{
set.put(d);
}
return ct;
}
//Read n lines (whee n is the maximum amount of lines that can fit into memory) at a time. Once line 0 has been processed read the n+1th line.For each line, add the
ip address into a trie as shown below.
//Node in trie.
public class Node{
int[] counts;//Stores frequency of each value. assumes that max value is the maximum value that can fit into a 32 bit integer.
Node[] arr;
public Node()
{
arr=new Node[Integer.MAX_VALUE];
counts=new int[arr.length];
}
}
//Adds a single IP address to the trie whose root is rt.
public void addIpAddress(String s,Node rt)
{
if(s!=null && s.length()!=0)
{
String[] sp=s.split('.');
Node v=rt;
for(String s:sp)
{
int k=Integer.parseInt(s);
v[k-1]=new Node();
counts[k-1]++;
v=v[k-1];
}
}
}
//Extracts the four most common subnets.
public ArrayList<String> getTopFour(Node rt)
{
ArrayList<String> ls=new ArrayList<String>();
int[] ips=new int[4];
int ipIdx=0;
for(int i=0;i<4;i++)
{
int maxCount=0;
int idx=-1;
for(int j=0;j<rt.arr.length;j++)
{
if(counts[j]>maxCount)
{
maxCount=counts[j];
idx=j;
}
}
ips[ipIdx++]=idx+1;
rt=rt.arr[idx];
}
ls.add(""+ips[0]+".*.*.*");
ls.add(""+ips[0]+"."+ips[1]+".*.*");
ls.add(""+ips[0]+"."+ips[1]+"."+ips[2]+".*");
ls.add(""+ips[0]+"." +ips[1]+"."+ips[2]+"."+ips[3]);
return ls;
}
public int[] modify(int[][] m)
{
if(m==null||m.length==0||m[0].length==0)
{
return null;
}
int[] result=new int[m.length*m[0].length];
int idx=0;
for(int i=0;i<m.length;i++)
{
if(i%2==0)
{
for(int c=0;c<m[0].length;c++)
{
result[idx++]=m[i][c];
}
}else
{
for(int c=m[0].length-1;c>=0;c--)
{
result[idx++]=m[i][c];
}
}
}
return result;
}
public Node flatten(Node head)
{
if (head==null||head.next==null && head.down==null)
{
return head;
}
Node v=head;
while(v!=null)
{
Node tmp=v.next;
Node s=v;
Node f=s.down;
while(f!=null)
{
s.next=f;
s.down=null;
s=f;
f=f.down;
}
s.next=tmp;
v=s.next;
}
return head;
}
//Time Complexity: Worst case: O(NM) where N is the number of words in input and M is the number of rows.
public class Solution
{
public String[] arrange(String[] words,int rows, int cols)
{
if(words==null||words.length==0||rows<=0||cols<=0)
{
return null;
}
String[] arr=new String[rows];
int i=0;
for(int j=0;j<arr.length;j++)
{
int c=0;
int wordCount=0;
int spaceCount=0;
while(c+arr[i].length()<=cols)
{
wordCount++;
if(c+arr[i].length()<cols)
{
spaceCount++;
c++;
}
c+=arr[i++].length();
if(i==arr.length)
{
i=0;
}
}
StringBuilder sb=new StringBuilder();
spaceCount=spaceCount+((c!=0)?cols-c:0);
sb.append(wordCount + " words " + spaceCount+ " spaces" );
arr[j]=sb.toString();
}
return arr;
}
}
I used a trie with random pointers and a boolean attribute in each trie node to indicate if it's the start of a word in the initial list.
//Time Complexity: Tree building-O(NL) where N is the number of words to be added and L is the length of the longest word. Pattern Querying-O(P) where P is the length of the pattern.
public class Node{
Node[] arr;
ArrayList<String> ls;
boolean isWordStart;
public Node{
arr=new Node[128];
ls=new ArrayList<String>();
isWordStart=false;
for(int i=0;i<pointers.length;i++)
{
pointers[i]=new ArrayList<Node>();
}
}
}
public class Solution
{
Node rt;
public Solution(String[] arr)
{
rt=new Node();
buildTree(arr);
}
private void buildTree(String[] arr)
{
for(String s:arr)
{
addToTree(rt,s);
rt.arr[(int)s.charAt(0)].isWordStart=true;
}
}
public ArrayList<String>query(String patt)
{
if(patt==null||patt.length()==0||rt==null)
{
return null;
}
return(findMatches(String p));
}
private ArrayList<String> findMatches(String p)
{
Node v=rt.arr[(int)p.charAt(0)]==null||!rt.arr[(int)p.charAt(0)].isWordStart?null:rt.arr[(int)p.charAt(0)];
ArrayList<String> ls=new ArrayList<String>();
for(int i=1;i<p.length();i++)
{
int idx=(int)p.charAt(i);
if(v[idx]==null)
{
v=null;
break;
}
v=v[idx];
}
if(v!=null)
{
ls.addAll(v.ls);
}
return ls;
}
private void addToTree(Node r,String str)
{
int lastIdx=str.length();
for(int i=str.length()-1; i>=0;i--)
{
int idx=(int)str.charAt(i);
if(isUpperCase(str.charAt(i)))
{
addHelper(r,str.substring(i,lastIdx),lastIdx);
lastIdx=i;
}
}
}
private boolean isUpperCase(char c)
{
return (int)(c-'A')==0;
}
private void addHelper(Node rt,String s,lastIdx)
{
if(rt.arr[(int)s.charAt(0)]==null)
{
rt.arr[(int)s.charAt(0)]=new Node();
}
Node v=rt.arr[(int)s.charAt(0)];
for(int i=1;i<s.length();i++)
{
int idx=(int)s.charAt(i);
if(v.arr[idx]==null)
{
v.arr[idx]=new Node();
}
if(lastIdx<s.length())
{
v.arr[(int)s.charAt(lastIdx)]=rt.arr[(int)s.charAt(lastIdx)];
}
v=v.arr[idx];
v.add(s);
}
if(lastIdx<s.length())
{
v.arr[(int)s.charAt(lastIdx)]=rt.arr[(int)s.charAt(lastIdx)];
}
}
}
Attempting this with Java.
/* Approach: Use counting sort to group hotel data together based on hotel Id. Iterate through the grouped data and compute
a moving average for each hotel Id/group's scores. If a group has an average score >= avg_min_score, add that hotel's id
to the list of ids to be returned. */
//Time Complexity: O(N).Space: O(N).
//Class representation of Input data.
class HotelData
{
String hotelId;
String userId;
int score;
}
public ArrayList<String> topHotels(HotelData[] scores,int min_avg)
{
if(scores==null||scores.length==0)
{
return Collections.<String>emptyList();
}
ArrayList<String> results=new ArrayList<String>();
if(scores.length==1){
if(scores[0].score>=minAvg)
{
results.add(scores[0].hotelId);
return results;
}
}
HashMap<String,Integer> counts=new HashMap<String,Integer>();
for(int i=0;i<scores.length;i++)
{
int ct=1;
if(!counts.containsKey(scores[i].hotelId))
{
counts.put(scores[i].hotelId,ct);
}else
{
ct=counts.get(scores[i].hotelId).intValue();
ct++;
counts.put(scores[i].ct);
}
}
HashMap<String,Integer> indices=new HashMap<String,Integer>();
int idx=0;
HotelData[] h=new HotelData[scores.length];
for(int i=0;i<scores.length;i++)
{
int p;
if(indices.containsKey(scores[i].hotelId))
{
p=indices.get(scores[i].hotelId).intValue();
}else{
p=idx;
idx=idx+(counts.get(scores[i].hotelId).intValue());
}
h[p]=scores[i];
indices.put(scores[i].hotelId;,++p);
}
int avg=h[0].score;
int ct=1;
for(int i=1;i<h.length;i++)
{
if(h[i].hotelId!=h[i-1].hotelId)
{
if(avg>=minAvg)
{
results.add(h[i].hotelId);
}
avg=h[i].score;
ct=1;
}else{
int sum=(avg*ct)+h[i].score;
ct++;
avg=sum/ct;
}
}
return results;
}
public int findKth(int k)
{
if(k<=0)
{
return -1;
}
if(k==1)
{
return 4;
}
if(k==2)
{
return 7;
}
int[] arr=new int[k+1];
arr[1]=4;
arr[2]=7;
for(int i=3;i<arr.length;i++)
{
arr[i]=i%2!=0?(arr[(i>>2)]*10)+4:(arr[(i>>2)-1]*10)+7;
}
return arr[arr.length-1];
}
//Time complexity: O(K). Space Complexity: O(K)
//I didn't do any input parsing, this is what comes after.
public class Point
{
int row;
int col;
public Point(int r,int c)
{
row=r;
col=c;
}
public int hashCode()
{
int[] vals={row,col};
return Arrays.hashCode(vals);
}
public boolean equals(Object obj)
{
if(obj==null || !obj instanceof Point)
{
return false;
}
Point p=(Point)obj;
return hashCode()==p.hashCode();
}
}
private void bfs(int[][] m,Point p)
{
int level=0;
Deque<Point> q=new LinkedList<Point>();
HashSet<Point> set=new HashSet<Point>();
set.add(p);
q.addFirst(p);
q.addLast(null);
while(!q.isEmpty())
{
level++;
while(q.peekFirst()!=null)
{
Point curr=q.removeFirst();
Point[] dirs={new Point(-1,0),new Point(1,0),new Point(0,-1),new Point(0,1)};
for(Point x:dirs)
{
Point next=new Point(curr.row+x.row,curr.col+x.col);
if(isValid(next,set,matrix) && m[next.row][next.col]>level)
{
m[next.row][next.col]=level;
q.addLast(next);
}
}
}
q.removeFirst();
q.addLast(null;)
}
}
private boolean isValid(Point p, HashSet<Point> set, int[][] m)
{
return(!set.contains(p) && (p.row>=0 && p.row<m.length) && (p.col>=0 && p.col<m[0].length));
}
public int[][] modifyArray(int[][] matrix)
{
if(matrix==null||matrix.length==0)
{
return null;
}
ArrayList<Point> ls=getZeros(matrix);
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix[0].length;j++)
{
if(m[i][j]!=0)
{
m[i][j]=Integer.MAX_VALUE;
}
}
}
for(Point p:ls)
{
bfs(matrix,p);
}
}
//Time Complexity: O(NMP) where N is number of rows, M is the number of columns and //P is the number positions with zero. Space: O(NM)
public class Point
{
int row;
int col;
public int hashCode()
{
return Objects.hashCode(new Integer(row), new Integer(col));
}
public boolean equals(Object obj)
{
if(obj==null||! obj instanceOf(Point))
{
return false;
}
Point p=(Point)obj;
return p.hashCode()==hashCode();
}
}
public ArrayList<Point> shortPath(Point start, Point end)
{
if(start==null||end==null||start.row<0||start.row>=8||end.row<0||end.col>=8)
{
return null;
}
return bfs(start,end,new HashMap<Point,Point>());
}
private ArrayList<Point> bfs(Point start,Point end, HashMap<Point,Point> mp)
{
ArrayList<Point> result=new ArrayList<Point>();
Deque<Point> q=new LinkedList<Point>();
q.addFirst(start);
mp.put(start,null);
while(!q.isEmpty())
{
Point top=q.removeFirst();
if(top.equals(end))
{
Point key=top;
while(key!=null)
{
result.add(0,key);
key=mp.get(key);
}
break;
}
Point[] next={new Point(2,1),new Point(2,-1),new Point(-2,1),new Point(-2,-1),new Point(1,2),new Point(1,-2),new Point(-1,2),new Point(-1,-2)};
for(Point p:next)
{
Point f=new Point(top.row+p.row,top.col+p.col);
if(!mp.containsKey(f) && (f.row>=0 && f.row<8) && (f.col>=0 && f.col<8))
{
q.addLast(f);
mp.put(f,top);
}
}
}
return result;
}
Time Complexity: O(1) Assuming chessboard is always 8x8. Otherwise O(N^2) where N is the number of rows. Space Complexity: O(1) in 8x8 case otherwise O(N^2).
public int numZeros(int[][] m)
{
if(m==null||m.length==0||m[0].length==0)
{
return 0;
}
int r=0;
int c=m[0].length-1;
int total=0;
while(r<m.length)
{
if(c<0)
{
r++;
c=m[0].length-1;
}else
{
if(m[r][c]==1)
{
c--;
}else{
if(c==m[0].length-1||m[r][c+1]==1)
{
total+=c+1;
r++;
}else{
c++;
}
}
}
}
return total;
}
Worst case: O(N) where N is the number of rows.
public int[][] rotate(int[][] m)
{
if(m==null||m.length==m[0].length)
{
return null;
}
for(int layer=0;layer<m.length/2;layer++)
{
int minRow=layer;
int minCol=minRow;
int maxRow=m.length-layer-1;
int maxCol=maxRow;
if (minRow==maxRow)
{
break;
}
int tmp=m[minRow][minCol];
for(int i=minRow+1;i<=maxRow;i++)
{
m[i-1][minCol]=m[i][minCol];
}
for(int i=minCol+1;i<=maxCol;i++)
{
m[maxRow][i-1]=m[maxRow][i];
}
for(int i=maxRow-1;i>=minRow;i--)
{
m[i+1][maxCol]=m[i][maxCol];
}
for(int i=maxCol-1;i>minCol;i--)
{
m[minRow][i+1]=m[minRow][i];
}
m[minRow][minCol+1]=tmp;
}
return m;
}
//Time Complexity: O(n^2) where n is the number of rows/columns in the input matrix.
- divm01986 June 24, 2016//Time complexity:O(N) where N is the number of entries in the array. Space: O(N).
public int numGrandchildren(String[][] mat,String gf)
{
if(mat==null||mat.length==0||gf==null||gf.length()==0)
{
return 0;
}
HashMap<String,ArrayList<String>> mp=new HashMap<String,ArrayList<String>>();
for(int i=0;i<mat.length;i++)
{
String father=mat[i][1];
if(!mp.containsKey(father))
{
mp.put(father,new ArrayList<String>());
}
mp.get(father).put(mat[i][0]);
}
int num=0;
ArrayList<String> ls=mp.get(gf);//Iterate through child of grandfather.
for(String s:ls)
{
int k=mp.containsKey(s)?mp.get(s).size():0;//For each child count the number of children.
num+=k;
}
return num;
}
Use an AVL tree where the nodes have 3 attributes-an int value from the array, the size of the left subtree, the size of the right subtree. Traverse the array from right to left, for each element, insert it into the AVL tree and also compute the number of values greater then this value. Keep a variable that stores the maximum prefix size and update as new values are inserted into the AVL tree.
- divm01986 June 22, 2016//Assumption:When finding a path from start to end you can only move to the right or down.
//Time complexity: O(mn + m+n).Space: O(mn)
public class Point
{
double x;
double y;
public class Point(double r, double c)
{
x=r;
y=c;
}
public int hashCode()
{
return Objects.hash(new Double(x),new Double(y));
}
public boolean equals(Object obj)
{
if(obj==null|| !obj instanceOf(Point))
{
return false;
}
Point p=(Point)obj;
return p.hashCode()==hashCode();
}
}
public ArrayList<Point> findPath(Point top,Point bott,Point[] sensors,double r)
{
if(top==null||bott==null||sensors==null)
{
return null;
}
ArrayList<Point> path=new ArrayList<Point>();
HashMap<Point,Boolean> mp=getBlockedZones(sensors,top,bott,r);
for(doube startX=top.x; startX<=bott.x;startX++)
{
if(dfs(startX,top,bott,mp,path))
{
break;
}
}
return path;
}
private boolean dfs(Point start, Point top,Point bott, HashMap<Point,Boolean> blocked, ArrayList<Point> pth)
{
if(start.y==bott.y)
{
pth.add(start);
return true;
}
if(blocked.containsKey(start) || (start.x<top.x) || (start.x>bott.x) || (start.y>top.y) || (start.y<bott.y))
{
return false;
}
Point next=new Point(start.x+1.0,start.y);
if(dfs(next,top,bott,blocked,pth))
{
pth.add(0,next);
return true;
}
next=new Point(start.x,start.y+1.0);
if(dfs(next,top,bott,blocked,pth))
{
pth.add(0,next);
return true;
}
blocked.put(start,false);
return false;
}
private HashMap<Point,Boolean> getBlockedZones(Point[] sensors,Point t,Point b, double rad)
{
HashMap<Point,Boolean> blocked=new HashMap<Point,Boolean>();
for(Point s:sensors)
{
updateBlocked(blocked,s,t,b,rad);
}
return blocked;
}
private void updateBlocked(HashMap<Point,Boolean> mp, Point sensor,Point top,Point bott, double rad)
{
Deque<Point>q=new LinkedList<Point>();
q.addFirst(sensor);
mp.put(sensor,true);
while(!q.isEmpty())
{
Point top=q.removeFirst();
for(double i=top.x-1.0;i<=top.x+1.0;i++)
{
for(double j=top.y-1.0;j<=top.y+1.0;j++)
{
Point p=new Point(i,j);
if(inBounds(p,sensor,rad,top,bott) && !mp.containsKey(p))
{
mp.put(p,true);
q.addLast(p);
}
}
}
}
}
private boolean inBounds(Point p,Point s, double r, Point top,Point bott){
return(p.x>=top.x && p.x<=bott.x) && (p.y>=top.y && p.y<=bott.y) && dist(p,s)<=r);
}
private double dist(Point f,Point g)
{
double xDist=Math.abs(f.x-g.x);
double yDist=Math.abs(f.y-g.y);
return Math.sqrt(Math.pow(xDist,2) + Math.pow(yDist,2));
}
Worst case time complexity: O(N^2) where N is the size of the String. Space: O(N)
public class Result
{
String min;
String max;
public Result(String mi,String ma)
{
min=mi;
max=ma;
}
}
public Result findMinMax(String str)
{
if(str==null||str.length()<=1)
{
return null;
}
String min=findMin(str);
String max=findMax(str);
if(min==null && max==null)
{
return null;
}
if(min!=null && max==null)
{
return new Result(min,min);
}
if(min==null && max!=null)
{
return new Result(max,max);
}
return new Result(min,max);
}
private String findMin(String s)
{
String min;
int i=0;
int j=1;
while(j<s.length())
{
if(!isVowel(str.charAt(i)) ||(min!=null && (str.charAt(i)-'a')>(min.charAt(0)-'a')))
{
i++;
j++;
}else
{
if(!isVowel(str.charAt(j)))
{
String sub=str.substring(i,j+1);
min=min==null|| sub.compare(min)<0?sub:min;
i=j++;
}else{
if((str.charAt(j)-'a')<= (str.charAt(i)-'a'))
{
i=j++;
}else{
j++;
}
}
}
}
return min;
}
private String findMax(String str)
{
String max;
int i=0;
int j=1;
while(j<str.length())
{
if(!isVowel(str.charAt(i)) ||((max!=null)&&(str.charAt(i)-'a'<max.charAt(0)-'a')))
{
i++;
j++;
}else{
if(!isVowel(str.charAt(j)))//If consonant, keep extending.
{
j++;
}else{
if((str.charAt(j)-'a')>=(str.charAt(i)-'a'))//If vowel is higher then vowel at i, start a new string.
{
i=j++;
}else{
if(!isVowel(str.charAt(j-1)))//If previous is a consonant, update max.
{
String sub=str.substring(i,j);
max=max==null||sub.compare(max)>0?sub:max;
i=j++;
}else
{
j++;
}
}
}
}
}
return max;
}
private boolean isVowel(char c)
{
return(c=='a'||c=='e'||c=='i'||c=='o'||c=='u');
}
public ArrayList<ArrayList<ArrayList<Integer>>> allCombs(int[] arr)
{
if(arr==null||arr.length==0)
{
return null;
}
ArrayList<ArrayList<ArrayList<Integer>>> ls=new ArrayList<ArrayList<ArrayList<Integer>>>();
ArrayList<ArrayList<Integer>> initial=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> l=new ArrayList<Integer>();
l.add(arr[0]);
initial.add(l);
ls.add(l);
for(int i=1;i<arr.length;i++)
{
ArrayList<ArrayList<ArrayList<Integer>>> updated=new ArrayList<ArrayList<ArrayList<Integer>>>();
Iterator<ArrayList<ArrayList<Integer>>> it=ls.iterator();
ArrayList<Integer> elem=new ArrayList<Integer>();
elem.add(arr[i]);
while(it.hasNext())
{
ArrayList<ArrayList<Integer>> curr=it.next();
ArrayList<ArrayList<Integer>> next=new ArrayList<ArrayList<Integer>>();
next.addAll(curr);
next.add(elem);
updated.add(next);
curr.get(curr.size()-1).add(arr[i]);
updated.add(curr);
it.remove();
}
ls=updated;
}
return ls;
}
//Time Complexity: O(2^N) where N is the input array size. Space: O(2^N)
//Assumptions each of the range objects somehow overlaps with first and last.
public class Range{
int left;
int right;
cost;
}
public int minCost(int start,int end, Range[] arr)
{
if(start<end||start<0||end<0||arrr==null||arr.length==0)
{
return -1}
double[][] m=new double[end-start+1][end-start+1];
for(int r=0;r<m.length;r++)
{
for(int c=0;c<m[0].length;c++)
{
m[r][c]=-1.0;
}
}
for(int i=0;i<arr.length;i++)
{
Range entry=arr[i];
int row=start-start;
int col=end-start;
if(entry.left>=start && entry.left<=end)
{
row=entry.left-start;
}
if(entry.right>=start && entry.right<=end)
{
col=entry.right-start;
}
m[row][col]=m[row][col]==-1.0||m[row][col]>entry.cost?entry.cost:m[row][cost];
}
for(int c=m[0].length-1;c>=0;c--)
{
if(m[0][c]==-1.0 ||m[0][c]>m[0][c+1] && m[0][c+1]>0.00))
{
m[0][c]=m[0][c+1];
}
}
for(int r=1;r<m.length;r++)
{
int col=m[0].length-1;
m[r][col]=m[r][col]==(-1.0||(m[r][col]>m[r-1][col] && m[r-1][col]>0.0))?m[r-1][col]:m[r][col];
while(col>=r)
{
m[r][col]=m[r][col]==-1.0||(m[r][col]>m[r][col+1] && m[r][col+1]>0.0)?m[r][col+1]:m[r][col];
m[r][col]=m[r][col]==(-1.0||(m[r][col]>m[r-1][col] && m[r-1][col]>(float)0.0)?m[r-1][col]:m[r][col];
col--;
}
}
double minCost=-1.0;
for(int i=0;i<arr.length;i++)
{
double total=arr[i].cost;
if((end-entry.right)>0 && (m[entry.right+1][last]>0.0))
{
total+= m[entry.right][last];
}
if((entry.left-start)>0 && (m[start][entry.left-1]>0.0))
{
total+=m[start][entry.left-1];
}
minCost=minCost==-1.0||total<minCost?total:minCost;
}
return minCost;
}
/**Time Complexity: O(NM + M^2) where N is the number of range objects and M is the size of the range between first and last.
Space Complexity: O(M^2)**/
/* The brute-force approach involves using recursion without any caching and takes exponential time.
A more optimal approach is using an approach similar to calculating fibonacci (just store the previous 2 results) and compute the current results.
This takes O(N^2) time where N i the length of the string. The space is also O(N^2). */
public ArrayList<String> encodings(String s)
{
if(s==null||s.length()==0||s.charAt(0)=='0')
{
return Collections.<String>emptyList();
}
ArrayList<ArrayList<Integer>> i_2=new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> i_1=new ArrayList<ArrayList<Integer>>();
i_1.add("" + s.charAt(0));
for(int i=1;i<s.length();i++)
{
int d1=s.charAt(i-1)-'0';
int d2=s.charAt(i)-'0';
d1=(d1*10)+d2;
ArrayList<ArrayList<Integer>> tmp=new ArrayList<ArrayList<Integer>>();
//if one digit combination is valid (between 1-26 and not equal to 2 digit combination)
if((d2>=1 && d2<=26) && d1!=d2))
{
tmp.addAll(append(i_2,d2));
}
//if two digit combination is valid (between 1-26 and not equal to 1 digit combinaton)
if((d1>=1 && d1<=26) && d1!=d2))
{
tmp.addAll(append(i_1,d1));
}
i_2=i_1;
i_1=tmp;
}
}
private ArrayList<ArrayList<Integer>> append(ArrayList<ArrayList<Integer>> ls, int d)
{
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> l:ls)
{
ArrayList<Integer> x=new ArrayList<Integer>(l);
x.add(d);
result.add(x);
}
return result;
}
//Time Complexity: O(nLogK) where n is the number of people and K is the number of slices in the smallest pie.
//Space Complexity:O(1)
public int countMaxSlices(int[] pie,int n)throws NullPointerException
{
if(pie==null)
{
throw new NullPointerException();
}
if(pie.length==0||n<=0)
{
return 0;
}
int end=pie[0];
int maxPerPerson=0;//max slices per person overall
int start=1;
//Iterate through the list of slices for each pie and find the pie that has the minimum total slices
for(int i=1;i<pie.length;i++)
{
end=Math.min(end,pie[i]);
}
//Use binary search to find optimal number of slices
while(start<=end)
{
int mid=(start+end)/2;
if(isFeasible(mid,pie,n))//Check if "mid" slices per person is feasible
{
maxPerPerson=mid;
start=mid+1;
}else
{
end=mid-1;
}
}
return maxPerPerson;
}
private boolean isFeasible(int perPerson,int[] pie, int n)
{
//distribute the pie slices in a greedy manner.
int slice=pie[0];//total number of slices in first pie (note this will never be greater than the total slices in the smallest pie)
int p=1;//first person to be served
int idx=0;
while(p<=n)//while there are people to be served
{
slice-=perPerson;//deduct slices from the current pie
p++;//prepare to serve next person
if(slice<perPerson)//if the current pie doesn't have enough slices (it is less than the value in perPerson)
{
idx++;//go to the next pie.
if(idx==pie.length)//if there is no more pies left.
{
break;
}
slice=pie[idx];//select current pie for next batch of slices.
}
}
return p>n;//if this condition is true, then all n people can be served with perPerson slices for each person.
}
O(KN) where K is the number of entries in the input list and N is the number of digits in the longest entry.
public int countGroups(int[] values)
{
if(values==null||values.length==0)
{
return 0;
}
HashMap<Integer,Boolean> mp=new HashMap<Integer,Boolean>();
int groupCount=0;
for(int x:values)
{
int[] digitCounts=countDigits(x);
int key=Arrays.hashCode(digitCounts);
if(!mp.containsKey(key))
{
mp.put(key);
groupCount++;
}
}
return groupCount;
}
private int[] countDigits(int val)
{
int[] counts=new int[10];
if(val==0)
{
counts[0]==1;
return counts;
}
while(val!=0)
{
int rem=val%10;
counts[rem]++;
val/=10;
}
return counts;
}
I would use the following:
public class HeapNode
{
int unit;
int rank;
}
public UnitDetail
{
int queueIdx;
ArrayList<WorkerId> workers;
}
1) HashMap<Integer,UnitDetail> unitWorkers//contains details on each unit (unit number is the key. the value is an object containing the heap node representing that unit along with the list of workers for the unit)
2) Queue<Integer> queue of unit numbers with the most recently queried unit number as the head.
Here's how it will work:
Step 1) If user queries a unit that is not in the map, fetch the workers from the server.
Create a new entry in the hash map for this unit.Otherwise, simply fetch the list corresponding to this key in the hashmap and return the list then proceed to step 2.
Step 2)
For a new entry in the hashmap: If the queue is full, create a new queue with the
new entry's unit number as the head and transfer to it all EXCEPT last element in the existing queue.Update the queueIdx attribute in the hashmap for each transferred unit.
For an existing entry int he hashmap: Take all elements before the queried unit in the queue(refer to queueIdx) and re-insert them into the queue so that they occurr after the queried unit. Update queueIdx values.
Use a similar approach for the Department based Queries.
The department details can also be set up similarly (using a separate max heap and HashMap).
A HashMap and Binary Search Tree. Each hash map entry will have a key which is a hash value (integer) and the corresponding value will be the associated BST node. "Access" operations (Checking if an element exists or getting an existing element) will be O(1). Modification operations (deletion of an existing element, changing its attribute, insertion) will be O(logN) provided that the tree is balanced, otherwise it can take upto O(N) time where N is the number of elements stored.
- divm01986 April 16, 2016//Similar to DFS with some caching. Not exactly sure what the time complexity here is.I think it's something like O(V^2+E). Space complexity is O(V+E).
public class Edge
{
int start;
int end;
char col;
public Edge(int s, int e, char c)
{
start=s;
end=e;
col=c;
}
public int hashCode()
{
return Objects.hash(Integer.valueOf(start),Integer.valueOf(end),Character.valueOf(col));
}
public boolean equals(Object o)
{
if(o==null|| o !instanceof(Edge)))
{
return false;
}
Edge e=(Edge)o;
return e.hashCode()==hashCode();
}
}
public ArrayList<Edge> findTree(ArrayList<Edge>[] adj)
{
if(adj==null||adj.length==0)
{
return Collections.<Edge>emptyList();
}
HashMap<Edge,ArrayList<Edge>> cache=new HashMap<Edge,ArrayList<Edge>>();
for(int i=0;i<adj.length;i++)
{
HashMap<Integer,Edge> visited=new HashMap<Integer,Edge>();
boolean r=find(new Edge(i,i,'-'),visited,adj,cache);
if(r)
{
return makeList(visited);
}
}
return Collections.<Edge>emptyList();
}
private boolean find(Edge curr,HashMap<Integer,Edge> v, ArrayList<Edge>[] adj,HashMap<Edge,ArrayList<Edge>> cache)
{
v.put(curr.end,curr);//Mark the current vertex as visited and store the associated edge.
if(v.size()==adj.length)
{
return true;
}
boolean result=false;
//If a dfs through this edge was already done before, use its results
if(cache.containsKey(curr))
{
ArrayList<Edge> ls=cache.get(curr);
for(Edge x:ls)
{
if(!v.containsKey(x.end))
{
result=find(x,v,adj,cache);
if(result)
{
break;
}
}
}
}
//If a dfs through this edge wasn't done before, recurse
else
{
cache.put(curr,new ArrayList<Edge>());
int vertex=curr.end;
for(Edge x: adj[vertex])
{
if(x.col!=curr.col && !v.containsKey(x.end))
{
cache.get(curr).add(x);
result=find(x,v,adj,cache);
if(result)
{
break;
}
}
}
}
return result;
}
//Assumption:The graph is in the form of an adjacency matrix.
//Time Complexity: O(v+e) where v is the number of vertices and e is the number of edges.
//Space: O(v);
public boolean hasCycle(boolean[][] adj)
{
if(adj==null||adj.length==0)
{
return false;
}
boolean[] visited=new boolean[adj.length];
for(int i=0;i<visited.length;i++)
{
if(!visited[i])
{
boolean hasCycle=checkCycle(i,visited, adj, new HashMap<Integer,Boolean>());
if(hasCycle)
{
return true;
}
}
}
return false;
}
private boolean checkCycle(int p, boolean[] v,boolean[][] m, HashMap<Integer,Boolean> mp)
{
v[p]=true;
mp.put(p,true);
for(int i=0;i<m[p].length;i++)
{
if(m[p][i])
{
if(mp.containsKey(i))
{
return true;
}
if(![v])
{
boolean c=checkCycle(i,v,m,mp);
if(c)
{
return true;
}
}
}
}
return false;
}
//Assumptions: A dictionary in the form of HashMap is given where the keys are the different languages of the characters and the values tell us their lexicographic value.
//Time complexity:O(Min(n,m)) where n and m are the sizes of the strings.Why Min??Because, if one of the strings is smaller then the other we will not assess the excess characters
of the larger string.
public int compare(String s1, String s2, HashMap<String,Integer> mp)throws NullPointerException
{
if(s1==null||s2==null)
{
throw new NullPointerException();
}
int i=1;
int j=1;
while(i<s1.length() && j<s2.length())
{
String str1=s1.substring(i-1,i);
String str2=s2.substring(j-1,j);
if(mp.containsKey(str1) && mp.containsKey(str2))
{
int v=mp.get(str1).intValue();
int w=mp.get(str2).intValue();
if(v==w)
{
i++;
j++;
}else
{
return v-w;
}
}
else if (!mp.containsKey(str1) && !mp.containsKey(str2))
{
str1+=s1.substring(i,i+1);
str2+=s2.substring(j,j+1);
if(!mp.containsKey(str1)||!mp.containsKey(str2))
{
throw new Exception("Invalid character");
}
int v=mp.get(str1).intValue();
int w=mp.get(str2).intValue();
if(v==w)
{
i+=2;
j+=2;
}else{
return v-w;
}
}
else if (!mp.containsKey(str1))
{
str1+=s1.substring(i,i+1);
if(!mp.containsKey(str1))
{
throw new Excepton("invalid character");
}
int v=mp.get(str1);
int w=mp.get(str2);
return v-w;
}else{
str2+=s2.substring(j,j+1);
if(!mp.containsKey(str2))
{
throw new Exception("Invalid character");
}
int v=mp.get(str1);
int w=mp.get(str2);
return v-w;
}
}
//If we get out of the loop and both strings are of different lengths
if(s1.length()!=s2.length())
{
return s1.length()-s2.length();
}
//If we get out of the loop because the last character is not part of a pair (ie i=s1.length() && j==s2.length())
String str1=s1.substring(i-1);
String str2=s2.substring(j-1);
if(!mp.containsKey(str1)||!mp.containsKey(str2))
{
throw new Exception("invalid character");
}
return(mp.get(str1).intValue()-mp.get(str2).intValue());
}
//Similar to KMP. Instead of longest suffix that matches a prefix, find the longest suffix
that is lexicographically greater than a prefix.
Time complexity: O(N). Space:O(1).
public String longestSubstring(String str)throws NullPointerException
{
if(str==null)
{
throw new NullPointerException();
}
if(str.length)==0)
{
return "";
}
//Variation of KMP algorithm.Instead of finding longest suffix that matches a prefix. Find the longest suffix that is lexicographically greater then a prefix
int start=-1;
int i=0;
int j=1;
while(j<str.length())
{
//If lexicographically less, move on to the next character
int diff=str.charAt(j)-str.charAt(i);
if(diff>=0)
{
j++;
i++;
if(diff>0)//If current char is lexicographically greater then an earlier character.
{
//j indicates length of this string's prefix, use it to determine start
start=j-i+1;
break;
}
}else
{
j++;
}
}
return start!=-1? str.substring(start):"";
}
//Time complexity: O(V+E). Space complexity: O(V+E)
//I assume there are several other ways of doing this as well.
public class Node
{
int value;
ArrayList<Node> connect;
}
public ArrayList<ArrayList<Integer>> groups(Node n)
{
HashMap<Integer,Boolean> connected=new HashMap<Integer,Boolean>();
//Hash map with keys for all nodes connected to input node.
for(Node x: n.connect)
{
connected.put(x.value,false);
}
ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
for(Node x:n.connect)
{
ArrayList<Integer> connectedNodes=checkConnect(x,connected);
results.add(connectedNodes);
}
return connectedNodes;
}
private ArrayList<Integer> checkConnect(Node x,HashMap<Integer,Boolean> mp)
{
ArrayList<Integer> r=new ArrayList<Integer>();
r.add(x.value);
mp.put(x.value,true);
if(x.connect!=null)
{
for(Node g:x.connect)
{
if(mp.containsKey(g.value))
{
boolean visited=mp.get(g.value);//Check if this vertex has already been visited
if(!visited)
{
r.add(g.value);
}
}
}
}
return r;
}
//Assumptions: Input is a 2D Matrix of integers where 1 represents a coin being present and 0 represents no coin
//Approach: Dynamic programming with recursion and caching.
//Time Complexity:O(NM)
//Space complexity:O(NM);
public int maxCoins(int[][] m)
{
int[][][] cache=new int[m.length][m[0].length][1];
//Initialize cache to contain -1 to indicate that a cell has not been visited yet.
for(int row=0;row<m.length;row++)
{
for(int col=0;col<m[0].length;col++)
{
cache[row][col][0]=-1;
}
}
return getMax(m,0,0,cache);
}
private int getMax(int[][]m, int row, int col, int[][][] cache)
{
if(row==m.length && col==m[0].length)
{
return m[0][0];
}
if(cache[row][col][0]!=-1)
{
return cache[row][col][0];
}
int maxCoin=0;
for(int dx=1;row+dx<m.length;dx++)
{
for(int dy=1;col+dy<m[0].length;dy++)
{
maxCoin=Math.max(maxCoin,getMax(m,row+dx,col+dy,cache)));
}
}
maxCoin+=m[row][col];
cache[row][col][0]=maxCoin;
return maxCoin;
}
public int minDistance(String[] wrds, String[] arr)
{
if(wrds.length!=3 || arr==null||arr.length<3)
{
return -1;
}
int idxOne=-1;
int idxTwo=-1;
int idxThree=-1
HashMap<String,Boolean> w=new HashMap<String,Boolean>();
for(int i=0;i<wrds.length;i++)
{
w.put(wrds[i],i);
}
int min=-1;
for(int i=0;i<wrds.length;i++)
{
if(w.containsKey(wrds[i]))
{
int x=w.get(wrds[i]);
if(x==0)
{
idxOne=i;
}else if (x==1)
{
idxTwo=i;
}else{
idxThree=i;
}
}
if(idxOne!=-1 && idxTwo!=-1 && idxThree!=-1)
{
int diff=Math.max(idxOne,Math.max(idxTwo,IdxThree))-Math.min(idxOne,IdxTwo,IdxThree)
min=min==-1?diff:Math.min(min,diff);
}
}
return min;
}
//O(N) time, O(N) space. Works for the [4,-1,7] case giving a result of 8 and for the case //mentioned in the post giving a result of 16.
public class MaxDiffSvc
{
public static int findMaxDiff(int[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
int maxDiff=Integer.MIN_VALUE();
int[][] cache=new int[3][arr.length];
cache[0][0]=arr[0];//Max sum subarray seen so far
cache[1][0]=arr[0];//Min sum subarray seen so far
cache[2][0]=arr[0];//Cumulative sum seen so far
int minCumSum=0;//Index of minimum cumulative sum seen so far.
int maxCumSum=0;//Index of Maximum cumulative sum seen so far.
for(int i=1;i<arr.length;i++)
{
cache[2][i]=cache[2][i-1]+arr[i];
int c=cache[2][i];
int currMax=c-cache[2][minCumSum];//Maximum sum subarray with the element at i.
int currMin=c-cache[2][maxCumSum];//Minimum sum subarray with the element at i
//Take the current maximum and subtract the minimum sum subarray upto the index containing the minimum cumulative sum(update maxDiff if needed)
maxDiff=Math.max(maxDiff,Math.abs(currMax-cache[1][minCumSum]));
//Take the current minimum and subtract the maximum sum subarray upto the index containing the maximum cumulative sum(update maxDiff if needd)
maxDiff=Math.max(maxDiff,Math.abs(cache[0][maxCumSum]-currMin));
//Update the maximum and minimum sum subarray known to this point
cache[0][i]=Math.max(cache[0][i-1],currMax);
cache[1][i]=Math.min(cache[1][i-1],currMin);
//Update the maximum and minimum cumulative sums known to this point
minCumSum=c<cache[2][minCumSum]?i:minCumSum;
maxCumSum=c>cache[2][maxCumSum]?i:maxCumSum;
}
return maxDiff;
}
}
Variation of Quicksort. Create sorted segments out of every 1 billion values (we will have 1000 segments) and write these segments back to the file. Create an array of size 1000 with numbers from 0 to 999 (each of these numbers is an index for a sorted segment). Randomly select a segment ( say index 77) and designate it's minimum value as a pivot. Partition segments around this pivot -compare the remaining segments' maximum values to the pivot value. If the segment's maximum is less than the pivot then move that segment's index value before 77 in the array of values. After partitioning, you will know the position of the pivot value in the overall sorted array (ie. say the pivot is the 9856 value). Since 9856 is less than 500 billion (median value position in a Terabyte size set of values), repeat this randomized quicksort approach to segments whose index values that appear to the right of segment 77. Keep doing this until you find the segment containing the 500 billionth value then, once the correct segment is found, apply binary search to find the value which is the median.
- divm01986 March 21, 2016/*Works for main and follow-up
Time complexity(let n=rows m=columns)
Sorting rows-Time: O(nmlogm) Space: O(m)
Sorting columns-Time: O(mnlogn) Space: O(n)
Removing Row repeats-Time: O(nm) Space:O(1)
Removing Column repeats-Time: O(nm) Space: O(1) */
public class Point
{
int row;
int col;
public Point(int r,int c)
{
row=r;
col=c;
}
}
public int[][] sort(int[][] m)throws NullPointerException
{
if(m==null)
{
throw new NullPointerException();
}
if(m.length==1 && m[0].length==1)
{
return m;
}
sortRows(m);
sortColumns(m);
fixRepeatsRow(m);
fixRepeatsCol(m);
return m;
}
private void sortRows(int[][] m)
{
for(int i=0;i<m.length;i++)
{
Arrays.sort(m[i]);
}
}
private void sortColumns(int[][]m)
{
MinHeap<Integer> mh;
for(int i=0;i<m[0].length;i++)
{
mh==new MinHeap<Integer>(m.length);
for(int r=0;r<m.length;r++)
{
mh.insert(m[r][i]);
}
int rowIdx=0;
while(!mh.isEmpty())
{
m[rowIdx++][i]==mh.extractMin();
}
}
}
private void fixRepeatsRow(int[][] m)
{
for(int r=0;r<m.length;r++)
{
for(int c=1;c<m[0].length;c++)
{
if(m[r][c]==m[r][c-1])
{
Point p=findClosest(r+1,c-2,r-1,c+1,m);
if(m[p.row][p.col]<m[r][c])
{
swap(r,c-1,p.row,p.col,m);
}else
{
swap(r,c,p.row,p.col,m);
}
}
}
}
}
private void fixRepeatsCol(int[][] m)
{
for(int c=0;c<m[0].length;c++)
{
for(int r=1;r<m.length;r++)
{
if(m[r][c]==m[r-1][c])
{
Point p=findClosest(r-2,c+1,r+1,c-1,m);
if(m[p.row][p.col]<m[r][c])
{
swap(p.row,p.col,r-1,c,m);
}else{
swap(p.row,p.col,r,c,m);
}
}
}
}
}
private void swap(int r1,int c1, int r2,int c2,int[][] m)
{
int tmp=m[r1][c1];
m[r1][c1]=m[r2][c2];
m[r2][c2]=tmp;
}
private Point findClosest(int r1,int c1,int r2,int c2,int[][] m)
{
if((r1>=0 && r1<m.length) && (c1>=0 && c1<m[0].length))
{
return new Point(r1,c1);
}
if((r2>=0 && r2<m.length) && (c2>=0 && c2<m[0].length))
{
return new Point(r2,c2);
}
return null;
}
//O(N) time complexity, O(N) space complexity where N is the size of the input sequence.
public int[] createSeq(String seq)throws NullPointerException
{
if(seq==null)
{
throw new NullPointerException();
}
if(seq.length()==0||seq.trim().equals(""))
{
System.out.println("Input should not be empty or consist of blank space");
return null;
}
int[] arr=seq.length+1;
for(int i=arr.length;i>=1;i--)
{
arr[arr.length-i]=i;
}
int j=arr.length-1;
for(int i=seq.length-1;i>=0;i--)
{
if(seq.charAt(i)=='I')
{
swap(j,j-1,arr);
}
j--;
}
}
private void swap(int i, int j, int[] a)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
//Worst case: O(N) time, O(N) space
public int maxOnes(int[] arr,int k)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
if(arr.length<k)
{
return 0;
}
int i=0;
int maxLen=Integer.MIN_VALUE();
int zeros=0;
int[] results=new int[arr.length];
results[0]=1;
int s=0;
for(int j=1;j<results.length;j++)
{
results[j]=1+results[j-1];
if(arr[j]==0)
{
zeros++;
}
while(zeros>k)
{
if(arr[i]==0)
{
zeros--;
}
i++
s=results[i-1];
}
maxLen=Math.max(maxLen,results[j]-s);
j++;
}
return maxLen;
}
//Using LinkedLists with worst case time complexity of O(N+M) and space complexity //O(N+M)
public class IntervalOperations
{
public static Interval mergeIntervals(Interval a,Interval b)throws NullPointerException{
if(a==null||b==null)
{
throw new NullPointerException
}
Interval i=a;
Interval prevA=a;
Interval j=b;
Interval prevB=b;
Interval result;
Interval c;
if(a.start<=b.start)
{
result=i;
c=i;
prevA=i;
i=i.next;
}else
{
result=j;
c=j;
prevB=j;
j=j.next;
}
c.next=null;
while(i!=null && j!=null){
if(i.start<=j.start)
{
if(isOverlap(c,i))
{
c.start=Math.min(c.start,i.start);
c.end=Math.max(c.end,i.end);
prevA=i;
i=i.next;
}else{
prevA.next=null;
c.next=i;
c=c.next;
i=i.next;
c.next=null;
}
}else{
if(isOverlap(c,j))
{
c.start=Math.min(c.start,j.start);
c.end=Math.max(c.end,j.max);
prevB=j;
j=j.next;
}
prevB.next=null;
c.next=j;
c=c.next;
j=j.next;
c.next=null;
}
}
while(j!=null)
{
if(isOverlap(c,j))
{
c.start=Math.min(c.start,j.start);
c.end=Math.max(c.end,j.end);
prevB=j;
j=j.next;
}else{
prevB.next=null;
c.next=j;
c=c.next;
j=j.next;
c.next=null;
}
}
while(i!=null)
{
if(isOverlap(c,i))
{
c.start=Math.min(c.start,i.start);
c.end=Math.max(c.end,i.end);
prevA=i;
i=i.next;
}else{
prevA.next=null;
c.next=i;
c=c.next;
i=i.next;
c.next=null;
}
}
return result;
}
private static boolean isOverlap(Interval x,Interval y)
{
if(x.end<y.start||y.end<x.start)
{
return false;
}
return true;
}
public class Interval{
int start;
int end;
Interval next;
public Interal(int s,int e)
{
start=s;
end=e;
}
}
public static void printInterval(Interval a)
{
while(a!=null)
{
System.out.print("start: " + a.start + ", end: " + a.end + "-")
a=a.next;
}
}
public static void Main(String[] args)
{
Interval i=new Interval(3,10);
Interval v=i;
v.next=new Interval(12,15);
v=v.next;
v.next=new Interval(21,25);
Interval j=new Interval(6,10);
v=j;
v.next=new Node(11,18);
Interval result=IntervalOperations.mergeIntervals(i,j);
IntervalOperations.printInterval(i);
IntervalOperations.printInteval(j);
IntervalOperations.printInterval(result);
}
}
// Determine if a sequence of non-negative integers is arithmetic.
public class Arithmetic
{
public static boolean isArithmetic(int[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
if(arr.length==1)
{
return true;
}
int min=arr[0];
int max=arr[0];
for(int i=0;i<arr.length;i++)
{
min=Math.min(min,arr[i]);
max=Math.max(max,arr[i]);
}
int diff=(max-min)/(arr.length-1)
int expSum=0
int j=1;
for(int i=min;i<=max && j<=arr.length;i+=diff)
{
expSum+=i;
j++;
}
int actSum=0;
for(int i=0;i<arr.length;i++)
{
actSum+=arr[i];
}
return actSum==expSum;
}
public static void main(String[] args)
{
int[] arr={3,3};
System.out.println("sample input: " + Arrays.toString(arr));
System.out.println("result: " + Arithmetic.isArithmetic(arr));
arr={1,2,3,4,5};
System.out.println("sample input: " + Arrays.toString(arr));
System.out.println("result: " + Arithmetic.isArithmetic(arr));
arr={1,2,23,4,5};
System.out.println("sample input: " + Arrays.toString(arr));
System.out.println("result: " + Arithmetic.isArithmetic(arr));
}
}
//O(n) time, where n is the number of elements.
//I spent a little more time on this problem and got a more efficient solution
public int maxGain(int[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
int[] tmp=new int[arr.length+2];
tmp[0]=1;//Used for computing value after bursting arr[0]
tmp[tmp.length-1]=1;//Used for computing value of bursting arr[arr.length-1]
Arrays.copy(arr,tmp,0,1,arr.length);
arr=tmp;
int[] results=new int[4];//results[0]--max gain from popping balloon at index i, results[1]--max gain from not popping balloon at index i
results[2]=1;//updated balloon if balloon at index i is popped
results[3]=1;//update balloon if balloon at index i is not popped
for(int i=1;i<arr.length-1;i++)
{
int i_1_pop=results[0];
int pop_i_pop_i_1=(arr[i]*arr[i+1]*results[2])+results[0]//Max gain from popping baloon at index i and balloon at index i_1
int pop_i_not_i_1=(arr[i]*arr[i+1]*results[3])+results[1]//Max gain from popping baloon at index i and not popping balloon at i_1
//Max gain if balloon i is popped.
if(pop_i_pop_i_1>pop_i_not_i_1)
{
results[0]=pop_i_pop_i_1;
}
else
{
results[0]=pop_i_not_i_1;
results[2]=results[3];//If i_1 was not popped then i will contain the same value as i_1
}
//Max gain if balloon i is not popped.
results[1]=Math.max(i_1_pop,resultsp[1]);//Maximum of popping or not popping balloon i_1
results[3]=arr[i];
}
return Math.max(results[0],results[1]);
}
//Time complexity O(N) space complexity O(N) where N is the size of the input array
public int countNdigitValues(int n)
{
if(n<=1)
{
return 0;
}
int[] ends=new int[10];//store cumulative counts on the number of 2 digit values that end with 0-i(where i>=0 && i<=9)
int[] begins=new int[10];//store cumulative counts on the number of 2 digit values that begin with 0-9 (where i>=0 && i<=9)
for(int i=0;i<ends.length;i++)
{
int digits=countDigitsLess(i)+countDigitsGreater(i);
ends[i]=ends[i-1]+digits;
begins[i]=begins[i-1]+digits;
}
for(int i=3;i<=n;i++)
{
int[] endsUpdate=new int[10];//stores how many i digit values end with each digit using counts for i-1 digits
int[] beginsUpdate=new int[10];//stores how many i digit values begin with each digit using counts for i-1 digits
for(int j=0;j<9;j++)
{
if(j+4<=9)
{
endsUpdate[j]=ends[9]+ends[j+4-1];
beginsUpdate[j]=begins[9]+begins[j+4-1];
}
if(j-4>=0)
{
endsUpdate[j]+=ends[j-4];
beginsUpdate[j]+=begins[j-4];
}
}
ends=endsUpdate;
begins=beginsUpdate;
}
return ends[ends.length-1]+begins[begins.length-1];
}
//Time complexity is O(N), space is O(1)
//Count the number of digits 4 or more units less than k.
private int countDigitsLess(int k)
{
if(k>=4)
{
return(k-4+1);
}
return 0;
}
//Count the number of digits 4 or more units greater then k.
private int countDigitsGreater(int k)
{
if(k<=5)
{
return(9-(k+4)+1)
}
return 0;
}
public int findRepN4(int[] arr)
{
if(arr==null)
{
throw new NullPointerException();
}
int mid=(arr.length-1)/2;
int idx=-1;
idx=getRep(0,mid,arr);
if(arr.length%2==0)
{
return(idx!=-1)?arr[idx]:arr[checkSub(mid+1,end,arr)];
}
return arr[checkSub(mid,end,arr)];
}
private int checkSub(int start,int end,int[] arr)
{
int mid=end+start/2;
if(end-start+1%2==0)
{
if(arr[mid]==arr[start])
{
return start;
}
return(arr[end]==arr[mid+1]?end:-1);
}
return(arr[mid]==arr[start]||arr[end]==arr[mid])?mid:-1;
}
public int findMaxCoins(int[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
return maxGain(1,0,arr.length-1,1,arr);
}
private int maxGain(int left, int start,int end, int right, int[] arr)
{
if(s>e)
{
return 0;
}
if(s==e)
{
return arr[s];
}
//result of bursting the left most balloon
int leftEnd=(arr[start]*arr[start+1]*left) + maxGain(left,start+1,end,right,arr);
//result of bursting the right most balloon
int rightEnd=(arr[end]*arr[end-1]*right)+maxGain(left,start,end-1,right,arr);
int midMax=0//result of bursting any balloon other then left most and right most balloons
for(int i=start+1;i<end;i++)
{
int l=maxGain(left,start,i-1,arr[i+1],arr);
int r=maxGain(arr[i-1],i+1,end,right,arr);
midMax=Math.max(midMax,l+r+(arr[i]*arr[i-1]*arr[i+1]));
}
return Math.max(midMax,Math.max(leftEnd,rightEnd));
}
//Time Complexity: Exponential O(2^N). Space complexity: O(N).
**Forgot just 2 lines see below:
private boolean checkNodeValues(ArrayList<Integer> ls, int start, int treeSize)
{
int leftIdx=start;
int leftEnd=start+treeSize;
int rightIdx=leftEnd;
while(leftIdx<leftEnd)
{
if(!ls.get(leftIdx).equals(ls.get(rightIdx)))
{
return false;
}
leftIdx++;//Missing line 1
rightIdx++//Missing line 2
}
return true;
}
- 30
RepDiscover the cheapest packers and movers in Gurgaon at best price with smooth and hassle free relocation. We provide truck ...
- 0
Repjacksonbetty625, Accountant at 247quickbookshelp
My work is specialized help, regardless of whether on the telephone, face to face, or distantly, identified with PC frameworks ...
- 10
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 ...
- 0
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 ...
- 0
RepAmmoBoard, Employee at A9
The best online ammo shop to buy ammunition for your rifles, handguns & shotguns from top brands you like.
- 0
RepGet powerful wazifa to know who did black magic. Guru Ji is the master of black magic totke, kala jadu ...
Could you plz clarify what is meant by merging two objects that have similar id? Is it adding their weights or just including one of the multiple entries in the final entry.
- divm01986 July 28, 2016