Advanced Competitive Programming Interview Test (20 Questions)

1. Which of the following time complexities represents the most efficient algorithm?
A) O(n²)
B) O(2ⁿ)
C) O(log n)
D) O(n log n)

2. What will be the output of the following code?

   def mystery(n):
       if n <= 1:
           return 1
       return n * mystery(n - 1)
   print(mystery(5))
   

3. Write a function to find the longest increasing subsequence in an array using dynamic programming.

4. Explain the difference between BFS and DFS in graph traversal, and when each is preferred.

5. Given a sorted array of integers, which algorithm can be used to find a target value in O(log n) time?
A) Linear search
B) Binary search
C) Bubble sort
D) Merge sort

6. What is the time complexity of the following code snippet?

   for i in range(n):
       for j in range(i, n):
           print(i, j)
   

7. Write a program to implement Dijkstra's algorithm for finding the shortest path in a weighted graph.

8. What does the term "greedy choice property" refer to in greedy algorithms?

9. Which data structure is most suitable for implementing a priority queue efficiently?
A) Stack
B) Queue
C) Binary heap
D) Linked list

10. What will be the output of this code?

    import sys
    sys.setrecursionlimit(10000)
    def f(n):
        if n == 0:
            return 0
        return n + f(n-1)
    print(f(999))
    

11. Implement a recursive function to compute the nth Fibonacci number with memoization.

12. Describe the concept of divide and conquer with an example.

13. What is the space complexity of quicksort in the worst case?
A) O(1)
B) O(log n)
C) O(n)
D) O(n²)

14. Write a function that checks whether a given string is a palindrome using recursion.

15. In the context of competitive programming, what is the purpose of using bit manipulation?

16. What will be the output of the following code?

    s = "abc"
    print(s[1:3] + s[0])
    

17. Design a solution to find the maximum sum subarray using Kadane’s algorithm.

18. Explain the concept of backtracking with an example (e.g., N-Queens problem).

19. Which of the following problems cannot be solved using dynamic programming?
A) Longest common subsequence
B) Matrix chain multiplication
C) Traveling Salesman Problem
D) Binary search

20. Given two strings, write a function to determine if one is a permutation of the other using character frequency counting.

#CompetitiveProgramming #Algorithms #InterviewPrep #CodeForces #LeetCode #ProgrammingContest #DataStructures #AlgorithmDesign

By: @DataScienceQ 🚀

World Programming Championship Problem Solving Test

1. Given an array of integers, write a program to find the length of the longest increasing subsequence.

2. What will the output be for the following code snippet?

def func(n):  
    if n == 0:  
        return 0  
    return n + func(n - 1)  

print(func(5))

3. Which data structure is most efficient for implementing a priority queue? 
   a) Array 
   b) Linked List 
   c) Heap 
   d) Stack

4. Write a function to check whether a given string is a palindrome considering only alphanumeric characters and ignoring cases.

5. Explain the difference between Depth-First Search (DFS) and Breadth-First Search (BFS) with examples where each is preferred.

6. Output the result of this snippet:

print(3 * 'abc' + 'def' * 2)

7. Given a graph represented as an adjacency list, write a program to detect if there is a cycle in the graph.

8. What is the time complexity of binary search on a sorted array?

9. Implement a function that returns the number of ways to make change for an amount given a list of coin denominations.

10. What is the output of this code?

def f(x=[]):  
    x.append(1)  
    return x  

print(f())  
print(f())

11. Describe the sliding window technique and provide a problem example where it is used effectively.

12. Write code to find the median of two sorted arrays of possibly different sizes.

13. Which sorting algorithm has the best average-case time complexity for large datasets? 
    a) Bubble Sort 
    b) Quick Sort 
    c) Insertion Sort 
    d) Selection Sort

14. Given the task of finding the shortest path between two nodes in a weighted graph with no negative edges, which algorithm would you use and why?

15. What does this code output?

for i in range(3):  
    print(i)  
else:  
    print("Done")

16. Implement a program that finds the maximum sum subarray (Kadane’s Algorithm).

17. How is memoization used to optimize recursive solutions? Provide a classic example.

18. Write a function that returns all valid combinations of n pairs of parentheses.

19. Given an integer array, find the maximum product of any three numbers.

20. Explain what a greedy algorithm is and present a problem where a greedy approach yields an optimal solution.

#CompetitiveProgramming #Algorithms #DataStructures #ProblemSolving #CodingInterview

By: @DataScienceQ 🚀