Skip to content

Automatically exported from code.google.com/p/elements-of-programming-interviews

Notifications You must be signed in to change notification settings

koth/elements-of-programming-interviews

Folders and files

NameName
Last commit message
Last commit date

Latest commit

3e28135 · Jun 16, 2014

History

60 Commits
Feb 23, 2014
Aug 4, 2013
Feb 23, 2014
Jan 6, 2014
Jun 16, 2014
Jan 23, 2014
Jun 16, 2014
Feb 23, 2014
Oct 18, 2013
Mar 31, 2014
Jun 16, 2014
Jan 23, 2014
Jan 23, 2014
Jul 10, 2013
Feb 23, 2014
Jan 23, 2014
Jan 23, 2014
Feb 23, 2014
Feb 23, 2014
Feb 23, 2014
Feb 23, 2014
Nov 9, 2012
Sep 27, 2013
Oct 17, 2013
Oct 17, 2013
Jun 16, 2014
Jan 16, 2013
Jan 13, 2014
Jun 16, 2014
Jan 6, 2014
Jan 6, 2014
Jan 10, 2014
Jun 16, 2014
Jun 16, 2014
Mar 31, 2014
Sep 2, 2013
Feb 23, 2014
Jan 23, 2014
Jan 23, 2014
Feb 23, 2014
Sep 1, 2013
Sep 27, 2013
Sep 1, 2013
Mar 2, 2014
Feb 23, 2014
Jan 13, 2014
Feb 23, 2014
Sep 25, 2013
Mar 31, 2014
Sep 27, 2013
Jun 16, 2014
Feb 23, 2014
Dec 12, 2013
Mar 31, 2014
Jun 16, 2014
Jan 16, 2013
Feb 23, 2014
Feb 23, 2014
Jan 13, 2014
Jun 16, 2014
Mar 2, 2014
Jan 23, 2014
Mar 31, 2014
Feb 23, 2014
Feb 23, 2014
Jan 16, 2013
Jan 6, 2014
Sep 28, 2013
Mar 31, 2014
Jan 13, 2014
Feb 23, 2014
Nov 4, 2013
Oct 17, 2013
Nov 9, 2012
Feb 23, 2014
Mar 2, 2014
Nov 9, 2012
Jun 16, 2014
Oct 17, 2013
Jan 16, 2013
Dec 12, 2013
Feb 23, 2014
Feb 23, 2014
Aug 31, 2013
Feb 23, 2014
Feb 23, 2014
Aug 16, 2013
Jan 13, 2014
Feb 23, 2014
Sep 27, 2013
Aug 4, 2013
Sep 25, 2013
Jun 16, 2014
Mar 31, 2014
Mar 31, 2014
Feb 23, 2014
Jul 10, 2013
Nov 9, 2012
Sep 27, 2013
Mar 2, 2014
Feb 23, 2014
Jan 23, 2014
Feb 23, 2014
Jan 6, 2014
Feb 23, 2014
Jun 16, 2014
Feb 23, 2014
Sep 25, 2013
Sep 28, 2013
Sep 28, 2013
Sep 28, 2013
Mar 31, 2014
Mar 31, 2014
Mar 2, 2014
Sep 28, 2013
Nov 4, 2013
Jan 23, 2014
Feb 23, 2014
Sep 25, 2013
Sep 5, 2013
Jun 16, 2014
Sep 28, 2013
Sep 28, 2013
Jun 16, 2014
Feb 23, 2014
Feb 23, 2014
Jun 16, 2014
Mar 31, 2014
Feb 23, 2014
Feb 23, 2014
Sep 27, 2013
Jan 23, 2014
Sep 25, 2013
Jun 16, 2014
Sep 28, 2013
Sep 5, 2013
Sep 28, 2013
Sep 28, 2013
Jan 16, 2013
Dec 12, 2013
Dec 12, 2013
Feb 23, 2014
Sep 27, 2013
Jan 6, 2014
Jan 13, 2014
Mar 31, 2014
Dec 12, 2013
Feb 23, 2014
Feb 23, 2014
Jan 23, 2014
Sep 28, 2013
Dec 11, 2013
Dec 12, 2013
Jun 16, 2014
Dec 22, 2013
Jan 23, 2014
Dec 10, 2013
Jun 16, 2014
Sep 28, 2013
Mar 31, 2014
Jan 13, 2014
Sep 27, 2013
Jun 16, 2014
Jun 16, 2014
Jan 13, 2014
Jun 16, 2014
Mar 31, 2014
Mar 31, 2014
Feb 23, 2014
Sep 26, 2013
Aug 4, 2013
Feb 23, 2014
Sep 25, 2013
Dec 12, 2013
Aug 4, 2013
Jan 6, 2014
Sep 25, 2013
Mar 31, 2014
Dec 12, 2013
Oct 17, 2013
Sep 28, 2013
Sep 28, 2013
Dec 12, 2013
Jan 13, 2014
Sep 25, 2013
Jun 16, 2014
Jun 16, 2014
Mar 31, 2014
Nov 9, 2012
Jan 6, 2014
Jan 10, 2014
Jan 6, 2014
Jan 6, 2014
Sep 25, 2013
Sep 26, 2013
Nov 9, 2012
Jul 10, 2013
Mar 31, 2014
Jan 23, 2014
Feb 23, 2014
Feb 23, 2014
Mar 2, 2014
Mar 2, 2014
Feb 23, 2014
Feb 23, 2014
Mar 31, 2014
Jan 13, 2014
Sep 28, 2013
Sep 26, 2013
Mar 2, 2014
Sep 25, 2013
Feb 23, 2014
Sep 25, 2013
Feb 23, 2014
Feb 23, 2014
Dec 12, 2013
Sep 25, 2013
Jan 13, 2014
Jan 13, 2014
Jan 13, 2014
Sep 25, 2013
Nov 9, 2012
Nov 9, 2012
Jan 6, 2014
Sep 28, 2013
Jan 23, 2014
Feb 23, 2014
Feb 23, 2014
Jan 6, 2014
Mar 31, 2014
Sep 27, 2013
Mar 31, 2014
Feb 23, 2014
Jan 13, 2014
Jan 13, 2014
Jan 16, 2013
Jan 16, 2013
Jun 16, 2014
Sep 26, 2013
Nov 9, 2012
Dec 12, 2013
Sep 27, 2013
Sep 27, 2013
Sep 27, 2013
Mar 9, 2013
Jun 16, 2014
Aug 4, 2013
Dec 12, 2013
Sep 25, 2013
Mar 2, 2014
Oct 17, 2013
Nov 9, 2012
Jan 6, 2014
Mar 2, 2014
Feb 23, 2014
Jan 6, 2014
Sep 25, 2013
Nov 9, 2012
Mar 31, 2014
Jan 16, 2013
Jan 16, 2013
Sep 28, 2013
Jan 23, 2014
Mar 9, 2013
Nov 9, 2012
Jan 16, 2013
Mar 31, 2014
Mar 31, 2014
Feb 23, 2014
Jan 23, 2014
Dec 22, 2013
Nov 9, 2012
Sep 28, 2013
Dec 11, 2013
Jan 10, 2014
Dec 12, 2013
Nov 9, 2012
Jan 6, 2014
Jan 23, 2014
Jan 6, 2014
Sep 28, 2013
Dec 12, 2013
Dec 12, 2013
Feb 23, 2014
Sep 28, 2013
Feb 23, 2014
Sep 28, 2013
Jan 6, 2014
Dec 12, 2013
Feb 23, 2014
Feb 23, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Sep 2, 2013
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Sep 28, 2013
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jan 23, 2014
Feb 23, 2014
Jan 23, 2014
Jan 6, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Sep 27, 2013
Jun 16, 2014
Jun 16, 2014
Jan 23, 2014
Sep 27, 2013
Aug 4, 2013
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Sep 13, 2013
Jun 16, 2014
Mar 31, 2014
Mar 31, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Sep 27, 2013
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Dec 8, 2013
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Aug 15, 2013
Aug 15, 2013
Jun 16, 2014
Dec 12, 2013
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014
Jun 16, 2014

