Hot Topics
Filpkart Solution
Technical Round
Find the second maximum element in an unsorted array of integers, using single for loop.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int first = -1, second = -1;
for (int i = 0; i < n; i++) {
if (arr[i] > first) {
second = first;
first = arr[i];
} else if (arr[i] > second && arr[i] != first) {
second = arr[i];
}
}
cout << second << endl;
return 0;
}
/*
OUTPUT
5
7
8
9
3
6
8
*/Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, etc.
Multi-threading is a process in Java in which two or more threads executes simultaneously for maximum utilization of the CPU.
class SpecialStack:
def __init__(self, capacity):
self.stack = []
self.capacity = capacity
def push(self, data):
if len(self.stack) == self.capacity:
return "Stack is full"
minimum = data if len(self.stack) == 0 else min(data, self.stack[-1][1])
self.stack.append((data, minimum))
def pop(self):
if len(self.stack) == 0:
return "Stack is empty"
return self.stack.pop()[0]
def getMin(self):
if len(self.stack) == 0:
return "Stack is empty"
return self.stack[-1][1]
def isEmpty(self):
return len(self.stack) == 0
def isFull(self):
return len(self.stack) == self.capacity
This implementation takes O(1) time for all operations including getMin().
How do you flat an Array numpy?
In NumPy, you can use the ravel function to flatten a multi-dimensional array into a one-dimensional array. For example:
import numpy as np
# Create a 2-dimensional array
array = np.array([[1, 2, 3], [4, 5, 6]])
# Flatten the array
flattened_array = array.ravel()
print(flattened_array) # Output: [1 2 3 4 5 6]
Alternatively, you can use the flatten method, which returns a copy of the flattened array:
flattened_array = array.flatten()
print(flattened_array) # Output: [1 2 3 4 5 6]
Both ravel and flatten produce a one-dimensional array that has the same data as the original array, but with the dimensions removed. The difference between the two functions is that ravel returns a flattened array that is a reference to the original array, while flatten returns a copy of the flattened array.
How do you display a tree spirally?
To display a binary tree spirally, you can traverse the tree level by level and reverse the order of nodes at alternate levels. Here’s an example implementation in Python:
class SpecialStack:
def __init__(self, capacity):
self.stack = []
self.capacity = capacity
def push(self, data):
if len(self.stack) == self.capacity:
return "Stack is full"
minimum = data if len(self.stack) == 0 else min(data, self.stack[-1][1])
self.stack.append((data, minimum))
def pop(self):
if len(self.stack) == 0:
return "Stack is empty"
return self.stack.pop()[0]
def getMin(self):
if len(self.stack) == 0:
return "Stack is empty"
return self.stack[-1][1]
def isEmpty(self):
return len(self.stack) == 0
def isFull(self):
return len(self.stack) == self.capacity
This implementation uses two stacks and alternates between them to traverse the tree in a spiral manner. The variable level is used to keep track of the level of the tree, which determines the order of the nodes in each level. The time complexity of this algorithm is O(n), where n is the number of nodes in the tree.
Encode and Decode a tree.
To encode a tree, you can perform a pre-order traversal of the tree and store the values of each node in a string. For example, in the following tree:
1
/ \
2 3
/ \
4 5
The encoded string would be “1 2 4 5 3”.
Here’s an implementation in Python for encoding a tree:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def serialize(root):
if not root:
return "#"
return str(root.val) + " " + serialize(root.left) + " " + serialize(root.right)To decode the encoded string, you can reconstruct the tree by reading the values in the string one by one and creating a node for each value. You can use a queue to store the values and traverse the tree in a breadth-first manner.
Here’s an implementation in Python for decoding a tree:
def deserialize(data):
values = data.split()
index = 0
return helper(values, index)
def helper(values, index):
if values[index] == "#":
return None
node = TreeNode(int(values[index]))
index += 1
node.left = helper(values, index)
index += 1
node.right = helper(values, index)
return node
The time complexity of both encoding and decoding is O(n), where n is the number of nodes in the tree.
Given an integer n, find the number of structurally unique BSTs possible, of N nodes numbered from 1 to N.
The number of structurally unique BSTs of n nodes can be found using dynamic programming. We can define a recursive formula dp[i] to represent the number of structurally unique BSTs of i nodes, where i ranges from 1 to n.
Here’s the formula:
dp[i] = sum(dp[j-1] * dp[i-j] for j in range(1, i+1))
where j is the root node and j-1 and i-j are the number of nodes in the left and right subtrees, respectively. The base case is dp[0]=1 and dp[1]=1.
Here’s an implementation in Python:
def numTrees(n):
dp = [0] * (n+1)
dp[0], dp[1] = 1, 1
for i in range(2, n+1):
for j in range(1, i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[n]
The time complexity of this solution is O(n^2).
Automata Fixing