CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers.

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google and Uber etc.),
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
Microsoft question bank for questions outside leetcode and sorted by frequency. Get the best chance within limited time.

Get hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

class RingBuffer:
    def __init__(self, capacity):
        self.size = capacity
        self.capacity = 0
        self.Buffer = [None] * capacity
        self.Head = 0
        self.Tail = 0

    def full(self):
        return self.size == self.capacity

    def empty(self):
        return self.capacity == 0

    def add(self, obj):
        self.Buffer[self.Tail] = obj
        self.Tail = (self.Tail + 1) % self.size
        Self.capacity += 1

    def pop(self):
        self.Head = (self.Head + 1) % self.size
        Self.capacity -= 1
        return self.Buffer[self.Head - 1]

//merge interval
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include<cmath>
#include <unordered_map>
#include<memory>
#include<algorithm>
#include<assert.h>
#include <sstream>

using namespace std;
bool comparator(vector<int> a, vector<int> b)
{
	return a[0] < b[0];
}

bool rcomparator(vector<int> a, vector<int> b)
{
	return a[0] > b[0];
}
void mergeInterval(vector<vector<int>>& arr)
{
	int n = arr.size();
	int count = n;
	sort(arr.begin(), arr.end(), comparator);
	for (int i = 0; i < n-1; i++)
	{
		if (arr[i][1] >= arr[i + 1][0])
		{
			arr[i][1] = max(arr[i][1], arr[i + 1][1]);
			arr[i + 1][0] = -1;
			//arr.erase(arr.begin()+i + 1);
			count--;
		}
	}
	sort(arr.begin(), arr.end(), rcomparator);
	arr.resize(count);
	sort(arr.begin(), arr.end(), comparator);


}

int main() {
	vector<vector<int>> arr = { { 6,8 },{ 1,9 },{ 2,4 },{ 4,7 } };
	mergeInterval(arr);
	int n = arr.size();
	for (int i = 0; i < n; i++)
		cout << arr[i][0] << " " << arr[i][1] << endl;
	
	return 0;
}

package com.ibm.mypackage;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Stack;

public class AlienDictionaryTest
{
static HashMap<Character, Integer> map = new HashMap<Character, Integer>();
static int[][] adjMatrics;

static int buildGraph(String[] dick)
{
int n = 0;
int arrLen = dick.length;
for (int i = 0; i < arrLen; i++)
{
String word = dick[i];
int wordLen = word.length();
for (int j = 0; j < wordLen; j++)
{
if (map.containsKey(word.charAt(j)) == false)
{
map.put(word.charAt(j), n);
n++;
}
}
}
return n;
}

static void setVertice(String[] dick, int numOfChars)
{
adjMatrics = new int[numOfChars][numOfChars];
int arrLen = dick.length;

for (int i = 0; i < arrLen - 1; i++)
{
String word1 = dick[i];
String word2 = dick[i + 1];
int shorter = Math.min(word1.length(), word2.length());
for (int j = 0; j < shorter; j++)
{
if (word1.charAt(j) != word2.charAt(j))
{
adjMatrics[map.get(word2.charAt(j))][map.get(word1.charAt(j))] = 1;
}
}
}
}

static int getRoot()
{
int numOfChars = adjMatrics[0].length;
boolean hasDep;
for (int i = 0; i < numOfChars; i++)
{
hasDep = false;
for (int j = 0; j < numOfChars; j++)
{
if (adjMatrics[j][i] == 1)
hasDep = true;
}
// need to process error if there are more than 1 root
if (hasDep == false)
return i;
}
// also need to handle error if there is no root;
return -1;
}

static void searchGraph(String[] dick)
{
int numOfChars = buildGraph(dick);
setVertice(dick, numOfChars);
int[] visited = new int[numOfChars];
for (int i = 0; i < numOfChars; i++)
visited[i] = 0;
Stack<Integer> stack = new Stack<Integer>();
int root = getRoot();
DFS(root, visited, stack, numOfChars);
printCharOrder(stack);
}

static void DFS(int root, int[] visited, Stack<Integer> stack, int numOfChars)
{
visited[root] = 1;
for (int i = 0; i < numOfChars; i++)
{
if (adjMatrics[root][i] == 1 && visited[i] == 0)
DFS(i, visited, stack, numOfChars);
}
visited[root] = 2;
stack.push(root);
}

static void printCharOrder(Stack<Integer> stack)
{
int numOfChars = adjMatrics[0].length;
char[] chars = new char[numOfChars];
Iterator it = map.entrySet().iterator();
while (it.hasNext())
{
Map.Entry<Character, Integer> entry = (Map.Entry<Character, Integer>) it.next();
chars[entry.getValue()] = entry.getKey();
}
Stack<Integer> reversed = new Stack<Integer>();
while (!stack.isEmpty())
{
reversed.push(stack.pop());
}
while (!reversed.isEmpty())
{
int index = reversed.pop();
System.out.print(chars[index]);
System.out.print(" ");
}
}

public static void main(String[] args)
{
String[] dick = { "wrt", "wrf", "er", "ett", "rftt" };
searchGraph(dick);
}
}

