zyfo2
BAN USER 0of 0 votes
Answersc = ‘a’
 zyfo2 in United States
w = “apple”
c covers w, iff w contains c.
c_set = {‘a’, ‘b’, ‘c’, ‘g’}
w_set = {‘apple’, ‘ibm’, ‘cisco’, ‘google’}
c_set covers w_set, iff every w in w_set is covered by some c in c_set.
Given c_set and w_set, Whether w_set is covered by c_set?
Follow up: if w_set is fixed say a book, how to determine whether a c_set covers this w_set? Report Duplicate  Flag  PURGE
Google Software Engineer / Developer Data Structures
@Alex
I dont quite get this "The great complexity of transit graphs is just moved to the run time"
I dont see why my algorithm makes it more complex. It's just the same BFS which takes every line in the list as a node to traverse. I believe it's the same complexity.
And I believe in my real life, I see stations on bus stops as a list. I don't need to connect every two of them. All I need to know is that this stop has a certain list of bus lines. and I only need to switch if I want to go to a stop that's not my current line.
you connecting every two of them seems kind of redundant to me.
@Alex
I got your idea.
you represent the same station by different numbers which is kind of misleading.
but, I have a question. For station C in your last example, do you also have to connect 3 and 13 since they are the same station and you need only one switch from line 1 to line 3? and for station D do you have to connect 4 and 14?
if so, I will form a kind of very complex graph if the intersection station have a lot of bus lines. you probably need to connect every two of them. also you need extra storage of node to ID mapping to check. though may not be a problem, but a little bit waste of memory and time.
my idea is basically the same. for your example
Bus 1: abcde
Bus 2: fgcdh
Bus 3: ijcdk
a[1] f[2] i[3]
  
b[1] g[2] j[3]
\  /
c [1,2,3]

