AtCoder ABC057 D - Maximum Average Sets

問題 D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder N(1 <= N <= 50)個の品物が与えられ、それぞれの品物には価値Vi(1 <= i <= N)が設定されている。A個以上、B以下の品物を取ることが出来る時、選択した品物の価値の最大の平均値と、…

AtCoder ABC057 C - Digits in Multiplication

問題 C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder 整数N(1 <= N <= 1010)が与えられ、A * B = Nを満たすA, BについてF(A, B)の値が最小となるものを出力する問題。ここで、F(A, B)とはAとBの桁数を比べ小さい方の桁数を返り値す…

【グラフ理論とネットワーク理論】Matrix Expression of Graphs and Paths #2

Introduction Here is the article of the last time class. keita-matsushita.hatenablog.com Matrix Expression of Graphs and Paths Graphs can be expressed by matrixes. Below matrixes express above the graph. Incidence matrix (接続行列) Cols re…

【Deep Learning お勉強 #3】ニューラルネットワークとは

はじめに 前回の記事はこちら 【Deep Learning お勉強 #2】パーセプトロンを実装してみよう - マツシタケイタの技術ブログ(勉強中) 今回はニューラルネットワークについて触れる。 パーセプトロンからニューラルネットワークへ 復習も兼ねてパーセプトロンの…

【Deep Learning お勉強 #2】パーセプトロンを実装してみよう

はじめに この記事はパーセプトロンを実際に簡単な例を使って実装してみようというもの。 パーセプトロン自体の説明は以下の記事を参照。 keita-matsushita.hatenablog.com 論理回路をパーセプトロンで表現する 以下のテーブルはANDゲートの真偽値表である。…

【Deep Learningのお勉強 #1 】パーセプトロンとはなんぞや

はじめに 『ゼロから作るDeep Learning』という本を読み、得た知識などをメモとしてを書き記す。 また、この記事はパーセプトロンというアルゴリズムについてまとめる。 どうやら、パーセプトロンというものは、ディープラーニングの起源となるアルゴリズム…

【グラフ理論とネットワーク理論】Graph #1

グラフとは何か グラフは以下のコンポーネントで成り立つ。 節点、頂点: 対象物(スイッチ、ルータ) Node, Vertex: Objectives(Switch, Router) 枝、辺: 接点間の関係(伝送路) Branch, Edge: Relation among nodes(Transmission lines) つまり、グラフとは節…

SwiftでCurrentUserを実装する

ソースコード シングルトンを使って実装する。 参考 stackoverflow.com

AtCoder ARC 004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

B - 2点間距離の最大と最小 ( Maximum and Minimum ) B: 2点間距離の最大と最小 ( Maximum and Minimum ) - AtCoder Regular Contest 004 | AtCoder N + 1個(0 ~ N)点がx,y平面上にある時、i番目の点とi+1番目の点との距離が与えられる(0 <= i < N)。 この時…

AtCoder ARC 004 A - 2点間距離の最大値 ( The longest distance )

