challapallirahul
BAN USERMy Solution :
public static List<List<String>> groupAnagrams(String[] words) {
List<List<String>> result = new ArrayList<List<String>>();
Pair[] pairs = new Pair[words.length];
for (int i=0; i<words.length; i++) {
pairs[i] = new Pair(words[i]);
}
Arrays.sort(pairs);
List<String> cur = new ArrayList<String>();
cur.add(pairs[0].a);
result.add(cur);
for (int i=1; i<pairs.length; i++) {
if (pairs[i].b.equals(pairs[i-1].b)) {
cur.add(pairs[i].a);
} else {
cur = new ArrayList<String>();
cur.add(pairs[i].a);
result.add(cur);
}
}
return result;
}
public static class Pair implements Comparable<Pair>{
String a;
String b;
public Pair(String str) {
a = str;
StringBuffer sb = new StringBuffer();
char[] strArr = str.toLowerCase().toCharArray();
Arrays.sort(strArr);
str = new String(strArr);
sb.append(str.charAt(0));
for (int i=1; i<str.length(); i++) {
char cur = str.charAt(i);
if (cur == str.charAt(i-1)) {
continue;
} else {
sb.append(cur);
}
}
b = sb.toString();
}
public int compareTo(Pair p) {
return this.b.compareTo(p.b);
}
}
We can solve this using a 2 pointer approach
1. Maintain a sliding window using 'left' and 'right' variables
2. If the sliding window contains k distinct characters increment the right pointer. See if the substring in the window is the maximum seen till now
3. If the sliding window contains more than k distinct characters increment the left window
public static String longest(String str, int k) {
int left = 0;
int right = 0;
String max = "";
// maintain the latest position of each distinct element
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
while (right <str.length()) {
if (map.size() > k) {
// process the left element
map.put(str.charAt(left), map.get(str.charAt(left))-1);
if (map.get(str.charAt(left)) == 0) {
map.remove(str.charAt(left));
}
left++;
} else {
// process the right element
if (map.containsKey(str.charAt(right))) {
map.put(str.charAt(right), map.get(str.charAt(right)+1));
if (right+1-left > max.length()) max = str.substring(left, right+1);
} else {
map.put(str.charAt(right), 1);
}
right++;
}
}
return max;
}
Check whether the graph is bipartite. A simple solution using dfs. (1 and -1 are used for colors)
public static class Graph {
int n;
List<Integer>[] adjList;
int[] colors;
public Graph(int n) {
this.n = n;
adjList = (ArrayList<Integer>[])new ArrayList[n];
colors = new int[n];
for (int i=0; i<n; i++) {
adjList[i] = new ArrayList<Integer>();
}
}
public void addEdge(int u, int v) {
adjList[u].add(v);
adjList[v].add(u);
}
public boolean isGroupingPossible(int root, int color) {
if (colors[root] == 0) colors[root] = color;
else if (colors[root]!=color) {
return false;
} else {
return true;
}
for (Integer child : adjList[root]) {
if (!isGroupingPossible(child, color*-1)) return false;
}
return true;
}
}
This question seems in-complete. Otherwise wouldn't the last element of the pre-order traversal be a leaf node? Am I missing anything?
If the intent was to find a leaf node in the left sub-tree then we can follow the below steps
1. The root is the first element
2. Find the first value, say max, which is greater than root in the pre-order traversal. We can use binary search for this. Now the value before the max in the pre-order traversal is a leaf node.
1. Consider all intervals which start before the target start time
2. Among those pick the interval with max end time
3. Update the target start time to the previous max end time and repeat
public static int minimumMerge(Interval[] intervals, Interval target) {
int result = 0;
Arrays.sort(intervals);
int targetStart = target.start;
int maxEndtime = Integer.MIN_VALUE;
int mergedIntervals = 0;
int i=0;
while (i < intervals.length) {
if (intervals[i].start <= targetStart) {
maxEndtime = Math.max(maxEndtime, intervals[i].end);
i++;
} else {
targetStart = maxEndtime+1;
mergedIntervals++;
}
}
if (maxEndtime >= target.end) return ++mergedIntervals;
return 0;
}
public static class Interval implements Comparable<Interval>{
int start;
int end;
Interval() { start = 0; end = 0; }
Interval(int s, int e) { start = s; end = e; }
public int compareTo(Interval i) {
return start-i.start;
}
}
Thanks @kryzoo.m for pointing out flaws in my execution. Below is the revised approach
1. Find local minimums and local maximums. Each min and max will form an interval
2. See if you can merge current interval with the previous one, otherwise the previous interval can used as a min and max of your transaction
public static int maxProfit(int[] prices, int fee) {
int maxProfit = 0;
List<Interval> intervals = new ArrayList<Interval>();
int i=0;
while (i<prices.length-1) {
// find the local minima
while (i<prices.length-1 && prices[i]>=prices[i+1])
i++;
if (i==prices.length-1) break;
int min = prices[i];
// find the local maxima
while (i<prices.length-1 && prices[i] <= prices[i+1])
i++;
intervals.add(new Interval(min, prices[i]));
}
if (intervals.size()==0) return 0;
Interval merge=null;
for (int j=0; j<intervals.size(); j++) {
if (merge == null) {
merge = intervals.get(j);
continue;
}
// check if current interval can be merged with the merge interval
if (merge.max - intervals.get(j).min <= fee && intervals.get(j).max > merge.max) {
merge.max = intervals.get(j).max;
} else {
// consume the interval
maxProfit+=merge.max-merge.min-fee;
merge = intervals.get(j);
}
}
if (merge!=null) maxProfit+=merge.max-merge.min-fee;
return maxProfit;
}
public static class Interval {
int min;
int max;
public Interval (int s, int e) {
min = s;
max = e;
}
}
Imagine plotting the values on a coordinate axis. There will several local minimums and local maximums. You can buy at a local minimum and sell at a local maximum if the difference is greater than the fee
public static int maxProfit(int[] prices, int fee) {
int maxProfit = 0;
int i = 1;
int currentMin = Integer.MAX_VALUE;
while (i < prices.length) {
// find the local minimum
while (i<prices.length && prices[i] <= prices[i-1]) {
i++;
}
// now buy the stock
if (currentMin==Integer.MAX_VALUE) currentMin = prices[i-1];
// find the local maximum
while (i<prices.length && prices[i] >= prices[i-1]) {
i++;
}
// now sell the stock
if (prices[i-1] - currentMin > fee) {
maxProfit+=prices[i-1]-currentMin-fee;
currentMin = Integer.MAX_VALUE;
}
}
Like the others have mentioned, the greedy approach does not work. Below is a dynamic programming based approach.
1. Lets say we have a rectangle with dimensions i and j. We cut a square of size k*k.
2. After the above k sized square is removed, we can have the below 2 options
a) Rectangle (i-k,k) & Rectangle (i, j-k)
b) Or Rectangle(i-k,j) & Rectangle(k, j-k)
3. Take the min of (a) and (b)
Repeat the process for all values of k. Below is an iterative implementation
public static int minSquares(int x, int y) {
int[][] partial_solutions = new int[x+1][y+1];
for (int i=0; i<=x; i++) {
for (int j=0; j<=y; j++) {
if (i==0 || j==0) {
partial_solutions[i][j] = 0;
continue;
}
if (i==j) {
partial_solutions[i][j] = 1;
continue;
}
if (x%y == 0) {
partial_solutions[x][y] = x/y;
continue;
}
if (y%x == 0) {
partial_solutions[x][y] = y/x;
continue;
}
int smaller = Math.min(i, j);
int min = Integer.MAX_VALUE;
for (int k=1; k<=smaller; k++) {
int minK = Math.min(partial_solutions[i-k][j] + partial_solutions[k][j-k], partial_solutions[i][j-k]+partial_solutions[i-k][k]);
min = Math.min(min, minK);
}
partial_solutions[i][j] = 1+min;
}
}
return partial_solutions[x][y];
}
This is essentially the same as the coin change problem. Below is a little different approach which works if the required number 'n' is reasonably small. Time Complexity is O(n)
- challapallirahul March 22, 2017