Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Evaluate Division

problem Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0. Exa…

Trie tree

What is Trie tree? Trie tree is a data structure of handling string. - Looking up data in a trie is faster in the worst case O(m)(m is the length of a search string). - There are no collisions of different keys in a trie. - There is no nee…

First Common Ancestor

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. NOTE: This is not necessarily a binary search tree. how to solve Starting from …

Word Break (LeetCode)

problem Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not cont…

Coins

problem Given a number of dollars, , and a list of dollar values for distinct coins, , find and print the number of different ways you can make change for dollars if each coin is available in an infinite quantity. how to solve I can solve …

LRU Cache (Leet Code, Amazon)

problem Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, other…

TopCoder srm 708c PalindromicSubseq2

problem Problem Statement A palindrome is a string that reads the same forwards and backwards. For example, “abba” and “racecar” are palindromes. An odd palindrome is a palindrome with an odd length. For example, “racecar” is an odd palind…

TopCoder srm 708b BuildingStrings

problem The score of a string is its length multiplied by the number of different characters in the string. For example, the score of “abbcdxc” is 7 * 5 = 35. This is because the length of this string is 7 and there are five different char…

TopCoder srm 708a SafeBetting

problem Limak is in a casino. He has b dollars. He wants to have at least c dollars (to be able to buy flowers for a girl he likes). In order to achieve that, he must win the money he’s missing. The casino allows guests to risk some of the…

Tread vs Process

problem What is the difference between a thread and a process? answer English A process can be thought of as an instance of a program in execution. A process is an independent entity to which system resources( cpu time and memory) are allo…

Paths with Sum

