Tip 1 : Practice competitive programming regularly
Tip 2 : Look at interview experience
Tip 3 : Talk to seniors who work there
Tip 1 : Get it reviewed by professional
Tip 2 : Mention only what you know
An edge with type 1 can only be traversed by a person ‘A’.
An edge with type 2 can only be traversed by a person ‘B’.
An edge with type 3 can be traversed by both persons ‘A’ and ‘B’.
We can solve this problem using DFS. One simple solution is to delete each edge one by one and check subtree sum difference. Finally choose the minimum of them. This approach takes quadratic amount of time. An efficient method can solve this problem in linear time by calculating the sum of both subtrees using total sum of the tree. We can get the sum of other tree by subtracting sum of one subtree from the total sum of tree, in this way subtree sum difference can be calculated at each node in O(1) time. First we calculate the weight of complete tree and then while doing the DFS at each node, we calculate its subtree sum, by using these two values we can calculate subtree sum difference.
Gcd of two numbers (X, Y) is defined as the largest integer that divides both ‘X’ and ‘Y’.
# Python program to print all
# primes smaller than or equal to
# n using Sieve of Eratosthenes
def SieveOfEratosthenes(n):
# Create a boolean array
# "prime[0..n]" and initialize
# all entries it as true.
# A value in prime[i] will
# finally be false if i is
# Not a prime, else true.
prime = [True for i in range(n+1)]
p = 2
while (p * p <= n):
# If prime[p] is not
# changed, then it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p * p, n+1, p):
prime[i] = False
p += 1
# Print all prime numbers
for p in range(2, n+1):
if prime[p]:
print(p)
# Driver code
if __name__ == '__main__':
n = 20
print("Following are the prime numbers smaller"),
print("than or equal to", n)
SieveOfEratosthenes(n)
Input: 'a' = [7, 12, 1, 20]
Output: NGE = [12, 20, 20, -1]
Explanation: For the given array,
- The next greater element for 7 is 12.
- The next greater element for 12 is 20.
- The next greater element for 1 is 20.
- There is no greater element for 20 on the right side. So we consider NGE as -1.
# Function to print element and NGE pair for all elements of list
def printNGE(arr):
for i in range(0, len(arr), 1):
next = -1
for j in range(i+1, len(arr), 1):
if arr[i] < arr[j]:
next = arr[j]
break
print(str(arr[i]) + " -- " + str(next))
# Driver program to test above function
arr = [11, 13, 21, 3]
printNGE(arr)
# This code is contributed by Sunny Karira
Here's your problem of the day
Solving this problem will increase your chance to get selected in this company
Which SQL keyword removes duplicate records from a result set?