Euihoon Seol
BAN USERuse bfs/level order traversal while keeping track of a distance from a root. If the first occurence of each number of the given array is found, update the result array with the current distance.
time O(n) where n is the total number of nodes in a tree
space O(Math.max(k, n)) where k is the total number of elements in an array.
public static int[] getDistanceFromRoot(Node head, int[] arr) {
int[] result = new int[arr.length];
for (int i = 0; i < result.length; ++i) {
result[i] = -1;
}
HashMap<Integer, Integer> hm = new HashMap<>();
for (int j = 0; j < arr.length; ++j) {
hm.put(arr[j], j);
}
Queue<Node> q = new LinkedList<>();
q.add(head);
int level = 0;
while (!q.isEmpty()) {
int size = q.size();
while (size > 0) {
Node temp = q.remove();
if (hm.containsKey(temp.val) && result[hm.getValue(temp.val)] == -1) {
result[hm.get(temp.val)] = level;
}
--size;
}
++level;
}
return result;
}
// recursive
class WordDictionary {
class Node {
Node[] letters;
boolean endOfWord;
public Node() {
letters = new Node[26];
endOfWord = false;
}
}
Node head;
/** Initialize your data structure here. */
public WordDictionary() {
head = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
if (word == null) {
return;
}
addWordUtil(word, 0, word.length() - 1, head);
return;
}
public void addWordUtil(String word, int currIdx, int endIdx, Node n) {
if (currIdx < endIdx) {
if (n.letters[word.charAt(currIdx) - 'a'] == null) {
n.letters[word.charAt(currIdx) - 'a'] = new Node();
}
addWordUtil(word, currIdx + 1, endIdx, n.letters[word.charAt(currIdx) - 'a']);
}
else if (currIdx == endIdx) {
if (n.letters[word.charAt(currIdx) - 'a'] == null) {
n.letters[word.charAt(currIdx) - 'a'] = new Node();
}
n.letters[word.charAt(currIdx) - 'a'].endOfWord = true;
}
return;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
if (word == null) {
return false;
}
// dfs - recursive
return searchUtil(word, 0, word.length() - 1, head);
}
public boolean searchUtil(String word, int currIdx, int endIdx, Node currNode) {
if (currIdx < endIdx) {
if (word.charAt(currIdx) == '.') {
for (Node letter : currNode.letters) {
if (letter != null && searchUtil(word, currIdx + 1, endIdx, letter)) {
return true;
}
}
}
else {
if (currNode.letters[word.charAt(currIdx) - 'a'] == null) {
return false;
}
else {
return searchUtil(word, currIdx + 1, endIdx, currNode.letters[word.charAt(currIdx) - 'a']);
}
}
}
else if (currIdx == endIdx) {
if (word.charAt(currIdx) == '.') {
for (Node letter : currNode.letters) {
if (letter != null && letter.endOfWord) {
return true;
}
}
}
else {
if (currNode.letters[word.charAt(currIdx) - 'a'] != null && currNode.letters[word.charAt(currIdx) - 'a'].endOfWord) {
return true;
}
}
}
return false;
}
}
// iterative : add commas from the left most while counting the number of commas added.
// time O(n) space O(1) where n is the number of characters in a given string s
public static String returnWithCommas (String s) {
if (s == null || s.length() <= 3) {
return s;
}
int countCommas = 0;
int remain = s.length() % 3;
int strIdx = 0;
s = s.substring(strIdx, strIdx + remain) + "," + s.substring(strIdx + remain);
++countCommas;
strIdx += (remain + countCommas);
while (strIdx < s.length() - 1) {
s = s.substring(strIdx, strIdx + 3) + "," + s.substring(strIdx + 3);
++countCommas;
strIdx += 3;
}
return s;
}
// recursive : recursively chop the string up every three characters and add a commas
// time O(n) space O(1)
public static String returnWithCommas (String s) {
if (s == null || s.length() < 4) {
return s;
}
int remain = s.length() % 3;
return s.substring(0, remain) + "," + returnWithCommasUtil(s, remain);
}
public static String returnWithCommasUtil (String s, int strIdx) {
if (strIdx >= s.length() - 1) {
return s.substring(strIdx);
}
return s.substring(strIdx, 3) + "," + returnWithCommasUtil(s, strIdx + 3);
}
iterate a given array while keeping track of max consecutive 1s so far and counting running consecutive 1s. Compare max so far and running num.
iterate the input array by counting the number of zeros.
/*
use a Trie structure where each node has a character and has a list of nodes.
*/
// iterative
class WordDictionary {
class Node {
Node[] letters;
boolean endOfWord;
public Node() {
letters = new Node[26];
endOfWord = false;
}
}
Node head;
/** Initialize your data structure here. */
public WordDictionary() {
head = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
if (word == null) {
return;
}
Node temp = head;
for (int i = 0; i < word.length(); ++i) {
if (temp.letters[word.charAt(i) - 'a'] == null) {
temp.letters[word.charAt(i) - 'a'] = new Node();
}
temp = temp.letters[word.charAt(i) - 'a'];
if (i == word.length() - 1) {
temp.endOfWord = true;
}
}
return;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
if (word == null) {
return false;
}
// bfs - iterative
Queue<Node> q = new LinkedList<>();
q.add(head);
for (int i = 0; i < word.length(); ++i) {
int size = q.size();
if (size == 0) {
return false;
}
if (word.charAt(i) == '.') {
while (size > 0) {
Node temp = q.remove();
Node[] tempLetters = temp.letters;
for (Node letter : tempLetters) {
if (letter != null) {
q.add(letter);
}
}
--size;
}
}
else {
while (size > 0) {
Node temp = q.remove();
Node[] tempLetters = temp.letters;
if (tempLetters[word.charAt(i) - 'a'] != null) {
q.add(tempLetters[word.charAt(i) - 'a']);
}
--size;
}
}
}
while (!q.isEmpty()) {
Node temp = q.remove();
if (temp.endOfWord) {
return true;
}
}
return false;
}
}
/*
i1 * i2
int result = 0;
add i1 to result i2 times.
*/
public int multiple (int i1, int i2) {
int i = 0;
int result = 0;
while (i2 > i) {
result = add(result, i1);
i = add(i, 1);
}
return result;
}
public int add(int i1, int i2) {
// iterate until there is no carry
while (i2 != 0) {
// carry contains common set bits of i1 and i2
int carry = i1 & i2;
// sum of bits of i1 and i2 where at least either of i1 and i2 bits is 0
i1 = i1 ^ i2;
// carry is shifted by one so that adding it to i1 gives the required sum
i2 = carry << 1;
}
return i1;
}
/*
iterative : use a stack
time O(n)
space O(n)
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
levelOrderUtil(root, result);
return result;
}
private void levelOrderUtil(TreeNode node, List<List<Integer>> result) {
if (node == null) {
return;
}
Stack<Node> s = new Stack<>();
Node temp = new Node(node, 0);
s.push(temp);
while (!s.empty()) {
temp = s.pop();
if (result.size() < temp.level + 1) {
result.add(new LinkedList<Integer>());
}
result.get(temp.level).add(temp.tn.val);
if (temp.tn.right != null) {
s.push(new Node(temp.tn.right, temp.level + 1));
}
if (temp.tn.left != null) {
s.push(new Node(temp.tn.left, temp.level + 1));
}
}
return;
}
class Node {
TreeNode tn;
int level;
public Node(TreeNode tn, int level) {
this.tn = tn;
this.level = level;
}
}
}
level order using dfs
recursive : recursively call left child first and right child next while adding visited nodes to result.
time O(n)
space O(n)
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
levelOrderUtil(root, 0, result);
return result;
}
private static void levelOrderUtil(TreeNode node, int level, List<List<Integer>> result) {
if (node == null) {
return;
}
if (result.size() < level + 1) {
result.add(new LinkedList<Integer>());
}
result.get(level).add(node.val);
levelOrderUtil(node.left, level + 1, result);
levelOrderUtil(node.right, level + 1, result);
return;
}
}
/*
iterative : search a given node by using a queue. Once found, use a stack to iterate through the trie. Add currently visited node to the stack. pop it out, add it to the result list and add its children back to the stack in a reverse order.
time O(n) where n is total number of nodes in a trie
space O(n) in the worst case when a trie is two-level
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> result = new LinkedList<>();
Node target = new Node(3);
root = findNode(root, target, result);
preorderUtil(root, result);
return result;
}
private Node findNode(Node node, Node target, List<Integer> result) {
if (node.val == target.val) {
return node;
}
Queue<Node> q = new LinkedList<>();
q.add(node);
while (!q.isEmpty()) {
Node temp = q.remove();
if (temp.val == target.val) {
return temp;
}
else {
List<Node> children = temp.children;
for (Node child : children) {
q.add(child);
}
}
}
return null;
}
private void preorderUtil(Node node, List<Integer> result) {
Stack<Node> s = new Stack<>();
s.push(node);
while (!s.empty()) {
Node temp = s.pop();
result.add(temp.val);
List<Node> children = temp.children;
Stack<Node> tempS = new Stack<>();
for (Node child : children) {
tempS.push(child);
}
while (!tempS.empty()) {
s.push(tempS.pop());
}
}
return;
}
}
/*
recursive solution : search a given node. Once found, add a currently visited node to result and call a method itself recursively for every child of its children. Repeat the steps until it visits all the nodes.
time O(n) where n is the total number of nodes in a n-ary tree/trie.
space O(n) in the worst case when a trie is left-skewed and a call stack would have n number of method calls.
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> result = new LinkedList<>();
Node target = new Node(3);
root = findNode(root, target, result);
preorderUtil(root, result);
return result;
}
private Node findNode(Node node, Node target, List<Integer> result) {
if (node.val == target.val) {
return node;
}
Queue<Node> q = new LinkedList<>();
q.add(node);
while (!q.isEmpty()) {
Node temp = q.remove();
if (temp.val == target.val) {
return temp;
}
else {
List<Node> children = temp.children;
for (Node child : children) {
q.add(child);
}
}
}
return null;
}
private void preorderUtil(Node node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
List<Node> children = node.children;
for (Node child : children) {
preorderUtil(child, result);
}
return;
}
}
Sys Requirements
the system does not allow more vehicles than the maximum capacity of the parking lot. if the parking is full, show a message at the entrance panels on the ground floor.
each parkingLot has floors
each parkingLot has multiple entry and exit points
customers collect a parking ticket from entry points and pay the parking fee at the exit points or customer info portal
customers pay via both cash and credit cards
multiple floors
each floor has spots
each floor has counter screen
each spot has a type (motorcycle, compact, large, handicapped...)
the parking lot has some spots for electric cars. These spots have an electric panel for customers to pay
the system has a per-hour parking model (1st hour = $3, 2nd hour = $2, all the remaining hours = $1.5)
if we assume that the skewed tree is a tree where all the nodes has either of one child or no child. The probability at t is 1 (as long as it has a child to go down or is a leaf) or 0 (if a current node is null).
- Euihoon Seol October 18, 2020If the tree is a binary tree, calculate the probability by multiplying the number of children of a current node.
If three is n-ary, multiply the number of children of a current node.
If it is now a directed acyclic graph, multiply the number of connected neighborhood of a current node.