Posts tagged as “design”

花花酱 LeetCode 1656. Design an Ordered Stream

By zxi on November 14, 2020

There are n (id, value) pairs, where id is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that takes the n pairs in an arbitrary order, and returns the values over several calls in increasing order of their ids.

Implement the OrderedStream class:

OrderedStream(int n) Constructs the stream to take n values and sets a current ptr to 1.
String[] insert(int id, String value) Stores the new (id, value) pair in the stream. After storing the pair:
- If the stream has stored a pair with id = ptr, then find the longest contiguous incrementing sequence of ids starting with id = ptr and return a list of the values associated with those ids in order. Then, update ptr to the last id + 1.
- Otherwise, return an empty list.

Example:

Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
Explanation
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].

Solution: Straight Forward

Time complexity: O(n) in total
Space complexity: O(n)

C++

// Author: Huahua

class OrderedStream {

public:

OrderedStream(int n): data_(n + 1) {}

vector<string> insert(int id, string value) {

data_[id] = value;

vector<string> ans;

if (ptr_ == id)

while (ptr_ < data_.size() && !data_[ptr_].empty())

ans.push_back(data_[ptr_++]);

return ans;

}

private:

int ptr_ = 1;

vector<string> data_;

};

Python3

# Author: Huahua

class OrderedStream:

def __init__(self, n: int):

self.data = [None] * (n + 1)

self.ptr = 1

def insert(self, id: int, value: str) -> List[str]:

self.data[id] = value

if id == self.ptr:

while self.ptr < len(self.data) and self.data[self.ptr]:

self.ptr += 1

return self.data[id:self.ptr]

return []

花花酱 LeetCode 1206. Design Skiplist

By zxi on November 6, 2020

Design a Skiplist without using any built-in libraries.

A Skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists are just simple linked lists.

For example: we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add , erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).

To be specific, your design should include these functions:

bool search(int target) : Return whether the target exists in the Skiplist or not.
void add(int num): Insert a value into the SkipList.
bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.

See more about Skiplist : https://en.wikipedia.org/wiki/Skip_list

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

Example:

Skiplist skiplist = new Skiplist();

skiplist.add(1);

skiplist.add(2);

skiplist.add(3);

skiplist.search(0); // return false.

skiplist.add(4);

skiplist.search(1); // return true.

skiplist.erase(0); // return false, 0 is not in skiplist.

skiplist.erase(1); // return true.

skiplist.search(1); // return false, 1 has already been erased.

Constraints:

0 <= num, target <= 20000
At most 50000 calls will be made to search, add, and erase.

Solution:

C++

// Author: Huahua

