Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit9eed63a37a808c59990feaaaa3e1725dfdd31f3c (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-10-30 22:33:14 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-10-30 22:33:14 +0200
Filesbc22e2b8407f9207c7a5a8ef999f41446c0cee19
Data-structures-and-algorithms-9eed63a37a808c59990feaaaa3e1725dfdd31f3c.tar
Data-structures-and-algorithms-9eed63a37a808c59990feaaaa3e1725dfdd31f3c.tar.gz
Data-structures-and-algorithms-9eed63a37a808c59990feaaaa3e1725dfdd31f3c.zip
Parent0f17a224d2934c748b32b908f74724b3299d263a (diff)
Add SI consultation
12 files changed, 455 insertions, 0 deletions
-rw-r--r--Additional/Additional-2022-CS/README.md (renamed from Additional/README.md)0
-rw-r--r--Additional/Additional-2022-CS/concatenate-queues.cpp (renamed from Additional/concatenate-queues.cpp)0
-rw-r--r--Additional/Additional-2022-CS/equalize.cpp (renamed from Additional/equalize.cpp)0
-rw-r--r--Additional/Additional-2022-CS/merge-sorted.cpp (renamed from Additional/merge-sorted.cpp)0
-rw-r--r--Additional/Additional-2022-CS/oddEvenList.cpp (renamed from Additional/oddEvenList.cpp)0
-rw-r--r--Additional/Additional-2022-CS/rearange.cpp (renamed from Additional/rearange.cpp)0
-rw-r--r--Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp (renamed from Additional/reverse-nodes-in-k-group.cpp)0
-rw-r--r--Additional/Additional-2023-SI/IntervalCollection.cpp103
-rw-r--r--Additional/Additional-2023-SI/MergeIntoList.cpp117
-rw-r--r--Additional/Additional-2023-SI/queue-insertion.cpp109
-rw-r--r--Additional/Additional-2023-SI/readme.md14
-rw-r--r--Additional/Additional-2023-SI/rearrange.cpp112
diff --git a/Additional/README.md b/Additional/Additional-2022-CS/README.md
index 96b8018..96b8018 100644
--- a/Additional/README.md
+++ b/Additional/Additional-2022-CS/README.md
diff --git a/Additional/concatenate-queues.cpp b/Additional/Additional-2022-CS/concatenate-queues.cpp
index c3f772e..c3f772e 100644
--- a/Additional/concatenate-queues.cpp
+++ b/Additional/Additional-2022-CS/concatenate-queues.cpp
diff --git a/Additional/equalize.cpp b/Additional/Additional-2022-CS/equalize.cpp
index 263ccd2..263ccd2 100644
--- a/Additional/equalize.cpp
+++ b/Additional/Additional-2022-CS/equalize.cpp
diff --git a/Additional/merge-sorted.cpp b/Additional/Additional-2022-CS/merge-sorted.cpp
index b801a72..b801a72 100644
--- a/Additional/merge-sorted.cpp
+++ b/Additional/Additional-2022-CS/merge-sorted.cpp
diff --git a/Additional/oddEvenList.cpp b/Additional/Additional-2022-CS/oddEvenList.cpp
index 05a95ac..05a95ac 100644
--- a/Additional/oddEvenList.cpp
+++ b/Additional/Additional-2022-CS/oddEvenList.cpp
diff --git a/Additional/rearange.cpp b/Additional/Additional-2022-CS/rearange.cpp
index 48dacff..48dacff 100644
--- a/Additional/rearange.cpp
+++ b/Additional/Additional-2022-CS/rearange.cpp
diff --git a/Additional/reverse-nodes-in-k-group.cpp b/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp
index 70b63fd..70b63fd 100644
--- a/Additional/reverse-nodes-in-k-group.cpp
+++ b/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp
diff --git a/Additional/Additional-2023-SI/IntervalCollection.cpp b/Additional/Additional-2023-SI/IntervalCollection.cpp
new file mode 100644
index 0000000..0ac2c76
--- /dev/null
+++ b/Additional/Additional-2023-SI/IntervalCollection.cpp
@@ -0,0 +1,103 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+class IntervalCollection
+{
+ using Iterator = std::vector<std::pair<int, int>>::iterator;
+ using ConstIterator = std::vector<std::pair<int, int>>::const_iterator;
+
+ Iterator getRightmostInterval(int x)
+ {
+ std::pair<int, int> searcher = { x, x };
+ return std::lower_bound(
+ intervals.begin(),
+ intervals.end(),
+ searcher,
+ [](const std::pair<int, int>& first, const std::pair<int, int>& second) -> bool
+ {
+ return first.second < second.second;
+ }
+ );
+ }
+
+ ConstIterator getRightmostIntervalConst(int x) const
+ {
+ std::pair<int, int> searcher = { x, x };
+ return std::lower_bound(
+ intervals.begin(),
+ intervals.end(),
+ searcher,
+ [](const std::pair<int, int>& first, const std::pair<int, int>& second) -> bool
+ {
+ return first.second < second.second;
+ }
+ );
+ }
+
+public:
+ void insert(int x)
+ {
+ Iterator right = getRightmostInterval(x);
+ bool begin = (right == intervals.begin());
+
+ Iterator left = begin ? intervals.end() : right - 1;
+
+ bool needLeftMerge = !begin && (x - 1 == left->second);
+ bool needRightMerge = (right != intervals.end()) && (x + 1 == right->first);
+
+ if (right != intervals.end() && x >= right->first && x <= right->second)
+ {
+ return;
+ }
+
+ if (needLeftMerge && needRightMerge)
+ {
+ left->second = right->second;
+ intervals.erase(right);
+ }
+ else if (needLeftMerge)
+ {
+ left->second = x;
+ }
+ else if (needRightMerge)
+ {
+ right->first = x;
+ }
+ else
+ {
+ intervals.insert(right, { x, x });
+ }
+ }
+
+ bool contains(int x) const
+ {
+ ConstIterator right = getRightmostIntervalConst(x);
+ return (right != intervals.end() && x >= right->first && x <= right->second);
+ }
+
+ void print() const
+ {
+ for (const auto& x : intervals)
+ {
+ std::cout << x.first << " " << x.second << std::endl;
+ }
+ }
+private:
+ std::vector<std::pair<int, int>> intervals;
+};
+
+int main()
+{
+ IntervalCollection ic;
+
+ ic.insert(1);
+ ic.insert(3);
+ ic.insert(2);
+ ic.insert(5);
+ ic.insert(7);
+ ic.insert(4);
+ ic.insert(6);
+
+ std::cout << ic.contains(1) << " " << ic.contains(10);
+} \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/MergeIntoList.cpp b/Additional/Additional-2023-SI/MergeIntoList.cpp
new file mode 100644
index 0000000..7d575aa
--- /dev/null
+++ b/Additional/Additional-2023-SI/MergeIntoList.cpp
@@ -0,0 +1,117 @@
+#include <iostream>
+
+struct ListNode
+{
+ int val;
+ ListNode *next;
+ ListNode(int x, ListNode *n = nullptr) : val(x), next(n) {}
+};
+
+ListNode *advance(ListNode *from, size_t index)
+{
+ while (index)
+ {
+ if (from == nullptr)
+ {
+ return nullptr;
+ }
+
+ from = from->next;
+ --index;
+ }
+
+ return from;
+}
+
+ListNode *getTail(ListNode *list)
+{
+ if (!list || !list->next)
+ {
+ return list;
+ }
+
+ while (list->next)
+ {
+ list = list->next;
+ }
+ return list;
+}
+
+void freeRagne(ListNode *from, ListNode *to)
+{
+ while (from != to)
+ {
+ ListNode *node = from;
+ from = from->next;
+ delete node;
+ }
+}
+
+void free(ListNode *ll)
+{
+ while (ll)
+ {
+ ListNode *toDelete = ll;
+ ll = ll->next;
+ delete toDelete;
+ }
+}
+
+ListNode *addFront(ListNode *destination, ListNode *target, size_t to)
+{
+ ListNode *tail = getTail(target);
+ ListNode *end = advance(destination, to + 1);
+ tail->next = end;
+ freeRagne(destination, end);
+ return target;
+}
+
+ListNode *mergeInBetween(ListNode *destination, ListNode *target, size_t from, size_t to)
+{
+ if (from == 0)
+ {
+ return addFront(destination, target, to);
+ }
+
+ ListNode *predBegin = advance(destination, from - 1);
+ if (!predBegin)
+ {
+ return nullptr;
+ }
+
+ ListNode *postEnd = advance(predBegin, to - from + 2);
+ ListNode *toDeleteHolder = predBegin->next;
+ ListNode *targetTail = getTail(target);
+
+ predBegin->next = target;
+ targetTail->next = postEnd;
+
+ freeRagne(toDeleteHolder, postEnd);
+
+ return destination;
+}
+
+int main()
+{
+ ListNode *fst = new ListNode(1,
+ new ListNode(2,
+ new ListNode(3,
+ new ListNode(4,
+ new ListNode(6)))));
+
+ ListNode *snd = new ListNode(3,
+ new ListNode(4,
+ new ListNode(5)));
+
+ ListNode *ans = mergeInBetween(fst, snd, 1, 3);
+
+ ListNode *it = ans;
+
+ while(it)
+ {
+ std::cout << it->val << " ";
+ it = it->next;
+ }
+
+ free(ans);
+} \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/queue-insertion.cpp b/Additional/Additional-2023-SI/queue-insertion.cpp
new file mode 100644
index 0000000..f27416a
--- /dev/null
+++ b/Additional/Additional-2023-SI/queue-insertion.cpp
@@ -0,0 +1,109 @@
+#include <iostream>
+
+struct Node
+{
+ Node* next = nullptr;
+ int data = 0;
+ Node(int data, Node* next = nullptr) : data(data), next(next){}
+};
+
+struct Queue
+{
+ Node* head = nullptr;
+ Node* tail = nullptr;
+};
+
+void push(Queue& q, int el)
+{
+ if (q.head == nullptr)
+ q.head = q.tail = new Node(el);
+ else
+ {
+ Node* newNode = new Node(el);
+ q.tail->next = newNode;
+
+ q.tail = newNode;
+ }
+}
+void pop(Queue& q)
+{
+ if (!q.head)
+ return;
+ Node* toDelete = q.head;
+ q.head = q.head->next;
+ delete toDelete;
+}
+
+void insert(Queue& q, int el)
+{
+ Node* iter = q.head;
+
+ while (iter)
+ {
+ if (iter->data % 10 == el % 10)
+ {
+ break;
+ }
+ iter = iter->next;
+ }
+
+ if (iter)
+ {
+ Node* newNode = new Node(el);
+ newNode->next = iter->next;
+ iter->next = newNode;
+ }
+ else
+ {
+ if (!q.head)
+ {
+ Node* newNode = new Node(el);
+ q.head = q.tail = newNode;
+ }
+ else
+ {
+ Node* newNode = new Node(el);
+ q.tail->next = newNode;
+ q.tail = newNode;
+ }
+ }
+}
+
+void print(const Queue& q)
+{
+ const Node* it = q.head;
+
+ while(it)
+ {
+ std::cout << it->data << " ";
+
+ it = it->next;
+ }
+}
+void free(Queue& q)
+{
+ while (q.head)
+ {
+ Node* toDelete = q.head;
+ q.head = q.head->next;
+
+ delete toDelete;
+ }
+
+}
+int main()
+{
+ Queue q;
+
+ push(q, 1);
+ push(q, 2);
+ push(q, 4);
+ push(q, 8);
+ push(q, 16);
+
+ insert(q, 12);
+
+ print(q);
+
+ free(q);
+} \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/readme.md b/Additional/Additional-2023-SI/readme.md
new file mode 100644
index 0000000..8bd0567
--- /dev/null
+++ b/Additional/Additional-2023-SI/readme.md
@@ -0,0 +1,14 @@
+## Разгледани структури от STL
+
+* std::vector
+* std::list
+* std::forward_list
+
+## Разгледани функции от STL
+* std::sort()
+* std::lower_bound()
+* std::upper_bound()
+* std::find()
+* std::find_it()
+* std::merge()
+* std::list::splice \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/rearrange.cpp b/Additional/Additional-2023-SI/rearrange.cpp
new file mode 100644
index 0000000..e5ad080
--- /dev/null
+++ b/Additional/Additional-2023-SI/rearrange.cpp
@@ -0,0 +1,112 @@
+#include <iostream>
+
+struct Node
+{
+ Node* next = nullptr;
+ Node* prev = nullptr;
+ int data = 0;
+ Node(int data, Node* next = nullptr, Node* prev = nullptr) : data(data), next(next), prev(prev) {}
+};
+
+Node* rearange(Node* head)
+{
+ Node* evensBegin = nullptr;
+ Node* evensEnd = nullptr;
+ Node* oddsBegin = nullptr;
+ Node* oddsEnd = nullptr;
+
+ Node* iter = head;
+
+ while (iter)
+ {
+ if (iter->data % 2 == 0)
+ {
+ if (!evensBegin)
+ {
+ evensBegin = evensEnd = iter;
+ iter->prev = nullptr;
+ }
+ else
+ {
+ evensEnd->next = iter;
+ iter->prev = evensEnd;
+ evensEnd = iter;
+ }
+ }
+ else
+ {
+ if (!oddsBegin)
+ {
+ oddsBegin = oddsEnd = iter;
+ iter->prev = nullptr;
+ }
+ else
+ {
+ oddsEnd->next = iter;
+ iter->prev = oddsEnd;
+ oddsEnd = iter;
+ }
+ }
+ iter = iter->next;
+ }
+ if(evensEnd)
+ evensEnd->next = nullptr;
+ if(oddsEnd)
+ oddsEnd->next = nullptr;
+
+ // concat
+ if (!evensBegin)
+ return oddsBegin;
+ if (!oddsBegin)
+ return evensBegin;
+
+ evensEnd->next = oddsBegin;
+ oddsBegin->prev = evensEnd;
+ return evensBegin;
+}
+
+Node* push_front(Node* list, int elem)
+{
+ if(!list)
+ {
+ return new Node(elem);
+ }
+
+ Node* toReturn = new Node(elem, list);
+ list->prev = toReturn;
+ return toReturn;
+}
+
+void free(Node* l)
+{
+ Node* it = l;
+
+ while(it)
+ {
+ Node* toDelete = it;
+ it = it->next;
+ delete toDelete;
+ }
+}
+
+int main()
+{
+ Node* l = nullptr;
+
+ for (size_t i = 0; i < 50; i++)
+ {
+ l = push_front(l, 50 - i);
+ }
+
+ l = rearange(l);
+
+ Node* it = l;
+
+ while(it)
+ {
+ std::cout << it->data << " ";
+ it = it->next;
+ }
+
+ free(l);
+} \ No newline at end of file