soru.java

import java.util.*;

public class HelloWorld{
    // static HashSet<Integer> allLengths(int k, int shorter, int longer){
    //     HashSet<Integer> lengths = new HashSet<Integer>();
    //     getAllLengths(k, 0, shorter, longer, lengths);
    //     return lengths;
    // }
    // // O(2 ^ K)
    
    // static void getAllLengths(int k, int total, int shorter, int longer, HashSet<Integer> lengths) {
    //     if(k == 0) {
    //         lengths.add(total);
    //         return;
    //     }
        
    //     getAllLengths(k-1, total + shorter, shorter, longer, lengths);
    //     getAllLengths(k-1, total + longer, shorter, longer, lengths);
    // }
    
    // O(K)
    static HashSet<Integer> allLengths(int k, int shorter, int longer){
        HashSet<Integer> lengths = new HashSet<Integer>();
        for(int nShorter=0; nShorter <=k; nShorter++){
            int nLonger = k - nShorter;
            int length = nShorter * shorter + nLonger * longer;
            lengths.add(length);
        }
        return lengths;
    }

     public static void main(String []args){
        HashSet<Integer> lengths = allLengths(5, 10, 20);
        Iterator<Integer> it = lengths.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
     }
}

soru.js

/**
 * You are building a diving board by placing a bunch of planks of wood end to end.
 * There are two types of planks, one of length shorter and one of length longer.
 * You must use exactly K planks of wood. Write a method to generate all possible lengths for diving board.
 *
 * N short plank
 * L long plank
 *
 * Questions?
 *  - K input int
 *
 * Must use exactly K planks.
 * K = 5
 * S = 10 cm
 * L = 20 cm
 * S + S + S + S + S = 50
 * S + S + S + S + L = 60
 * S + S + S + L + L = 70
 * S + S + L + L + L = 80
 * S + L + L + L + L = 90
 * L + L + L + L + L = 100
 * 

 *
 * 6
 *
 */

/**
 * hashtable lengths;
 * getlength(k, count, shortPlankSize, longPlankSize, lengths)
 *   if(k < 0){
 *     return lengths;
 *   }
 *   lengths[k] = k * shortPlankSize + count * longPlankSize
 *   return getlength(k-1, count+1, shortPlankSize, longPlankSize, lengths)
 *
 */
// min O(k)
function calculateAllLengths(k, shortPlankSize, longPlankSize) {
  const allLengths = {};
  calculateLengths(k, 0, shortPlankSize, longPlankSize, allLengths);
  return allLengths;
}

function calculateLengths(k, count, shortPlankSize, longPlankSize, allLengths) {
  if (k < 0) {
    return allLengths;
  }
  allLengths[k] = k * shortPlankSize + count * longPlankSize;
  return calculateLengths(
    k - 1,
    count + 1,
    shortPlankSize,
    longPlankSize,
    allLengths
  );
}

const result = calculateAllLengths(5, 10, 20);
console.log(result);

tic-tac-toe.js

/**


 * Design an algorithm to figure out if someone has won a game of tic-tac-toe.
 * Questions:
 *  Rules of tic tac toe?
 *    standard tic tac toe.
 *  dimensions of tic tactoe board?
 *    3 x 3
 *    N x N
 *  How many players?
 *   2 player
 *  Winning conditions?
 *   standard tic tac toe.
 *  Where is this going to run? --irrelevant.
 *  What are the inputs?
 *    array of 3x3
 *
 * Examples:
 * Player 0 wins.
 * 0 0 1
 * 1 0 1
 * 0 1 0
 *
 * const input = [
 *  [0, 0, 1],
 *  [1, 0, 1]
 *  [0, 1, 0]
 * ]
 *
 * 0 1 0
 * 0 0 1
 * 0 1 1
 *
 * Player 0 wins.
 * 0 0 0
 * 1 1 -
 * - - -
 *
 *
 * Draw
 * 0 0 1
 * 1 0 0
 * 0 1 1
 *
 *
 * Conditions:
 */

const case_1 = [
  [0, 0, 0],
  [1, 0, 1],
  [0, 1, 0],
];

const case_2 = [
  [0, 1, 0],
  [0, 0, 1],
  [0, 1, 1],
];

const case_3 = [
  [0, 1, 0],
  [1, 1, null],
  [null, null, null],
];

/**
 * O(1)
 */
function hasWon(input) {
  if (input[0][0] === input[0][1] && input[0][0] === input[0][2]) return true;
  if (input[1][0] === input[1][1] && input[1][0] === input[1][2]) return true;
  if (input[2][0] === input[2][1] && input[2][0] === input[2][2]) return true;

  if (input[0][0] === input[1][0] && input[0][0] === input[2][0]) return true;
  if (input[0][1] === input[1][1] && input[0][1] === input[2][1]) return true;
  if (input[0][2] === input[1][2] && input[0][2] === input[2][2]) return true;

  if (input[0][0] === input[1][1] && input[0][0] === input[2][2]) return true;
  if (input[0][2] === input[1][1] && input[0][2] === input[2][0]) return true;

  return false;
}

const case_4 = [
  [0, 0, 1],
  [1, 0, 0],
  [1, 1, 1],
];

const case_5 = [
  [0, 0, 1, 0],
  [1, 0, 0, 1],
  [1, 1, 1, 1],
  [1, 1, 1, 0],
];

//0010
//1001
//1111
//1110
// let str = "";
// case_5.map((row) => row.join("")).join("");

// Board is N x N
// O(N^2 + N)
function hasWonN(board) {
  const boardSize = board.length;

  // Horizontal
  for (let xi = 0; xi < boardSize; xi++) {
    let firstTile = board[xi][0];
    if (firstTile === null) {
      break;
    }
    for (let yi = 1; yi < boardSize; yi++) {
      const tile = board[xi][yi];
      if (firstTile !== tile) {
        break;
      } else if (yi === boardSize - 1) {
        return true;
      }
    }
  }

  // Vertical
  for (let yi = 0; yi < boardSize; yi++) {
    let firstTile = board[0][yi];
    if (firstTile === null) {
      break;
    }
    for (let xi = 1; xi < boardSize; xi++) {
      const tile = board[xi][yi];
      if (firstTile !== tile) {
        break;
      } else if (xi === boardSize - 1) {
        return true;
      }
    }
  }

  // Diagonal
  // 0,0 1,1 2,2 3,3
  let firstTile = board[0][0];
  for (let xi = 1; xi < boardSize; xi++) {
    if (firstTile !== board[xi][xi]) {
      break;
    } else if (xi === boardSize - 1) {
      return true;
    }
  }

  // Diagonal
  // 0,3 1,2 2,1 3,0
  firstTile = board[0][boardSize - 1];
  for (let xi = 1; xi < boardSize; xi++) {
    if (firstTile !== board[xi][boardSize - xi]) {
      break;
    } else if (xi === boardSize - 1) {
      return true;
    }
  }
  return false;
}

class Pointer {
  constructor(size) {
    this.boardSize = size;
    this.column = 0;
    this.row = 0;
  }

  increase() {
    this.column += 1;
    this.row += 1;
    if (this.column % this.boardSize === 0 && this.row % this.boardSize === 0) {
      return false;
    }
  }
}

function check(row, col) {
  //
}

function optimisedHasWon(board) {
  const pointer = new Pointer(board.length);

  while (pointer.increase()) {
    check(pointer.row, pointer.column);
  }
}

console.log(hasWonN(case_1));
console.log(hasWonN(case_2));
console.log(hasWonN(case_3));
console.log(hasWonN(case_4));
console.log(hasWonN(case_5));