Second joint session.

Joint session II: Tomiwa & I.md

In today's session, we'd chill and vibe as usual over a couple of questions. Some of the questions will be in this Gist and we might choose some randomly from LeetCode. The questions are listed below, answers will be posted here subsequently.

Question 1

Write a program that takes an array A and an index i rnto A, and rearranges the elements such that all elements less than A[r] (the "pivot") appear first, followed by elements equal to the pivot, followed by elements greater than the pivot. You are expected to have a function solution(array, index)

Example:

input: array = [0,1,2,0,2,1,1], index = 3
output: [0,0,1,2,2,1,1]

input: [0,1,0,1,1,2,2], index = 2
output: [0,0,1,1,1,2,2]

input: array = [-3, 0, -1, 1, 1, 4, 2], index = 2
output: [-3,-1,0,1,1,2,4]

Question 2

Given an array A of n objects with Boolean-valued keys, reorder the array so that objects that have tje key false appear first. The relative ordering of objects with key true should not change. Use O(1) additional space and O(n) time.

Example:

input: array = [{'first': True}, {'second': False}, {'third': False}, {'fourth': True}, {'fifth': True}]
output: [{'second': False}, {'Third': False}, {'first': True}, {'fourth': True}, {'fifth': True}]

Question 1:

def solution(array, index):
    less, equal, greater = 0, 0, len(array)
    pivot = array[index]

    while equal < greater:
        if array[equal] < pivot:
            array[less], array[equal] = array[equal], array[less]
            equal, less = equal + 1, less + 1
        elif array[equal] == pivot:
            equal += 1
        else:
            greater -= 1
            array[equal], array[greater] = array[greater], array[equal]
    return array

That does it in O(n) time and O(1) space.

(This problem is an interactive problem.)
On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.
You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.
Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.
Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example :

Input:
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Constraints:
On the input ships is only given to initialize the map internally. You must solve this problem "blindfolded". In other words, you must find the answer using the given hasShips API, without knowing the ships position.
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000

Hm.