Detect Cycle in a Directed Graph

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true.

Solution
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.

import java.util.ArrayList;
import java.util.List;

public class Solution {
int n;
public List<List<Integer>> adjList = new ArrayList<>();

public Solution(int n) {
this.n = n;
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
}

public void addEdge(int from, int to) {
adjList.get(from).add(to);
}

public boolean hasCycle() {
boolean[] visited = new boolean[n];
boolean[] inStack = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfsCycle(i, visited, inStack)) {
return true;
}
}
}
return false;
}

private boolean dfsCycle(int start, boolean[] visited, boolean[] inStack) {
visited[start] = true;
inStack[start] = true;
for (int next : adjList.get(start)) {

if (!visited[start] && dfsCycle(next, visited, inStack)) {
return true;
} else if (inStack[next]) {
return true;
}
}
inStack[start] = false;
return false;
}

public static void main(String args[]) {
Solution g = new Solution(4);
g.addEdge(0, 1);
   g.addEdge(0, 2);
   g.addEdge(1, 2);
   g.addEdge(2, 0);
   g.addEdge(2, 3);
   g.addEdge(3, 3);
   System.out.println(g.hasCycle());
}
}

lowest common in multi-branch tree

给一个Employee类，有一个String name和一个List<Employee> directReport来表示一个公司的组织结构，然后给定一个公司的ceo和两个员工的名字，找到这两个员工的第一个common manager，给的两个员工一定存在。N-try tree的first common ancestor。楼主就用最naive的方法先找到从根到target节点的path然后在两个path中找第一个common ancestor。在电脑上写代码和测试样例，改掉测试样例的一个小bug之后通过。要求优化，说了用postorder traversal的方法来找，这样只需要遍历树一遍，说了一下整体的过程没有coding。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Solution {

public static class Employee {
List<Employee> employees;

String name;
int num;

public Employee(String name) {
this.name = name;
this.employees = new ArrayList<>();
}
}

private void outputTree(List<String> input) {
HashMap<String, Employee> map = new HashMap<>();
Employee head = null;
for (String entry : input) {
String tokens[] = entry.split("\\,");
Employee employee = map.get(tokens[0]);
if (employee == null) {
employee = new Employee(tokens[0]);
map.put(tokens[0], employee);
}
employee.num = Integer.parseInt(tokens[2]);
if (tokens[1].isEmpty()) {
head = employee;
continue;
}
Employee manager = map.get(tokens[1]);
if (manager == null) {
manager = new Employee(tokens[1]);
map.put(tokens[1], manager);
}
manager.employees.add(employee);
}
updateNum(head);
print(head, "");
}

private void print(Employee emp, String prefix) {
System.out.println(prefix + "" + emp.name + " " + emp.num);
StringBuilder sb = new StringBuilder();
for (char c : prefix.toCharArray()) {
if (c == '\\') {
sb.append(' ');
} else if (c != '_' && c != '-') {
sb.append(c);
}
}
for (int i = 0; i < emp.employees.size(); i++) {
Employee emp2 = emp.employees.get(i);
if (i != emp.employees.size() - 1) {
print(emp2, sb.toString() + "|-");
} else {
print(emp2, sb.toString() + "\\_");
}
}
}

private int updateNum(Employee emp) {
int res = emp.num;
for (Employee emp2 : emp.employees) {
res += updateNum(emp2);
}
emp.num = res;
return res;
}

public String getCommon(List<String> input, String name1, String name2) {
HashMap<String, Employee> map = new HashMap<>();
Employee head = null;
for (String entry : input) {
String tokens[] = entry.split("\\,");
Employee employee = map.get(tokens[0]);
if (employee == null) {
employee = new Employee(tokens[0]);
map.put(tokens[0], employee);
}
employee.num = Integer.parseInt(tokens[2]);
if (tokens[1].isEmpty()) {
head = employee;
continue;
}
Employee manager = map.get(tokens[1]);
if (manager == null) {
manager = new Employee(tokens[1]);
map.put(tokens[1], manager);
}
manager.employees.add(employee);
}

Employee common = getCommon(head, map.get(name1), map.get(name2));
return common.name;
}

private Employee getCommon(Employee root, Employee emp1, Employee emp2) {
if (root == emp1 || root == null || root == emp2) {
return root;
}
Employee find1 = null;
Employee find2 = null;
for (Employee child : root.employees) {
Employee find = getCommon(child, emp1, emp2);
if (find != null) {
if (find1 == null) {
find1 = find;
} else if (find2 == null) {
find2 = find;
}
}
}
if (find1 != null && find2 != null) {
return root;
} else {
return find1;
}
}

public static void main(String args[]) {
Solution s = new Solution();
List<String> list = Arrays.asList("Bob,Alice,3", "Carol,Bob,2",
"Richard,Carol,5", "Kim,Richard,5", "Tom,Carol,5",
"David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1", "Alice,,5",
"Chen,Eve,5", "Cen,Eve,2", "Eli,Cen,1", "Baba,Cen,2",
"Rui,Chen,2");
// List<String> list = Arrays.asList("Bob,Alice,3", "Alice,,5",
// "Cal,Alice,3");
// List<String> list = Arrays.asList("Alice,,5", "Bob,Alice,3",
// "Carol,Bob,2", "David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1");
s.outputTree(list);
System.out.println(s.getCommon(list, "Alice", "Tom"));
}
}

