Showing posts with label Interview. Show all posts
Showing posts with label Interview. Show all posts

How to Land Your Dream Job


Read more »
Posted by at
Labels: , , , ,

How to Write Bug Free Code During Interview


Read more »
Posted by at
Labels: , , , ,

Traps and Mistakes during Phone Interview


Read more »
Posted by at
Labels: ,

When it Goes Wrong - How to Ace System Design Interview


How to Land Your Dream Job Series

The Approach

  • It’s important to follow some systematic approach and drive/lead this conversation.
    • SNAKE(Scenario, Needs, Application, Kilobyte(Data), Evolve)
    • Requirements, constraints/estimates, high-level design, detailed design
    • Talk about different approaches, pros and cons
  • It’s more important to follow the approach when you don’t have (much) clue or the interviewer wants to focus on specific domain or jump to detail too early.

System design interview is very important, as it’s usually conducted by managers or senior engineers who have more power to decide to hire or not, or the level.

Different from coding interview, how the system design interview goes varies a lot. Some companies(like Facebook) follow some good process, but others are not.

Depended on the interviewer, or what the candidate says, the system design interview may go wrong pretty soon.

1. Algorithm/Coding Question as a part of System Design

  • During the middle of the discussion, the interviewer may (unexpectedly) ask algorithm question.

Example: Autocomplete Service

  • As a system design question, the candidate may talk about: requirement
  • for a distributed prefix tree, how to shard data: consistent hash etc.
  • The interviewer may also ask and focus on how to Get top x word (ranked by frequency) from a single server trie: the algorithm question.
  • The candidate should be aware of the change, and approach it as an algorithm question and quickly give an optimal algorithm/pseudo code quickly.

2. The interviewer looking for specific direction/answer

Focus on detail too soon and too much

  • There are a lot of things the candidate can talk, but sometimes, the interviewer is looking for some specific direction/answer.
  • This is not good, as the system design is supposed to let the candidate lead the process, but you have to try your best when you are in this situation.

Example: One backend key value db server is slow, how to solve it?

The interviewer may jump to how to use cache, before you go that direction, make sure you also(still) talk about the scenario, outline other approaches first.

You may not have much time to go through those: you have to take and talk a lot about X when the interviewer is saying: let's go X approach, but still outline them in the whiteboard, at least you can resume those later.

  • Make sure ask these questions first
    • does the backend provide client library?
    • How many client apps? How easy to update them to new code/library?
    • What’s the goal? How much effort? a short term fix to just make it work? or a long term invest
    • What’s the team structure? Who is responsible to fix it (what team has the resource)? DB team or client team?
  • Potential solutions/discussion:
    • local cache in client side or remote central cache
    • request coalescing in client library
    • distribute the db: shard the database and add a proxy layer which can distribute the request to the right shard
    • Stability: rate limit, etc

What We Can Do?

Do Not Repeat Yourself

  • When asked the same questions after you already give (some) answer about it. Don’t just repeat your previous answer or try to expand it.
  • Usually, this means your answer is not what the interviewer is looking for at all.
  • Talk something meaningful and useful, that shows your skills.

Know/Guess what’s the interview is looking for

How vs Why and What

In system design, how to do it in detail is usually not important, instead focus on why and what info we are trying to get.

  • Between approach x and y, how you can determine which approach to take?
  • With the system is already running, how can you decide you should add local cache or centralized cache?
    • THIS IS NOT IMPORTANT: how to add the log, what to log and how to analyze log
    • WHAT IS IMPORTANT: how to determine the cache performance: hit ratio.

System Design Books

System Design Prep Resource

Posted by at
Labels: , , ,

Graph Algorithm - How to Succeed in Algorithms Interview


Graph Algorithm - How to Succeed in Algorithms Interview

Series: How to Succeed in Algorithms Interview

Graph represent

  • AdjacencyMatrix
  • AdjacencyList: List[]
  • EdgeList: Edge[] edges
  • Map<Integer, Set> map
  • Map indegrees
  • Topological Sort O(V+E)
  • create graph when 2 elements meets some criteria

Approaches

Binary tree to graph

int N;
Map<Integer, List<Integer>> graph;
Integer[][] memo;

