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…

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 …

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…

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…

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…

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 …

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…

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

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

merge sort

マージソートの実装 分割統治法と再帰の練習

連結リスト

単方向の連結リストの実装。 Note 構造体のポインタ変数をメンバ変数に持つとき、そのままだと実体をもたないので、 head = (struct Node *)malloc( sizeof(struct Node) ); head = new Node; コンストラクタとかで上みたいな感じで実体をもたせる。 あとは…