読者です 読者をやめる 読者になる 読者になる

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 処…

iOSのNSFileManagerについて

NSFileManager API Reference NSFileManager - Foundation | Apple Developer Documentation なぜNSFileManagerが気になるか SDWebImageのソースコードを読んでいたらキャッシュの保存場所が2つあった。MemoryとDiscだ。Memoryにキャッシュを保存する場合は…

NSCacheのリファレンスを読む

NSCacheの公式リファレンス NSCache - Foundation | Apple Developer Documentation What is NSCache NSCacheのオブジェクトはmutable(変わりうる)なデータの集まりでkey-valueによって保存される。NSDictionaryオブジェクトに似ている。データの追加や削除…

SDWebImageのドキュメントを読む

What is SDWebImage 非同期での画像のダウンロードや画像のキャッシュをサポートするライブラリ。 UIによってカテゴライズされている(UIImageView, UIButton, MKAnnotationView) github.com Read.meを読む 特徴 UIによってウェブ画像の追加やキャッシュの機…

Implement a Queue by using two Stacks

Problem Implement a MyQueue class which implements a queue using two stacks Source Code

Sort an array of strings by anagrams

Problem Write a method to sort an array of strings so that all the anagrams are next to each other. Solution This problem asks us to group the strings in arrays such that anagrams appear next to each other. How to find the anagram The feat…

Merge two sorted arrays

Problem You are given two sorted arrays, A and B, where A has large enough buffer at the end to hold B. Write a method to merge B into A in sorted order How to Solve By merging two arrays like merge sort, we can achieve the goal. Since A h…

Merge Sort and Quick Sort

Merge Sort Runtime: 0(n Log(n)) average and worst case. Quick Sort Runtime: 0(n Log(n)) average,0(n2) worst case.

Write a method to return all subsets of a set

Problem Write a method to return all subsets of a set Solution This problem can be solve by choosing each element or not. For example we given an array = {1, 2, 3}. First, we do the two patterns that we select 1 or not. By this operation, …

Find a Magic Index from Sorted Array

Problem A magic index in an array A[] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A. FOLLOW UP What if the values are not distinct? …

Robot is moving in grid

Problem Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0, 0) to (X, Y)? How to Solve By using Dynam…