Problem Description

Given an input of a dictionary of words and an input string that does not contain spaces,
write a method that returns a string with spaces inserted accordingly.

Sample inputs - Expected outputs

Input: "bloombergisfun", ["bloom","bloomberg","is","fun"]
Output: "bloomberg is fun"

This problem asks you to segment a concatenated string into valid dictionary words. It is a classic word-break problem: greedily picking the longest prefix in the dictionary also works for this particular example, but in general you use dynamic programming or backtracking to find a valid segmentation.

Bloomberg Interview Question: Count Ships in a Rectangular Region Using hasShips API

Problem Description

You work on a project that has to implement a new ship discovering technology.
You are provided with the function:

struct Point {
    const int x_;
    const int y_;
    Point(int x, int y) : x_(x), y_(y) {}}

bool hasShips(const Point& bottom_left, const Point& top_right);
// Returns true if there are 1 or more ships within the area with corners bottom_left
// and top_right. Returns false if there are no ships within the area.

Using the hasShips function, implement the function:

int countShips(const Point& bottom_left, const Point& top_right);
// Returns the number of ships in the area with corners bottom_left and top_right.

Sample inputs - Expected outputs:

// "X" marks the presence of a ship
// A, B and C are points defined below

    y2 | B | C |
       +---+---+
       | X |   |
       +---+---+
       |   | X |
       +---+---+
    y1 | A |   |
       +---+---+
        x1   x2

Point A(0,0);
Point B(0,3);
Point C(2,3);

hasShips(A,C) == true;
hasShips(B,C) == false;
hasShips(C,C) == false;

countShips(A,C) == 2;
countShips(B,C) == 0;
countShips(C,C) == 0;

You must implement countShips but may only query via hasShips(), which tells you whether a region contains ≥1 ship. Since direct coordinates of ships are unknown, the solution is a divide-and-conquer approach: recursively split the rectangle into four quadrants, skip empty regions (hasShips==false), and count ships in sub-rectangles until reaching 1×1 cells.