Repository files navigation

// Copyright (c) 2013 Elements of Programming Interviews. All rights reserved.

#include <cassert>
#include <iostream>
#include <memory>
#include <random>

#include "./Postings_list_prototype.h"

using std::cout;
using std::default_random_engine;
using std::endl;
using std::make_shared;
using std::random_device;
using std::shared_ptr;
using std::uniform_int_distribution;

// @include
shared_ptr<ListNode<int>> copy_postings_list(
    const shared_ptr<ListNode<int>>& L) {
  // Returns empty list if L is nullptr.
  if (!L) {
    return nullptr;
  }

  // 1st stage: Copies the nodes from L.
  shared_ptr<ListNode<int>> p = L;
  while (p) {
    auto temp =
        make_shared<ListNode<int>>(ListNode<int>{p->data, p->next, nullptr});
    p->next = temp;
    p = temp->next;
  }

  // 2nd stage: Updates the jump field.
  p = L;
  while (p) {
    if (p->jump) {
      p->next->jump = p->jump->next;
    }
    p = p->next->next;
  }

  // 3rd stage: Restores the next field.
  p = L;
  shared_ptr<ListNode<int>> copied = p->next;
  while (p->next) {
    shared_ptr<ListNode<int>> temp = p->next;
    p->next = temp->next;
    p = temp;
  }
  return copied;
}
// @exclude

template <typename T>
void check_postings_list_equal(shared_ptr<ListNode<T>> a,
                               shared_ptr<ListNode<T>> b) {
  while (a && b) {
    cout << a->data << ' ';
    assert(a->data == b->data);
    assert((a->jump == shared_ptr<ListNode<T>>(nullptr) &&
            b->jump == shared_ptr<ListNode<T>>(nullptr)) ||
           (a->jump && b->jump && a->jump->data == b->jump->data));
    if (a->jump) {
      cout << a->jump->data;
    }
    cout << endl;
    a = a->next, b = b->next;
  }
  assert(a == shared_ptr<ListNode<T>>(nullptr) &&
         b == shared_ptr<ListNode<T>>(nullptr));
}

int main(int argc, char* argv[]) {
  default_random_engine gen((random_device())());
  for (int times = 0; times < 1000; ++times) {
    int n;
    if (argc == 2) {
      n = atoi(argv[1]);
    } else {
      uniform_int_distribution<int> n_dis(1, 1000);
      n = n_dis(gen);
    }
    shared_ptr<ListNode<int>> L = nullptr;
    shared_ptr<ListNode<int>> curr = L;
    for (int i = 0; i < n; ++i) {
      auto temp = make_shared<ListNode<int>>(ListNode<int>{i, nullptr});
      if (L) {
        curr->next = temp;
        curr = temp;
      } else {
        curr = L = temp;
      }
      // Randomly assigned a jump node.
      uniform_int_distribution<int> dis(0, i + 1);
      int jump_num = dis(gen);
      shared_ptr<ListNode<int>> jump = L;
      while (jump_num--) {
        jump = jump->next;
      }
      temp->jump = jump;
    }
    shared_ptr<ListNode<int>> copied = copy_postings_list(L);
    check_postings_list_equal<int>(L, copied);
  }
  return 0;
}

About

Automatically exported from code.google.com/p/elements-of-programming-interviews

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published