# マツシタのお勉強メモ

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

##### welcome to my engineering blog
###### Hacker Rank # 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

# Maximum Product of Word Lengths

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…

# Heaps: Find the Running Median

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…

# Count Path Sum in Binary Tree

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…

# Find an Element from Sorted Matrix

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…

# Find the location of the given string from a sorted array of string which is interspersed with empty strings

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…

# Print all paths which sum to a given value in a Binary Tree

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…

# Check if small binary tree T1 is a suibtree of large binary Tree T2

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…

# Find the next node (in-oder traversal) of a given node in a binary search tree

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…

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

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

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

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

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

# Implement a Queue by using two Stacks

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

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

# Merge two sorted arrays

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 and Quick Sort

Merge Sort Runtime: 0(n Log(n)) average and worst case. Quick Sort Runtime: 0(n Log(n)) average,0(n2) worst case.

# Write a method to return all subsets of a set

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

# Find a Magic Index from Sorted Array

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

# Robot is moving in grid

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…

# Count how many possible ways the child can run up the stairs

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…