# マツシタのお勉強メモ

#### マツシタのお勉強

##### welcome to my engineering blog
###### Hacker Rank # Find the heavy bottle

Problem You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the sca…

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

# Make a Binary Search Tree from sorted array

Problem Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height. How to Solve This problem asks me to create a BST (Binary Search Tree) from array. What is…

# Find out whether there is a routes between two nodes

Problem Given a directed graph, design an algorithm to find out whether there is a route between two nodes. How to Solve This problem can be solved by depth first search or breadth first search. While traversing the graph, we have to contr…

# Check if a binary tree is balanced

Problem Implement a function to check if a binary tree is balanced. For the purposes of this question. balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one. How to Solve …

# Towers of the Hanoi in Java

Problem In the classic problem of the Towers of Hanoi, you have 3 towers and N discs of different sizes which can slide onto any tower. How to Solve First we think about sliding nth disc onto another tower. This handling is composed by the…

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

# Use a single array to implement three stacks

Problem Describe how you could use a single array to implement three stacks. We can divide the array in three equal parts. So we use the array like this. For stack 1, we will use [0, n/3) For stack 2, we will use [n/3, 2n/3) For stack 3, w…

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

# Compress a String

Problem Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the string would not become smaller than the original string, your method…

# Replace all space in a string with '%20'

Problem Write a method to replace all space in a string with '%2d'. You may assume that the string has sufficient space at the end of the string to hold the additional character, and that you are given the true length of the string. [examp…

# If the string is a permutation of another string

Problem Given two strings, write a method to decide if one is a permutation of the other. How to Solve In oder to count of the number that how many times each characters appeared, I use array like HashMap. In case the given strings is ASCI…

# Implementation Reverse String Function

How to Implement By swapping the head of the string character and the tail of one, I can reverse a string

# Determine if a string has all unique characters

Problem Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures. How to solve Character can be transformed into integer. So, by using array its size is 256(ASCII), we can…