Coding Challenge Round 1

Given a function f(n) = f(n-1) + f(n-2) with f(0) = 0 and f(1) = 1, what is the most time-efficient way to compute f(10^6)?

• Recursion

• Memoized Recursion

• Iterative with DP

• Matrix Exponentiation

You are building a function that needs to generate all permutations of a string. What is the time complexity?

• O(n)

• O(n!)

• O(n²)

• O(n log n)

Which algorithm is the most appropriate for solving the "Minimum Spanning Tree" problem in a weighted undirected graph?

• Dijkstra’s Algorithm

• Floyd-Warshall Algorithm

• Kruskal’s or Prim’s Algorithm

• Bellman-Ford Algorithm

You are asked to evaluate the following logic in a scheduling problem:

"Given a list of tasks with start and end times, what’s the maximum number of non-overlapping tasks you can perform?"

Which approach solves this optimally?

• Greedy - Sort by start time

• Dynamic Programming - Overlapping Intervals

• Greedy - Sort by end time

• Backtracking with Memoization

You need to find the number of subarrays with a sum equal to k in an integer array. What technique gives the best performance?

• Brute Force O(n²)

• Sliding Window O(n)

• Prefix Sum + HashMap O(n)
  

• Merge Sort O(n log n)

You are implementing a caching system with a Least Recently Used (LRU) policy. Which of the following data structure combinations is typically used to achieve O(1) get and put operations?

• HashMap + Doubly Linked List

• HashMap + Stack

• Heap + Array

• Queue + Binary Tree

Suppose you need to design a data structure that supports the following operations in O(1):

• 1. Insert

• 2. Delete

• 3. Get Random Element

Which combination of structures would best serve this purpose?

• Stack and Queue

• Hash Table and Array/List

• Linked List and Stack
  

• Tree and Array

Given an array of n integers where each integer is in the range [1, n], and some elements appear more than once, what is the best approach to find all duplicates in O(n) time and O(1) extra space (excluding output)?

• Use a hash map

• Sort the array and compare neighbors

• Modify array indices as markers (e.g., negating values)

• Use a priority queue

Which of the following data structures allows Last In First Out (LIFO) access?

• Queue

• Stack

• Array

• Linked List

What does the term 'recursion' mean in programming?

• Calling a method from a different class

• A function that calls itself

• A function that loops forever

• A function that halts the program