Coder
BAN USER
This will work on BST with time complexity of O(n) where n is the size of the tree.
private static boolean pathExist(String target, TreeNode treeNode) {
return pathExist(treeNode, target, false);
}
private static boolean pathExist(TreeNode treeNode, String target, boolean pathStarted) {
if (target.length() == 0)
return true;
if (treeNode == null) return false;
String dataAsString = String.valueOf(treeNode.data);
boolean targetStartsWithData = target.startsWith(dataAsString);
if (pathStarted && !targetStartsWithData) {
return false;
}
if (targetStartsWithData) {
pathStarted = true;
target = target.substring(dataAsString.length());
}
return pathExist(treeNode.left, target, pathStarted)
|| pathExist(treeNode.right, target, pathStarted);
}
Traverse the tree in in-order and while you're at it, decrement and track K. When K hits zero then sum N nodes (decrement N for each addition after K hits zero) and then short circuit once N reaches zero. Here's the implementation with runtime O(n+k):
public static int findNSumAfterK(TreeNode treeNode, int k, int n) {
CounterHolder counterHolder = new CounterHolder(k, n);
findSum(treeNode, counterHolder);
return counterHolder.sum;
}
private static void findSum(TreeNode treeNode, CounterHolder counterHolder) {
if (treeNode == null || counterHolder.n <= 0) return;
findSum(treeNode.left, counterHolder);
track(treeNode.data, counterHolder);
findSum(treeNode.right, counterHolder);
}
private static void track(int data, CounterHolder counterHolder) {
if (counterHolder.k == 0) {
if (counterHolder.n > 0) {
counterHolder.sum += data;
}
counterHolder.n--;
} else {
counterHolder.k--;
}
}
static class CounterHolder {
int k, n, sum;
public CounterHolder(int k, int n) {
this.k = k;
this.n = n;
}
}
static class TreeNode {
final int data;
TreeNode left;
TreeNode right;
TreeNode(int data) {
this.data = data;
}
}
This can be solved using BFS.
In this solution, findMinNumStepsBFS takes maze[][], which contains 0s and 1s (1 represents an obstacle), and row and column exit coordinates:
private static int findMinNumStepsBFS(int[][] maze, HashMap<Point, Integer> pathCache, int exitRow, int exitCol) {
LinkedList<PointStepsPair> bfsWorkQueue = new LinkedList<>();
PointStepsPair start = new PointStepsPair(new Point(0, 0), 0);
bfsWorkQueue.add(start);
pathCache.put(start.p, 0);
int leastNumberOfStepsToDestination = Integer.MAX_VALUE;
while (!bfsWorkQueue.isEmpty()) {
PointStepsPair pointStepsPair = bfsWorkQueue.pop();
if (pointStepsPair.p.row == exitRow && pointStepsPair.p.column == exitCol) {
leastNumberOfStepsToDestination = Math.min(pointStepsPair.steps, leastNumberOfStepsToDestination);
} else {
loadAdjacenciesIfNeeded(maze, bfsWorkQueue, pathCache, pointStepsPair);
}
}
if (leastNumberOfStepsToDestination == Integer.MAX_VALUE)
return -1;
return leastNumberOfStepsToDestination;
}
private static void loadAdjacenciesIfNeeded(int[][] maze, LinkedList<PointStepsPair> workingQueue, HashMap<Point, Integer> pathTaken, PointStepsPair pointStepsPair) {
int row = pointStepsPair.p.row;
int col = pointStepsPair.p.column;
int newSteps = pointStepsPair.steps + 1;
Point down = new Point(row + 1, col);
if (canMoveInDirection(maze, down)) {
updateCacheAndWorkingQueueIfNeeded(workingQueue, pathTaken, newSteps, down);
}
Point up = new Point(row - 1, col);
if (canMoveInDirection(maze, up)) {
updateCacheAndWorkingQueueIfNeeded(workingQueue, pathTaken, newSteps, up);
}
Point right = new Point(row, col + 1);
if (canMoveInDirection(maze, right)) {
updateCacheAndWorkingQueueIfNeeded(workingQueue, pathTaken, newSteps, right);
}
Point left = new Point(row, col - 1);
if (canMoveInDirection(maze, left)) {
updateCacheAndWorkingQueueIfNeeded(workingQueue, pathTaken, newSteps, left);
}
}
private static void updateCacheAndWorkingQueueIfNeeded(LinkedList<PointStepsPair> workingQueue, HashMap<Point, Integer> pathTaken, int newSteps, Point down) {
if (pathTaken.containsKey(down)) {
Integer steps = pathTaken.get(down);
if (steps > newSteps) {
workingQueue.add(new PointStepsPair(down, newSteps));
pathTaken.put(down, newSteps);
}
} else {
workingQueue.add(new PointStepsPair(down, newSteps));
pathTaken.put(down, newSteps);
}
}
private static boolean canMoveInDirection(int[][] maze, Point p) {
return p.row < maze.length && p.row >= 0 && p.column < maze[0].length && p.column >= 0 && maze[p.row][p.column] != 1;
}
static class PointStepsPair {
public Point p;
public int steps;
public PointStepsPair(Point p, int steps) {
this.p = p;
this.steps = steps;
}
}
public static class Point {
public int row, column;
public Point(int row, int column) {
this.row = row;
this.column = column;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
return row == point.row &&
column == point.column;
}
@Override
public int hashCode() {
return Objects.hash(row, column);
}
}
Suppose we have a city of a given length and width which we can represent as a grid (int[][]) and a list of locker points (x and y coordinates), then we can pre-compute the distance of the closest locker to each point in the grid:
private static int[][] getLockerDistanceGrid(int cityLength, int cityWidth, List<Point> lockerPositions) {
int[][] grid = new int[cityLength][cityWidth];
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
grid[row][col] = findClosestManhattanDistance(getCoordinate(row), getCoordinate(col), lockerPositions);
}
}
return grid;
}
private static int getCoordinate(int zeroBasedPosition) {
return zeroBasedPosition + 1;
}
private static int findClosestManhattanDistance(int x, int y, List<Point> lockerPositions) {
int closesDistance = Integer.MAX_VALUE;
for (Point p : lockerPositions) {
int distance = Math.abs(x - p.x) + Math.abs(y - p.y);
closesDistance = Math.min(distance, closesDistance);
// we know we can't get better than 0 distance
if (closesDistance == 0)
return closesDistance;
}
return closesDistance;
}
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
This can be solved either using iterative breadth or recursive depth first search.
// breadth first approach, O(N)
private static Stack<LinkedList<TreeNode>> createLevelLinkedListBFS(TreeNode root) {
Stack<LinkedList<TreeNode>> result = new Stack<>();
LinkedList<TreeNode> workingTree = new LinkedList<>();
workingTree.add(root);
while (!workingTree.isEmpty()) {
result.add(workingTree);
LinkedList<TreeNode> levelNodes = workingTree;
workingTree = new LinkedList<>();
for (TreeNode node : levelNodes) {
if (node.left != null) {
workingTree.add(node.left);
}
if (node.right != null) {
workingTree.add(node.right);
}
}
}
return result;
}
// depth first approach, O(N)
private static Stack<LinkedList<TreeNode>> createLevelLinkedListDFS(TreeNode root) {
ArrayList<LinkedList<TreeNode>> levelsList = new ArrayList<>();
createLevelLinkedListDFS(root, levelsList, 0);
Stack<LinkedList<TreeNode>> result = new Stack<>();
for (LinkedList<TreeNode> nodes : levelsList) {
result.push(nodes);
}
return result;
}
private static void createLevelLinkedListDFS(TreeNode root, ArrayList<LinkedList<TreeNode>> result, int level) {
if (result.size() == level) {
result.add(new LinkedList<>());
}
LinkedList<TreeNode> nodes = result.get(level);
nodes.add(root);
if (root.left != null) {
createLevelLinkedListDFS(root.left, result, level + 1);
}
if (root.right != null) {
createLevelLinkedListDFS(root.right, result, level + 1);
}
}
This can be solved two ways:
BFS solution using backtracking HashMap:
private static LinkedList<String> transformBFS(String start, String end, HashSet<String> dict) {
LinkedList<String> q = new LinkedList<>();
HashSet<String> visited = new HashSet<>();
Map<String, String> wordBackTrack = new HashMap<>();
q.add(start);
visited.add(start);
while (!q.isEmpty()) {
String currentWord = q.poll();
for (String neighbour : getOneEditAwayWords(currentWord, dict)) {
if (neighbour.equals(end)) {
LinkedList<String> path = new LinkedList<>();
path.add(neighbour);
while (currentWord != null) {
path.add(currentWord);
currentWord = wordBackTrack.get(currentWord);
}
return path;
}
if (!visited.contains(neighbour)) {
wordBackTrack.put(neighbour, currentWord);
q.add(neighbour);
visited.add(neighbour);
}
}
}
return null;
}
private static ArrayList<String> getOneEditAwayWords(String word, HashSet<String> dict) {
ArrayList<String> oneEditAwayWords = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String s = word.substring(0, i) + c + word.substring(i + 1);
if (dict.contains(s))
oneEditAwayWords.add(s);
}
}
return oneEditAwayWords;
}
Or using recursive DFS, the benefit of this is that we can utilise the recursion stack to do the backtracking:
private static LinkedList<String> transformDFS(String start, String end, HashSet<String> dict) {
return transformDFS(new HashSet<String>(), start, end, dict);
}
private static LinkedList<String> transformDFS(HashSet<String> visited, String start, String end, HashSet<String> dict) {
if (start.equals(end)) {
LinkedList<String> path = new LinkedList<>();
path.add(end);
return path;
}
if (visited.contains(start)) return null;
visited.add(start);
for (String v : getOneEditAwayWords(start, dict)) {
LinkedList<String> path = transformDFS(visited, v, end, dict);
if (path != null) {
path.add(start);
return path;
}
}
return null;
}
private static ArrayList<String> getOneEditAwayWords(String word, HashSet<String> dict) {
ArrayList<String> oneEditAwayWords = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String s = word.substring(0, i) + c + word.substring(i + 1);
if (dict.contains(s))
oneEditAwayWords.add(s);
}
}
return oneEditAwayWords;
}
O(a + b)
private static ListNode merge(ListNode a, ListNode b) {
ListNode result = null;
ListNode head = null;
while (a != null && b != null) {
ListNode newNode;
if (a.data < b.data) {
newNode = new ListNode(a.data);
a = a.next;
} else {
newNode = new ListNode(b.data);
b = b.next;
}
if (head == null) {
head = result = newNode;
} else {
result.next = newNode;
result = result.next;
}
}
while (a != null) {
ListNode newNode = new ListNode(a.data);
a = a.next;
if (head == null) {
head = result = newNode;
} else {
result.next = newNode;
result = result.next;
}
}
while (b != null) {
ListNode newNode = new ListNode(b.data);
b = b.next;
if (head == null) {
head = result = newNode;
} else {
result.next = newNode;
result = result.next;
}
}
return head;
}
private static class ListNode {
int data;
ListNode next;
private ListNode(int data) {
this.data = data;
}
}
private static ArrayList<Interval> mergeIntervals(ArrayList<Interval> a, ArrayList<Interval> b) {
ArrayList<Interval> result = new ArrayList<>();
int aIndex = 0;
int bIndex = 0;
while (aIndex < a.size() && bIndex < b.size()) {
Interval aInterval = a.get(aIndex);
Interval bInterval = b.get(bIndex);
if (!result.isEmpty() && (result.get(result.size() - 1).overlap(aInterval) || result.get(result.size() - 1).overlap(bInterval))) {
Interval previousResultInterval = result.get(result.size() - 1);
if (previousResultInterval.overlap(aInterval)) {
result.set(result.size() - 1, merge(previousResultInterval, aInterval));
aIndex++;
} else {
result.set(result.size() - 1, merge(previousResultInterval, bInterval));
bIndex++;
}
} else {
if (aInterval.before(bInterval)) {
result.add(aInterval);
aIndex++;
} else {
result.add(bInterval);
bIndex++;
}
}
}
while (aIndex < a.size()) {
result.add(a.get(aIndex));
aIndex++;
}
while (bIndex < b.size()) {
result.add(b.get(bIndex));
bIndex++;
}
return result;
}
private static Interval merge(Interval a, Interval b) {
if (a.overlap(b)) {
return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
}
return null;
}
private static class Interval {
final int start, end;
private Interval(int start, int end) {
this.start = start;
this.end = end;
}
private boolean overlap(Interval b) {
if ((start <= b.start && end >= b.start)
|| (b.start <= start && b.end >= start))
return true;
return false;
}
public boolean before(Interval other) {
return end < other.end;
}
@Override
public String toString() {
return "{" +
"start=" + start +
", end=" + end +
'}';
}
}
Solved this using DP.
private static int maxCoins(boolean[][] board) {
return maxCoinsHelper(board, 0, 0, new HashMap<>());
}
private static int maxCoinsHelper(boolean[][] board, int row, int col, HashMap<Point, Integer> cache) {
if (row == board.length || col == board[0].length)
return 0;
Point p = new Point(row, col);
if (cache.containsKey(p))
return cache.get(p);
int coinsCount = 0;
for (int dx = 1; dx + row < board.length; dx++) {
for (int dy = 1; dy + col < board[0].length; dy++) {
coinsCount = Math.max(coinsCount, maxCoinsHelper(board, row + dx, col + dy, cache));
}
}
coinsCount += board[row][col] ? 1 : 0;
cache.put(p, coinsCount);
return coinsCount;
}
In principal, every pair has the option to be part of the pair swap operation tree or not. We build an operation tree with and without a pair, then return the largest lexicographical string result. We continue doing so until we come across a combination of (pair+string) in the cache.
This is a brute force solution, but possibly acceptable for a 45 minute interview session.
private static String getLargestLexicographicalString(String str, ArrayList<Pair> pairs) {
return getLargestLexicographicalString(str, pairs, 0, new HashSet<>());
}
private static String getLargestLexicographicalString(String str, ArrayList<Pair> pairs, int index, HashSet<String> cache) {
// reset if index reaches pairs list size as we will
// keep trying until we get the highest lexicographical
// possible string (pair swapping can be reused).
if (index == pairs.size())
index = 0;
Pair pair = pairs.get(index);
// return if (string + pair) has been processed before
if (cache.contains(str + pair.toString()))
return str;
String swappedString = swap(str, pair);
// mark (string + pair) as visited
cache.add(str + pair.toString());
String withSwap = getLargestLexicographicalString(swappedString, pairs, index + 1, cache);
String withOutSwap = getLargestLexicographicalString(str, pairs, index + 1, cache);
return withSwap.compareTo(withOutSwap) > 0 ? withSwap : withOutSwap;
}
private static String swap(String s, Pair pair) {
char[] str = s.toCharArray();
char temp = str[pair.x];
str[pair.x] = str[pair.y];
str[pair.y] = temp;
return new String(str);
}
static class Pair {
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "x=" + x + ", y=" + y;
}
}
public class CommonManagerTopBottom {
static class Employee {
final String name;
List<Employee> reporters;
public Employee(final String name) {
this.name = name;
}
@Override
public String toString() {
return "Employee{" +
"name='" + name + '\'' +
'}';
}
}
public static Employee closestCommonManager(final Employee ceo, final Employee firstEmployee, final Employee secondEmployee) {
if (ceo == null || firstEmployee == null || secondEmployee == null)
return null;
if (!covers(ceo, firstEmployee) && covers(ceo, secondEmployee))
return null;
final Queue<Employee> workingQueue = new LinkedList<>();
workingQueue.offer(ceo);
Employee closestKnownManager = null;
while (!workingQueue.isEmpty()) {
Employee employee = workingQueue.poll();
if (covers(employee, firstEmployee) && covers(employee, secondEmployee)) {
closestKnownManager = employee;
for (Employee em : employee.reporters) {
workingQueue.offer(em);
}
}
}
return closestKnownManager;
}
public static boolean covers(final Employee manager, final Employee employee) {
if (manager == null)
return false;
if (manager.name.equals(employee.name))
return true;
if (manager.reporters == null)
return false;
boolean covers = false;
for (Employee em : manager.reporters) {
covers = covers || covers(em, employee);
}
return covers;
}
public static void main(String[] args) {
Employee samir = new Employee("samir");
Employee dom = new Employee("dom");
Employee michael = new Employee("michael");
Employee peter = new Employee("peter");
Employee porter = new Employee("porter");
Employee bob = new Employee("bob");
dom.reporters = Arrays.asList(bob, peter, porter);
Employee milton = new Employee("milton");
Employee nina = new Employee("nina");
peter.reporters = Arrays.asList(milton, nina);
Employee bill = new Employee("bill");
bill.reporters = Arrays.asList(dom, samir, michael);
System.out.println(closestCommonManager(bill, milton, nina));
System.out.println(closestCommonManager(bill, nina, porter));
System.out.println(closestCommonManager(bill, nina, samir));
System.out.println(closestCommonManager(bill, peter, nina));
}
}
- 80
Repjimbtam, Backend Developer at ASAPInfosystemsPvtLtd
I was extremely into photography for a number of years.My father was also interested in photography, so I was ...
- 10
Repnoradweisser, Backend Developer at ASU
I am Nora, I am a writer, I write many types blogs and articles. I collected many types and astrology ...
- 0
RepRobin Strain, Consultant
I am from New york. I am 26 year old. I work in a Central Hardware as a Worker compensation ...
- 10
Replillyalaird, Associate at Achieve Internet
I am Lilly from Eau Claire USA, I am working as a manager in a Best products company. My interest ...
- 0
Repjennifertkramer, AT&T Customer service email at ADP
I had a dream to open my own Restaurant in FL. and i came true all dream with my hard ...
- 10
Repdaysidbass, Junior programmer at AppPerfect
I have 5 years international experience working in the UK. I assist companies to gain greater value out of their ...
- 0
Repjohndbutler0, Aghori Mahakal Tantrik at BMO Harris Bank
I consider myself to be driven, proactive, hard working, a team player, creative and absolutely passionate person! I am strong ...
- 20
Repsusancmeans, Apple Phone Number available 24/7 for our Customers at Absolute Softech Ltd
I am Susan from Bronx, I am working as a Business management analyst in Brendle's company. I Have a ...
- 0
Repethelynfrose, Computer Scientist at 247quickbookshelp
Hello, I am Ethelyn and I live in Lake Worth, USA. I am working as a Dog Trainer and Dog ...
- 0
Replestermauldin, Assignment editor at Royal Gas
I am Lester Assignment editor . I am responsible for organizing the assignment desk to operate around the clock. I often ...
- 100
Repmakaylaangwin, Backend Developer at Abs india pvt. ltd.
I'm part owner of Bloom Floral Land, an Australian floral design company. Life is really short, try to smile ...
- 40
RepCarlERhodes, Cloud Support Associate at Baidu
I am an Engineering manager in Mosier USA. I am a freelance events coordinator and a lifetime entrepreneur. I want ...
Here is the solution in Kotlin, solved using depth-first traversal:
- Coder February 13, 2017object Worksheet { @JvmStatic fun main(args: Array<String>) { val projects = arrayOf("a", "b", "c", "d", "e", "f", "g", "h", "i", "j") val dependencies = arrayOf(arrayOf("a", "b"), arrayOf("b", "c"), arrayOf("a", "c"), arrayOf("d", "e"), arrayOf("b", "d"), arrayOf("e", "f"), arrayOf("a", "f"), arrayOf("h", "i"), arrayOf("h", "j"), arrayOf("i", "j"), arrayOf("g", "j")) val buildOrder = buildOrderWrapper(projects, dependencies) if (buildOrder.isEmpty()) { println("Circular Dependency.") } else { for (s in buildOrder) { println(s) } } } private fun buildOrderWrapper(projects: Array<String>, dependencies: Array<Array<String>>): Array<String> { val graph = buildGraph(projects, dependencies) val orderedProjects = Stack<Project>() graph.nodes.forEach { p -> if (!dfs(p, orderedProjects)) return emptyArray() } return Array(orderedProjects.size, { orderedProjects.pop().name }) } private fun dfs(p: Project, orderedProjects: Stack<Project>): Boolean { if (p.state == Project.State.PARTIAL) return false if (p.state == Project.State.BLANK) { p.state = Project.State.PARTIAL p.children.forEach { child -> if (!dfs(child, orderedProjects)) { return false } } orderedProjects.push(p) p.state = Project.State.COMPLETE } return true } private fun buildGraph(projects: Array<String>, dependencies: Array<Array<String>>): Graph { val graph = Graph() projects.forEach { s -> graph.getOrCreateNode(s) } dependencies.forEach { s -> graph.addEdge(s[0], s[1]) } return graph } class Graph { val nodes = ArrayList<Project>() private val map = HashMap<String, Project>() fun getOrCreateNode(name: String): Project { if (!map.containsKey(name)) { val node = Project(name) nodes.add(node) map.put(name, node) } return map[name] as Project } fun addEdge(startName: String, endName: String) { val start = getOrCreateNode(startName) val end = getOrCreateNode(endName) start.addNeighbor(end) } } class Project(val name: String) { val children = ArrayList<Project>() private val map = HashMap<String, Project>() var state = State.BLANK fun addNeighbor(node: Project) { if (!map.containsKey(node.name)) { children.add(node) map.put(node.name, node) } } enum class State { COMPLETE, PARTIAL, BLANK } } }