public int numSquarefulPerms(int[] A) {
  N = A.length;
  graph = new HashMap();
  memo = new Integer[N][1 << N];

  for (int i = 0; i < N; ++i)
    graph.put(i, new ArrayList());

  for (int i = 0; i < N; ++i)
    for (int j = i + 1; j < N; ++j) {
      int r = (int) (Math.sqrt(A[i] + A[j]) + 0.5);
      if (r * r == A[i] + A[j]) {
        graph.get(i).add(j);
        graph.get(j).add(i);
      }
    }

  int[] factorial = new int[20];
  factorial[0] = 1;
  for (int i = 1; i < 20; ++i)
    factorial[i] = i * factorial[i - 1];

  int ans = 0;
  for (int i = 0; i < N; ++i)
    ans += dfs(i, 1 << i);

  Map<Integer, Integer> count = new HashMap();
  for (int x : A)
    count.put(x, count.getOrDefault(x, 0) + 1);
  for (int v : count.values())
    ans /= factorial[v];

  return ans;
}

public int dfs(int node, int visited) {
  if (visited == (1 << N) - 1)
    return 1;
  if (memo[node][visited] != null)
    return memo[node][visited];

  int ans = 0;
  for (int nei : graph.get(node))
    if (((visited >> nei) & 1) == 0)
      ans += dfs(nei, visited | (1 << nei));
  memo[node][visited] = ans;
  return ans;

}

Detect Cycle in Undirected Graph

Detect Cycle in a Directed Graph

  • dfs
    • Recursion stack[] is used from keep track of visiting vertices during DFS from particular vertex and gets reset once cycle is not found from that vertex and will try DFS from other vertices.
    • isCycleUtil(int vertex, boolean[] visited, boolean[] recursiveArr)
  • dfs + using colors
  • Topological sort

Check if a directed graph is strongly connected

  1. Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS traversal doesn’t visit all vertices, then return false.
  2. Reverse all arcs (or find transpose or reverse of graph) and Do a DFS traversal of reversed graph starting from same vertex , If DFS traversal doesn’t visit all vertices, then return false.
  • The idea is, if every node can be reached from a vertex v, and every node can reach v, then the graph is strongly connected. In step 1, we check if all vertices are reachable from v. In step 2, we check if all vertices can reach v (In reversed graph, if all vertices are reachable from v, then all vertices can reach v in original graph)

Eulerian path

Eulerian Cycle
  • For an undirected graph has Eulerian cycle
    1. All vertices with non-zero degree are connected.
    2. All vertices have even degree.

Eulerian Path

  • For an undirected graph has Eulerian Path
    1. Same as condition (a) for Eulerian Cycle
    2. If two vertices have odd degree and all other vertices have even degree. Note that only one vertex with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph)

Eulerian Cycle for a directed graph

  • A directed graph has an eulerian cycle if following conditions are true
    1. All vertices with nonzero degree belong to a single strongly connected component.
    2. In degree and out degree of every vertex is same.

Hamiltonian Cycle

Connected Components

Matrix to Graph

Tree to Graph

Color during DFS

Create Reverse Graph

Degree(in-degree, out-degree)

public int findJudge(int N, int[][] trust) {
    int[] count = new int[N+1];
    for (int[] t: trust) {
        count[t[0]]--;
        count[t[1]]++;
    }
    for (int i = 1; i <= N; ++i) {
        if (count[i] == N - 1) return i;
    }
    return -1;
}

Floyd Warshall Algorithm - All Pairs Shortest Path: O(V^3)

  • one by one pick all vertices and updates all shortest paths which include the picked vertex as an intermediate vertex in the shortest path.
  • when we pick vertex number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices.
