Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

CUDA まとめ

CUDAのメモリについて グローバルメモリはGPU上どこからでも見えるがメモリアドレスが低速なメモリ シェアードメモリは同一ブロックからしかみえないが高速に読み書きができるメモリ コンスタントメモリは読み込み専用だがグラオーバルメモリと同様のスレッ…

AtCoder Regular Contest 029 B 高橋君と禁断の書

問題 arc029.contest.atcoder.jp 解き方 二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指…

xgboost memory problem

Memory is shortage in xgboost program Sometimes, program is forcibly quit when using xgboost. In that time, there are several solutions(It is true that the solution is existed except for the following). https://www.kaggle.com/c/grupo-bimbo…

AtCoder Beginner Contest 060 D - Simple Knapsack

Problem Statement You have N items and a bag of strength W. The i-th item has a weight of wi and a value of vi. You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W. …

Build Order

problem You are given a list of projects and a list of dependencies ( which is a list of pairs of projects, where the second project is dependent on the first project). All of a project’s dependencies must be built before the project is. F…

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…

Check Subtree

problem T1 and T2 are two very large binary trees, with T1 much bigger than T2. Create an algorithm to determine if T2 is a subtree of T1. A tree T2 is a subtree of T1 if thre exists a node n in T1 such that the subtree of n is identical t…

return k-th to last

problem Implement an algorithm to find the kth to last element of a singly linked list how to solve We use two pointers slow-pointer and fast-pointer. Firstly we proceed the fast-pointer in k step. Secondly, we move them at the same pace a…

Atcoder Grand Contest : B Splatter Painting

problem agc012.contest.atcoder.jp how to solve The limitation of d is very small and it is key point to solve this problem. Consider that dp[v][i] which means “paint dp[v][i] among the range d distance from vertex v”. The time complexity i…

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…