Linkedin Interview Question for Senior Software Development Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

``````class TournamentTree {
/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Node root) {
if(root.left == null && root.right == null) {
return Integer.MAX_VALUE;
}
Node node;
int min;
if(root.left.value == root.value) {
node = root.left;
min = root.right.value;
} else {
node = root.right;
min = root.left.value;
}
return Math.min(min, secondMin(node));
}
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

Do we really have to recurse to left or right child node to find Min? I mean, if root is the current minimum of the tree, then either left or right child will be the 2nd minimum. So, why to go down? Some additional example trees will be helpful.

Comment hidden because of low score. Click to expand.
0

Try this one : 1, 2, 3, 4, 5, 6, 7, 8.

Here 1 and 2 will compete first and 2 will be sitting on the leaf level. Unless we recurse all the way down we will not find 2. Basically we are trying to find all the competitors of (1) that lost to (1) and find the min of those losers.

Comment hidden because of low score. Click to expand.
0

How is that tree valid? Isn't the property of the tree that at each root it contains the min of its children. None of those nodes are the min of their children. Unless I'm missing something?

Comment hidden because of low score. Click to expand.
1
of 1 vote

It's a min heap.
Solution -
1 Delete min
2 Move last element to top and adjust heap.
3 Repeat step 2 if new min is same as old min.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int FindSecondMinimun(Node *node, int smallest)
{
if ((node->left == nullptr) || (node->data > smallest))
{
return node->data;
}

int left_data = FindSecondMinimun(node->left, node->data);
int right_data = FindSecondMinimun(node->right, node->data);

// Not 100% std::min is a thing but i think it is =P
return std::min(left_data, right_data);
}

int FindSecondMinimun(Node *node)
{
if (node == nullptr)
{
throw new Exception("Invalid Parameter");
}

int left = FindSecondMinimun(node->left, node->data);
int right = FindSecondMinimun(node->right, node->data);
return std::min(left, right);
}