void floydWarshall(int graph[][])
{
    int dist[][] = new int[V][V];
    int i, j, k;
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
    // Add all vertices one by one to the set of intermediate vertices.
    for (k = 0; k < V; k++)
    {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++)
        {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++)
            {
                // If vertex k is on the shortest path from i to j, then update the value of dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}
  • LeetCode 399 - Evaluate Division
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
  HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
  Function<String, HashMap<String, Double>> function = s -> new HashMap<>();
  for (int i = 0; i < equations.length; i++) {
      graph.computeIfAbsent(equations[i][0], function).put(equations[i][0], 1.0);
      graph.computeIfAbsent(equations[i][1], function).put(equations[i][1], 1.0);
      graph.get(equations[i][0]).put(equations[i][1], values[i]);
      graph.get(equations[i][1]).put(equations[i][0], 1 / values[i]);
  }
  for (String mid : graph.keySet()) {
      for (String src : graph.get(mid).keySet()) {
          for (String dst : graph.get(mid).keySet()) {
              double val = graph.get(src).get(mid) * graph.get(mid).get(dst);
              graph.get(src).put(dst, val);
          }
      }
  }
  double[] result = new double[queries.length];
  for (int i = 0; i < result.length; i++) {
      if (!graph.containsKey(queries[i][0])) {
          result[i] = -1;
      } else {
          result[i] = graph.get(queries[i][0]).getOrDefault(queries[i][1], -1.0);
      }
  }
  return result;
}

Examples

Posted by at
Labels: , , ,

Reverse Thinking - How to Succeed in Algorithms Interview


Reverse Thinking - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

Scan from right to left

public boolean backspaceCompare(String S, String T) {
    for (int i = S.length() - 1, j = T.length() - 1;; i--, j--) {
        for (int b = 0; i >= 0 && (b > 0 || S.charAt(i) == '#'); --i) b += S.charAt(i) == '#' ? 1 : -1;
        for (int b = 0; j >= 0 && (b > 0 || T.charAt(j) == '#'); --j) b += T.charAt(j) == '#' ? 1 : -1;
        if (i < 0 || j < 0 || S.charAt(i) != T.charAt(j)) return i == -1 && j == -1;
    }
}
public String parseTernary(String expression) {
    if (expression == null || expression.length() == 0) return "";
    Deque<Character> stack = new LinkedList<>();

    for (int i = expression.length() - 1; i >= 0; i--) {
        char c = expression.charAt(i);
        if (!stack.isEmpty() && stack.peek() == '?') {

            stack.pop(); //pop '?'
            char first = stack.pop();
            stack.pop(); //pop ':'
            char second = stack.pop();

            if (c == 'T') stack.push(first);
            else stack.push(second);
        } else {
            stack.push(c);
        }
    }
    return String.valueOf(stack.peek());
}
public String decodeAtIndex(String S, int K) {
  long size = 0;
  int N = S.length();
  for (int i = 0; i < N; ++i) {
    char c = S.charAt(i);
    if (Character.isDigit(c))
      size *= c - '0';
    else
      size++;
  }
  for (int i = N - 1; i >= 0; --i) {
    char c = S.charAt(i);
    K %= size;
    if (K == 0 && Character.isLetter(c))
      return Character.toString(c);
    if (Character.isDigit(c))
      size /= c - '0';
    else
      size--;
  }
  throw null;
}
public String decodeAtIndex(String S, int K) {
  long size = 0;
  int N = S.length();
  // Find size = length of decoded string
  for (int i = 0; i < N; ++i) {
    char c = S.charAt(i);
    if (Character.isDigit(c))
      size *= c - '0';
    else
      size++;
  }
  for (int i = N - 1; i >= 0; --i) {
    char c = S.charAt(i);
    K %= size;
    if (K == 0 && Character.isLetter(c))
      return Character.toString(c);
    if (Character.isDigit(c))
      size /= c - '0';
    else
      size--;
  }
  throw null;
}
  • LeetCode 853 - Car Fleet
    • from closet to furthest
    public int carFleet(int target, int[] position, int[] speed) {
  TreeMap<Integer, Integer> map = new TreeMap<>();
  int n = position.length;
  for(int i=0; i<n; ++i){
      map.put(target - position[i], speed[i]);
  }
  int count = 0;
  double r = -1.0;
  for(Map.Entry<Integer, Integer> entry: map.entrySet()){
      int d = entry.getKey(); // distance
      int s = entry.getValue(); // speed
      double t = 1.0*d/s; // time to target
      if(t>r){ // this car is unable to catch up previous one, form a new group and update the value
          ++count;
          r = t;
      }
  }
  return count;
}

From (potential) target to source

  • LeetCode 780 - Reaching Points
    • if we start from sx and sy, there is two possibility, but if we start from target, there is only one possibility
    • use modulo to speed minus
bool reachingPoints(int sx, int sy, int tx, int ty) {
    while(tx >= sx && ty >= sy){
        if(tx > ty){
            if(sy == ty) return (tx - sx) % ty == 0;
            tx %= ty;
        }else{
            if(sx == tx) return (ty - sy) % tx == 0;
            ty %= tx;
        }
    }
    return false;
}

public boolean reachingPoints(int sx, int sy, int tx, int ty) {
    if (sx > tx || sy > ty) return false;
    if (sx == tx && (ty - sy) % sx == 0) return true;
    if (sy == ty && (tx - sx) % sy == 0) return true;
    return reachingPoints(sx, sy, tx % ty, ty % tx);
}

Reverse

Reverse - call same function again

Guess

  • [LeetCode 843 - Guess the Word]
    • [minimum our worst outcome]
      • worse case: only 0 match,
      • we guess the word with minimum words of 0 matches
// random
public void findSecretWord(String[] wordlist, Master master) {
  for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
      String guess = wordlist[new Random().nextInt(wordlist.length)];
      x = master.guess(guess);
      List<String> wordlist2 = new ArrayList<>();
      for (String w : wordlist)
          if (match(guess, w) == x)
              wordlist2.add(w);
      wordlist = wordlist2.toArray(new String[wordlist2.size()]);
  }
}

