Hot Topics
Linkedin Solution
Technical Round
Find the second largest element in a Binary Search Tree.
The second largest element in a Binary Search Tree can be found by traversing the tree in the following steps:
Start by initializing a variable to store the current node, and set it to the root of the tree.
If the current node has a right child, move to the right child, and continue this step until the current node does not have a right child. This will lead you to the largest element in the tree.
If the current node does not have a right child, it must be the parent of the largest element, which was previously a left child. The second largest element is the largest element in the left subtree of the current node. To find the largest element in the left subtree, traverse the tree to the rightmost node in the left subtree.
Note: If the tree has only one node, the largest and second largest elements are the same and equal to the only node in the tree. If the tree has two nodes, the largest element is the root, and the second largest element is the left child.
Describe a routine which returns the set of integers in {1..100} divisible without remainder by 3 but not by 9.
One possible routine to accomplish this task is to use a loop to iterate through the numbers in the range {1..100}, and use an if statement to check if each number is divisible by 3 but not by 9. Here’s an example in Python:
def divisible_by_3_not_9(numbers):
result = set()
for num in numbers:
if num % 3 == 0 and num % 9 != 0:
result.add(num)
return result
numbers = range(1, 101)
result = divisible_by_3_not_9(numbers)
print(result)This routine takes a range of numbers as input and returns a set of integers in that range that are divisible by 3 but not by 9.
Find median of an infinite stream of integers in O(1) time.
Finding the median of an infinite stream of integers in constant time is not possible because an infinite stream does not have a finite number of elements, so you cannot determine the median by simply sorting the elements or counting the number of elements.
However, you can use a data structure called a “median heap” to keep track of the median of the stream in constant time. A median heap consists of two heaps: a max-heap to store the smaller half of the elements and a min-heap to store the larger half of the elements. Each time a new element is added to the stream, it can be inserted into the appropriate heap to maintain the balance between the two heaps.
The median can then be easily determined as the root of the max-heap if the number of elements is odd, or the average of the roots of the two heaps if the number of elements is even.
Here’s an example implementation in Python:
import heapq
class MedianHeap:
def __init__(self):
self.max_heap = []
self.min_heap = []
def add_element(self, element):
if len(self.max_heap) == 0 or element <= -self.max_heap[0]:
heapq.heappush(self.max_heap, -element)
else:
heapq.heappush(self.min_heap, element)
if len(self.max_heap) > len(self.min_heap) + 1:
heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
elif len(self.min_heap) > len(self.max_heap):
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
def get_median(self):
if len(self.max_heap) == len(self.min_heap):
return (-self.max_heap[0] + self.min_heap[0]) / 2
else:
return -self.max_heap[0]
median_heap = MedianHeap()
median_heap.add_element(1)
median_heap.add_element(2)
median_heap.add_element(3)
median_heap.add_element(4)
median = median_heap.get_median()
print(median)
/*
Output: 2.5
*/
This implementation allows you to find the median of an infinite stream of integers in constant time for each new element added to the stream.
Write a function that, given a list of integers (both positive and negative) returns the sum of the contiguous subsequence with maximum sum. Thus, given the sequence (1, 2, -4, 1, 3, -2, 3, -1) it should return 5.
One common approach to solve this problem is to use dynamic programming. The idea is to keep track of the maximum sum ending at each position and use that information to determine the maximum sum of any contiguous subsequence.
Here’s an implementation in Python:
def max_sum_contiguous_subsequence(numbers):
max_sum = float("-inf")
current_sum = 0
for num in numbers:
current_sum = max(current_sum + num, num)
max_sum = max(max_sum, current_sum)
return max_sum
numbers = [1, 2, -4, 1, 3, -2, 3, -1]
result = max_sum_contiguous_subsequence(numbers)
print(result)
/*
OUTPUT 5
*/This function iterates through the list of numbers and updates the current_sum variable with the maximum sum ending at each position. The maximum sum of any contiguous subsequence is the maximum value of current_sum encountered during the iteration. The time complexity of this solution is O(n), where n is the length of the input list.
Search a sorted array for the first element larger than k.
To search a sorted array for the first element larger than a given value k, you can use binary search. The basic idea is to divide the array in half repeatedly until you find the desired element or determine that it does not exist.
Here’s an implementation in Python:
def search_first_larger_than(numbers, k):
left, right = 0, len(numbers) - 1
while left <= right:
mid = (left + right) // 2
if numbers[mid] <= k:
left = mid + 1
else:
right = mid - 1
return left if left < len(numbers) else -1
numbers = [1, 2, 3, 4, 5, 6, 7]
result = search_first_larger_than(numbers, 4)
print(result)
/*
OUTPUT _ - 5
*/This implementation uses a binary search loop to repeatedly divide the array in half. If the middle element is less than or equal to k, the search continues in the right half of the array. If the middle element is greater than k, the search continues in the left half of the array. The loop terminates when the left pointer is greater than the right pointer, which indicates that the desired element is not in the array. The time complexity of this solution is O(log n), where n is the length of the input array.
Print binary tree level by level.
To print a binary tree level by level, you can use a breadth-first search (BFS) approach. One way to implement BFS is to use a queue to keep track of the nodes at each level.
Here’s an implementation in Python using a tree node class:
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def print_level_by_level(root):
if root is None:
return
queue = [root]
while queue:
level_size = len(queue)
for i in range(level_size):
current = queue.pop(0)
print(current.val, end=" ")
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
print()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print_level_by_level(root)
/*
1
2 3
4 5 6 7
*/This implementation uses a binary search loop to repeatedly divide the array in half. If the middle element is less than or equal to k, the search continues in the right half of the array. If the middle element is greater than k, the search continues in the left half of the array. The loop terminates when the left pointer is greater than the right pointer, which indicates that the desired element is not in the array. The time complexity of this solution is O(log n), where n is the length of the input array.
Find distance between words in a string e.g.: String => “I am a good girl” distance between “I” and “good” is 3.
o find the distance between two words in a string, you can first split the string into a list of words and then use two pointers to iterate through the list.
Here’s an implementation in Python:
def word_distance(sentence, word1, word2):
words = sentence.split()
idx1, idx2 = -1, -1
min_distance = float("inf")
for i, word in enumerate(words):
if word == word1:
idx1 = i
if idx2 != -1:
min_distance = min(min_distance, idx1 - idx2)
if word == word2:
idx2 = i
if idx1 != -1:
min_distance = min(min_distance, idx2 - idx1)
return min_distance
sentence = "I am a good girl"
result = word_distance(sentence, "I", "good")
print(result)
/*
OUTPUT - 3
*/
This implementation uses two pointers, idx1 and idx2, to keep track of the indices of the two words. When one of the words is encountered in the list, its index is updated and the minimum distance between the two words is calculated. The time complexity of this solution is O(n), where n is the number of words in the sentence.
Given a grid of size m by n, write an algorithm that computes all paths from 0, 0 to m,n such that you can always step. horizontally or vertically but cannot reverse
Here is an algorithm that computes all paths from (0,0) to (m,n) in a grid of size m by n:
Create a 2D array called
pathsof size m by n to store all paths from (0,0) to (m,n).Create a 2D array called
visitedof size m by n to track which cells have been visited.Initialize
paths[0][0] = [[0,0]]and setvisited[0][0] = True.Create a queue to store all possible paths.
Enqueue
paths[0][0]into the queue.While the queue is not empty:
Dequeue the first path from the queue.
Get the last cell of the path.
If the last cell is (m,n), append the path to the
pathsarray and continue.If the last cell is not (m,n), visit all its unvisited neighbors (top, bottom, left, and right) and enqueue the new path (append the neighbor to the end of the path).
Return
paths.
Given a nested list of integers, returns the sum of all integers in the list weighted by their depth given the list {{1,1},2,{1,1}} the function should return 10 (four 1’s at depth 2, one 2 at depth 1).
Here’s a function in Python that computes the sum of all integers in a nested list of integers weighted by their depth:
def nested_list_sum(lst, depth=1):
total = 0
for element in lst:
if type(element) is int:
total += element * depth
elif type(element) is list:
total += nested_list_sum(element, depth + 1)
return totalThis function uses recursion to traverse the nested list and sum up all the integers. The depth argument keeps track of the current depth, and it is incremented by 1 for each nested list encountered. The function checks the type of each element in the list, and if it is an integer, it adds the product of the integer and the current depth to the total. If it is a list, the function calls itself on the list, passing in the new depth. Finally, the total is returned.
Write a function and return true or false if there is a pair of number that sum up as 10
Here’s a function in Python that returns True if there is a pair of numbers in a list that sum up to 10:
def has_pair_with_sum(lst, target_sum):
seen = set()
for num in lst:
if target_sum - num in seen:
return True
seen.add(num)
return FalseThe function uses a set to keep track of the numbers seen so far in the list. For each number in the list, the function checks if target_sum - num is in the set. If it is, then there is a pair that adds up to target_sum, so the function returns True. If not, the current number is added to the set. After processing all numbers in the list, the function returns False if no pair was found.
How to check if the string is palindrome?
#include <stdio.h>
#include <string.h>
int main()
{
char str[20];
int flag;
printf("Enter a string");
gets(str);
int len=strlen(str);
for(int i=0;i<len/2;i++){
if(str[i]==str[len-i-1])
flag=0;
}
if(flag){
printf("String is not palindrome");
}
else{
printf("String is palindrome");
}
return 0;
}
/*
OUTPUT -
Enter a string
121
String is palindrome
*/Write a function that takes a string and check if it is a number
Here’s a function in Python that checks if a string is a number:
def is_number(string):
try:
float(string)
return True
except ValueError:
return FalseThis function uses the float function to try converting the string to a floating-point number. If the conversion succeeds, the function returns True, indicating that the string is a number. If the conversion fails, a ValueError is raised, and the function returns False, indicating that the string is not a number. Note that this function only checks for floating-point numbers and not for other types of numbers such as integers or complex numbers.
Write a function that takes a string and check if it is a number
Here’s a function in C++ that finds a number in a sorted array that has been rotated:
#include <iostream>
using namespace std;
bool findNumber(int numbers[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (numbers[mid] == target) {
return true;
} else if (numbers[left] <= numbers[mid]) {
if (numbers[left] <= target && target < numbers[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (numbers[mid] < target && target <= numbers[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
int main() {
int numbers[] = {6,7,1,2,3,4,5};
int n = sizeof(numbers) / sizeof(numbers[0]);
int target = 3;
if (findNumber(numbers, n, target)) {
cout << "The target number is found in the array." << endl;
} else {
cout << "The target number is not found in the array." << endl;
}
return 0;
}
/*
OUTPUT - The target number is found in the array.
*/
This function uses the float function to try converting the string to a floating-point number. If the conversion succeeds, the function returns True, indicating that the string is a number. If the conversion fails, a ValueError is raised, and the function returns False, indicating that the string is not a number. Note that this function only checks for floating-point numbers and not for other types of numbers such as integers or complex numbers.
Automata Fixing