bigFloatAdd

稍微聊了下问了big float加法，中间有个compile error找了半天，找到以后有个小bug，改了下，大叔自己让我弄几个test case，测了下都过了，他自己测了下也没问题，然后就完了。又聊了一会，他说他希望new grad来了三个礼拜之内能ship feature。
解法：就是把一个float分成两部分，point之前的跟point之后的，然后用类似big int加法的做法做，先处理point之后的部分，然后处理之前的那部分，注意进位就行。

import java.util.Random;

public class Solution {

public String bigFloatAdd(String f1, String f2) {
String[] part1 = split(f1);
String[] part2 = split(f2);

StringBuilder floatSum = new StringBuilder();
int carry = addFloat(part1[1], part2[1], floatSum);
String integerSum = addInteger(part1[0], part2[0], carry);
return integerSum + "." + floatSum.reverse().toString();
}

private String[] split(String f1) {
int p1 = f1.indexOf(".");
String int1 = "";
String float1 = "";
if (p1 != -1) {
int1 = f1.substring(0, p1);
float1 = f1.substring(p1 + 1);
} else {
int1 = f1;
float1 = "";
}
return new String[]{int1, float1};
}

private int addFloat(String s1, String s2, StringBuilder sb) {
int len = Math.max(s1.length(), s2.length()) - 1;
int carry = 0;
while (len >= 0) {
int val = carry;
val += len < s1.length() ? s1.charAt(len) - '0' : 0;
val += len < s2.length() ? s2.charAt(len) - '0' : 0;
len--;
carry = val / 10;
sb.append(val % 10);
}
return carry;
}

private String addInteger(String s1, String s2, int carry) {
if (s1.isEmpty()) {
return s2;
}
if (s2.isEmpty()) {
return s1;
}
int i1 = s1.length() - 1;
int i2 = s2.length() - 1;
StringBuilder sb = new StringBuilder();
while (i1 >= 0 || i2 >= 0 || carry != 0) {
int val = carry;
val += i1 >= 0 ? s1.charAt(i1) - '0' : 0;
val += i2 >= 0 ? s2.charAt(i2) - '0' : 0;
carry = val / 10;
sb.append(val % 10);
i1--;
i2--;
}
return sb.reverse().toString();
}


public static void main(String args[]) {
Solution s = new Solution();
double d1 = 2.93;
double d2 = 107.08;
double sum = d1 + d2;
String strSum = s.bigFloatAdd(Double.toString(d1), Double.toString(d2));
System.out.println(d1 + "+" + d2 + "=" + sum + " == " + strSum);
}
}