public void findSecretWord(String[] wordlist, Master master) {
  for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
      HashMap<String, Integer> count = new HashMap<>();
      for (String w1 : wordlist)
          for (String w2 : wordlist)
              if (match(w1, w2) == 0)
                  count.put(w1, count.getOrDefault(w1 , 0) + 1);
      Pair<String, Integer> minimax = new Pair<>("", 1000);
      for (String w : wordlist)
          if (count.getOrDefault(w, 0) < minimax.getValue())
              minimax = new Pair<>(w, count.getOrDefault(w, 0));
      x = master.guess(minimax.getKey());
      List<String> wordlist2 = new ArrayList<String>();
      for (String w : wordlist)
          if (match(minimax.getKey(), w) == x)
              wordlist2.add(w);
      wordlist = wordlist2.toArray(new String[0]);
  }
}
Posted by at
Labels: , , ,

Sliding Window - How to Succeed in Algorithms Interview


Sliding window - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

Applications of Sliding Window

  • window of size k
  • Shortest/longest Subarray with xxx
  • continuous subarrays or substrings

How to Implement Sliding Window

  • expand (end pointer) the window until it meets the criteria
  • reset value when it violates
  • shrink (start pointer) to make it smallest
  • maintain states when expand and shrink: put in a map/set
  • use together with queue or monotone queue

Implementation Detail

Multiple List

public int lengthOfLongestSubstring(String s) {
     if (s.length()==0) return 0;
     HashMap<Character, Integer> map = new HashMap<Character, Integer>();
     int max=0;
     for (int i=0, j=0; i<s.length(); ++i){
         if (map.containsKey(s.charAt(i))){
             j = Math.max(j,map.get(s.charAt(i))+1);
         }
         map.put(s.charAt(i),i);
         max = Math.max(max,i-j+1);
     }
     return max;
 }
public List<Integer> findAnagrams(String s, String p) {
    Map<Character, Integer> map = counter(p);
    int match = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) - 1);
            if (map.get(c) == 0) {
                match++;
            }
        }
        if (i >= p.length()) {
            c = s.charAt(i - p.length());
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
                if (map.get(c) == 1) {
                    match--;
                }
            }
        }
        if (match == map.size()) {
            result.add(i - p.length() + 1);
        }
    }
    return result;
}

Window class

  • LeetCode 992 - Subarrays with K Different Integers
    public int subarraysWithKDistinct(int[] A, int K) {
Window window1 = new Window();
Window window2 = new Window();
int ans = 0, left1 = 0, left2 = 0;
for (int right = 0; right < A.length; ++right) {
  int x = A[right];
  window1.add(x);
  window2.add(x);
  while (window1.different() > K)
    window1.remove(A[left1++]);
  while (window2.different() >= K)
    window2.remove(A[left2++]);
  ans += left2 - left1;
}
return ans;
}

    Jumping Window + Fixed Size

  • LeetCode 683 - K Empty Slots
    public int kEmptySlots(int[] flowers, int k) {
  int[] days = new int[flowers.length];
  for (int i = 0; i < flowers.length; i++) days[flowers[i] - 1] = i + 1;
  int left = 0, right = k + 1, result = Integer.MAX_VALUE;
  for (int i = 0; right < days.length; i++) {
      if (days[i] < days[left] || days[i] <= days[right]) {
          if (i == right)
              result = Math.min(result, Math.max(days[left], days[right]));
          left = i;
          right = k + 1 + i;
      }
  }
  return (result == Integer.MAX_VALUE) ? -1 : result;
}
Posted by at
Labels: , , ,

Using Priority Queue - How to Succeed in Algorithms Interview


Using Priority Queue - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

Applications of Priority Queue

  • TopK

Implementation

  • Use poll, peek, offer
  • Don’t use remove (if need update it: just keep the old one and add a new one)
  • Alternation: use TreeSet/Map

