Coding Interview - Useful Terms Cheatsheet
Big-O notation In simpler terms, its kind of a unit to measure how efficient an…
August 14, 2020
First try to understand question.
For Case-2, on finding that both nodes are on the same side. We will repeat our same algorithm going forward in that side only.
Lets see a code for this.
public class CommonAncestor {
public static class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
/**
* To check whether a node exists in a root element
*/
private boolean covers(Node root, Node toSearch) {
if (root == null || toSearch == null) {
return false;
}
if (root.data == toSearch.data) {
return true;
}
return this.covers(root.left, toSearch) || this.covers(root.right, toSearch);
}
private Node helper1(Node root, Node node1, Node node2) {
if (root == null) {
return null;
}
if (root.data == node1.data || root.data == node2.data) {
return root;
}
boolean firstNodeFoundOnLeft = this.covers(root.left, node1);
boolean firstNodeFoundOnRight = this.covers(root.left, node2);
if (firstNodeFoundOnLeft != firstNodeFoundOnRight) {
//both are on different sides. Found result.
return root;
}
//both are on the same side.
return this.helper1(firstNodeFoundOnLeft ? root.left : root.right,
node1, node2);
}
public Node findCommonAncestor_1(Node root, Node node1, Node node2) {
if (!this.covers(root, node1) || !this.covers(root, node2)) {
//one or both nodes are not in the tree
System.out.println("Not covered");
return null;
}
return this.helper1(root, node1, node2);
}
}
helper1(root, node1, node2)
The function calls recursively, and same code repeats.
Consider the tree to be balanced tree.
covers()
is called twice. So, its 2 times O(n)
, which computes to O(n)
helper1()
function gets called on branches one time for each node.
2 * n/2 for both nodes.
Which comes out to be: 2n/2 + 2n/4 + 2n/8 ~= O(logn)
Total complexity of this code is O(n)
Big-O notation In simpler terms, its kind of a unit to measure how efficient an…
Problem Implement an algorithm to determine if a string has all the characters…
Problem Statement You are given two non-empty linked lists representing two non…
Introduction I will list some of the interesting usage of bitwise operators…
Problem Statement Roman numerals are represented by seven different symbols: I…
Here are some tips while preparing for your coding interviews. 1. Do study or…
Introduction This post has the complete code to send email through smtp server…
Introduction In a normal email sending code from python, I’m getting following…
Introduction In one of my app, I was using to talk to . I have used some event…
Introduction So you have a Django project, and want to run it using docker image…
Introduction It is very important to introduce few process so that your code and…
Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…