blckembr
BAN USER@Edd, so did the interviewer had in mind a distributed system design that handles very large number of updates, terrabytes of storage and very frequent queries, with lots of "players". And the system should be fault tolerant, etc?
Or is it just single machine algo/data structure question?
@Iuri Sitinschi Isn't the semantics of MRU a little different from what is required here?
It will hold the most recently added strings at the top, so the most frequent can get masked by new less frequent strings. For example, let's say we see string "aaa" 100 times, but then we get 1000 new strings, the top 100 of MRU cache are all strings that appeared only 1 time, masking the string that was seen 100 times.
Maybe you intended to update the cache based on frequency of the word and not when that appears, but then you need to track frequencies. Moreover, what data structures do you intend to use for the cache?
All in all, you solution needs a little more elaborate explanation, if you do not mind.
Are we looking for 3 elements (not necessarily consecutive) in this row of balloons that yield maximum product? So that we can burst some balloons in between them and then burst the middle of those 3 and get the maximum number of coins from single burst?
Or is the goal to find 3 consecutive elements that yield max product and we burst only once?
Or.. Is it about coming up with a strategy to burst all balloons so that accumulated number of coins is maximum?
If I understand correctly, Bitmap class is supposed to provide a diff(Btimap other) method that should output the diff?
Also, is the goal to minimize number of changed/removed/added bits in the diff?
For example, given two bitmaps {0,1,0,1,0,1} and {1,0,1,0,1,0}, should the diff be <Added: {0}, Removed: {5}> or <Changed {0-5}>?
Couldn't this be done just by traversing rows keeping index of max row at every iteration, without conversion to decimal, just by comparing?
public static int getMaxDecialIndex(int[][] matrix) {
if (matrix.length == 0) return -1;
int maxRowIdx = 0;
for (int r = 1; r<matrix.length; r++) {
int[] currRow = matrix[r];
if (compare(matrix[maxRowIdx], currRow) < 0 ) {
maxRowIdx = r;
}
}
return maxRowIdx;
}
private static int compare(int[] first, int[] second) {
for (int c = 0; c<first.length; c++) {
if (first[c] > second[c]) {
return 1;
} else if (first[c] < second[c]){
return -1;
}
}
return 0;
}
Complexity is O(m*n)
- blckembr November 24, 2015@Pratap Das, you are correct, but... There are variations on quickselect that avoid O(N^2) worst case, simplest is randomization, which still suffers from worst N^2 for specially crafted input, using median-of-medians for pivot selection, which also still vulnerable to certain inputs, and finaly Introselect, which has the same basic idea as Introsort and switches to known O(n) worst case (such as median-of-medians) in case partitioning is not effective for some input. All of that is worth at least discussing during interview, because coding might be too much in the time given.
- blckembr November 21, 2015@hellohello
Does your function return true if str1 is "bigger" than str2? such as '9' is bigger than '918'? So '9' should be selected first and then '918' appended to it?
Could you please run your function on str1='81' and str2='811' and then swap str1 and str2? I think it will return 'true' in both cases, unless I misunderstood your code. Hard to understand because indentation is gone. Could you please enclose it in {{ { and } }} and repost?
In Java, iterative, but following same recursive logic as by @kyduke
public class MatchsticksSum {
public static int getSum(int[] boxes, int F, int K) {
int[][][] memo = new int[K+1][F][boxes.length+1];
for (int i = 0; i<=boxes.length; i++) {
for (int k = 0; k<=K; k++) {
for (int f = 0; f < F; f++) {
if (i<k) {
memo[k][f][i] = Integer.MAX_VALUE;
continue;
}
if (k==0) {
if (f==0) {
memo[k][f][i] = 0;
} else {
memo[k][f][i] = Integer.MAX_VALUE;
}
continue;
}
if (k==1 && i==1) {
if (boxes[i-1]%F==f) {
memo[k][f][i] = boxes[i-1];
} else {
memo[k][f][i] = Integer.MAX_VALUE;
}
continue;
}
int remIdx = (f>=boxes[i-1] % F)?(f-boxes[i-1] % F):(F+(f - boxes[i-1]%F));
if (memo[k-1][remIdx][i-1] != Integer.MAX_VALUE) {
memo[k][f][i] = Math.min(memo[k-1][remIdx][i-1] + boxes[i-1]
,memo[k][f][i-1]);
} else {
memo[k][f][i] = memo[k][f][i-1];
}
}
}
}
int res = memo[K][0][boxes.length];
return res==Integer.MAX_VALUE?-1:res;
}
}
Number of nodes on left and right sides of root are not always equal even in a Balanced BST, such as Red-Black Tree. The only thing that is promised is that height of left and right do not differ by more than some small number. The best in this is an AVL tree where height do not differ by more than 1.
I think the interviewer had this in mind:
- Build a self balancing BST
- when inserting a new node, increment left and right count on each parent (depending on where the new node goes)
Now we have count of left side and right side on the root. if they are equal, root is median, if they are not, can go either back or forth in inorder traversal starting from root the required number of steps which can be calculated from how many nodes are on left and right sides of root.
Can use quickselect to quickly find median (in O(n)).
So if length is odd, one run of quickselect (with k = middle) is enough.
Now, if the problem requires average of two middle elements in case length is even , can run quick select once and then find max on the left half of the array, which is now pivoted around the right number of the two in the middle.
If it is ok to output left of the two middle numbers, than this is again just a single quickselect.
Also, there are multiple variations of quick select that suffers from worst case O(n^2) same as quicksort, which are probably worth discussing, some variants use random to select pivot, median-of-medians is commonly known good choice, or even Introselect variant that falls back to Heapsort in case partitioning is not effective. All these help to reduce worst case of O(n^2).
So assuming some variation of quickselect is used that has worst case O(N), total complexity is O(N) for quickselect + O(N) for finding left of the two middle elements.
Using the simplest implementation of quickselect:
public static double findMedian(int[] input) {
Random rand = new Random(System.currentTimeMillis());
if (input==null || input.length<=0) throw new IllegalArgumentException();
if (input.length%2==0) {
int left = qselect(input, 0, input.length-1, input.length/2, rand);
int right = getMax(input, 0, input.length/2-1);
return (left + right)/2.0;
} else {
return qselect(input, 0, input.length-1, input.length/2, rand);
}
}
private static int getMax(int[] input, int i, int j) {
int max = input[i++];
while (i <= j) {
if (input[i]>max) {
max = input[i];
i++;
}
}
return max;
}
private static int qselect(int[] input, int i, int j, int k, Random rand) {
if (j<=i) {
return input[j];
}
int p = rand.nextInt(j-i+1) + i;
int pIdx = partition(input, i, j, p);
if (pIdx == k) {
return input[pIdx];
} else if (pIdx < k) {
return qselect(input, pIdx+1, j, k, rand);
} else {
return qselect(input, i, pIdx-1, k, rand);
}
}
private static int partition(int[] input, int start, int end, int pIdx) {
int pivot = input[pIdx];
int pivIdx = start;
swap(input, pIdx, end);
for (int i=start; i <= end-1; i++) {
if (input[i] < pivot) {
swap(input, i, pivIdx);
pivIdx++;
}
}
swap(input, pivIdx, end);
return pivIdx;
}
Almost same as @sameer's, in java, no recursion
public static int getMaxNumber(int[] A, int[] B, int K) {
//trivial cases are when K=0, when nothing used from first array, when nothing used from second array
int[][][] memo = new int[K+1][A.length+1][B.length+1];
for (int i = 0; i <= K; i++) {
for (int a = 0; a<= A.length; a++) {
for (int b = 0; b <= B.length; b++) {
if (i==0) {
memo[i][a][b] = 0;
continue;
}
if (a == 0 && b == 0) {
memo[i][a][b] = 0;
continue;
}
if (a == 0) {
memo[i][a][b] = Math.max(B[b-1] + memo[i-1][0][b-1]*10, memo[i][0][b-1]);
}
else if (b == 0) {
memo[i][a][b] = Math.max(A[a-1] + memo[i-1][a-1][0]*10, memo[i][a-1][0]);
} else {
memo[i][a][b] = Math.max(A[a-1] + memo[i-1][a-1][b]*10,
Math.max(B[b-1] + memo[i-1][a][b-1]*10
,memo[i][a-1][b-1]));
}
}
}
}
return memo[K][A.length][B.length];
}
@sameer I understand your solution and I think it should work, but when I implemented it in java, it returned wrong result (for the example above). I added all of the fixes from your comments. How do you intend to handle corner cases when i or j are out of bounds?
- blckembr November 19, 2015O(nlogn) solution: thinking about ranges as if they were representing start and end of an event. With this in mind, sorting starts end ends 'event's separately. Then counting 'start' and 'end' of 'event's, if count is larger than 1 at some point, this would mean at least 2 ranges overlap.
public static boolean checkOverlap(int[][] ranges) {
if (ranges == null || ranges.length <=0) {
return false;
}
int[] starts = new int[ranges.length];
int[] ends = new int[ranges.length];
for (int i = 0; i<ranges.length; i++) {
starts[i] = ranges[i][0];
ends[i] = ranges[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int count = 0;
int s = 0;
int e = 0;
while (e<ranges.length) {
if (s<ranges.length && starts[s] == ends[e]) {
return true;
} else {
if (s<ranges.length && starts[s] < ends[e]) {
count++;
if (count > 1) {
return true;
}
s++;
} else {
count--;
e++;
}
}
}
return false;
}
O(N) solution where N is the length of the string to search in and considering alphabet size is constant (for this question it seems limited to english letters).
In 2 passes, first starts from end of input and calculates smallest index p to which all characters from search string are found and puts those into array.
Second pass on the created array calculates shortest subarray that contains all characters from string to be searched.
public class MinSubstringContains {
public static String getSubArray(String input, String locate) {
if (input == null || input.isEmpty() || locate == null || locate.isEmpty()) {
return null;
}
int len = input.length();
LastFoundTracker lastFoundTracker = new LastFoundTracker(locate);
int[] closestFound = new int[len];
for(int i = input.length()-1; i>=0; i--) {
closestFound[i] = lastFoundTracker.updateIdx(input.charAt(i), i);
}
int subArrSize = 0;
int subArrStart = 0;
for (int i = 0; i<closestFound.length; i++) {
if (closestFound[i] == Integer.MAX_VALUE) {
break;
}
if (subArrSize == 0 || subArrSize > closestFound[i] - i +1) {
subArrSize = closestFound[i] - i + 1;
subArrStart = i;
}
}
StringBuilder strB = new StringBuilder();
for (int j = 0;j < subArrSize; j++) {
strB.append(input.charAt(subArrStart+j));
}
return strB.toString();
}
public static class LastFoundTracker {
Map<Character, Integer> lastFoundMap = new HashMap<>();
int lastFound = Integer.MAX_VALUE;
public LastFoundTracker(String searchStr) {
for (char c : searchStr.toCharArray()) {
lastFoundMap.put(c, Integer.MAX_VALUE);
}
}
public int updateIdx(char c, int i) {
if (! lastFoundMap.containsKey(c)) {
return lastFound;
}
lastFoundMap.put(c, i);
//find new farthest location that where all chars from search string are found
int max = -1;
for (Integer idx : lastFoundMap.values()) {
if (idx == Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (idx > max) {
max = idx;
}
}
lastFound = max;
return lastFound;
}
}
}
@HauntedGhost
Got a feeling there might be a little bug: 19 is still a valid letter code, but the if will not consider it as 2 digit code. try {1,9}, should return both "ai" and "s".
I'd suggest changing the if slightly toif(i < n-1 && ( (a[i+1] <= 6 && a[i] == 2) ||
(a[i+1] <= 9 && a[i] == 1)) )
@kyduke I used your awesome greedy tactics idea to reimplement the BFS part in my solution below. Now it does not queue children that end past the currently queued child. Effectively, it always queues only the one with max end.
For single run, your solution will be faster, because you only sort once nlogn, and then O(n) search, and I need to also construct the Inteval Tree.
But had the question asked to initialize once and run multiple queries then Interval Tree solution would have a potential to perform faster, because it is O(kLogn) k - size of output, and at most O(N) when all ranges end up in the output. (Am I correct with this analysis?)
@Ahmed Bassiouny The search part is O(n) alright! Try to look at it recursively and you'll see that it never visits a range more than twice always advancing forward because the target range's left point is shifting. And if kyduke updated maxIndex to last range that was filtered out, instead of maxIndex++, it would visit each range only once, it seams.
Very good algorithm.
Here's O(nlogn) solution based on Interval Tree and modified BFS.
The modified BFS is inspired by @kyduke greedy tactics, it does not add a child node if the currently stored node (the queued child) ends past new child, or replaces currently stored otherwise.
Input: list of 'ranges', target range 'r'
- First we add a dummy range [r.hi, max(tree_max, r.hi)] to ranges.
- Sort 'ranges' by 'lo'
- Build Balanced BST from sorted list
- From a dummy range [r.lo,r.lo] do BFS to reach [r.hi, max(tree_max, r.hi)]. (each node is one of the ranges in 'ranges' + the dummy, and edge is connected if 'node.hi' intersects another node which we determine by lookup in the interval tree.
It can be easily proven that any path from dummy start to end covers the whole input range. (by contradiction)
Now, since we use BFS, the output path represents one of the minimal subsets.
The complexity is dominated by sort and tree construction, but it would amortize in case this solution will be used for multiple queries, because dummy can be inserted and removed each time, and sorting/building tree is done only once. Then complexity of each query will be kLogn where k is the output set length (and at most N).
public class FindMinimalSubset {
private static final Logger logger = LoggerFactory.getLogger(FindMinimalSubset.class);
private IntervalNode bbstRoot = null;
public List<IntervalNode> getMinimalSet(List<IntervalNode> ranges, IntervalNode input) {
//sort ranges by lo and build balanced binary tree
Collections.sort(ranges);
//BST is used as interval tree, and it is balanced since the array was sorted
//prior to building the BST
buildIntervalT(ranges);
//insert the dummy end, it's 'hi' is max of input.hi and current max in the tree (that of root)
IntervalNode terminal = new IntervalNode(input.hi, Math.max(bbstRoot.max, input.hi));
insert(bbstRoot, terminal);
int left = input.lo;
int right = input.hi;
//do modified BFS filtering out ranges with smaller 'hi' than what was already found,
//from dummy start to dummy end and reconstruct path
//any path from start to end will contain the given range, and
//since it is a BFS, the path is minimal
IntervalNode bfsNode = doBfs(left, right, terminal);
//remove dummy end, in case need to be modified to initialize once and then multiple rins with different target range
//removeNode(terminal);
List<IntervalNode> path = reconstructPath(bfsNode);
return path;
}
//return path without last and first (which served as dummy start and end for bfs)
private List<IntervalNode> reconstructPath(IntervalNode bfsNode) {
if (bfsNode == null) {
return Collections.emptyList();
}
List<IntervalNode> ranges = new ArrayList<>();
IntervalNode parent = bfsNode.bfsParent;
while(parent != null && parent.bfsParent != null) {
ranges.add(parent);
parent = parent.bfsParent;
}
return ranges;
}
//do bfs starting with dummy start (lo,lo) and dummy end
private IntervalNode doBfs(int lo, int hi, IntervalNode terminalRange) {
Set<IntervalNode> visited = new HashSet<>();
//Queue<IntervalTNode> queue = new LinkedList<IntervalTNode>();
IntervalNode start = new IntervalNode(lo, lo);
visited.add(start);
IntervalNode currNode = start;
while (currNode != null) {
IntervalNode node = currNode;
currNode = null;
int x = node.hi;
//search for neighbors that intersect with 'hi' of this node in the interval tree
List<IntervalNode> containList = query(x);
if (containList != null) {
for (IntervalNode child : containList) {
if (child.equals(terminalRange)) {
child.bfsParent = node;
return child;
}
if (visited.contains(child) || child == node) {
continue;
}
visited.add(child);
if (currNode != null) {
if (currNode.hi < child.hi) {
currNode = child;
child.bfsParent = node;
}
} else {
currNode = child;
child.bfsParent = node;
}
}
}
}
return null;
}
private List<IntervalNode> query(int x) {
return query(bbstRoot, x);
}
private List<IntervalNode> query(IntervalNode root, int x) {
//usual interval tree query, as in wiki for example
//to find ranges that overlap the given point
}
private void buildIntervalT(List<IntervalNode> ranges) {
//the usual technique, can be found in wiki, using input[mid].lo as root key
bbstRoot = ...
}
private IntervalNode insert(IntervalNode root, IntervalNode newNode) {
//usual insert algorithm, can be found in wiki
}
public static class IntervalNode implements Comparable<IntervalNode>{
public int lo;
public int hi;
public IntervalNode bfsParent;
public IntervalNode left;
public IntervalNode right;
public int max = Integer.MIN_VALUE;
public IntervalNode(int lo, int hi) {
....
}
public boolean intersects(int x) {
return x>= lo && x<=hi;
}
@Override
public int compareTo(IntervalNode o) {
...
}
@Override
public int hashCode() {
...
}
@Override
public boolean equals(Object obj) {
...
}
}
}
@kyduke, I as well started with subsums, but then instead of doing N^2 comparisons treated this as 2SUM problem, where a-b=TargetSum and 'a' and 'b' are from the subsums array.
public class SubArrayWithSum {
public boolean hasSubArrayWithSum(int[] input, int sum) {
return getSubArrayWithSum(input, sum) != null;
}
public int[] getSubArrayWithSum(int[] input, int sum) {
int[] subSumArr = getSubSums(input);
Map<Integer, Integer> pairsMap = new HashMap<>();
for (int i =0; i<subSumArr.length; i++) {
if (pairsMap.containsKey(Integer.valueOf(subSumArr[i]))) {
return subArray(input, pairsMap.get(subSumArr[i]), i-1);
} else {
pairsMap.put(sum + subSumArr[i], Integer.valueOf(i));
}
}
return null;
}
private int[] subArray(int[] input, int start, int end) {
int[] subArr = new int[end-start+1];
for(int i = 0; i<subArr.length; i++) {
subArr[i] = input[i+start];
}
return subArr;
}
private int[] getSubSums(int[] input) {
int[] subSums = new int[input.length+1];
subSums[0] = 0;
for (int i = 1; i<=input.length; i++) {
subSums[i] = subSums[i-1] + input[i-1];
}
return subSums;
}
}
Here's O(nlogn + k) solution.
- Sort ranges by start
- keep index of next non empty range (rangeId) (initially pointing to smallest range)
- starting from lowest range get the start and set it to kth, incrementing k every time start of range is equal to current running kth and replacing range with a new range with start shifted by one. Once reached start > kth, break.
- When done with a range increment the lowest range index (rangeId)
repeat till k<K
import java.util.Collections;
import java.util.List;
public class KSmallestFromRanges {
public int findKSmallest(List<Range> ranges, int K) {
if (K<=0) {
throw new IllegalArgumentException("K must be greater than zero");
}
Collections.sort(ranges);
int rangeId = 0;
int k = 0;
int kth = -1;
while (k < K) {
if (rangeId >= ranges.size()) {
break;
}
kth = ranges.get(rangeId).start;
for (int firstRange = rangeId; firstRange<ranges.size(); firstRange++) {
if (ranges.get(firstRange).start > kth) {
break;
}
if ( (firstRange == rangeId) &&
(ranges.get(firstRange).start + 1 > ranges.get(firstRange).end) ) { //this range is done
rangeId++;
k++;
break;
} else {
if ( ! (ranges.get(firstRange).start > ranges.get(firstRange).end )) { //skip a range if it is not the first but has already depleted
ranges.set(firstRange, new Range(ranges.get(firstRange).start + 1, ranges.get(firstRange).end));
k++;
}
}
}
}
return kth;
}
public static class Range implements Comparable<Range>{
int start;
int end;
public Range(int start, int end) {
super();
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
@Override
public int compareTo(Range o) {
if (this.start < o.start) {
return -1;
} else if (this.start > o.start) {
return 1;
} else {
if (this.end < o.end) {
return -1;
} else {
return 1;
}
}
}
@Override
public String toString() {
return "[" + start + ", " + end + "]";
}
}
}
What do you mean nothing to do?
in the example we could have minimized it to [[2:20]] because it contains all ranges from original input.
So is the input "[[2:6], [3:8], [5:20]]" valid for this question? Is the task asks to only remove ranges that are completely included in other ranges or to minimize number of ranges so that all numbers from original input are still covered (by smaller number of ranges)?
@Test
public void test() {
weekSched.addEvent("Tue 09:00:00", "Tue 22:00:00");
weekSched.addEvent("Tue 09:00:00", "Thu 22:00:00");
weekSched.addEvent("Sun 00:00:00", "Tue 08:59:59");
weekSched.addEvent("Wed 15:00:00", "Fri 22:00:00");
weekSched.addEvent("Wed 15:00:00", "Fri 22:00:00");
weekSched.addEvent("Fri 22:00:00", "Sat 23:59:59");
boolean actual = weekSched.spansWeek();
logger.info("Spans week? {}", actual?"yes":"no");
assertTrue(actual);
}
Using Balanced BST to merge ranges (TreeSet in java)
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.TreeSet;
public class WeekSchedule {
private static final int SECONDS_IN_WEEK = 60*60*24*7;
private TreeSet<Event> treeSet = new TreeSet<Event>();
public void addEvent(String start, String end) {
addRange(convertToInt(start), convertToInt(end));
}
public boolean spansWeek() {
int secSum = 0;
if (treeSet == null) {return false;}
for (Event pair : treeSet) {
secSum = secSum + (pair.end - pair.start + 1);
}
return secSum == SECONDS_IN_WEEK;
}
private void addRange(int start, int end) {
if (end<start) {
//split into 2 events, does not matter because they are recurring anyway
addRange(start, SECONDS_IN_WEEK);
addRange(1, end % SECONDS_IN_WEEK);
return;
}
Event newPair = new Event(start, end);
if (treeSet.isEmpty()) {
treeSet.add(newPair);
return;
}
Event ceiling = treeSet.ceiling(new Event(end,end));
if (ceiling == null) {ceiling = treeSet.last();
}
Event floor = treeSet.floor(new Event(start, start));
if (floor == null) {floor = treeSet.first();}
Event rangeLeft = null;
Event rangeRight = null;
if (newPair.compareTo(floor) == -1
|| newPair.compareTo(ceiling) == 1) {
treeSet.add(newPair);
} else {
if (floor.inRange(newPair.start)) {
rangeLeft = floor;
newPair = new Event(floor.start, newPair.end);
} else {
rangeLeft = newPair;
}
if (ceiling.inRange(newPair.end)) {
rangeRight = ceiling;
newPair = new Event(newPair.start, ceiling.end);
} else {
rangeRight = newPair;
}
treeSet.removeAll(treeSet.subSet(rangeLeft, rangeRight));
treeSet.remove(rangeRight);
}
treeSet.add(newPair);
}
public static final class Event implements Comparable<Event> {
private int start = 0;
private int end = 0;
public Event(int left, int right) {
super();
this.start = left;
this.end = right;
}
public boolean inRange(int num) {
return num >= start && num <= end;
}
@Override
public int compareTo(Event o) {
if (this.end < o.start) {
return -1;
} else if (o.end < this.start) {
return 1;
} else {
return 0;
}
}
@Override
public String toString() {
return "Pair [" + start + ", " + end + "]";
}
}
private int convertToInt(String eventTime) {
SimpleDateFormat dateFormat = new SimpleDateFormat("E HH:mm:ss");
Calendar calendar = Calendar.getInstance();
try {
calendar.setTime(dateFormat.parse(eventTime));
} catch (ParseException e) {
throw new RuntimeException("wrong date");
}
int seconds = (calendar.get(Calendar.DAY_OF_WEEK) - 1) * 60*60*24;
seconds = seconds + calendar.get(Calendar.HOUR_OF_DAY) * 3600
+ calendar.get(Calendar.MINUTE) * 60
+ calendar.get(Calendar.SECOND);
return seconds;
}
}
@Good Replier
If it is allowed to change pattern while iterating, we could "eat up" equal characters like this:
if (sourceStr.charAt(sourceIndex) == patternStr.charAt(patternIndex - 1)) {
//NEW CODE
if (patternIndex > 1 && patternStr.charAt(patternIndex - 1) == patternStr.charAt(patternIndex - 2)) {
patternStr = patternStr.substring(0, patternIndex - 1) + "*";
patternIndex--;
}
//END NEW CODE
return isMatching(sourceStr, patternStr, --sourceIndex, patternIndex);
}
Had @Good Maker used char[] for the pattern instead of String, could have avoided subString and concat. Could just replace current char with "*" after characters that remained after "eating up" equals.
- blckembr October 14, 2015What is wrong with segment tree? Why the -1 vote?
it is not going to be Log(N) as in segment tree, because usually segment trees are used to combine single values stored at nodes, for example sums of sub ranges, min of range, etc. In this case I am assuming Darkhan's intention was to store sorted sub range which needs to be potentially merged with another sub-range on the same level. I am not sure what O(log^2n) is. My calculation came to O(N). Space is correctly O(nlogn), imagine each item stored in all of its parents (that's at max the height of the full binary tree - logN)
RepDessieBieri, Human Resource Executive at Bazaarvoice
I am Dessie, an academic advisor with more than 2 years of extensive field experience and a well-developed industry knowledge ...
Stating this as optimization problem: Find max non decreasing sequence so that each species contributes at least one element. If max length is equal to length of species, answer to original question is TRUE.
Trying to solve this as simple DP might yield false positive results when all elements are taken from only one of the species, e.g. {{2,2,3,3},{4,1,1,1}}, to avoid this we will induce fake obstacles, a different pair of indexes from species A an B. This will force DP to make a switch at least once.
Overall complexity will be O(n^3).
- blckembr December 16, 2015