CareerCup

C++ solution with operand and operator stack

#include <map>
#include <sstream>
#include <stdio.h>
#include <string>
#include <stack>
using namespace std;

double GetNum(stringstream &ss) {
  double v;
  ss >> v;
  return v;
}

char GetOp(stringstream &ss) {
  char c;
  ss >> c;
  return c;
}

void Calc(stack<char> &ops, stack<double> &nums) {
  double v2 = nums.top();
  nums.pop();
  double v1 = nums.top();
  nums.pop();
  double res;
  switch (ops.top()) {
    case '+': res = v1+v2; break;
    case '-': res = v1-v2; break;
    case '*': res = v1*v2; break;
    case '/': res = v1/v2; break;
  };
  nums.push(res);
  ops.pop();
}

double EvalExpressionString(const string &e) {
  const map<char, int> op_prec{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
  stack<double> nums;
  stack<char> ops;
  stringstream ss(e);

  // add first number
  nums.push(GetNum(ss));
  while (!ss.eof()) {
    char next_op = GetOp(ss);

    // calc all ops in stack with higher precedence than next op
    while (!ops.empty() && op_prec.at(ops.top()) > op_prec.at(next_op))
      Calc(ops, nums);

    ops.push(next_op);
    nums.push(GetNum(ss));
  }

  // calc remaining ops
  while (!ops.empty())
    Calc(ops, nums);
  return nums.top();
}

int main() {
  printf("%f\n", EvalExpressionString("3+12*3-4/7"));
  printf("%f\n", EvalExpressionString("3+2*2*3-1"));
}

C++ solution

Btw: The second example multiplication is wrong, it's 536282028 X 352321 (one less 8)

#include <algorithm>
#include <vector>
using namespace std;

vector<int> MultiplyVectors(const vector<int> &v1, const vector<int> &v2) {
  vector<vector<int>> sums;
  for (int i = v2.size()-1; i >= 0; --i) {
    sums.push_back(vector<int>(v2.size()-1-i, 0));
    int carry = 0;
    for (int j = v1.size()-1; j >= 0; --j) {
      int v = v1[j]*v2[i]+carry;
      sums.back().push_back(v%10);
      carry = v/10;
    }
    if (carry != 0)
      sums.back().push_back(carry);
  }

  size_t max_idx = 0;
  for (size_t i = 0; i < sums.size(); ++i)
    max_idx = max(max_idx, sums[i].size());

  vector<int> ret;
  int v = 0;
  for (size_t i = 0; i < max_idx; ++i) {
    for (size_t j = 0; j < sums.size(); ++j) {
      if (i < sums[j].size())
        v += sums[j][i];
    }
    ret.push_back(v%10);
    v /= 10;
  }
  if (v != 0)
    ret.push_back(v);

  reverse(ret.begin(), ret.end());
  return ret;
}

C++ implementation with O(n)

#include <stdio.h>
#include <vector>
using namespace std;

struct Node {
  int value;
  Node *next;
};

Node *MergeLinkedLists(Node *n1, Node *n2) {
  Node *head = nullptr;
  Node *prev = nullptr;
  while (n1 || n2) {
    Node *next = nullptr;
    if (!n1 ||
        (n1 && n2 && n2->value < n1->value)) {
      next = n2;
      n2 = n2->next;
    } else {
      next = n1;
      n1 = n1->next;
    }
    if (!head)
      head = next;
    else
      prev->next = next;
    prev = next;
  }
  return head;
}

// Test Code

Node *MakeLinkedList(const vector<int> &v) {
  Node *prev = nullptr;
  Node *head = nullptr;
  for (auto &e : v) {
    Node *n = new Node{e, nullptr};
    if (!head)
      head = n;
    else
      prev->next = n;
    prev = n;
  }
  return head;
}

void Print(Node *n) {
  while (n) {
    printf("%d\n", n->value);
    n = n->next;
  }
}

int main() {
  Node *l1 = MakeLinkedList({1, 3, 4, 8});
  Node *l2 = MakeLinkedList({2, 3, 9});

  Node *l_merged = MergeLinkedLists(l1, l2);

  Print(l_merged);
}

C++11 implementation using topological sort

#include <map>
#include <set>
#include <stdio.h>
#include <vector>
using namespace std;

typedef map<string, vector<string>> DepMap;

// collect reversed topological sorted order in acc
void Visit(const string &key, DepMap &dm, set<string> &visited, vector<string> &acc) {
  if (visited.find(key) == visited.end()) {
    visited.insert(key);
    for (const auto &dep_key : dm[key])
      Visit(dep_key, dm, visited, acc);
    acc.push_back(key);
  }
}

// DepMap -> build order
vector<string> ModuleBuildOrder(DepMap dm) {
  vector<string> order;
  set<string> visited;
  if (!dm.empty())
    Visit(dm.begin()->first, dm, visited, order);
  return order;
}

int main() {
  vector<string> order = ModuleBuildOrder({
      {"A", {"B", "C"}},
      {"B", {"D", "E", "F"}},
      {"D", {"F"}} });
  for (const auto &s : order)
    printf("%s\n", s.c_str());
}

Can you elaborate that? It does exactly the same amount of I/O as your solution if called with 2*st_blksize and has a lot less unneeded complexity

C++ solution without recursion. It uses a binary count/mask to choose which elements are considered for the sum. It's O(2^n), same as NP-hard subset sum problem.

#include <stdio.h>
#include <vector>
using namespace std;

bool TryInc(vector<int> &v) {
  int carry = 1;
  for (auto &e : v) {
    e += carry;
    carry = (e > 1);
    e %= 2;
  }
  return carry == 0;
}

void FindSubsetSumZero(const vector<int> &v) {
  vector<int> mask(v.size(), 0);
  mask.front() = 1;

  while (TryInc(mask)) {
    // calculate sum
    int sum = 0;
    for (size_t i = 0; i < v.size(); ++i)
      sum += (mask[i] ? v[i] : 0);

    // print if found
    if (sum == 0) {
      for (size_t i = 0; i < v.size(); ++i)
        if (mask[i])
          printf("%d ", v[i]);
      printf("\n");
    }
  }
}

Only finds subsets of length 2 and 3

C++ solution using only FILE-API. It can be adjusted to use at most n bytes of extra memory

class MyFILE {
 public:
  MyFILE(const char* fname)
      : f_(fopen(fname, "r+"))
  {}

  ~MyFILE() {
    fclose(f_);
  }

  int Size() {
    fseek(f_, 0, SEEK_END);
    return ftell(f_);
  }

  void ReadAt(int pos, int len, uint8_t *v) {
    fseek(f_, pos, SEEK_SET);
    fread(&v[0], 1, len, f_);
  }

  void WriteAt(int pos, int len, const uint8_t *v) {
    fseek(f_, pos, SEEK_SET);
    fwrite(&v[0], 1, len, f_);
  }

 private:
  FILE *f_;
};


void ReverseFileInplace(const char *fname, const int max_bufsize) {
  int bufsize = max_bufsize/2;
  vector<uint8_t> buf(2*bufsize, 0);
  MyFILE f(fname);
  int size = f.Size();

  int b = 0;
  int e = size-bufsize;

  while (b+bufsize <= e) {
    f.ReadAt(b, bufsize, &buf[0]);
    f.ReadAt(e, bufsize, &buf[bufsize]);
    reverse(buf.begin(), buf.end());
    f.WriteAt(e, bufsize, &buf[bufsize]);
    f.WriteAt(b, bufsize, &buf[0]);
    b += bufsize;
    e -= bufsize;
  }

  int rest = e+bufsize-b;
  f.ReadAt(b, rest, &buf[0]);
  reverse(buf.begin(), buf.begin()+rest);
  f.WriteAt(b, rest, &buf[0]);
}

Short C++ solution (O(n))

#include <string>
using namespace std;

void TrimSpaces(string &s) {
  int write_idx = 0;
  int read_idx = 0;
  bool do_trim = true;  // trim at start
  while (read_idx < s.size()) {
    if (s[read_idx] != ' ' || !do_trim)
      s[write_idx++] = s[read_idx];
    do_trim = (s[read_idx++] == ' ');
  }
  // fill up with spaces (or trunc string to write_idx length)
  while (write_idx < s.size())
    s[write_idx++] = ' ';
}

Short O(n) solution (C++11)

#include <stdio.h>
#include <vector>
using namespace std;

typedef pair<int, int> App;

void FindFreeSlots(const vector<App>& v1, const vector<App>& v2)
{
  auto i1 = v1.begin();
  auto i2 = v2.begin();

  while (i1+1 != v1.end() || i2+1 != v2.end()) {
    int start = max(i1->second, i2->second) + 1;
    int end = 0;

    if (i1+1 == v1.end()) {
      end = (i2+1)->first - 1;
      ++i2;
    } else if (i2+1 == v2.end()) {
      end = (i1+1)->first - 1;
      ++i1;
    } else {
      end = min((i1+1)->first, (i2+1)->first) - 1;
      if ((i1+1)->first < (i2+1)->first)
        ++i1;
      else
        ++i2;
    }

    if (end-start > 0)
      printf("(%d, %d)\n", start, end);
  }
}

int main() {
  FindFreeSlots({{1,5}, {10, 14}, {19, 20}, {21,24}, {27, 30}},
                {{3, 5}, {12, 15}, {18, 21}, {23, 24}});
  // ouput: (6,9) (16,17) (25,26)
  return 0;
}