import java.util.ArrayList;
import java.util.Stack;

public class LeetDictionaryTest
{
   public static Graph buildGraph(String[] dictionary)
   {
      Graph graph = new Graph();
      int arrLen = dictionary.length;
      for (int i = 0; i < arrLen - 1; i++)
      {
         String word1 = dictionary[i];
         String word2 = dictionary[i + 1];
         int compareLen = Math.min(word1.length(), word2.length());
         for (int j = 0; j < compareLen; j++)
         {
            if (word1.charAt(j) != word2.charAt(j))
            {
               graph.addDependency(word1.charAt(j), word2.charAt(j));
            }
         }
      }

      return graph;
   }

   public static Stack<Letter> getOrder(Graph graph)
   {
      Stack<Letter> stack = new Stack<Letter>();
      ArrayList<Letter> letters = graph.getNodes();
      for (Letter letter : letters)
      {
         if (letter.getState() == Letter.State.UNVISTITED)
         {
            if (!DFS(letter, stack))
            {
               return null;
            }
         }
      }
      return stack;
   }

   public static boolean DFS(Letter letter, Stack<Letter> stack)
   {
      if (letter.getState() == Letter.State.VISITING)
      {
         return false;
      }

      if (letter.getState() == Letter.State.UNVISTITED)
      {
         letter.setState(Letter.State.VISITING);
         for (Letter l : letter.getSibling())
         {
            if (!DFS(l, stack))
            {
               return false;
            }
         }
         letter.setState(Letter.State.VISITED);
         stack.push(letter);
      }
      return true;
   }

   public static void printStack(Stack<Letter> stack)
   {
      while (!stack.isEmpty())
      {
         System.out.print(stack.pop().getName());
         System.out.print(" ");
      }
   }

   public static void main(String[] args)
   {
      String[] dictionary = { "wrt", "wrf", "er", "ett", "rftt" };
      Graph graph = buildGraph(dictionary);
      Stack<Letter> stack = getOrder(graph);
      if (stack == null)
      {
         System.out.println("Circular error occurred;");
      }
      else
      {
         printStack(stack);
      }
   }
}

import java.util.ArrayList;
import java.util.HashMap;

public class Graph
{
   ArrayList<Letter> nodes = new ArrayList<Letter>();
   HashMap<Character, Letter> map = new HashMap<Character, Letter>();

   public Letter addOrCreateNode(char c)
   {
      if (!map.containsKey(c))
      {
         Letter node = new Letter(c);
         nodes.add(node);
         map.put(c, node);
      }
      return map.get(c);
   }

   public void addDependency(char c, char nextChar)
   {
      Letter letter = addOrCreateNode(c);
      Letter nextSibling = addOrCreateNode(nextChar);
      letter.addNextSibling(nextSibling);
   }

   public ArrayList<Letter> getNodes()
   {
      return this.nodes;
   }
}

import java.util.ArrayList;
import java.util.HashMap;

public class Letter
{
   public enum State
   {
      UNVISTITED, VISITING, VISITED
   };

   char name;
   ArrayList<Letter> smallSiblings = new ArrayList<Letter>();
   HashMap<Character, Letter> map = new HashMap<Character, Letter>();
   State state = State.UNVISTITED;

   public Letter(Character c)
   {
      this.name = c;
   }

   public char getName()
   {
      return this.name;
   }

   public State getState()
   {
      return this.state;
   }

   public void addNextSibling(Letter sibling)
   {
      if (!map.containsKey(sibling.getName()))
      {
         this.smallSiblings.add(sibling);
         this.map.put(sibling.getName(), sibling);
      }
   }

   public ArrayList<Letter> getSibling()
   {
      return this.smallSiblings;
   }

   public void setState(State state)
   {
      this.state = state;
   }
}