Order - How to add elements

for (int i = 0; i + 1 < nums.length; ++i) {
    heap.offer(new Node(i, i+1));
}

Node node = null;
for (; k > 0; --k) {
    node = heap.poll();
    if (node.nei + 1 < nums.length) {
        heap.offer(new Node(node.root, node.nei + 1));
    }
}

Merge k sorted list

  • Element: [outerIndex, innerIndex]
  • Iterator
Examples
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
  List<Interval> res = new ArrayList<Interval>();
  PriorityQueue<Node> minHeap = new PriorityQueue<Node>(
      (a, b) -> schedule.get(a.employee).get(a.index).start - schedule.get(b.employee).get(b.index).start);
  int start = Integer.MAX_VALUE;
  for (int i = 0; i < schedule.size(); i++) {
    minHeap.add(new Node(i, 0));
    start = Math.min(start, schedule.get(i).get(0).start);
  }
  while (!minHeap.isEmpty()) {
    Node cur = minHeap.poll();
    if (start < schedule.get(cur.employee).get(cur.index).start) {
      res.add(new Interval(start, schedule.get(cur.employee).get(cur.index).start));
    }
    start = Math.max(start, schedule.get(cur.employee).get(cur.index).end);
    cur.index++;
    if (cur.index < schedule.get(cur.employee).size()) {
      minHeap.add(cur);
    }
  }
  return res;
}
class Node {
  int employee;
  int index;
  public Node(int employee, int index) {
    this.employee = employee;
    this.index = index;
  }
}

Examples

public int nthSuperUglyNumber(int n, int[] primes) {
    int[] ugly = new int[n];
    int[] idx = new int[primes.length];
    int[] val = new int[primes.length];
    Arrays.fill(val, 1);

    int next = 1;
    for (int i = 0; i < n; i++) {
        ugly[i] = next;

        next = Integer.MAX_VALUE;
        for (int j = 0; j < primes.length; j++) {
            //skip duplicate and avoid extra multiplication
            if (val[j] == ugly[i]) val[j] = ugly[idx[j]++] * primes[j];
            //find next ugly number
            next = Math.min(next, val[j]);
        }
    }
    return ugly[n - 1];
}

public int nthSuperUglyNumberHeap(int n, int[] primes) {
    int[] ugly = new int[n];
    PriorityQueue<Num> pq = new PriorityQueue<>();
    for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
    ugly[0] = 1;
    for (int i = 1; i < n; i++) {
        ugly[i] = pq.peek().val;
        while (pq.peek().val == ugly[i]) {
            Num nxt = pq.poll();
            pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
        }
    }
    return ugly[n - 1];
}
public int minRefuelStops(int target, int startFuel, int[][] stations) {
    int curFarthest = startFuel, refuel = 0;
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    for (int[] station : stations) {
        // check if we can reach this station
        // if we cannot reach this station, refuel the gas from the previous station with most gas
        // redo the operation until we get enough gas to reach this station
        while (curFarthest < station[0]) {
            if (pq.isEmpty()) return -1; // if we reful in each station but still cannot reach this station, return -1
            curFarthest += pq.poll();
            refuel++;
        }
        pq.offer(station[1]);
    }
    // now we have reached the last station, check if we can reach the target
    while (curFarthest < target) {
        if (pq.isEmpty()) return -1;
        curFarthest += pq.poll();
        refuel++;
    }
    return refuel;
}

public int minRefuelStops(int target, int cur, int[][] s) {
    Queue<Integer> pq = new PriorityQueue<>();
    int i = 0, res;
    for (res = 0; cur < target; res++) {
        while (i < s.length && s[i][0] <= cur)
            pq.offer(-s[i++][1]);
        if (pq.isEmpty()) return -1;
        cur += -pq.poll();
    }
    return res;
}

Poll multiple elements - slots