// Then we just FindSecondMinimun(Node*) from the root node.
int result = FindSecondMinimun(tree);

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SecondMinElement {

public static void main(String[] args) {
BTN N7 = new BTN(3, null, null);
BTN N6 = new BTN(5, null, null);
BTN N5 = new BTN(2, null, null);
BTN N4 = new BTN(4, null, null);
BTN N3 = new BTN(3, N6, N7);
BTN N2 = new BTN(2, N4, N5);
BTN N1 = new BTN(2, N2, N3);

int[] arr = new int[2];
arr[0] = Integer.MAX_VALUE;
arr[1] = Integer.MAX_VALUE;
int[] res = getMin(N1, arr);
System.out.println("Second min - " + res[1]);
}

static int[] getMin(BTN node, int[] arr){
if(node == null) return arr;
arr = getMin(node.left, arr);
arr = getMin(node.right, arr);
if(node.val < arr[0]){
arr[0] = node.val;
}if(node.val < arr[1] && node.val > arr[0]){
arr[1] = node.val;
}
return arr;
}

}
class BTN{
int val;
BTN left;
BTN right;
public BTN(int val, BTN left, BTN right) {
super();
this.val = val;
this.left = left;
this.right = right;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution {
public static Integer secondMin(Note root) {
if(root->left != null {
if(root->left->value == root->value) {
return root->right->value;
}
else {
return root->left->value;
}
}
return root->value;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Implementation in C:

``````int FindSecMin(Node *n)
{
if(n == NULL)
return -1;
else if( !n->left)
return -1;
else
{
Node *left_child = n->left;
Node * right_child = n->right;
return(left_child->data > right_child->data? left_child->data:right_child->data);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

``````1. If leaf node, then return
2. Hold on larger child and go down the smaller one
3. If either of the value in 2 is same as node, then return other value; else return min``````

``````private static Node getSecondMin(Node node){
if(node.left==null && node.right==null) return node;
Node n1, n2;
if(node.left.val == node.val){
n1 = node.right;
n2 = getSecondMin(node.left);
} else {
n1 = node.left;
n2 = getSecondMin(node.right);
}
if(n1.val == node.val) return n2;
if(n2.val == node.val) return n1;
return n1.val < n2.val ? n1 : n2;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static Node getSecondMin(Node node){
if(node.left==null && node.right==null) return node;
Node n1, n2;
if(node.left.val == node.val){
n1 = node.right;
n2 = getSecondMin(node.left);
} else {
n1 = node.left;
n2 = getSecondMin(node.right);
}
if(n1.val == node.val) return n2;
if(n2.val == node.val) return n1;
return n1.val < n2.val ? n1 : n2;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public Integer secondMin(int minValue, int secondMinValue) {
if (value < minValue) {
secondMinValue = minValue;
minValue = value;
} else if (value < secondMinValue && value > minValue) {
secondMinValue = value;
}

if (leftNode != null) {
return leftNode.secondMin(minValue, secondMinValue);
}

if (rightNode != null) {
return rightNode.secondMin(minValue, secondMinValue);
}

return secondMinValue;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do we really have to recurse to left or right child node to find Min? I mean, if root is the current minimum of the tree, then either left or right child will be the 2nd minimum. So, why to go down? Some additional example trees will be helpful.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int getSecondMin(Node root){

if(root != null && root.left !=null){
if(root.left.val == root.val){
return Math.min(root.right.val, getSecondMin(root.left));
}else{
return Math.min(root.left.val, getSecondMin(root.right));
}
}else{
return Integer.MAX_VALUE;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ok, my solution in php.

class Solution{

public function secondMin(\$root){
if (\$root===null)
return null;
if (\$root->left===null)
return \$root->value;
\$left=\$this->secondMin2(\$root->left,\$root->value);
\$right=\$this->secondMin2(\$root->right, \$root->value);
if (\$root->value<\$left && \$root->value<\$right)
return min(\$left,\$right);
return max(\$left,\$right);

}

public function secondMin2(\$root, \$min ) {

if ( \$root->left ===null || \$root->value > \$min ) //var_dump(\$root);
return \$root->value;
\$left=\$this->secondMin2(\$root->left,\$min);
\$right=\$this->secondMin2(\$root->right,\$min);
if (\$min < \$left && \$min < \$right)
return min(\$left,\$right);
return max(\$left,\$right);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

In PHP:

``````class Solution{

public function secondMin(\$root){
if (\$root===null)
return null;
if (\$root->left===null)
return \$root->value;
\$left=\$this->secondMin2(\$root->left,\$root->value);
\$right=\$this->secondMin2(\$root->right, \$root->value);
if (\$root->value<\$left && \$root->value<\$right)
return min(\$left,\$right);
return max(\$left,\$right);

}//function nodeRoot
public function secondMin2(\$root, \$min )  {

if ( \$root->left ===null || \$root->value > \$min ) 	//var_dump(\$root);
return \$root->value;
\$left=\$this->secondMin2(\$root->left,\$min);
\$right=\$this->secondMin2(\$root->right,\$min);

if (\$min < \$left && \$min < \$right)
return min(\$left,\$right);
return max(\$left,\$right);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution{

public function secondMin(\$root){
if (\$root===null)
return null;
if (\$root->left===null)
return \$root->value;
\$left=\$this->secondMin2(\$root->left,\$root->value);
\$right=\$this->secondMin2(\$root->right, \$root->value);
if (\$root->value<\$left && \$root->value<\$right)
return min(\$left,\$right);
return max(\$left,\$right);

}
public function secondMin2(\$root, \$min )  {

if ( \$root->left ===null || \$root->value > \$min )
return \$root->value;
\$left=\$this->secondMin2(\$root->left,\$min);
\$right=\$this->secondMin2(\$root->right,\$min);

if (\$min < \$left && \$min < \$right)
return min(\$left,\$right);
return max(\$left,\$right);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{}}} {{{class Solution{}}} {{{ }}} {{{ public function secondMin(\$root){}}} {{{ if (\$root===null)}}} {{{ return null;}}} {{{ if (\$root->left===null)}}} {{{ return \$root->value;}}} {{{ \$left=\$this->secondMin2(\$root->left,\$root->value);}}} {{{ \$right=\$this->secondMin2(\$root->right, \$root->value);}}} {{{ if (\$root->value<\$left && \$root->value<\$right)}}} {{{ return min(\$left,\$right);}}} {{{ return max(\$left,\$right);}}} {{{ {{{ }}}} {{{ public function secondMin2(\$root, \$min ) { }}} {{{ if ( \$root->left ===null || \$root->value > \$min )}}} {{{ return \$root->value;}}} {{{ \$left=\$this->secondMin2(\$root->left,\$min);}}} {{{ \$right=\$this->secondMin2(\$root->right,\$min);}}} {{{ if (\$min < \$left && \$min < \$right)}}} {{{ return min(\$left,\$right);}}} {{{ return max(\$left,\$right);}}} {{{ }}}} {{{{}}}
Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution{

public function secondMin(\$root){
if (\$root===null)
return null;
if (\$root->left===null)
return \$root->value;
\$left=\$this->secondMin2(\$root->left,\$root->value);
\$right=\$this->secondMin2(\$root->right, \$root->value);

if (\$root->value<\$left && \$root->value<\$right)
return min(\$left,\$right);
return max(\$left,\$right);

}
public function secondMin2(\$root, \$min )  {

if ( \$root->left ===null || \$root->value > \$min )
return \$root->value;
\$left=\$this->secondMin2(\$root->left,\$min);
\$right=\$this->secondMin2(\$root->right,\$min);

if (\$min < \$left && \$min < \$right)
return min(\$left,\$right);
return max(\$left,\$right);
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````1
/    \
1      3
/  \    /  \
1   2  3  4``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* This should return the minimum
* int value in the given tournament tree
*/
public static Integer findMin(Tree root, int min, int secondmin) {
if(root.left == null && root.right == null)
return min;

min = Math.min(min, root.value);
return Math.min(findMin(root.left, min, secondmin), findMin(root.right, min, secondmin));
}

/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Tree root, int min, int secondmin) {

if(root == null) {
return secondmin;
}

if (root.value > min && root.value < secondmin) {
secondmin = root.value;
}

return Math.min(secondMin(root.left, min, secondmin), secondMin(root.right, min, secondmin));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* This should return the minimum
* int value in the given tournament tree
*/
public static Integer findMin(Tree root, int min, int secondmin) {
if(root.left == null && root.right == null)
return min;

min = Math.min(min, root.value);
return Math.min(findMin(root.left, min, secondmin), findMin(root.right, min, secondmin));
}

/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Tree root, int min, int secondmin) {

if(root == null) {
return secondmin;
}

if (root.value > min && root.value < secondmin) {
secondmin = root.value;
}

return Math.min(secondMin(root.left, min, secondmin), secondMin(root.right, min, secondmin));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* This should return the minimum
* int value in the given tournament tree
*/
public static Integer findMin(Tree root, int min, int secondmin) {
if(root.left == null && root.right == null)
return min;

min = Math.min(min, root.value);
return Math.min(findMin(root.left, min, secondmin), findMin(root.right, min, secondmin));
}

/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Tree root, int min, int secondmin) {

if(root == null) {
return secondmin;
}

if (root.value > min && root.value < secondmin) {
secondmin = root.value;
}

return Math.min(secondMin(root.left, min, secondmin), secondMin(root.right, min, secondmin));``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* This should return the minimum
* int value in the given tournament tree
*/
public static Integer findMin(Tree root, int min, int secondmin) {
if(root.left == null && root.right == null)
return min;

min = Math.min(min, root.value);
return Math.min(findMin(root.left, min, secondmin), findMin(root.right, min, secondmin));
}

/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Tree root, int min, int secondmin) {

if(root == null) {
return secondmin;
}

if (root.value > min && root.value < secondmin) {
secondmin = root.value;
}

return Math.min(secondMin(root.left, min, secondmin), secondMin(root.right, min, secondmin));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class SecondMinimum {
int min = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
public void secMin(TreeNode root) {
if(root != null) {
if(root.data <= min) {
min2 = min;
min = root.data;
}
secMin(root.left);
secMin(root.right);
}
return min2;
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.