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 problem without the link to its parent node. This problem can be solved the following steps
- define the method to check if the subtree of the one node includes target node. I name this method
boolean hasNode(Node root, Node target). - assume that
pandqare the nodes that we want to get their ancestor. - define the method to get ancestor of p and q. I name this method
Node ancestor(Node root, Node p, Node q). - ancestor method can be defined like this.
- return null, if neither p nor q are not included in root.
- return root, if root is p or q.
- return root, if p is included on the other side to q.
- else, return ancestor(child, p, q)
Source Code
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, max)
The Min / Max Solution
This solution is that we keep a range at each node. As traversing the tree, we update the range that the value of node can be possible. In first node (root), we set the range as (min = Int_Min, max = Int_max). And if we traverse to left, we have to change the max to the value of the current node. And if we traverse to right, we have to change the min to the value of the current node.
This solution takes O(N) times and space complexity is O(log N) (log N is the depth of the tree). This is best solution.
In-Oder Traversal Solution
A binary search tree can be a sorted array by in-oder traversal. So we make the array and the check if the array is sorted.
But this solution can not handle duplicate values int the tree values. In binary search tree, if left.value <= current.value, it is valid. But if current.value <= right.value, it is invalid. This solution can not distinguish the difference.
Bad Solution
The restriction of the binary search tree is that left.value <= root.value < right.value. So I thought that it is ok I check the restriction on each node. But this thought is not good because if the restriction is satisfied, the binary tree can not be a binary search tree.
This is a bad Solution.
ツリーグラフにおける最短ルートの算出
問題
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 want you to bring all the data into memory.
So What do we do? We only bring part of the data into memory.
We will divide the file into chunks which are x megabytes each, where x is the amount of memory we have available. Each chunk is sorted separately and then saved back to the file system.
Once all the chunks are sorted, we then merge the chunks, one by one. At the end, we have a fully sorted file. This algorithm is known as external sort.
About external sorting.
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 30, we can put all cards on the table. But if we have to sort more than 30 cards, we can not put all cards one time. In such case, we have to prepare the another table for work in order to sort them.
This is same as the programming.
Internal Sorting
When we can put the all data into the one memory, internal sorting is used.
External Sorting
When we can not put the all data into the one memory since the data is too large, external sorting is used.
Reference
http://www.bohyoh.com/Books/MeikaiJavaAlgo/MKJavaAlgoB06a.pdf
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 solved by applying binary search. If the middle element is larger than the left element (arr[left] < arr[mid]), the left side is normally ordered. If the middle element is smaller than the left element (arr[left] > arr[mid]), the right side is normally ordered. If the left side is ordered and the x that we want to know the index is contained in the left side, we search the left side.
This solution takes O(log N) time.
Source Code
SDWebImageの処理を追ってみる
SDWebImageの振る舞いが気になる
SDWebImageは良くWeb画像のダンロードや画像データのキャッシュに用いられるライブラリだがその中身の実装がどうなっているか気になって夜も眠れない。
SDWebImageについては以下を参照
keita-matsushita.hatenablog.com
処理を追う
よく使用する下のメソッドの処理の流れをソースコードを覗いてみる。
このメソッドはUIImageView+WebCache.mというファイルに定義されていた。
SDWebImage/UIImageView+WebCache.m at master · rs/SDWebImage · GitHub
このメソッドの中ではsd_setImageWithURLというメソッドが呼ばれている。上記のメソッドの引数にprogressとcompletedという引数がブロックで定義されていた。progressは画像のダウンロードの進捗具合、completedはダンロードが完了したタイミングで呼ばれ、ダウンロードが成功したか失敗したかが引数により確認することができる。
さらに内部的にsd_internalSetImageWithURLというメソッドが呼ばれている。これはUIView+WebCache.mというファイルに定義されている。UIImageView+WebCache.mファイルに#import "UIView+WebCache.h"という記述があることからも分る。
画像のキャッシュの管理について
sd_internalSetImageWithURLメソッド内でloadImageWithURLという怪しいメソッドが呼ばれている。この処理のブロックの引数として得られた画像やらエラーやらを使ってcompletedBlockなどを呼んでいる。loadImageWithURLはSDWebImageManager.mというファイルに定義されてる。queryCacheOperationForKeyというメソッドで画像がキャッシュされているか否かをチェックしている。
具体的にはキーが存在しなければSDImageCacheTypeNoneをブロックの引数に指定し返している。キーが存在する場合は、メモリー上にキャッシュが存在するか確認している。この時NSCacheクラスが使われている。メモリー上に無ければディスク上にキャッシュが存在するか確認する。ディスクへの読み書きは時間のかかる処理なので非同期で実装されていることが分る。