class Skiplist {

public:

Skiplist() { head_ = make_shared<Node>(); }

bool search(int target) {

for (auto node = head_; node; node = node->down) {

while (node->next && node->next->val < target)

node = node->next;

if (node->next && node->next->val == target)

return true;

}

return false;

}

void add(int num) {

stack<shared_ptr<Node>> s;

shared_ptr<Node> down;

bool insert = true;

for (auto node = head_; node; node = node->down) {

while (node->next && node->next->val < num)

node = node->next;

s.push(node);

}

while (!s.empty() && insert) {

auto cur = s.top(); s.pop();

cur->next = make_shared<Node>(num, cur->next, down);

down = cur->next;

insert = rand() & 1; // 50% chance

}

if (insert) // create a new layer.

head_ = make_shared<Node>(-1, nullptr, head_);

}

bool erase(int num) {

bool found = false;

for (auto node = head_; node; node = node->down) {

while (node->next && node->next->val < num)

node = node->next;

if (node->next && node->next->val == num) {

found = true;

node->next = node->next->next;

}

return found;

}

private:

struct Node {

Node(int val = -1,

shared_ptr<Node> next = nullptr,

shared_ptr<Node> down = nullptr):

val(val), next(next), down(down) {}

int val;

shared_ptr<Node> next;

shared_ptr<Node> down;

};

shared_ptr<Node> head_;

};

/**

* Your Skiplist object will be instantiated and called as such:

* Skiplist* obj = new Skiplist();

* bool param_1 = obj->search(target);

* obj->add(num);

* bool param_3 = obj->erase(num);

Python3

import random

class Node:

def __init__(self, val=-1, right=None, down=None):

self.val = val

self.right = right

self.down = down

class Skiplist:

def __init__(self):

self.head = Node() # Dummy head

def search(self, target: int) -> bool:

node = self.head

while node:

# Move to the right in the current level

while node.right and node.right.val < target:

node = node.right

if node.right and node.right.val == target:

return True

# Move to the the next level

node = node.down

return False

def add(self, num: int) -> None:

nodes = []

node = self.head

while node:

# Move to the right in the current level

while node.right and node.right.val < num:

node = node.right

nodes.append(node)

# Move to the next level

node = node.down

insert = True

down = None

while insert and nodes:

node = nodes.pop()

node.right = Node(num, node.right, down)

down = node.right

insert = (random.getrandbits(1) == 0)

# Create a new level with a dummy head.

# right = None

# down = current head

if insert:

self.head = Node(-1, None, self.head)

def erase(self, num: int) -> bool:

node = self.head

found = False

while node:

# Move to the right in the current level

while node.right and node.right.val < num:

node = node.right

# Find the target node

if node.right and node.right.val == num:

# Delete by skipping

node.right = node.right.right

found = True

# Move to the next level

node = node.down

return found

# Your Skiplist object will be instantiated and called as such:

# obj = Skiplist()

# param_1 = obj.search(target)

# obj.add(num)

# param_3 = obj.erase(num)

花花酱 LeetCode 1603. Design Parking System

By zxi on October 3, 2020

Design a parking system for a parking lot. The parking lot has three kinds of parking spaces: big, medium, and small, with a fixed number of slots for each size.

Implement the ParkingSystem class:

ParkingSystem(int big, int medium, int small) Initializes object of the ParkingSystem class. The number of slots for each parking space are given as part of the constructor.
bool addCar(int carType) Checks whether there is a parking space of carType for the car that wants to get into the parking lot. carType can be of three kinds: big, medium, or small, which are represented by 1, 2, and 3 respectively. A car can only park in a parking space of its carType. If there is no space available, return false, else park the car in that size space and return true.

Example 1:

Input
["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
Output
[null, true, true, false, false]

Explanation ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0); parkingSystem.addCar(1); // return true because there is 1 available slot for a big car parkingSystem.addCar(2); // return true because there is 1 available slot for a medium car parkingSystem.addCar(3); // return false because there is no available slot for a small car parkingSystem.addCar(1); // return false because there is no available slot for a big car. It is already occupied.

Constraints:

0 <= big, medium, small <= 1000
carType is 1, 2, or 3
At most 1000 calls will be made to addCar

Solution: Simulation

Time complexity: O(1) per addCar call
Space complexity: O(1)

C++

// Author: Huahua

class ParkingSystem {

public:

ParkingSystem(int big, int medium, int small):

slots_{{big, medium, small}} {}

bool addCar(int carType) {

return slots_[carType - 1]-- > 0;

}

private:

vector<int> slots_;

};

Python3

# Author: Huahua

class ParkingSystem:

def __init__(self, big: int, medium: int, small: int):

self.slots = {1: big, 2: medium, 3: small}

def addCar(self, carType: int) -> bool:

if self.slots[carType] == 0: return False

self.slots[carType] -= 1

return True

花花酱 LeetCode 1472. Design Browser History

By zxi on June 6, 2020

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
void visit(string url) visits url from the current page. It clears up all the forward history.
string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

Example:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]
Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(2);                   // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

Constraints:

1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage and url consist of ‘.’ or lower case English letters.
At most 5000 calls will be made to visit, back, and forward.

Solution: Vector

Time complexity:
visit: Amortized O(1)
back: O(1)
forward: O(1)

C++

// Author: Huahua

class BrowserHistory {

public:

BrowserHistory(string homepage) :

index_(0) {

urls_.push_back(std::move(homepage));

}

void visit(string url) {

while (urls_.size() > index_ + 1)

urls_.pop_back();

++index_;

urls_.push_back(std::move(url));

}

string back(int steps) {

index_ = max(index_ - steps, 0);

return urls_[index_];

}

string forward(int steps) {

index_ = min(index_ + steps, static_cast<int>(urls_.size()) - 1);

return urls_[index_];

}

private:

int index_;

vector<string> urls_;

};

花花酱 LeetCode 1396. Design Underground System

By zxi on March 28, 2020

Implement the class UndergroundSystem that supports three methods:

1. checkIn(int id, string stationName, int t)

A customer with id card equal to id, gets in the station stationName at time t.
A customer can only be checked into one place at a time.

2. checkOut(int id, string stationName, int t)

A customer with id card equal to id, gets out from the station stationName at time t.

3. getAverageTime(string startStation, string endStation)

Returns the average time to travel between the startStation and the endStation.
The average time is computed from all the previous traveling from startStation to endStation that happened directly.
Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t₁ at some station, then it gets out at time t₂ with t₂ > t₁. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

There will be at most 20000 operations.
1 <= id, t <= 10^6
All strings consist of uppercase, lowercase English letters and digits.
1 <= stationName.length <= 10
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Hashtable

For each user, store the checkin station and time.
For each trip (startStation + “_” + endStation), store the total time and counts.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class UndergroundSystem {

public:

UndergroundSystem() {}

void checkIn(int id, string stationName, int t) {

m_[id] = {stationName, t};

}

void checkOut(int id, string stationName, int t) {

const auto& [s0, t0] = m_[id];

string key = s0 + "_" + stationName;

times_[key].first += (t - t0);

++times_[key].second;

}

double getAverageTime(string startStation, string endStation) {

const auto& [sum, count] = times_[startStation + "_" + endStation];

return static_cast<double>(sum) / count;

}

private:

unordered_map<int, pair<string, int>> m_; // id -> {station, t}

unordered_map<string, pair<int, int>> times_; // trip -> {sum, count}

};