public String rearrangeString(String str, int k) {
    if(k<=1){ return str; }
    int[] count = new int[26];
    for(int i=0; i<str.length(); i++){
        count[str.charAt(i)-'a']++;
    }
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->b[0]-a[0]);
    for(int i=0; i<count.length; i++){ pq.add(new int[]{ count[i], i}); }   
    char[] result = new char[str.length()];
    int idx = 0;
    int start = 0;
    while(!pq.isEmpty()){
        int[] num = pq.remove();
        for(int i=0; i<num[0]; i++){
            result[idx] = (char)(num[1]+'a');
            if(idx>0 && result[idx-1]==result[idx]){ return ""; }
            idx+=k;
            if(idx>=str.length()){ idx=++start; }
        }
    }
    return new String(result);
}
public String rearrangeString(String str, int k) {
    for(char c: map.keySet())
        queue.offer(c);
    StringBuilder sb = new StringBuilder();
    int len = str.length();
    while(!queue.isEmpty()){
        int cnt = Math.min(k, len);
        ArrayList<Character> temp = new ArrayList<Character>();
        for(int i=0; i<cnt; i++){
            if(queue.isEmpty())//\\
                return "";
            char c = queue.poll();
            sb.append(String.valueOf(c));
            map.put(c, map.get(c)-1);
            if(map.get(c)>0){
                temp.add(c);
            }
            len--;
        }
        for(char c: temp)
            queue.offer(c);
    }
    return sb.toString();
}
public int leastInterval(char[] tasks, int n) {
    Map<Character, Integer> counts = new HashMap<Character, Integer>();
    for (char t : tasks) {
        counts.put(t, counts.getOrDefault(t, 0) + 1);
    }
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
    pq.addAll(counts.values());
    int alltime = 0;
    int cycle = n + 1;
    while (!pq.isEmpty()) {
        int worktime = 0;
        List<Integer> tmp = new ArrayList<Integer>();
        for (int i = 0; i < cycle; i++) {
            if (!pq.isEmpty()) {
                tmp.add(pq.poll());
                worktime++;
            }
        }
        for (int cnt : tmp) {
            if (--cnt > 0) {
                pq.offer(cnt);
            }
        }
        alltime += !pq.isEmpty() ? cycle : worktime;
    }    
    return alltime;
}

Min/MaxHeap(TreeSet)

BFS + PriorityQueue

Dijkstra

Examples

public int kthSmallest(final int[][] matrix, int k) {
    int c = 0;
    PriorityQueue<int[]> queue = new PriorityQueue<>(
        k, (o1, o2) -> matrix[o1[0]][o1[1]] - matrix[o2[0]][o2[1]]);
    queue.offer(new int[] {0, 0});
    while (true) {
        int[] pair = queue.poll();
        if (++c == k) {
            return matrix[pair[0]][pair[1]];
        }
        if (pair[0] == 0 && pair[1] + 1 < matrix[0].length) {
            queue.offer(new int[] {0, pair[1] + 1});
        }
        if (pair[0] + 1 < matrix.length) {
            queue.offer(new int[] {pair[0] + 1, pair[1]});
        }
    }
}
// O(KlogK)
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    PriorityQueue<int[]> que = new PriorityQueue<>((a,b)->a[0]+a[1]-b[0]-b[1]);
    List<int[]> res = new ArrayList<>();
    if(nums1.length==0 || nums2.length==0 || k==0) return res;
    for(int i=0; i<nums1.length && i<k; i++) que.offer(new int[]{nums1[i], nums2[0], 0});
    while(k-- > 0 && !que.isEmpty()){
        int[] cur = que.poll();
        res.add(new int[]{cur[0], cur[1]});
        if(cur[2] == nums2.length-1) continue;
        que.offer(new int[]{cur[0],nums2[cur[2]+1], cur[2]+1});
    }
    return res;
}

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<int[]> res = new LinkedList<>();
    if(nums1==null || nums1.length==0 || nums2==null || nums2.length==0) {
        return res;
    }
    PriorityQueue<int[]> minQ = new PriorityQueue<>(new Comparator<int[]>(){
        public int compare(int[] pair1, int[] pair2) {
            return (nums1[pair1[0]]+nums2[pair1[1]])-(nums1[pair2[0]]+nums2[pair2[1]]);
        }
    });
    minQ.offer(new int[]{0, 0});
    while (k>0 && !minQ.isEmpty()) {
        int[] pair=minQ.poll();
        int i = pair[0];
        int j = pair[1];
        res.add(new int[]{nums1[i], nums2[j]});
        k--;
        if(j+1<nums2.length) {
            minQ.offer(new int[]{i, j+1});
        }
        if(j==0 && i+1<nums1.length){
            minQ.offer(new int[] {i+1, 0});
        }
    }
    return res;
}
Posted by at
Labels: , , ,
Subscribe to: Posts (Atom)

Labels

ANT (6) Algorithm (69) Algorithm Series (35) Android (7) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) JSON (7) Java (186) JavaScript (27) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) adsense (5) bat (8) regex (5) xml (5)