マツシタのお勉強

LinkedList

Least Recently Used (LRU) cache を実装する

問題 LRUキャッシュとはキーとバリューをマッピングするデータ構造で、キャパティを超えたら最後に使われたキャッシュが削除されるという挙動をする。 leetcode.com 解法 HashMapと双方向連結リストを利用することで実装することができる。 リストを用いるこ…

LinkedListから重複した要素を除く Hacker Rank

問題 www.hackerrank.com ソースコード

LinkedListが回文になっているか否かを判定 Palindrome Linked List in LeetCode

問題 leetcode.com 解法 通常の速さと、その2倍の速さでLinkedListを探索していくと、早いほうが末尾に到着する時に遅い方はちょうど中間地点にいる。 中間地点まできたら、そこから末尾まで進むと同時にリストを逆順にしていく。 ここまでの操作で、リスト…

2つのLinkedListが交わる点を見つける Intersection of Two Linked Lists in LeetCode

問題 2つのLinkedListが与えられ、2つが交差する点を見つける問題 leetcode.com 解法 HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。 以下の2つの処理を同時に行う リストAを順番に先頭から見ていき、末尾までいったらリストB…

LinkedListが輪になっているかを判定する Hacker Rank

問題 LinkedListの先頭のノードheadが与えられ、そのリストがサイクルしているかを判定する問題 www.hackerrank.com 解法 異なるスピードで2箇所から探索を開始し、探索途中に2つの探索位置が一致した場合、そのリストは輪となっていることが分る。 ソース…

Knowledges about Java 【Interview preparation】

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

LRU Cache

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

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

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…

Create a Linked List of all the nodes at each depth in Binary Tree

Problem Given a binary tree, design a algorithm which creates a linked list of all the nodes at each depth (e.g, if you have a tree with depth D, you'll have D linked lists) How to Solve The important point of the this problem How we shoul…

Implement SetOfStacks

Problem Implement a data structure SetOfStacks. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and .pop() should behave identically to a single stac…

Implement function min which returns minimum element in stack

Problem How would you design a stack which, in addition to push and pop, also has a function min which return minimum element? Push, pop and min should all operate in O(1) time. How to Solve By keeping a minimum value at each state, we can…

Implementation of Stack with LinkedList in Java

Implementation of Stack with LinkedList I defined the Stack class with a top property which is defined as the following explanation. top: the position to insert next Node at next time and the position to get a Node at next time. When I pus…

Implementation of Queue with LinkedList in Java

Implement Queue with LinkedList I defined a Queue class with the following two property, first and last. first: first it the position to dequeue at next time last: last.next is the position to enqueue at next time

Partition a Linked List around a value x

Problem Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes larger than x or equal to x How to Solve First, I prepare two nodes that are beforeStart and afterStart. These nodes can …

Delete a Node in the middle of singly Linked List

Problem Implement an algorithm to delete a Node in the middle of singly Linked List, given only access to that Node example: in following linked list case ①→②→③→④→⑤ I'm given only node③ and I have to delete node③. Source Code

Find the kth to last element of singly Linked List

Problem Implement an algorithm to find the kth to last element of singly Linked List. How to Solve This problem can be solved by Recursive or normal traverse. In recursive case, we have to create IntWrapper Class and implement like this. B…

Remove Duplicates from an Linked List

Problem Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed? How to Solve By using HashSet, I can control if each value appears or not already. And i…

プライオリティキューを用いたダイクストラ法 ~トレジャーハント編 ~

問題 D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder 解法 流れ 滞在する必要のある頂点は1つと考える。滞在する頂点を頂点iとすると、頂点0から最短で頂点iに到達し、できるだけ長く頂点iに滞在し、最短で頂点0に戻る事を考える。頂点iを…

深さ優先探索を用いて社長のお給料を決める

問題 C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder 解き方 問題の入力値から、上司と部下の関係をグラフを起こす。すると、今回の問題では部下に対する上司の人数は必ず1人なので木構造になる。 根ノードは社長になり、葉ノードは部下を持た…

LinkedListの実装(単方向連結リスト) Java

問題 github.com ソースコード せっかくなので、単方向連結リストを実装してみる。