pretty print organization

Employee,Manager,ItemsSold
Alice,,5
Bob,Alice,3. 1point 3acres 璁哄潧
Carol,Bob,2
Richard,Carol,5
Kim,Richard,5
Tom,Carol,5. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
David,Bob,3
Eve,Alice,2-google 1point3acres
Ferris,Eve,1
就是员工跟他的manager还有销售的item，之后输出下面的结构，数字表示该员工跟他下属的sold item总额. 1point 3acres 璁哄潧
Alice 31
|-Bob 23
| |-Carol 17
| | |-Richard 10
| | | \_Kim 5
| | \_Tom 5
| \_David 3
\_Eve 3
  \_Ferris 1
解法：这题略坑，算法就是先建图然后跑dfs，主要是output很恶心，output也是用dfs做的，当时写到最后还是差一些，这个output给大家一点参考吧，如果你的代码能输出上面那个例子，应该已经过了。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Solution {

public static class Employee {
List<Employee> employees;

String name;
int num;

public Employee(String name) {
this.name = name;
this.employees = new ArrayList<>();
}
}

private void outputTree(List<String> input) {
HashMap<String, Employee> map = new HashMap<>();
Employee head = null;
for (String entry : input) {
String tokens[] = entry.split("\\,");
Employee employee = map.get(tokens[0]);
if (employee == null) {
employee = new Employee(tokens[0]);
map.put(tokens[0], employee);
}
employee.num = Integer.parseInt(tokens[2]);
if (tokens[1].isEmpty()) {
head = employee;
continue;
}
Employee manager = map.get(tokens[1]);
if (manager == null) {
manager = new Employee(tokens[1]);
map.put(tokens[1], manager);
}
manager.employees.add(employee);
}
updateNum(head);
print(head, "");
}

private void print(Employee emp, String prefix) {
System.out.println(prefix + "" + emp.name + " " + emp.num);
StringBuilder sb = new StringBuilder();
for (char c : prefix.toCharArray()) {
if (c == '\\') {
sb.append(' ');
} else if (c != '_' && c != '-') {
sb.append(c);
}
}
for (int i = 0; i < emp.employees.size(); i++) {
Employee emp2 = emp.employees.get(i);
if (i != emp.employees.size() - 1) {
print(emp2, sb.toString() + "|-");
} else {
print(emp2, sb.toString() + "\\_");
}
}
}

private int updateNum(Employee emp) {
int res = emp.num;
for (Employee emp2 : emp.employees) {
res += updateNum(emp2);
}
emp.num = res;
return res;
}

public static void main(String args[]) {
Solution s = new Solution();
// List<String> list = Arrays.asList("Bob,Alice,3", "Carol,Bob,2",
// "Richard,Carol,5", "Kim,Richard,5", "Tom,Carol,5",
// "David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1", "Alice,,5",
// "Chen,Eve,5", "Cen,Eve,2", "Eli,Cen,1", "Baba,Cen,2", "Rui,Chen,2");
List<String> list = Arrays.asList("Bob,Alice,3", "Alice,,5","Cal,Alice,3");
// List<String> list = Arrays.asList("Alice,,5", "Bob,Alice,3",
// "Carol,Bob,2", "David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1");
s.outputTree(list);
}
}

bigint subtract

bigint subtract

import java.util.Random;