d [1,2,3]
/  \
e[1] h[2] k[3]
the int list in [] are bus lines the station has.
when BFS traversing from one stop to next, we always keep track of the current line number.
and when meeting intersection station, we traverse all line number in the list and we only do switch++ when changing current line number.
Is that clear?
I think this is a little bit easier to understand and saves memory.
Please correct me if I got anything wrong :)
class result {
String val;
boolean shouldBracket;
}
Result equation (Node root) {
if (root == null) {
return new Result("", false);
}
String val = "";
boolean shouldBracket = false;
Result l = equation(root.left);
Result r = equation(root.right);
if (root.toString().equals("*")  root.toString().equals("\")) {
if (l.shouldBracket == false) {
val = "(" + l.val + ")";
}
} else {
val = l.val;
shouldBracket = true;
}
val += root.toString();
if (root.toString().equals("*")  root.toString().equals("\")) {
if (r.shouldBracket == false) {
val += "(" + r.val + ")";
}
} else {
val += r.val;
shouldBracket = true;
}
return new Result(val, shouldBracket);
}

zyfo2
December 06, 2017 @Alex
that's exactly why I voted down your answer
You didn't handle that example in your solution.
But in my solution. we can store the all the bus numbers in one node say in node c and d in your example, we need to store [1,2,3] there. and we also keep track of the current bus number we are on. and when going to another bus line, switch++.
another way is to replicate node c and d three times and each of them is bond with the bus number.
I believe I made it clear in my answer.
it's an interesting and actually a practical one.
the way I came up is that:
form a graph using these lists, node as station and do BFS.
but it's not a normal graph. you have to store bus numbers in the node itself and keep track of your current bus number in BFS. so when do BFS, you meet a station with multiple bus numbers, you traverse all of them and when current bus number changes your switch++.
or to make it more clear, you replicate the nodes for nodes having multiple bus numbers. so a node is essentially a bus station binding a bus number.
also a small trick to cut possible BFS branches, you'll have at most n switches (n is the totally number of bus numbers) and you never switch back to a previous bus number(cause only switches count in this question).
use DP
traverse from left to right and up to down.
cost[i][j]= min(cost[i1][j] + possible_cost, cost[i][j1] + possible_cost)
got it at last.
follow up:
start from right bottom, use the cost value to get the previous point (either [i1][j] or [i][j1]) and print it. do it iteratelly to reach the start point.
1. keep hash map record: A[i] > i
traverse A, return max (i  map(A[i] 1))
O(n) space O(n) time
2. keep hash map record: A[i] > i
sort A as B, then replace value with A[B[i]] which set B[i] to the origin index in A
then traverse B and update smallest and largest index and return largest diff
(note when smallest is updated largest is set to the same value)
eg:
A: 3 4 5 6 0 1 2
B: 4 5 6 0 1 2 3
smallest: 4 4 4 0 0 0 0
largest: 4 5 6 0 1 2 3
max: 0 1 2 2 2 2 3
thus return 3(i=3, j=6)
O(nlgn) time, O(n) space
check from bottom up recursively.
for every node, it has a longest left subtree length lmax, and right subtree length rmax
update result if lmax + rmax > result
and return max(lmax, rmax) to its parent node.
note: the idea behind it is that it's not necessarily the root node be included in the longest path.
two ways to solve it:
1. merge two arrays, time:O(m+n)
2. binary search every element in the other array, O(n*logm)
option depends the size of two arrays
below is the 2nd implementation
class Solution {
public static void main(String[] args) {
Interval[] a = {new Interval(1,2), new Interval(5,7)};
Interval[] b = new Interval[]{new Interval(2,7)};
List<Interval> res = Intersection(a,b);
for(Interval i : res){
System.out.println(i.start);
System.out.println(i.end);
}
}
public static List<Interval> Intersection(Interval[] i1, Interval[] i2) {
if (i1 == null  i2 == null) return null;
int index1 = 0;
int index2 = 0;
List<Interval> result = new ArrayList<>();
for (Interval interval : i2) {
Integer start = search(i1, interval.start, 0);
Integer end = search(i1, interval.end, 1);
if (start == null  end == null) {
break;
}
result.add(new Interval(start, end));
}
return result;
}
public static Integer search(Interval[] i, int x, int type) {
int low = 0;
int high = i.length  1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (i[mid].start < x && i[mid].end > x) {
return x;
} else if (i[mid].start == x && type == 0) {
return x;
} else if (i[mid].end == x && type == 1) {
return x;
} else if (i[mid].start > x) {
high = mid  1;
} else {
low = mid + 1;
}
}
if (type == 1) {
if (high < 0) { return null;}
else return i[high].end;
} else {
if (low == i.length) return null;
else return i[low].start;
}
}
}

zyfo2
October 09, 2017 linkedlist is one way. the head stores the latest and the tail is the oldest. also keep a hashmap for all nodes in the linkedlist. whenever some new query happens, check whether it's in the hashmap, if yes, move it to the head , if not, remove the tail one and bring the new node to head. besides, update the hashmap every time.
 zyfo2 March 19, 2013DFS is good. just elaborate if it's a graph. we probably don't have a root.
...O...O
../..\../..\
O...O...O
in the above graph, we'll need to check every node for its children. and you can meet the same node more than once like in the example and it may not be a cycle. so only visited flag is not enough.
we can add one more flag for detecting cycles in the recursion phase.
so just add the stack flag in the code.
boolean isLoop(Node root,HashMap hash)
{if(!root.isVisited){
root.isVisited=true;
bool isloop=false;
hash.put(root,true);
for(int i=0;i<root.Childs.Count();i++)
{
if(hash.get(root.Childs[i])==true)
return true;
else if( !root.childs[i].isVisited&&isLoop(root.childs[i],hash))
return true;
}
hash.put(root,false);}
return false;
}
int main(){
HashMap hash=new ....;
for(Node x:all nodes){
if(isLoop(x,hash)) return true;}
return false;}
sorry for my bad explaination, I'm really not good at it. but I think the idea is simple and clear.
let me try an example
say k=6, number=14, N=20
the array after mod is {seven 1s, three 2s, six 3s, four 4s}
let's check whether it's possible.
1. use DP to find a sum set consisted of 6 numbers(must include all distinct numbers 1,2,3,4 and two other numbers) which sums up to 14
it can only be (1,2,2,2,3,4) or (1,1,2,3,3,4)
2. check (1,2,2,2,3,4)
so set is one 1, three 2s, one 3 and one four
N/k=3;
so
total count of 1s should be >= 3*one=3 and <3*one+k=9 true 3<=7<9
total count of 2s should be >= 3*three=9 and <3*three+k=15 false 3<9
...
so it's false;
3. check (1,1,2,3,3,4)
so set is two 1s, one 2s, two 3s and one four
N/k=3;
total count of 1s should be >= 3*two=6 and <3*two+k=12 true 6<=7<12
total count of 2s should be >= 3*one=3 and <3*one+k=9 true 3<=3<9
total count of 3s should be >= 3*two=6 and <3*two+k=12 true 6<=6<12
total count of 4s should be >= 3*one=3 and <3*one+k=9 true 3<=4<9
so it's true
if every set checks to be false, return false
I'm not saying we need try every combination. instead, we just count the remaining after decreasing by N/k, and check whether it's a possible combination of the sum set(1,2,3,4,4).
actually we don't need check the remaining. we just need check whether all number has count more than N/K*(the corresponding count in that sum set)
so basically, we have at most k distinct number(after mod). then we use DP or whatever to check whether we can get the sum with k numbers(must include all distinct number and may possibly include some repeated number, can be done in DP when k is very large!) if not obviously false. else we can check every possibility. say 1,2,3 and two 4s, can be an example of k=5 number=14. so we check the count of these numbers(1,2,3,4). it should be N/k 1s, N/k 2s, N/k 3s, 2N/k 4s and possibly any combination of N%k elements from (1,2,3,4,4).
Let me know whether I get it!
Open Chat in New Window
It's actually a sliding window function of streaming processing system like Flink, Storm, etc.
 zyfo2 December 09, 2017To store the data, use a fifo list to store every element with timestamp. and each time a new element comes to the tail of the list, evict the expired elements using timestamp and update the sum.
use map reduce like function to shard messages to multiple machines, and sort them perhaps or keep a minheap of top K.