Cracking The Coding Interview
問題 LRUキャッシュとはキーとバリューをマッピングするデータ構造で、キャパティを超えたら最後に使われたキャッシュが削除されるという挙動をする。 leetcode.com 解法 HashMapと双方向連結リストを利用することで実装することができる。 リストを用いるこ…
問題 ２つの整数配列が与えられる。それぞれの配列から１つずつ要素を決め、それらを交換した時に２つの配列の要素の合計値が一致するようなペアを見つける問題。 入力: {4, 1, 2, 1, 1, 2} と {3, 6, 3, 3} 出力: {1, 3} 解法 全列挙の解法 O(A*B) i, jを添…
問題 ガラケーのキーボードにおいて、入力値としてキーボード上の押した数字が与えられる(連打回数は無視)。 この時に、押した数字によって得られる単語の組合せの内、辞書に乗っているものを出力する問題。辞書は予め与えられ、データ構造は自由に設定でき…
問題 { {0, 2, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}, {0, 1, 0, 1} } が与えられる。0の部分が湖で、縦横斜めで０が連なっている所は同じ湖とする。全ての湖のサイズを列挙する問題。 ソースコード
問題 文字列wordとパターンを表すpatternが入力値として与えれる。patternは'a'と'b'のみで構成されている。wordがpatternにマッチするか否かを求める問題。 例 word = “catcatgocatgo”, pattern = “abbab” a -> cat b -> go とすればwordはpatternにマッチ…
問題 xy平面上にN個の点が与えられる。最も多くの点を通るように直線を引いた時の点の最大値を求める問題 leetcode.com 解法 HashMapを用いることでO(N2)で解くことができる。forループを２回使い２つの点を全列挙する。２つの点のを結ぶ傾きをキーとして、H…
問題 整数Nが与えら、Nの階乗を計算した時に、末尾に連なる0の数を求める問題。 解き方 どんな時に末尾に０が来るか考える。階乗の計算では足し算はなく掛け算のみなので、10を掛けた時に末尾に0がつく。また、１０は2×5なので２と５を掛けた回数分、０が着…
Introduction This article is for my preparation of technical interview. And this focuses on programming language “Java”. final keyword The final keyword in Java has different meaning depending on whether it is applied to a variable, class …
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
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…
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…
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 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…
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…
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…
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…
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…
Problem A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. How to Solve This problem can be solved e…
