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…

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…

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…

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…

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

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…

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…

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 …

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…

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…

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

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…

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…

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…

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 解法 与えられたノードからスタートし、宝石を全て取得するように巡回し始めのノードに戻ってくるルートの最短距離を求める問題。 それぞれのノードについて、巡回すべきノードであるか否かを…

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…

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 …

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

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

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

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

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

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…

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 Runtime: 0(n Log(n)) average and worst case. Quick Sort Runtime: 0(n Log(n)) average,0(n2) worst case.

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

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

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…