[JS] Basic CS Assessments

과정을 시작한지 3주가 되어가는 시점에서 중간고사 격이라고 생각되는 평가 시간이 다가왔다. 3주 동안 배운 내용들을 잘 이해하고 있는지 코드로 구현하고, this 바인딩, closure 등 헷갈릴 수 있는 개념에 대해 객관식 테스트가 진행됐다.

1. algorithm time complexity

몇가지 함수가 나오고, 해당 함수들의 시간 복잡도를 계산하는 문제다. 친절하게도, 문제의 답을 먼저 알려주고 왜 이런 복잡도를 갖는지 이유를 설명하게끔 했다. 3 문제가 나왔고, 각각의 답은 LINEAR, LOGARITHMIC, EXPONENTIAL 이었다.

복잡도를 계산하는 방법을 정확히 알지 못하기 때문에, 추상적으로 정답을 유추해봤는데, 그 과정이 인상적이었던 문제는 정답이 LOGARITHMIC인 문제였다.

var nthPower = function(base, exponent) {
  // Base case:
  if (exponent === 0) {
    return 1;
  // If exponent is odd
  } else if (exponent % 2 !== 0) {
    return base * nthPower(base, exponent - 1);
  // If exponent is even
  } else {
    return nthPower(base * base, exponent / 2);
  }
};

base에는 상관없이 exponent 의 값을 5, 10, 100, 1000 으로 증가시켰을 때, 계산횟수 또한 늘어나기는 했지만, 증가폭이 갈 수록 줄어들었다.(4, 5, 10, 15...) 이는 O(1)보다는 크고 O(n)보다는 작은 복잡도를 지니기 때문에 O(log n)이라고 유추했다.

2. datastructure:queue

큐(Queue)를 구현하는 문제다. 구현해야 하는 큐의 메소드는 큐에 값을 추가하는 add() 값을 제거하는 remove(). 큐는 FIFO(First In First Out)형태로, 추가를 할 때는 맨 뒤에 추가 되지만, 제거를 할 때는 큐의 맨 앞부분이 먼저 제거가된다. 큐는 트리나 그래프에서 너비우선탐색(Breadth First Search, BFS)에 사용된다.

var Queue = function() {
  this._storage = {};
  this.length = 0;
};

Queue.prototype.add = function(value) {
  if(this.length === 0){
    this._storage[0] = value;
    this.length++;
  }
  else{
    this._storage[this.length] = value;
    this.length++;
  }
};
Queue.prototype.remove = function() {
  let output;
  if(this.length === 0){
    return undefined;
  }else{
    output = this._storage[0];
    delete this._storage[0];
  }
  return output;
};

3. javascript inheritance using pseudo classical pattern

자바스크립트에서의 상속을 Pseudo classical Pattern 으로 구현하는 문제다. ES6 에서는 class 키워드가 있기 때문에 생략할 수 있는 부분들이 있지만, 원리를 집고 넘어가기 위한 문제인 듯 하다. 부모 클래스를 상속받기 위해서 자식 클래스를 선언할 때 꼭 해줘야 하는 것들은 생성자 상속, 프로토타입 설정, 생성자 설정, 메소드 상속 이다.

• 생성자 상속: 자식 클래스의 안에서 부모클래스이름.call(this)를 해주면 된다. 여기서 this는 자식 클래스를 뜻하며, 부모클래스의 생성자를 자식클래스를 this바인딩 시켜서 호추랗는 것이다.
• 프로토타입 설정: 상속을 구현할 때, 상속의 모델을 프로토타입으로 가지고 있어야 한다. 여기서는 FlyingHorse라는 클래스가 Horse라는 클래스를 상속받고 있기 때문에, FlyingHorse.prototype을 Horse.prototype으로 설정해줘야 한다. FlyingHorse.prototype = Object.create(Horse.prototype);
• 생성자 설정: FlyingHorse프로토타입만 설정해주면 FlyingHorse는 자신의 constructor와의 연결이 끊어진다. 다시 연결해준다. lyingHorse.prototype.constructor = FlyingHorse;
• 메소드 상속: 다형성을 구현하기 위해 필요하다. Class키워드를 이용할 때 처럼 super()를 사용하면 될 줄 알았는데, 클래스가 class 로 선언되어있지 않으면 사용할 수 없는 것 같다. FlyingHorse의 메소드 안에서 Horse의 메소드를 상속받고 싶다면, call혹은 apply를 이용하자.

FlyingHorse.prototype.goSomewhere = function(destination, milesToDestination){
Horse.prototype.goSomewhere.call(this,destination);
}

전체 코드

var Horse = function(name) {
  this.name = name;
};
Horse.prototype.goSomewhere = function(destination) {
  return this.name + ' is galloping to ' + destination + '!';
};
//Horse를 상속
var FlyingHorse = function(name, color) {
  this.color = color;
  Horse.call(this,name);
};
// 1. 프로토타입 설정
FlyingHorse.prototype = Object.create(Horse.prototype);
// 2. 생성자 설정
FlyingHorse.prototype.constructor = FlyingHorse;
// 3. 메소드 상속
FlyingHorse.prototype.goSomewhere = function(destination, milesToDestination){
  if (milesToDestination < 10) {
    return Horse.prototype.goSomewhere.call(this,destination);
  } else {
    return this.name + ' is flying to ' + destination + '!';
  }
}

4. recursion print array

입력으로 들어오는 배열에 있는 요소들을 string형태로 붙여서 출력하는 함수를 작성하는 문제다. 예를 들어 입력이 [1,2,3,,['hello',7],90] 이라면 출력은 '123hello790'이 되어야한다. 문제를 해결하기 위해서는 배열안의 요소가 배열일 경우를 처리해야한다. 깊이우선탐색을 이용했다.

var printArray = function(array=[]) {
  var makeStr = function(arr){
    return arr.reduce((acc,cur) => Array.isArray(cur)? acc.concat(makeStr(cur)) :
                      acc.concat(cur),[]);
  }
  return makeStr(array).join('');
};

5. tree-map

트리를 구현하는 문제다. 트리에 자식노드를 추가하는 addChild()와 트리를 순회하는 map() 두가지 메소드를 작성해야 하는데, 핵심은 map()구현인 것 같다. map()은 callback함수를 인자로 받고, original 트리의 모든 노드에 callback함수를 적용한 값을 가진 새로운 트리를 반환해야 한다.

var Tree = function(value) {
  this.value = value;
  this.children = [];
};

Tree.prototype.addChild = function(child) {
  const newTree = new Tree(child);
  this.children.push(newTree);
};

Tree.prototype.map = function(callback) {
  // your code here
  const newTree = new Tree(callback(this.value));
  (this.children || []).forEach(
    child => newTree.children.push(child.map(callback))
    );
  return newTree;
};