MFAI SOTI Quiz

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Which algorithm could be used that is less than O(n²) time complexity?

• HashMap/Dictionary 

• Brute Force 

• Binary Search 

•  Two Pointers

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Which algorithm is best suited for this program?

• Dynamic Programming 

• Brute Force 

• Two Pointer Approach 

• Monotonic Stack

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

Input: nums = [1,3], n = 6

Output: 1

Explanation:

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch.

What is the best time complexity that you can solve this problem in?

•  O(n) 

• O(log n) 

• O(n²)

• O(n log n) 

Given a non-negative integer c, decide whether there're two integers a and b such that ( a^2 + b^2 = c)
Example 1:

Input: c = 5

Output: true

Explanation: \( 1^2 + 2^2 = 5 \)

Which is the best time complexity in which you can solve this?

• O(sqrt(c)) 

•  O(log c) 

• O(c) 

• O(c log c)

Why does Java always produce a lower time complexity than Python?

• Python's dynamic typing 

• Java's static typing 

• Java's garbage collection

• JIT Compilation 

Which data structure allows storing elements in a sorted order?

• Stack 

• PriorityQueue 

• Queue 

• HashMap

Which sorting algorithm is best?

• BubbleSort 

• SelectionSort 

• InsertionSort

• QuickSort 

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

Which method could be used in order to solve this question optimally?

• Two Pointers

• Lomuto Partition Scheme

• Dutch National Flag

• Dijkstra’s Algorithm

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"

Output: 10

Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

What is the minimum time complexity that suits the problem?

• O(n!)

• O(n²)

• O(log n)

• O(n)

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

What is the method which you can use to get the optimal solution?

• Sliding Window Approach

• Two Pointer Approach

• Matrix Approach

• Dutch National Flag Approach