Hot Topics
Filpkart Solution
Technical Round
#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
*/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().
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.
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.
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.
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).
Popular Category
Hot Topics
Go through our study material. Your Job is awaiting.