Algorithms : complete 02-data_structures 01-basic_data_structures

3 files changed, 60 insertions, 19 deletions

diff --git a/02-data_structures/01-basic_data_structures/01-check_brackets_in_code/check_brackets.cpp b/02-data_structures/01-basic_data_structures/01-check_brackets_in_code/check_brackets.cpp
index 455f9a8..df67bd0 100644
--- a/02-data_structures/01-basic_data_structures/01-check_brackets_in_code/check_brackets.cpp
+++ b/02-data_structures/01-basic_data_structures/01-check_brackets_in_code/check_brackets.cpp
@@ -31,14 +31,32 @@ int main() {
         char next = text[position];
 
         if (next == '(' || next == '[' || next == '{') {
-            // Process opening bracket, write your code here
+            opening_brackets_stack.push(Bracket(next, position));
         }
 
         if (next == ')' || next == ']' || next == '}') {
-            // Process closing bracket, write your code here
+
+            if (opening_brackets_stack.size() == 0) {
+                std::cout << (position + 1) << std::endl;
+                return 1;
+            }
+
+            if (opening_brackets_stack.top().Matchc(next))
+                opening_brackets_stack.pop();
+            else {
+                std::cout << (position + 1) << std::endl;
+                return 1;
+            }
         }
     }
 
+    if (opening_brackets_stack.size() == 0)
+        std::cout << "Success" << std::endl;
+    else {
+        std::cout << (opening_brackets_stack.top().position + 1) << std::endl;
+        return 1;
+    }
+
     // Printing answer, write your code here
 
     return 0;
diff --git a/02-data_structures/01-basic_data_structures/02-tree_height/tree-height.cpp b/02-data_structures/01-basic_data_structures/02-tree_height/tree-height.cpp
index d050e88..c6a55cd 100644
--- a/02-data_structures/01-basic_data_structures/02-tree_height/tree-height.cpp
+++ b/02-data_structures/01-basic_data_structures/02-tree_height/tree-height.cpp
@@ -3,28 +3,39 @@
 #include <algorithm>
 
 class TreeHeight {
-  int n;             
+  int n;
+  int root;
   std::vector<int> parent;
 
 public:
   void read() {
-    std::cin >> n;
-    parent.resize(n);
-    for (int i = 0; i < n; i++)
-      std::cin >> parent[i];
+      std::cin >> n;
+      parent.resize(n);
+      for (int i = 0; i < n; i++) {
+          std::cin >> parent[i];
+          if (parent[i] < 0)
+              root = i;
+      }
+      /* std::cout << root << std::endl; */
   }
 
-  int compute_height() {
-    // Replace this code with a faster implementation
-    int maxHeight = 0;
-    for (int vertex = 0; vertex < n; vertex++) {
-      int height = 0;
-      for (int i = vertex; i != -1; i = parent[i])
-        height++;
-      maxHeight = std::max(maxHeight, height);
-    }
-    return maxHeight;
+  int compute_height()
+  {
+      std::vector<int> heights(n);
+      for (int vertex = 0; vertex < n; vertex++) {
+          if (heights[vertex] != 0)
+              continue;
+          int height = 0;
+          for (int i = vertex; i != -1; i = parent[i]) {
+              height++;
+              if (height > heights[i])
+                  heights[i] = height;
+              else break;
+          }
+      }
+      return heights[root];
   }
+
 };
 
 int main() {
diff --git a/02-data_structures/01-basic_data_structures/03-network_packet_processing_simulation/process_packages.cpp b/02-data_structures/01-basic_data_structures/03-network_packet_processing_simulation/process_packages.cpp
index 1d2df89..0f03689 100644
--- a/02-data_structures/01-basic_data_structures/03-network_packet_processing_simulation/process_packages.cpp
+++ b/02-data_structures/01-basic_data_structures/03-network_packet_processing_simulation/process_packages.cpp
@@ -29,9 +29,21 @@ public:
         finish_time_()
     {}
 
-    Response Process(const Request &request) {
-        // write your code here
+    Response Process(const Request &request)
+    {
+        while (finish_time_.size() > 0 && finish_time_.front() <= request.arrival_time)
+            finish_time_.pop();
+
+        int s = finish_time_.size();
+        if (s == size_)
+            return Response(true,0);
+
+        int start_time = ((s > 0) ? finish_time_.back() : request.arrival_time);
+        finish_time_.push(start_time + request.process_time);
+
+        return Response(false, start_time);
     }
+
 private:
     int size_;
     std::queue <int> finish_time_;