CareerCup

It's actually a sliding window function of streaming processing system like Flink, Storm, etc.
To 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 min-heap of top K.

@Alex
yeah, agreed. split in run time. that's just what BFS do.
As for the connection, probably just different interpretations of models.
Very helpful discussions. Thanks :D

@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);

}

@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).

random function for every bit
or
rand + 2 * rand + 4*rand + ...
you can see that rand + 2 *rand output 0 1 2 3 uniformly

the only way I can think of is to start from a matrix of 0s
and click several random points
but I dont see clear patterns.

sort and get inverted index for each element.
then compare the index array
Onlgn

O(N)
keep record of every descending line,
and when meeting an ascending line, compare with every descending line.
merge them if possible.

isnt it a BFS? and at most 3 levels.

use DP
traverse from left to right and up to down.
cost[i][j]= min(cost[i-1][j] + possible_cost, cost[i][j-1] + possible_cost)
got it at last.

follow up:
start from right bottom, use the cost value to get the previous point (either [i-1][j] or [i][j-1]) and print it. do it iteratelly to reach the start point.

if bit operation can be consider as O(1) and n,m < 32
then we can use integer on every row/column for bit mask, and compare them
then it should be O(m*n)

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;
        }
    }
  }

do u mean java reflection?

maybe use wait and notifyall

use a sliding window to count all the words till contains all words in L. and search till the end to find the minimum.

wtf does it mean? plz clarify this

stack will not work cause you need preserve the priority

I guess like "aaabb" to "a3b2"

got it. thank you

maybe count sort

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.

so does it mean always use static together with volatile? any case use volatile only?

I mean the negative to the original number. if it's negative originally, just add the positive ones.

just add the negative values to the original array to become subset sum problem
and avoid possible duplicate solutions

DFS 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;}

yeah, minimum sum diff using subset sum dp solution. one more thing is to get the closest sum to S/2

you don't need to sort it again. you only need to output the values in the hashtmap grouped by the key. as long as anagrams of the same key are output together, it's good.

good insight

he's just asking you to clarify the problem. you have problems understanding?

no problem. but we are always trying to do the best we can in an interview, don't we? and this one is probably the best we can do in time complexity, at least the best I can think of.

very cool algorithm! it's like dp, kind of hard to think of this.

I can't think of any O(n) solution. plz clarify

KMP should be good enough.

I believe if they ask this kind of problems, they will say k is not very large and they want this answer.

@Loler alright. for non-negative array, you have dp solutions for O(nk), if not N^2.

dp. you can do it in n^2. check the subset sum on wiki

always takes the trip from bottom to top or top down first. so that it'll avoid the starving case. but surely you can do some compromise with greedy algorithm to decrease the waiting time. I don't think there's a perfect plan

binary search twice on arrival time and depart time

dp[i][n][sum]=dp[i-1][n-1][sum-a[i]]+dp[i-1][n][sum]

simply reverse each byte
this is for reversing one byte b
int i=0;
while(i<4){
if((b>>i)^(b>>(7-i))){
b^=((1<<i)|(1<<(7-i)))}
}

use notify and wait in java concurrent package...not good at it

believe the second one is optimal

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!