iterator Archives - Huahua's Tech Road

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

By zxi on December 12, 2021

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

Adding scenic locations, one at a time.
Querying the i^th best location of all locations already added, where i is the number of times the system has been queried (including the current query).
- For example, when the system is queried for the 4^th time, it returns the 4^th best location of all locations already added.

Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

SORTracker() Initializes the tracker system.
void add(string name, int score) Adds a scenic location with name and score to the system.
string get() Queries and returns the i^th best location, where i is the number of times this method has been invoked (including this invocation).

Example 1:

Input

["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]

[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]

Output

[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

Explanation

SORTracker tracker = new SORTracker(); // Initialize the tracker system.

tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.

tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.

tracker.get(); // The sorted locations, from best to worst, are: branford, bradford.

// Note that branford precedes bradford due to its higher score (3 > 2).

// This is the 1st time get() is called, so return the best location: "branford".

tracker.add("alps", 2); // Add location with name="alps" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford.

// Note that alps precedes bradford even though they have the same score (2).

// This is because "alps" is lexicographically smaller than "bradford".

// Return the 2nd best location "alps", as it is the 2nd time get() is called.

tracker.add("orland", 2); // Add location with name="orland" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford, orland.

// Return "bradford", as it is the 3rd time get() is called.

tracker.add("orlando", 3); // Add location with name="orlando" and score=3 to the system.

tracker.get(); // Sorted locations: branford, orlando, alps, bradford, orland.

// Return "bradford".

tracker.add("alpine", 2); // Add location with name="alpine" and score=2 to the system.

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "bradford".

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "orland".

Constraints:

name consists of lowercase English letters, and is unique among all locations.
1 <= name.length <= 10
1 <= score <= 10⁵
At any time, the number of calls to get does not exceed the number of calls to add.
At most 4 * 10⁴ calls in total will be made to add and get.

Solution: TreeSet w/ Iterator

Use a treeset to store all the entries and use a iterator that points to the entry to return. When inserting a new entry into the tree, if it’s higher than the current element then let the iterator go backward one step.

Time complexity: add O(logn) / get O(1)

C++

// Author: Huahua

class SORTracker {

public:

SORTracker() {}

void add(string name, int score) {

if (*s.emplace(-score, name).first < *cit) --cit;

}

string get() {

return (cit++)->second;

}

private:

set<pair<int, string>> s;

// Note: cit points to begin(s) after first insertion.

set<pair<int, string>>::const_iterator cit = end(s);

};

花花酱 LeetCode 1670. Design Front Middle Back Queue

By zxi on November 28, 2020

Design a queue that supports push and pop operations in the front, middle, and back.

Implement the FrontMiddleBack class:

FrontMiddleBack() Initializes the queue.
void pushFront(int val) Adds val to the front of the queue.
void pushMiddle(int val) Adds val to the middle of the queue.
void pushBack(int val) Adds val to the back of the queue.
int popFront() Removes the front element of the queue and returns it. If the queue is empty, return -1.
int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, return -1.
int popBack() Removes the back element of the queue and returns it. If the queue is empty, return -1.

Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:

Pushing 6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5].
Popping the middle from [1, 2, 3, 4, 5, 6] returns 3 and results in [1, 2, 4, 5, 6].

Example 1:

Input:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
Output:
[null, null, null, null, null, 1, 3, 4, 2, -1]
Explanation:
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // return 1 -> [4, 3, 2]
q.popMiddle();    // return 3 -> [4, 2]
q.popMiddle();    // return 4 -> [2]
q.popBack();      // return 2 -> []
q.popFront();     // return -1 -> [] (The queue is empty)

Constraints:

1 <= val <= 10⁹
At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

Solution: List + Middle Iterator

Time complexity: O(1) per op
Space complexity: O(n) in total

C++

// Author: Huahua

class FrontMiddleBackQueue {

public:

FrontMiddleBackQueue() {}

void pushFront(int val) {

q_.push_front(val);

updateMit(even() ? -1 : 0);

}

void pushMiddle(int val) {

if (q_.empty())

q_.push_back(val);

else

q_.insert(even() ? next(mit_) : mit_, val);

updateMit(even() ? -1 : 1);

}

void pushBack(int val) {

q_.push_back(val);

updateMit(even() ? 0 : 1);

}

int popFront() {

if (q_.empty()) return -1;

int val = q_.front();

q_.pop_front();

updateMit(even() ? 0 : 1);

return val;

}

int popMiddle() {

if (q_.empty()) return -1;

int val = *mit_;

mit_ = q_.erase(mit_);

updateMit(even() ? -1 : 0);

return val;

}

int popBack() {

if (q_.empty()) return -1;

int val = q_.back();

q_.pop_back();

updateMit(even() ? -1 : 0);

return val;

}

private:

void updateMit(int delta) {

if (q_.size() <= 1) {

mit_ = begin(q_);

} else {

if (delta > 0) ++mit_;

if (delta < 0) --mit_;

}

bool even() const { return q_.size() % 2 == 0; }

list<int> q_;

list<int>::iterator mit_;

};

Iterables in Python

By zxi on June 29, 2020

Example Code:

Iterables in Python

# Author: Huahua

class MyListIterator:

def __init__(self, my_list, index=0):

self.my_list = my_list

self.index = index

def __next__(self):

if self.index < len(self.my_list.data):

val = self.my_list.data[self.index]

self.index += 1

return val

else:

raise StopIteration()

def __iter__(self):

return MyListIterator(self.my_list, self.index)

# return self

class MyList:

def __init__(self, data):

self.data = list(data)

def __getitem__(self, index):

return self.data[index]

def __len__(self):

return len(self.data)

def __iter__(self):

return MyListIterator(self)

my_list = MyList([1,2,3,4,5])

it = iter(my_list)

next(it)

it2 = iter(it)

next(it)

print('--- it ---')

for x in it:

print(x) # 3, 4, 5

print('--- it2 ---')

for x in it2:

print(x) # 2, 3, 4, 5

Posts tagged as “iterator”

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

Solution: TreeSet w/ Iterator

C++

花花酱 LeetCode 1670. Design Front Middle Back Queue

Solution: List + Middle Iterator

C++

Iterables in Python

Example Code:

Iterables in Python