public class Solution {

public String sub(String str1, String str2) {

if (str1.length() < str2.length() || (str1.length() == str2.length() && str1.compareTo(str2) < 0)) {

return "-" + sub(str2, str1);

}

StringBuilder sb = new StringBuilder();

int i1 = str1.length() - 1;

int i2 = str2.length() - 1;

int carry = 0;

while (i1 >= 0 || i2 >= 0) {

int val = -carry;

val += i1 >= 0 ? (str1.charAt(i1) - '0') : 0;

val -= i2 >= 0 ? (str2.charAt(i2) - '0') : 0;

if (val < 0) {

carry = 1;

val += 10;

} else {

carry = 0;

}

sb.append(val);

i1--;

i2--;

}

return sb.reverse().toString();

}

public static void main(String args[]) {

Solution s = new Solution();

Random r = new Random();

int n1 = r.nextInt(100000000);

int n2 = r.nextInt(100000000);

String n3 = s.sub(Integer.toString(n1), Integer.toString(n2));

System.out.println((n1 + "-" + n2) + "=" + (n1 - n2) + "=" + Integer.parseInt(n3));

}

}

BigInt add

刚刚面完第二轮电面，原题 BigInt, 不过把详细一点的放在这里，和我的答案。// This is the text editor interface. 
// Anything you type or change here will be seen by the other person in real time.
. more info on 1point3acres.com
/*
* class BigInt, to represent non-negative integers of arbitrary size
        * constructor accept a String, representing this non-neg int (e.g. "50"), assume valid input    . visit 1point3acres.com for more.
        * needs to be able to add to another BigInt, and return their sum as a new BigInt object
        * immutable
            * new BigInt("20").add(new BigInt("30")) --> BigInt("50")

import java.util.Random;

public class Solution {

public String add(String str1, String str2) {

StringBuilder sb = new StringBuilder();

int i1 = str1.length() - 1;

int i2 = str2.length() - 1;

int carry = 0;

int base = 10;

while (i1 >= 0 || i2 >= 0 || carry != 0) {

int val = carry;

val += i1 >= 0 ? (str1.charAt(i1) - '0') : 0;

val += i2 >= 0 ? (str2.charAt(i2) - '0') : 0;

carry = val / base;

sb.append(val % base);

i1--;

i2--;

}

return sb.reverse().toString();

}

public static void main(String args[]) {

Solution s = new Solution();

Random r = new Random();

int n1 = r.nextInt(100000000);

int n2 = r.nextInt(100000000);

String n3 = s.add(Integer.toString(n1), Integer.toString(n2));

System.out.println((n1 + n2) == Integer.parseInt(n3));

}

}

compute 24

 24点游戏。给你几个数字，判断他们做加减乘除运算是否可以得到24，顺序可以是任意的。dfs搜索搞定。。。但是这里要注意一些细节，每次计算得到新的数之后最好加入数组做下一次搜索，不然容易出错。

public class Solution {

private boolean compute(int[] nums, int target) {

boolean[] visit = new boolean[nums.length];

return helper(nums, visit, target, nums.length);

}

private boolean helper(int[] nums, boolean[] visit, int target, int c) {

if (c == 1) {

for (int i = 0; i < nums.length; i++) {

if (!visit[i]) {

return nums[i] == target;

}

}

} else {

for (int i = 0; i < nums.length; i++) {

if (visit[i])

continue;

for (int j = i + 1; j < nums.length; j++) {

if (visit[j])

continue;

int n1 = nums[i];

int n2 = nums[j];

visit[j] = true;

nums[i] = n1 + n2;

if (helper(nums, visit, target, c - 1))

return true;

nums[i] = n1 - n2;

if (helper(nums, visit, target, c - 1))

return true;

nums[i] = n2 - n1;

if (helper(nums, visit, target, c - 1))

return true;

nums[i] = n1 * n2;

if (helper(nums, visit, target, c - 1))

return true;

if (n2 != 0) {

nums[i] = n1 / n2;

if (helper(nums, visit, target, c - 1))

return true;

}

if (n1 != 0) {

nums[i] = n2 / n1;

if (helper(nums, visit, target, c - 1))

return true;

}

nums[i] = n1;

visit[j] = false;

}

}

}

return false;

}

public static void main(String args[]) {

Solution s = new Solution();

System.out.println(s.compute(new int[] { 2, 3, 2, 1 }, 24));

}

}