<commit_before>/*********************************************************************
 *                     Pair Programming I                            *
 *                                                                   *
 *  Instructions: List the Time and Space complexity of each         *
 *                of the following functions in the space provided   *
 *                                                                   *
 *********************************************************************/

/**
 * Problem 1:
 *  Time Complexity: 0(1)
 *  Auxiliary Space Complexity: 0(1)
 **/

function isThereCat(object) {

  while(object['cat']) {
    console.log("There is cat!");
    delete object['cat'];
  }
  console.log("There is no cat!");
};


/**
 * Problem 2:
 *  Time Complexity: // 0(1)
 *  Auxiliary Space Complexity: // 0(1)
 **/

function powerOfThrees(int) {
  var result = []; // 0(1)
  var count = 1; // 0(1)
  var temp = 1; // 0(1)

  while(count <= 3) { //0(1)
    temp *= int;
    result.push(temp);
    count++;
  }

  return result;
};


/**
 * Problem 3:
 *  Time Complexity: // 0(1)
 *  Auxiliary Space Complexity: // 0(1)
 **/

function findDuplicate(collection) {
  var len = collection.length; // 0(1)
  var currItem; // 0(1)

  for (var i = 0; i < len; i++) {
    currItem = collection[i];

    for (var j = 0; j < len; j++) {
      if (j !== i) {
        if (currItem === collection[j]) {
          return true;
        }
      }
    }
  }
  return false;
};


/**
 * Problem 4:
 *  Time Complexity: // 0(n*m)
 *  Auxiliary Space Complexity: // 0(n*m)
 **/

function intersectionPoints(array1, array2) {
  var result = []; // 0(1)
  var points; // 0(1)

  for (var i = 0; i < array1.length; i++) { // 0(n)
    for (var j = 0; j < array2.length; j++) { // 0(m)
      if (array1[i] === array2[j]) {
        points = [i,j];
        result.push(points); // 0(n*m)
        points = [];
      }
    }
  }

  return result;
};


/**
 * Problem 5:
 *  Time Complexity: 0(n)
 *  Auxiliary Space Complexity: // 0(n)
 **/

function nthFibonacci(n) {
  var result = [0,1]; // 0(1)

  for(var i = 1; i < n; i++) {
    result[i+1] = result[i] + result[i-1];
  }

  return result[n];
};


/************************
 *
 * Problem: Refactor findDuplicate to find all repeating elements in O(n) time complexity
 *          What is the auxiliary space complexity of your solution?
 *
 *          Auxiliary Space Complexity:
 **/

 function findDuplicate(collection) {
   lib ={};
   for elem in array
     if lib[elem]
       lib[elem]++
     else
       lib[elem] =1
     end
     result=[]
     for key in lib
       if lib[key] > 1
         result.push(key)
       end
     end
 end


/**
 *  Time Complexity:
 *  Auxiliary Space Complexity:
 **/

function nthFibonacci(n){
  var result; // 0(1)

  function searchFib(index){
    if(index < 2){
      return index;
    } else {
      return searchFib(index-2) + searchFib(index-1);
    }
  }

  result = searchFib(n);
  return result;
};

// /----------------------------------------------

// time complexity of the following code: O(log N)
 var a = 0, i = N;
        while (i > 0) {
            a += i;
            i /= 2;
        }

<commit_msg>add time complex problem<commit_after>/*********************************************************************
 *                     Pair Programming I                            *
 *                                                                   *
 *  Instructions: List the Time and Space complexity of each         *
 *                of the following functions in the space provided   *
 *                                                                   *
 *********************************************************************/

/**
 * Problem 1:
 *  Time Complexity: 0(1)
 *  Auxiliary Space Complexity: 0(1)
 **/

function isThereCat(object) {

  while(object['cat']) {
    console.log("There is cat!");
    delete object['cat'];
  }
  console.log("There is no cat!");
};


/**
 * Problem 2:
 *  Time Complexity: // 0(1)
 *  Auxiliary Space Complexity: // 0(1)
 **/

function powerOfThrees(int) {
  var result = []; // 0(1)
  var count = 1; // 0(1)
  var temp = 1; // 0(1)

  while(count <= 3) { //0(1)
    temp *= int;
    result.push(temp);
    count++;
  }

  return result;
};


/**
 * Problem 3:
 *  Time Complexity: // 0(1)
 *  Auxiliary Space Complexity: // 0(1)
 **/

function findDuplicate(collection) {
  var len = collection.length; // 0(1)
  var currItem; // 0(1)

  for (var i = 0; i < len; i++) {
    currItem = collection[i];

    for (var j = 0; j < len; j++) {
      if (j !== i) {
        if (currItem === collection[j]) {
          return true;
        }
      }
    }
  }
  return false;
};


/**
 * Problem 4:
 *  Time Complexity: // 0(n*m)
 *  Auxiliary Space Complexity: // 0(n*m)
 **/

function intersectionPoints(array1, array2) {
  var result = []; // 0(1)
  var points; // 0(1)

  for (var i = 0; i < array1.length; i++) { // 0(n)
    for (var j = 0; j < array2.length; j++) { // 0(m)
      if (array1[i] === array2[j]) {
        points = [i,j];
        result.push(points); // 0(n*m)
        points = [];
      }
    }
  }

  return result;
};


/**
 * Problem 5:
 *  Time Complexity: 0(n)
 *  Auxiliary Space Complexity: // 0(n)
 **/

function nthFibonacci(n) {
  var result = [0,1]; // 0(1)

  for(var i = 1; i < n; i++) {
    result[i+1] = result[i] + result[i-1];
  }

  return result[n];
};


/************************
 *
 * Problem: Refactor findDuplicate to find all repeating elements in O(n) time complexity
 *          What is the auxiliary space complexity of your solution?
 *
 *          Auxiliary Space Complexity:
 **/

 function findDuplicate(collection) {
   lib ={};
   for elem in array
     if lib[elem]
       lib[elem]++
     else
       lib[elem] =1
     end
     result=[]
     for key in lib
       if lib[key] > 1
         result.push(key)
       end
     end
 end


/**
 *  Time Complexity:
 *  Auxiliary Space Complexity:
 **/

function nthFibonacci(n){
  var result; // 0(1)

  function searchFib(index){
    if(index < 2){
      return index;
    } else {
      return searchFib(index-2) + searchFib(index-1);
    }
  }

  result = searchFib(n);
  return result;
};

// /----------------------------------------------

// time complexity of the following code: O(log N)
 var a = 0, i = N;
        while (i > 0) {
            a += i;
            i /= 2;
        }

// ---------------------------------------------

// What is the worst case time complexity of the following code :

/*
 * V is sorted
 * V.size() = N
 * The function is initially called as searchNumOccurrence(V, k, 0, N-1)
 */


function searchNumOccurrence(vector<int> &V, k, start, end) {
    if (start > end) return 0;
    var mid = (start + end) / 2;
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end);
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1);
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);
}

Time Complexity: 0(n); // all elements can be the same
{'fraction_non_alphanumeric': 0.21030405405405406, 'fraction_numerical': 0.021114864864864864, 'mean_word_length': 1.8149762282091917, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7377936', 'n_tokens_mistral': 2461, 'n_tokens_neox': 2306, 'n_words': 646}