A - 2点間距離の最大値 ( The longest distance ) A: 2点間距離の最大値 ( The longest distance ) - AtCoder Regular Contest 004 | AtCoder N個のx,y座標が与えられ、任意の2つの点の距離が最大となる値を出力する問題 解法 与えられる点の数がN(2 <= N <…

HimotokiとAPIKitでAPIクライアント

APIKitとは GitHub - ishkawa/APIKit: Type-safe networking abstraction layer that associates request type with response type. Himotokiとは GitHub - ikesyo/Himotoki: A type-safe JSON decoding library purely written in Swift 単一のモデルをデコ…

ネットワークの仮想化

ポートベースVLANとタグベースVLAN VLANとは、物理的にには1つのネットワークを理論的に複数のネットワークに分ける技術。 営業部が入居するオフィスに、経理部も同居することになった時、LAN配線は既存のもの使いながら、営業部と経理部とであたかも別の2…

TCP/IPで通信するための仕組み

可変長サブネットマスクとCIDR 可変長サブネットマスク サブネット毎に、サビネットマスクの長さを変えることができる技術。サブネットマスクの長さを自由に変えられるようになると、サブネット毎に接続するコンピュータ数を柔軟に決める事ができる。 CIDR …

TCP/IPの基礎知識

TCP/IP コンピュータネットワークで広く用いられている通信プロトコル。TCP(Transmission Control Protocol)とIP(Internet Protocol)と呼ばれるプロトコルのセット。 TCP/IPのレイヤー構成 アプリケーション層 ... 具体的な通信サービスを実現する トランス…

ネットワークの基礎知識

ネットワークとは ネットワークの働きは「アプリ同士が何かを行うためにデータをやり取りできるようにしてやること」。 それを実現するために、データを配送するためのルールや、使用する機器や通信媒体、サービス毎に決められたデータの形式や手順を覚えれ…

3Sum Closest : LeetCode

Problem leetcode.com 与えられたInt型の配列numsの要素の内、3つ選んだ要素の和がtargetに最も近い値を見つける問題。 Solution 全列挙によるO(N3)の解法 配列の全ての3つの要素の和を算出し、その中から一番targetに近い値を見つける事で問題を解くこと…

Maximum Size Subarray Sum Equals k

Problem discuss.leetcode.com Solution This problem can be solved by using HashMap effectively. First, we store each sum of range from 0 to i (0 <= i < N). While we traverse the array, we check if the (sum - k) is stored in HashMap. If the …

Alien Dictionary : LeetCode

Problem https://leetcode.com/problems/alien-dictionary/?tab=Description Solution This problem can be solved by using Topological Sort.

Combination Sum III : LeetCode

Problem leetcode.com Source Code

Implement Trie (Prefix Tree)

Problem leetcode.com Source Code

Problem leetcode.com Solution This problem can be solve by DFS with depth of tree. In my code, lists.size() == depth means that the traversing depth changes. Source Code

Maximum Product of Word Lengths

Problem leetcode.com Solution This problem can be solved effectively by using bit manipulation. We can manage the count of appearance of each letters. Lower case letters are transformed to Integer within 26. This takes 0(N2) time. Source C…

AWSにおける可用性を向上するパターンをまとめる

クラウドにおける可用性とは 「可用性(Availability)」とはシステムが継続して稼働できる能力の事。システムを稼働しているサーバーや、データを保存しておくデータベースが1つで設計されている場合、その1つが落ちた場合にシステムが止まってしまう。これ…

配列における3つの要素の和

Problem leetcode.com 与えられた配列において、任意の3点の和がゼロとなる組合せを全て取得する問題。 Solution この問題は以下のように解くことができる。 任意の3点をstart, middle, endと置く(start < middle < end) startを固定し、middle = start + …

AtCoder ABC D - Mixing Experiment

問題 D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder 解き方 全列挙を考える 全列挙する場合、i番目の薬品を購入する場合としない場合を2パターンをN回行うので、計算量はO(2N)となりNは最大40なので間に合わない。 動的計画法を使う dp(i…

ビット操作を用いて順列を求める

どの部分の要素を既に使用したかをbitを用いて管理する

Sort Objects with Comparator

Heaps: Find the Running Median

Problem www.hackerrank.com This problem is that we calculate median of array the range is from 0 to ith. Solution By using Two Priority Queues: minHeap and maxHeap, we can solve this problem. The roles of them are following. minHeap : To s…

Trie Tree in Java

What is Trie Tree Trie Tree is one of the tree structure to search element. The feature of this tree that each node dose not have element information, but also each edge has element information. Trie tree is used to search String like dict…

Heap Sort in Java

What is Heap Reference www.youtube.com Heap is the tree structure that has two following restrictions. Binary Tree Parent node is smaller or bigger than children nodes. Heap is good at controlling the relation about small and large. So hea…

Bucket Sort in Java

What is Bucket Sort Bucket Sort is linear sort algorithm. It takes O(N) time. But this algorithm has some restrictions to use. The restrictions are following We know the maximum value in array The maximum value is not too large each elemen…

Maximum Subarray

Problem Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6. leetcode.com…

Find All Anagrams in a String: Amazon

Problem Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of outp…

Count Path Sum in Binary Tree

Problem You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only fr…

LRU Cache

Problem leetcode.com Solution This problem can be solved by Double Linked List and HashMap. Source Code

Find an Element from Sorted Matrix

Problem Given an M * N matrix in which each row and each column is sorted in ascending order, write a method to find an element. Solution O(N + M) solution By traversing matrix from upper right to lower left, we can solve this problem in O…

Find the location of the given string from a sorted array of string which is interspersed with empty strings

Problem Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string EXAMPLE Input: find “ball” in {“at”, “”, “”, "ball”, "”, "”, "car”,“”, "”, "dad”, ”“, ”“} Output:4 Solu…

About HashTable in Java

What’s HashMap HashTable is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array. Hash table - Wikipedia Structure Of HashMap …

Print all paths which sum to a given value in a Binary Tree

Problem You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path dose not need to start or end at the root or leaf. Solution First, let’s approach this pro…

Check if small binary tree T1 is a suibtree of large binary Tree T2

Problem You have two large binary tree: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. A tree T2 is a subtree of T1 if there exists a node n in T1 such the the subtree of…

About LinkedList class in Java

What’s LinkedList The LinkedList class implements the List interface. The structure is Doubly-linked list in java, each node has next node and previous node. Time Complexity add(E e) function This function takes O(1) time. This is because,…

About ArrayList class in Java

What’s ArrayList The ArrayList class implements the List interface. ArrayList supports dynamic arrays that can grow as needed. Standard Java arrays are of a fixed length. After arrays are created, they cannot grow or shrink, which means th…

Find the next node (in-oder traversal) of a given node in a binary search tree

Problem Write an algorithm to find the next node (i.e., in-oder successor) of a given node in a binary search tree. You may assume that each node has a link to its parent. Solution This problem can be solved by thinking the two patterns. F…

Find the First Common Ancestor of the two nodes in a binary tree

Problem Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. Node: This is not necessarily a binary search tree. Solution I’ll solve this pr…

Check if a binary tree is a binary search tree

Problem Implement a function to check if a binary tree is a binary search tree Solution There are some solutions to solve this problem. I’ll introduce the all solution which includes I came up with. First Solution is using a range (min, ma…

ツリーグラフにおける最短ルートの算出

問題 B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder 解法 与えられたノードからスタートし、宝石を全て取得するように巡回し始めのノードに戻ってくるルートの最短距離を求める問題。 それぞれのノードについて、巡回すべきノードであるか否かを…

Sorting the too large size data

Problem Imagine you have a 20 GB file with one string per line. Explain how you would sort the file. Solution When an interviewer gives a size limit of 20 gigabytes, it should tell you something. In this case, it suggests that they don’t w…

Internal Sorting and External Sorting

Kind of Sort All sort can be classified the following two sorts Internal Sorting External Sorting Imagine we have to sort the cards on the table where we can put the 30 cards(max). If the number of cards which we have to sort is less than …

Find an element in the rotated array

Problem Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element int the array. You may assume that the array was originally sorted in increasing order. Solution This problem can be…

SDWebImageの処理を追ってみる

SDWebImageの振る舞いが気になる SDWebImageは良くWeb画像のダンロードや画像データのキャッシュに用いられるライブラリだがその中身の実装がどうなっているか気になって夜も眠れない。 SDWebImageについては以下を参照 keita-matsushita.hatenablog.com 処…