Best solutions for Codility Lessons. Lesson 7 Stacks and Queues
Task 1 Brackets
Solution:
This is a simple task for using a stack container. There are no any tricks. Actually this is a simplest parser based on a state machine. All other such parsers even very complex parsers for programming languages looks like this one. The idea is simple. We read symbols one by one and put them to a variable which contains a state of our state machine — “c”. The state machine switch its state based on this data. This leads to run the code which correspond to this state. The code process the state and then we read next symbol which switch the machine to another state.
To solve this task we need to find a closing bracket for each opening bracket. The most natural container for this task is a stack because the brackets may be nested one to another. So we put one half of the brackets to the stack (opening brackets) and each time when we meet a closed bracket in properly nested string we remove from the stack a closing bracket corresponding to this one. If type of the brackets is not the same or the stack is empty it means that the brackets in the string are not nested properly. In this case we should return error.
In C++ it looks like:
int check_brackets(const std::string &s) {
if (s.empty()) { return 1; }
auto s_len = s.length();
if (s_len % 2) { return 0; }//the length cannot be an odd number
std::stack<char> stack;
auto no_pair = [&stack](char c) {
if (stack.empty() || stack.top() != c) {
return true;
}
stack.pop();
return false;
};
for (auto c: s) {
switch (c) {
case ')':
if (no_pair('(')) { return 0; }
break;
case ']':
if (no_pair('[')) { return 0; }
break;
case '}':
if (no_pair('{')) { return 0; }
break;
default:
stack.push(c);
}
}
return stack.empty() ? 1 : 0;
}Task 2 Fish
Solution:
Actually we have here two kinds of fish which moving towards each other. So we should scan the stream, find the fish which moving downstream and compare them with the fish which moving upstream. The best container for collecting of downstream fish is stack because when we will take the fish from the stack for comparing it will be have opposite direction to upstream fish.
The task is similar to the previous one. We have two kinds of fish instead of three kinds of brackets. We need to compare these kinds and leave only those which meet given criteria.
In C++ it looks like:
int fish_stream(const vector<int> &fish, const vector<int> &directions) {
const auto UPSTREAM = 0;
int left = 0, fish_num = fish.size();
std::stack<int> stack; // scan the stream
for(int i = 0; i < fish_num; ++i) {
// if fish moves upstream
if(UPSTREAM == directions[i]) {
// compare it with downstream fish in front of it and remove
// from the stack all fish less than our one
// because they are eaten
while(!stack.empty() && (stack.top() < fish[i])) {
stack.pop();
}
// if we have no opposite fish which moves downstream
// just count our fish and leave it in the stream.
if(stack.empty()) {
left++;
}
}
// if fish moves downstream add it to the stack
else {
stack.push(fish[i]);
}
}
return left + stack.size();
}
Task 3 Nesting
Solution:
This task is so simple that the solution even doesn’t need for a stack to compare opening and closing brackets. It is enough to count their numbers and make sure that number of opening brackets is the same as number of closing brackets.
int check_nested(const string& s) {
if (s.empty()) { return 1; } //the length cannot be an odd number
if (s.length() % 2) { return 0; } int left_brackets = 0; for(auto c: s) {
if(c == '(') {
left_brackets ++;
}
else if(left_brackets > 0) {
left_brackets --;
}
else {
return 0;
}
}
return left_brackets ? 0 : 1;
}
Task 4 StoneWall
Solution:
The problem is to build a “Manhattan skyline” using the minimum number of rectangle blocks.
In simple words we need to cover the given figure by minimum number of rectangles. This figure looks like a skyline of a big city with its skyscrapers, this is the cause why this task calls “Manhattan skyline problem”.
The abstract algorithm is:
- break up each array element into sub-blocks to store on a stack
- for each subsequent array element, check if there are existing blocks on the stack that can create it.
- only add new block to the stack if impossible to reuse sub-blocks from stack
Example
[8, 8, 5, 7, 9, 8, 7, 4, 8] will be broken down into the following 7 unique blocks:
(0,8) //8
(0,8) //8
(0,5) //5 (after clearing stack)
(0,5), (5,7) //7
(0,5), (5,7), (7,9) //9
(0,5), (5,7), (7,8) //8 (after popping stack)
(0,5), (5,7) //7 (after popping stack)
(0,4) // 4 (after clearing stack)
(0,4), (4,8) //8
The solution in C++ looks like:
int stone_wall(const vector<int> &v) {
std::stack<int> stack;
int stones = 0; for (auto height : v) {
while (!stack.empty() && stack.top() > height) {
stack.pop();
}
if (!stack.empty() && stack.top() == height) {
continue;
}
stones++;
stack.push(height);
}
return stones;
}
This solution scans the skyline from left to right. It stores on a stack a sequence of horizontal edges, such that their heights form an increasing sequence. Whenever a peak is passed, it is eliminated by generating stone blocks that cover it. Each horizontal edge can be pushed onto the stack and popped from the stack once. Hence, the time complexity of this solution is O(N).
The same solution in Python:
def solution(H):
block_cnt = 0
stack = [] for height in H:
# remove all blocks that are bigger than my height
while len(stack) != 0 and stack[-1] > height:
stack.pop() if len(stack) != 0 and stack[-1] == height:
# we already paid for this size
pass
else:
# new block is required, push it's size to the stack
block_cnt += 1
stack.append(height)return block_cnt
Here is a description of the solution for this task from Codility website which was removed from there in 2012. May be it will add understanding for some one:
This problem is a variant of a problem known as the rectilinear skyline problem, or Manhattan skyline problem, in which a city skyline is given, with each building contributing a rectangle to the skyline, and the question is: what is the minimum number of buildings required to produce the given skyline? The skyline corresponds to the shape of the wall and the buildings correspond to the stone blocks.
At first glance, the problems seem different. On the one hand, buildings have to stand on the ground and rectangles corresponding to them can overlap. On the other hand, stone blocks cannot overlap but one block can be placed on top of another. However, as we will see, both problems can be solved using the same method.
Intuition tells us that by extending each stone block to the ground, we obtain a set of buildings that form the given skyline. The converse observation is less obvious.
The number of stone blocks (or buildings) is not larger than the number of horizontal edges that are above the ground in the skyline. Simply, for each such edge, we can place a separate building, or stone block, standing on the ground. To use fewer stone blocks, one stone block must be adjacent to several horizontal edges of the skyline. When is this possible? Clearly, if the two horizontal edges are adjacent to the same stone block, they must be of the same height. Moreover, the stone wall between the two edges cannot be lower than the edges. It turns out that these two conditions are sufficient.
The peak shown in the above figure should be made of a single stone block. But how tall should this stone block be? It turns out that making its lower edge level with the higher of the two neighboring horizontal edges is always a good choice. Using such a greedy strategy, any two horizontal edges of the skyline that satisfy the conditions specified above are adjacent to the same stone block. Applying this greedy strategy to the example data yields the following solution:
If you are interested in this subject there is highly optimized but more complex solution of this problem. You can read about it here: https://www.researchgate.net/publication/221049934_A_Skyline-Based_Heuristic_for_the_2D_Rectangular_Strip_Packing_Problem
Go back to the table of contents.
