Join Us
Loading Similar Posts
Entering edit mode
ATF STAGE 2 Important Questions
1. K Closest
Topic: Binary Search
Click here to Practice
Submit Problem to OJ
Given an array of N integers and a value 'X', find the k closest integers to 'X', preferring smaller values when distances are the same. Output the k-closest integers in ascending order.
2. Avoiding Landmines
Topic: Graphs
Click here to Practice
Submit Problem to OJ
You need to find the shortest path from a source city to a target city in a graph of N cities and M roads, while avoiding cities with landmines. If reaching the target city is impossible without crossing a landmine, return -1.
3. Sum of 3 equals K
Topic: Two Pointers
Click here to Practice
Submit Problem to OJ
Given an array of N integers and a target value K, check if there exist three distinct integers in the array whose sum equals K. Print "Yes" if such integers exist, otherwise print "No".
4. Next Greater Element
Topic: Stack
Click here to Practice
Submit Problem to OJ
In this problem, for each element in the array, you are tasked to find the next greater element on its right side. If no such element exists, return -1.
5. Longest Subarray Divisible by K
Topic: Hashing
Click here to Practice
Submit Problem to OJ
In this problem, you are asked to find the longest subarray of a given array that is divisible by a given integer K. The array may contain negative values as well.
6. House Robbery
Topic: Dynamic Programming
Click here to Practice
Submit Problem to OJ
© 2024 AlgoUniversity Technology Fellowship
Entering edit mode
I hope I will select for the second stage. i am thrilled to be part of the AlgouniversityTechnologyFellowshipOver the past few months, I have significantly improved my skills in programming and data analysis. I look forward to applying what I've learned in upcoming projects and further developing my expertise in technology
Entering edit mode
Approach:
Problem 1: K Closest
Approach 1 (Easy) :
- Time Complexity: O(N Log N)
- Auxiliary Space Complexity: O(N)
- Steps:
- Compute the absolute differences of all the numbers with X and add them to an array(say `computed`) along with the original number.
- Sort the resulting array based on the absolute differences. The first element will always be the number itself.
- Now print the array containing original numbers from the `computed` array from index 1 to K+1 in ascending order.
- Python code:
n = int(input())
arr = list(map(int,input().split()))
k, x = map(int,input().split())
q = [(abs(i-x),i) for i in arr]
q.sort()
print(' '.join(map(str,sorted([val[1] for val in q[1:k+1]]))))Approach 2 (Optimal) :
- Time Complexity: O(N Log N)
- Auxiliary Space Complexity: O(k)
- Steps:
- Sort the input array and find the index of number X.
- Initialize 2 pointers L and R and move away from the number X based on the absolute difference and add the numbers to an array.
- Sort this array and print the results.
- Tip: you may use binary search to find the index of X.
- Python code:
n = int(input())
arr = list(map(int,input().split()))
k, x = map(int,input().split())
arr.sort()
# You may use binary search for X
idx = 0
for idx in range(len(arr)):
if arr[idx]==x:
break
l, r = idx-1, idx+1
val_l, val_r, selected = 0, 0, 0
impossible_val = -10**9-1
result = []
for i in range(k):
if l<0:
val_l = impossible_val
else:
val_l = arr[l]
if r>=len(arr):
val_r = impossible_val
else:
val_r = arr[r]
if abs(x-val_l)<=abs(x-val_r):
selected = val_l
l-=1
else:
selected = val_r
r+=1
result.append(selected)
result.sort()
print(" ".join(map(str, result)))
Problem 2:Avoiding Landmines
Approach :
- Time Complexity: O(N)
- Auxiliary Space Complexity: O(N)
- Steps:
- Build adjacency list from the roads. Keep in mind, the roads are bi-directional.
- Initialize a queue, starting with the source city, process all the cities with no mines in layers using BFS to ensure we find the shortest path.
- Store minimum number of roads we required to reach the city.
- Keep track of visited nodes to avoid infinite loops.
- If target node is reached, return the number of roads else return -1
- Python code:
def find_n_roads(mines, adj, s, t):
# queue with value denoting and number of roads travelled and current city
q = [(0,s)]
visited = set([s])
idx = 0
while idx<len(q):
n_roads, curr = q[idx]
idx+=1
if mines[curr]==1:
continue
if curr==t:
return n_roads
n_roads +=1
for city in adj[curr]:
if city not in visited:
q.append((n_roads, city))
visited.add(city)
return -1
n,m = map(int,input().split())
s,t = map(int,input().split())
mines = list(map(int,input().split()))
adj = [[] for _ in range(n)]
for _ in range(m):
u,v = map(int,input().split())
adj[u].append(v)
adj[v].append(u)
# ====
res = find_n_roads(mines, adj, s, t)
print(res)