problem You are given a binary tree in which each node contains an integer value(which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at th…

Sparse Search

problem Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string. how to solve If it were not for the empty strings, we could simply use binary search. With empty string…

Sorted Matrix Search

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. how to solve http://articles.leetcode.com/searching-2d-sorted-matrix-part-ii/ The above link is very easy unde…

Minimal Tree

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 minimal tree means creating height balanced tree. Firstly, we want the ro…

Group Anagrams

problem Write a method to sort an array of strings so that all the anagrams are next to each other. how to solve I use hash table. once we have grouped all the words into these lists by anagram. we can then put them back into the array. co…

Successor

prblme Write an algorithm to find the “next” node(i.e., in-order successor) of a given node in a binary search tree. (You may assume that each node has a link to its parent or you can get the root node) how to solve “Next” node means that …

Contains Duplicate III

problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k. h…

Validate BST

problem Implement a function to check if a binary tree is a binary search tree. how to solve Binary search tree means that all left nodes must be less than or equal to the current node and all right nodes must be more than or equal to the …

Check Balanced

problem Implement a function to check if a binary tree is balanced. how to solve A 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. So I implement a function fetchHe…

Intersection

problem Write a program to find the node at which the intersection of two singly linked lists begins. - If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the funct…

Loop Detection

problem Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop. how to solve If I can use extra space, I can solve this very easily. I can justly use a hash table to detect if the element is…

srm707 medium StepsConstruct

problem There is a rectangular board that is divided into n rows by m columns of cells. Each cell is either empty or it contains an obstacle. You are given the description of the board in the board. Each character in board represents one c…

srm707 easy Cross

problem There is a rectangular board that is divided into n rows by m columns of cells. Each cell is either black or white. You are given the description of the board in the board. Each character in board represents one cell. More precisel…

Delete Middle Node

problem Implment an algorithm to delete a node in the middle of a singly linked list. But you can only access to that node. note The solution is simply to copy the data from the next node over to the current node. code

RemoveDups

problem Write code to remove duplicates from an unsorted linked list without using a temporary buffer. how to solve If I can use a temporary buffer, I recommend to use hash table. But in this case, I have to compare two elements to check t…

Insertion

problem You are given two 32bit numbers n and m and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. how to solve Clear the bits j through i in N Shift M so that it lines up with …

AnimalShelter

Problem An animal shelter, which holds only dogs and cats. Create the data structures to implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat. How to solve My approach is to simply use separate queues for dogs and ca…

Rotate Matrix

problem Given an image represented by an N*N matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? how to solve We swap on each layer, starting from the outermost laye…

OneAway

Problem There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away. How to solve I…

SortedMerge

problem You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method B into A in sorted order. how to solve In this problem, I can use array A which has a large enough buffer at the end t…

Queue via Stacks

problem Implement a MyQueue class which implements a queue using two stacks how to solve I implement two functions pop and push. The first one is getting and removing the oldest element in MyQueue. The second one is adding the element into…

Linear Regression Models with Logarithmic Transformations

Abstract 一言でいうと、線形回帰モデルを扱う際に、特徴量の尺度をそろえる方法として、 logを取ってあげるとうまくいくらしい。 http://www.kenbenoit.net/courses/ME104/logmodels2.pdf stats.stackexchange.com そうなる理由は↑を詳しくは参照 もとはと…

srm705 SuperUserDo

Problem Statement Fox Ciel just used the command "sudo" (super-user do) to gain administrative privileges in the UNIX-based operating system on her computer. She now wants to install several new programs. Each program has some dependencies…

276. Paint Fence (Google, LeetCode)

Problem There is a fence with n posts, each post can be painted with one of the k colors. You have to paint all the posts such that no more than two adjacent fence posts have the same color. Return the total number of ways you can paint th…

57. Insert Interval(Google, LeetCode)

# Problem Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1:Given intervals [1,3],[6,9…

317. Shortest Distance from All Buildings(Google, LeetCode)

problem You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where: Each 0 marks an empty land w…

BFS 320. Generalized Abbreviation (Google, LeetCode)

Problem Write a function to generate the generalized abbreviations of a word. Example: Given word = "word", return the following list (order does not matter): ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w…

302. Smallest Rectangle Enclosing Black Pixels

problem An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (…

200. Number of Islands(Leet Code, Google)

Problem Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are…

316. Remove Duplicate Letters (Leet Code, Google)

problem Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results. Exam…

340. Longest Substring with At Most K Distinct Characters (Leet Code, Google)

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/ problems Given a string, find the length of the longest substring T that contains at most k distinct characters. For example, Given s = “eceba” and k = 2, …

AtCoder Regular Contest 023 B - 謎の人物X

問題 arc023.contest.atcoder.jp note dpを使用した。i歩進むときの最大のたこ焼きの値段をdp[i]とした。 code

AtCoder Regular Contest 044 B - 最短路問題

問題 B: 最短路問題 - AtCoder Regular Contest 044 | AtCoder note 数学の問題 最短距離がnの場所の場合の数は、最短経路がn-1である場所の数と、最短距離がnの場所の数で決まることを利用して貪欲にとく。 code

累積和とってソートしてBluteForce AtCoder Regular Contest 035 B - アットコーダー王国のコンテスト事情

問題 arc035.contest.atcoder.jp note ペナルティの小さい順にソートして小さい順にペナルティをうけていけばよい。 コード

いもす法 累積和 AtCoder Regular Contest 048 B - AtCoderでじゃんけんを

Problem arc048.contest.atcoder.jp note あらかじめあるレーティングの人が何人いるのかの累積和と、あるレーティングである手をとるプレイヤーが何人いるかを記録しておく。 そうすると、それぞれの勝敗が次のようにO(1)でもとまる。 int win = dp[players…

2通りの全列挙 AtCoder Regular Contest 049 B - 高橋ノルム君

Problem arc049.contest.atcoder.jp Note 想定解のやり方と違うみたい。 nこの頂点から最も遠い2組の点が最小になるようにすればよいわけで、ある2点に対して、その2点間の間にあってそれぞれの点と距離が等しくなる任意の点との距離は、 (a.c * b.c) / (a…

div2 srm 704 hard ModEquationEasy

Problem Statement You are given the s n, K, and v. Consider the following modular equation with n variables: (x[0] * x[1] * x[2] * ... * x[n-1]) mod K = v. How many solutions does it have? Formally, we want to find the number of sequences …

srm704 middium ConnectedComponentConstruction

Problem Statement Any undirected graph can be decomposed into connected components. Two vertices u and v belong to the same connected component if we can travel from u to v by following a sequence of zero or more consecutive edges. The siz…

segment Treeを使用してRMQをとく。

RMQとは 数列a_0,a_1,...a_nがあるとき次の二つの処理をO(log n)で行う。 s, tが与えられたとき、a_s, a_s+1, .... , a_tの最小値を求める i, xが与えられたとき、a_iの値をxに変更する SegmentTreeとは プログラミングコンテストでのデータ構造 from Takuya…

いもす法を二回する AtCoder Regular Contest 045 B - ドキドキデート大作戦高橋君

問題 arc045.contest.atcoder.jp note まず累積和を使って、担当が1人しかいない掃除場所を探し出す。 その後、担当が1人しかいない場所を1、それよりも多い掃除場所を0として累積和をとればO(1)で任意の掃除の区間をサボれるかわかる code