SOA protocols like SOAP, WSDL, and WS-* were specifically created to facilitate web services communication using XML-based messaging, ensuring interoperability and standardization across disparate systems.
Service-Oriented ArchitectureSOA
...
2025.03.04
Different approachRL is different from other ML methods, as RL:
start with a fully interactive, goal-driven agent
it will make decisions
it will pursue a goal
Elements of RLA policy, a reward signal , a value function, and optionally, a m
...
2025.03.02
ML有三种。
Supervised Learning
Utilizes labeled datasets to train models for prediction or classification. Limited by the context of the training data.
Unsupervised Learning
Processes unlabeled data to discover underlying patterns and struc
...
2025.03.01
I have a love-hate relationship with Github Pages.
For it’s free, stable and deployed automatic with git, but also for it’s complexity when switching laptops, and its inaccessibility in mainland China.
Here’s how to do it anyways:
Setup a
...
2025.02.23
First thing after getting a new Mac:
1npm install -g pnpm
pnpm global123pnpm install -g @tarojs/cliorpnpm add -g @tarojs/cli
for npm:
1npm install -g @tarojs/cli
Installed packages1pnpm list -g --depth=0
For npm:
1npm list -g --depth=0
...
2024.12.08
TL;DR
Want simplicity? Use venv.
Want to look cool in front of your team? Use Poetry.
Stuck in a conservative workplace or older project? Go Pipenv.
Need data science tools? Embrace Conda.
DifferencepipenvPipenv is a tool that only manage
...
2024.12.05
Let’s start with a simple example.
Example 1: Postgresdocker-compose.yml:
123456789101112131415161718192021version: '3.8'name: project_name # Container Nameservices: postgres: # Service Name image: postgres:latest container
...
2024.12.03
When to use async/await in Python?
TL;DRTraditionally, use async/await in Python when we are doing IO-bound operations (e.g. HTTP requests, database queries, file operations, etc.).
Do not use async/await when we are doing CP
...
2024.12.01
Consider you have a monorepo with Next.js frontend and FastAPI backend:
123gitww/├── backend-fastapi/├── frontend-nextjs/
1. Run Backend (FastAPI)run-backend.sh
12345echo -ne "\033]0;gitww-backend\007"cd /usr/local/hub/gitww/back
...
2024.11.30
Design Amazon1. Requirements
350 million products
10 million orders per day, that’s 100 orders per second
1 MB of data per product, that is 1 PB needed to partition the product table.
Features
retail
concurrent edit of cart
inventory mgmt
...
2024.09.25
Design Bidding Platform1. Requirements
A user can bid on an item.
Fix-time bidding & Variable-time bidding.
Real-time price update.
Support 100+ QPS for each item.
2. Data Model
Bid表
bidID, auctionID, userID, price, serverside_timestam
...
2024.09.25
What is LLM?111 TODO TODO 222 new
...
2024.08.20
Requirements
User buy/sell financial products via an Exchange.
User can check their positions.
User sees real-time value of their assets on 1 screen
Minimize # of servers that listen to Exchange (this is very costly).
NumbersAssume 10
...
2024.08.09
Design TwitterWe’ll follow the 5-step procedure:
Scenario
Numbers
API and Database
Performance
Evolve
1. ScenarioFunctional requirement
tweets
create
delete
timeline/feeds
home timeline
user self timeline
follow
like
search
Non-
...
2024.07.29
Design TicketMasterWe’ll follow the 5-step procedure:
Scenario
Numbers
API and Database
[Important] also include HLD schema!
Performance
Sharding and caching.
Evolve
Read some real-world knowledge.
1. ScenarioFunctional require
...
2024.07.29
Design YoutubeWe’ll follow the 5-step procedure:
Scenario
Numbers
API and Database
[Important] also include HLD schema!
Performance
Sharding and caching
Evolve
1. ScenarioFunctional requirement
Upload video
Watch video
Comment an
...
2024.07.29
Link: TODO
Questiondifficulty: midadj diff:
CodeImage:
1code
...
2024.07.28
Link: 2285. Maximum Total Importance of Roads
Questiondifficulty: midadj diff: ?
You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.
You are also given a 2D integer array roads wh
...
2024.07.16
Link: 2341. Maximum Number of Pairs in Array
Questiondifficulty: easyadj diff: ?
You are given a 0-indexed integer array nums. In one operation, you may do the following:
Choose two integers in nums that are equal.
Remove both integers fro
...
2024.07.16
Link: 445. Add Two Numbers II
Questiondifficulty: midadj diff: ?
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add th
...
2024.07.16
Link: https://leetcode.cn/problems/insert-delete-getrandom-o1/
Questiondifficulty: midadj diff: 4
Implement the RandomizedSet class:
RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val int
...
2024.07.16
今天，我们在 VMware 中，跑起来 4 台 Zookeeper + 3 台 Kafka 机器。
ConventionsDownloaded packages: /opt/tools
Installed apps: /opt/apps
默认安装的软件：
1234567891011yum install tmux wget tree gitrpm -ivh jdk-8u351-linux-x64.rpmjava -versionsudo
...
2024.07.16
Link: https://leetcode.cn/problems/car-pooling/
Questiondifficulty: midadj diff: 2
There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).
You are given the integer capacity and
...
2024.07.16
Link: Maven零基础入门教程（一套轻松搞定maven工具）
Why Maven?现有的技术：
表现层
视图层 - Html/Css/Js
控制层 - Servlet/Action/Handler
业务逻辑层 - Spring IOC/AOP
持久化层 - JDBC/Hibernate/MyBatis
数据库层
问题是：
工程太大，需要拆分成Module。
不同module的jar依赖。
...
2023.01.16
QuestionDigital wallets have made sending and receiving money easier, but they require authentication. A user must have an access token to initiate transactions in this digital wallet system. There are two types of transactions:
Adding mon
...
2022.12.02
Java Exceptions are divided into 2 categories:
RuntimeException (also known as unchecked Exception)
Checked Exception
Checked exception
mandatory to try… catch…
otherwise: compile error
eg. ClassNotFoundException, IOException, SQLExcept
...
2022.12.01
Link: https://leetcode.cn/problems/top-k-frequent-elements/
Questiondifficulty: midadj diff: 3
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input:
...
2022.12.01
Link: https://leetcode.cn/problems/diameter-of-binary-tree/
Questiondifficulty: midadj diff: 4Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path be
...
2022.11.20
Link: https://leetcode.cn/problems/reverse-linked-list/
Questiondifficulty: easyadj diff: 3
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
E
...
2022.11.20
Link: https://leetcode.cn/problems/design-an-expression-tree-with-evaluate-function/
Questiondifficulty: midadj diff: 4
Given the postfix tokens of an arithmetic expression, build and return the binary expression tree that represents this e
...
2022.11.20
经验：尽量用 Comparator，不要用 Comparable。
Comparator class 标准写法：
1234567Queue<ListNode> heap = new PriorityQueue(size, new NodeComparator());class NodeComparator implements Comparator<ListNode> { public int compare(ListNode n1,
...
2022.11.20
Link: https://leetcode.cn/problems/analyze-user-website-visit-pattern/
Questiondifficulty: midadj diff: 3
You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and t
...
2022.11.20
Link: https://leetcode.cn/problems/find-the-celebrity/
Questiondifficulty: midadj diff: 2
Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. The definition of a celebrity is that
...
2022.11.18
Link: https://leetcode.cn/problems/inorder-successor-in-bst/
Questiondifficulty: midadj diff: 4
Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-or
...
2022.11.18
Link: https://leetcode.cn/problems/concatenated-words/
Questiondifficulty: hardadj diff: 5
字典树！
哎，太难了。做这道题之前去看 https://leetcode.cn/problems/implement-trie-prefix-tree/ 吧。
...
2022.11.18
Link: https://leetcode.cn/problems/nested-list-weight-sum-ii/
Questiondifficulty: midadj diff: 3
You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other li
...
2022.11.18
Link: https://leetcode.cn/problems/nested-list-weight-sum/
Questiondifficulty: midadj diff: 3
You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists
...
2022.11.18
Link: https://leetcode.cn/problems/first-unique-number/
Questiondifficulty: midadj diff: 3
You have a queue of integers, you need to retrieve the first unique integer in the queue.
Implement the FirstUnique class:
FirstUnique(int[] nums)
...
2022.11.18
Link: https://leetcode.cn/problems/leftmost-column-with-at-least-a-one/
Questiondifficulty: midadj diff: 4
A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix is sorted in non-decreasing order.
Given a
...
2022.11.18
Link: https://leetcode.cn/problems/inorder-successor-in-bst-ii/
Questiondifficulty: midadj diff: 3
Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return n
...
2022.11.18
Answering frameworkRequirements
Functional Requirements
Non-functional requirements
Out of scope
Capacity Estimation
Assumptions
Storage Estimations
Detailed Component Design
Client
Meta Service
Block Service
...
2022.11.17
Leetcodehttps://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/
https://leetcode.cn/problems/path-with-maximum-probability/
Q1排序以下 table:
name | start | end
abc 3 8
bcd 7 10
cd
...
2022.11.17
TikTokJava AOP 的用法Rest vs RPC 区别手写 singleton Javadouble checked locking singleton javadistributed lock 分布式锁LRU cache 如何变成线程安全，然后展开如果是分布系统，如何做 replica，并且保证数据一致性
系统设计，就是抖音的 profile 页面
Circular queue’s follow up 多个线程要访问这个 queue 怎么办。我说用锁。他说效率不好
...
2022.11.15
开篇GoF - 23 种设计模式。
The four authors Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides are collectively introduced the Gang of Four Design Patterns in Software development.
In 1994, they published a book (Design Patterns: Element
...
2022.11.15
Link: https://leetcode.cn/problems/course-schedule/
Questiondifficulty: midadj diff: 4
拓扑排序。不简单，好好写。
这道题跟 210. Course Schedule II 一模一样。
...
2022.11.15
Link: https://leetcode.cn/problems/decode-string/
Questiondifficulty: midadj diff: 3
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being
...
2022.11.15
Link: https://leetcode.cn/problems/max-area-of-island/
Questiondifficulty: midadj diff: 2
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You
...
2022.11.15
Link: https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/
Questiondifficulty: hardadj diff: 3
Given the root of a binary tree, calculate the vertical order traversal of the binary tree.
For each node at position (row, c
...
2022.11.15
Link: https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/
Questiondifficulty: easyadj diff: 1
Traversal + hashmap.
...
2022.11.15
Link: https://leetcode.cn/problems/last-stone-weight/
Questiondifficulty: easyadj diff: 1
Use a max-heap.
...
2022.11.15
Link: https://leetcode.cn/problems/find-words-that-can-be-formed-by-characters/
Questiondifficulty: easyadj diff: 1
Just use a bunch of hashmaps to compare.
...
2022.11.14
Link: https://leetcode.cn/problems/all-paths-from-source-to-target/
Questiondifficulty: midadj diff: 3
You are given an m x n binary grid, where each 1 represents a brick and 0 represents an empty space. A brick is stable if:
It is directl
...
2022.11.14
Link: https://leetcode.cn/problems/meeting-rooms-iii/
Questiondifficulty: hardadj diff: 4
You are given an integer n. There are n rooms numbered from 0 to n - 1.
You are given a 2D integer array meetings where meetings[i] = [starti, endi]
...
2022.11.14
Link: https://leetcode.cn/problems/k-empty-slots/
Questiondifficulty: highadj diff: 5
You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off. We turn on exactly one bulb every day until all bulbs are on afte
...
2022.11.14
Link: https://leetcode.cn/problems/logger-rate-limiter/
Questiondifficulty: lowadj diff: 2
Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 se
...
2022.11.12
Link: https://leetcode.cn/problems/next-closest-time/
Questiondifficulty: midadj diff: 4
Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times
...
2022.11.12
Link: https://leetcode.cn/problems/boundary-of-binary-tree/
Questiondifficulty: midadj diff: 4
The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order o
...
2022.11.12
Link: https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/
Questiondifficulty: midadj diff: 3
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child po
...
2022.11.11
Link: https://leetcode.cn/problems/maximum-population-year/
Questiondifficulty: easyadj diff: 2
You are given a 2D integer array logs where each logs[i] = [birthi, deathi] indicates the birth and death years of the ith person.
The populati
...
2022.11.10
Link: https://leetcode.cn/problems/sum-of-subarray-ranges/
Questiondifficulty: midadj diff: 5
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.
...
2022.11.09
Link: https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
Questiondifficulty: hardadj diff: 5
The distance of a pair of integers a and b is defined as the absolute difference between a and b.
Given an integer array nums and an i
...
2022.11.09
Link: https://leetcode.cn/problems/bag-of-tokens/
Questiondifficulty: midadj diff: 3
You have an initial power of power, an initial score of 0, and a bag of tokens where tokens[i] is the value of the ith token (0-indexed).
Your goal is to
...
2022.11.09
Link: https://leetcode.cn/problems/daily-temperatures/
Questiondifficulty: midadj diff: 2
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have t
...
2022.11.09
Link: https://leetcode.cn/problems/sliding-puzzle/
Questiondifficulty: hardadj diff: 4
On an 2 x 3 board, there are five tiles labeled from 1 to 5, and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally ad
...
2022.11.09
Link: https://leetcode.cn/problems/maximum-width-of-binary-tree/
Questiondifficulty: midadj diff: 3
Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all lev
...
2022.11.09
Link: https://leetcode.cn/problems/search-a-2d-matrix-ii/
Questiondifficulty: midadj diff: 2
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
Integer
...
2022.11.09
Link: https://leetcode.cn/problems/different-ways-to-add-parentheses/
Questiondifficulty: midadj diff: 5
Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group
...
2022.11.09
Link: https://leetcode.cn/problems/read-n-characters-given-read4-ii-call-multiple-times/
Questiondifficulty: hardadj diff: 5
Given a file and assume that you can only read the file using a given method read4, implement a method read to read
...
2022.11.09
Link: https://leetcode.cn/problems/remove-digit-from-number-to-maximize-result/
Questiondifficulty: easy
adj diff: 2
You are given a string number representing a positive integer and a character digit.
Return the resulting string after rem
...
2022.11.08
Link: https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/
Questiondifficulty: midadj diff:
Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.
...
2022.11.08
Link: https://leetcode.cn/problems/find-triangular-sum-of-an-array/
Questiondifficulty: midadj diff: 3
You are given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).
The triangular sum of nums is the va
...
2022.11.08
Link: https://leetcode.cn/problems/count-number-of-pairs-with-absolute-difference-k/
Questiondifficulty: easyadj diff: 1
Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - num
...
2022.11.08
Link: https://leetcode.cn/problems/maximum-units-on-a-truck/
Questiondifficulty: easyadj diff: 2
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUn
...
2022.11.08
Link: https://leetcode.cn/problems/string-transforms-into-another-string/
Questiondifficulty: highadj diff: 3
Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conve
...
2022.11.08
Link: https://leetcode.cn/problems/longest-happy-string/
Questiondifficulty: midadj diff: 4
A string s is called happy if it satisfies the following conditions:
s only contains the letters 'a', 'b', and 'c'.
s does
...
2022.11.08
Link: https://leetcode.cn/problems/missing-ranges/
Questiondifficulty: easyadj diff: 2
You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
A number x is con
...
2022.11.08
Link: https://leetcode.cn/problems/defuse-the-bomb/
Questiondifficulty: lowadj diff: 2
You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length of n and a key k.
To decryp
...
2022.11.08
Link: https://leetcode.cn/problems/product-of-array-except-self/
Questiondifficulty: midadj diff: 3
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
...
2022.11.08
Link: https://leetcode.cn/problems/meeting-rooms-ii/
Questiondifficulty: midadj diff: 3
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example
...
2022.11.08
Link: https://leetcode.cn/problems/graph-valid-tree/
Questiondifficulty: hardadj diff: 4
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is a
...
2022.11.08
Link: https://leetcode.cn/problems/paint-fence/
Questiondifficulty: midadj diff: 4
You are painting a fence of n posts with k different colors. You must paint the posts following these rules:
Every post must be painted exactly one color.
T
...
2022.11.08
Link: https://leetcode.cn/problems/alien-dictionary/
Questiondifficulty: hardadj diff: 5
There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.
You are given a list of strings
...
2022.11.08
Link: https://leetcode.cn/problems/sparse-matrix-multiplication/
Questiondifficulty: midadj diff: 3
Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is
...
2022.11.08
Link: https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/
Questiondifficulty: midadj diff: 4
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct
...
2022.11.08
Link: https://leetcode.cn/problems/moving-average-from-data-stream/
Questiondifficulty: lowadj diff: 2
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Implement the MovingAv
...
2022.11.08
Link: https://leetcode.cn/problems/find-leaves-of-binary-tree/
Questiondifficulty: midadj diff: 4
Given the root of a binary tree, collect a tree's nodes as if you were doing this:
Collect all the leaf nodes.
Remove all the leaf nodes.
...
2022.11.08
Link: https://leetcode.cn/problems/sentence-screen-fitting/
Questiondifficulty: midadj diff: 5
Given a rows x cols screen and a sentence represented as a list of strings, return the number of times the given sentence can be fitted on the sc
...
2022.11.08
Link: https://leetcode.cn/problems/continuous-subarray-sum/
Questiondifficulty: midadj diff: 2
Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multi
...
2022.11.08
Link: https://leetcode.cn/problems/design-search-autocomplete-system/
Questiondifficulty: highadj diff: 5
Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special characte
...
2022.11.08
Link: https://leetcode.cn/problems/check-if-two-string-arrays-are-equivalent/
Questiondifficulty: easyadj diff: 2
Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.
A stri
...
2022.11.08
Link: https://leetcode.cn/problems/shortest-word-distance-ii/
Questiondifficulty: midadj diff: 3
Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two di
...
2022.11.08
Link: https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/
Questiondifficulty: midadj diff: 3
Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.
Recall that:
The node of a binary t
...
2022.11.08
Link: https://leetcode.cn/problems/longest-common-subsequence/
Questiondifficulty: midadj diff: 2
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subs
...
2022.11.08
Link: https://leetcode.cn/problems/minimum-remove-to-make-valid-parentheses/
Questiondifficulty: midadj diff: 3
Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of pa
...
2022.11.08
Link: https://leetcode.cn/problems/number-of-closed-islands/
Questiondifficulty: midadj diff: 4
Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an is
...
2022.11.08
Link: https://leetcode.cn/problems/deepest-leaves-sum/
Questiondifficulty: midadj diff: 3
Given the root of a binary tree, return the sum of values of its deepest leaves.
Example 1:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
...
2022.11.08
Link: https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/
Questiondifficulty: hardadj diff: 5
There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The len
...
2022.11.08
Link: https://leetcode.cn/problems/product-of-the-last-k-numbers/
Questiondifficulty: midadj diff: 4
Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream.
Implement the Produc
...
2022.11.08
Link: https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/
Questiondifficulty: midadj diff: 2
There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer
...
2022.11.08
Link: https://leetcode.cn/problems/minimum-jumps-to-reach-home/
Questiondifficulty: midadj diff: 4
A certain bug's home is on the x-axis at position x. Help them get there from position 0.
The bug jumps according to the following rules
...
2022.11.08
Link：https://leetcode.cn/problems/binode-lcci/
Questiondifficulty: easyadj diff: 3
The data structure TreeNode is used for binary tree, but it can also used to represent a single linked list (where left is null, and right is the next node i
...
2022.11.08
Link: https://leetcode.cn/problems/ways-to-split-array-into-three-subarrays/
Questiondifficulty: midadj diff: 4
A split of an integer array is good if:
The array is split into three non-empty contiguous subarrays - named left, mid, right
...
2022.11.08
Link: https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/
Questiondifficulty: midadj diff: 4
You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith bo
...
2022.11.08
Link: https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating/
Questiondifficulty: midadj diff: 4
Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it i
...
2022.11.08
Link: https://leetcode.cn/problems/happy-number/
Questiondifficulty: easyadj diff: 3
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer,
...
2022.11.08
Link: https://leetcode.cn/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
Questiondifficulty: midadj diff: 4
You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You
...
2022.11.08
Link: https://leetcode.cn/problems/course-schedule-ii/
这道题跟 269. Alien Dictionary 基本一样。
Questiondifficulty: midadj diff: 5
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array pr
...
2022.11.08
Link: https://leetcode.cn/problems/count-complete-tree-nodes/
Questiondifficulty: midadj diff: 3
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the
...
2022.11.08
Link: https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/
Questiondifficulty: hardadj diff: 4
You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:
0 represents an empty cell,
...
2022.11.08
Link: https://leetcode.cn/problems/palindrome-linked-list/
Questiondifficulty: easyadj diff: 2
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Input: head = [1,2,2,1]
Output: true
...
2022.11.08
Link: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
Questiondifficulty: midadj diff: 3
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on
...
2022.11.08
Link: https://leetcode.cn/problems/find-median-from-data-stream/
Questiondifficulty: highadj diff: 3
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the
...
2022.11.08
Link: https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/
Questiondifficulty: midadj diff: 4
One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node'
...
2022.11.08
Link: https://leetcode.cn/problems/pacific-atlantic-water-flow/
Questiondifficulty: midadj diff: 4
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left
...
2022.11.08
Link: https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/
Questiondifficulty: hardadj diff: 5
Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].
Example 1:
Input: n = 13, k =
...
2022.11.08
Link: https://leetcode.cn/problems/island-perimeter/
Questiondifficulty: easyadj diff: 3
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected hor
...
2022.11.08
Link: https://leetcode.cn/problems/number-of-provinces/
Questiondifficulty: midadj diff: 3
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly wit
...
2022.11.08
Link: https://leetcode.cn/problems/design-circular-queue/
Questiondifficulty: midadj diff: 2
Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO
...
2022.11.08
Link: https://leetcode.cn/problems/print-binary-tree/solution/shu-chu-er-cha-shu-by-leetcode-solution-cnxu/
Given the root of a binary tree, construct a 0-indexed m x n string matrix res that represents a formatted layout of the tree. The f
...
2022.11.08
Link: https://leetcode.cn/problems/random-pick-with-blacklist/
Questiondifficulty: hard
adj diff: 5
You are given an integer n and an array of unique integers blacklist. Design an algorithm to pick a random integer in the range [0, n - 1]
...
2022.11.08
Link: https://leetcode.cn/problems/koko-eating-bananas/
Questiondifficulty: midadj diff: 4
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko
...
2022.11.08
Link: https://leetcode.cn/problems/time-based-key-value-store/
Questiondifficulty: midadj diff: 2
Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key'
...
2022.11.08
Link: https://leetcode.cn/problems/cousins-in-binary-tree/
Questiondifficulty: easyadj diff: 3
Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes correspond
...
2022.11.08
Link: https://leetcode.cn/problems/sliding-window-maximum/
Questiondifficulty: highadj diff: 4
Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part.
If there is no such window
...
2022.11.04
Link: https://leetcode.cn/problems/find-distance-in-a-binary-tree/
Questiondifficulty: midadj diff: 2
Given the root of a binary tree and two integers p and q, return the distance between the nodes of value p and value q in the tree.
The d
...
2022.11.04
Link: https://leetcode.cn/problems/count-univalue-subtrees/
Questiondifficulty: mid
adj diff: 3
Given the root of a binary tree, return the number of uni-value subtrees.
A uni-value subtree means all nodes of the subtree have the same val
...
2022.11.04
Link: https://leetcode.cn/problems/reorder-data-in-log-files/
Questiondifficulty: midadj diff: 3
You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.
There are two types of
...
2022.11.02
Link: https://leetcode.cn/problems/rotting-oranges/
Questiondifficulty: midadj diff: 3
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 represent
...
2022.11.02
Link: https://leetcode.cn/problems/basic-calculator/
Questiondifficulty: hardadj diff: 5
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are
...
2022.11.01
MyBatisMyBatis是一个持久层框架（persistence framework), 封装了JDBC的原装代码：
定制化SQL
存储过程
高级映射
Persistence framework 也是 Object-Relational Mapping (ORM) 工具。
MyBatis provides a mapping engine that maps SQL results to object trees in a declarative way.
软件
...
2022.11.01
RedisNoSQL = Not Only SQL
NewSQL = TiDB
Why MySQL maybe better than NoSQL?Because support of:
data consistency
transaction (ACID)
NoSQL 4 types
Key-value型：Redis，Voldemort，Tokyo Cabinet，Tyrant，BerkeleyDB 优点：快速查询 缺点：数据缺少结构化
列存储型
...
2022.10.31
Spring MVCGetting StartedB/S vs C/SC/S架构，已经过时了。
B/S架构 –> web应用。
其中的 S = web applicationJavaEE 制定了一套规范，很简单实现了 B/S 的沟通（结构处理）。
这套规范，就是servlet。“服务器端 小程序”
Java开发 web应用：需要遵循__三层架构__：
表现层
业务层
持久层
Spring MVC 只跟
...
2022.10.31
Link: https://leetcode.cn/problems/rank-teams-by-votes/
Questiondifficulty: midadj diff: 3
In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.
The ordering of teams is d
...
2022.10.30
MySQL-3: sharding
MySQL 连接数
MySQL默认100个连接。（单机最大1500连接）
数据量
如果单行是100 bytes，当超过50M行的时候，很吃力
索引
占空间大，命中率低，查询的可能很慢。
MySQL 性能优化4种方案：
参数优化
加Cache，加index
读写分离
（最终方案）： 分库分表
What is NewSQL分布式 + Relational DB，例如 TiDB。
分库分表类型：
垂直分
eg。不同表放入不同
...
2022.10.30
MySQL-2: master / slaveNewSQLMySQL 关系型
NoSQL（Redis，MongoDB）
NewSQL = 分布式 Relational DB，例如 淘宝的 TiDB
分布式 MySQL 最重要的3个概念
主从复制
读写分离
分库分表
主从复制主从复制 的原理
master开启binary log
master事务提交，记录入bin log
slave的I/O thread，读取master中的binary log
...
2022.10.30
MySQL-4: optimize性能分析Steps：
开启 slow query log
查看执行计划：explain 有问题的SQL语句
show profile 查看问题SQL的使用情况
Slow Query除了用慢查询日志，还可以用：
MySQL自带的 mysqldumpslow 工具
一款Linux软件：percona-toolkit (DBA喜欢用)
Profile1set profiling = 1
例如：
可以看出：sending data 耗费
...
2022.10.30
MySQL Knowledge Graph
Performance
MySQL cluster
Sharding
Indexing
MySQL architecture
Lock
MySQL事务 （ACID）
Architecture
最上层：connector
中间：SQL Layer
包含：connection pool （包括，Auth，thread，check memory，cache），以及 Management Services & Utiliti
...
2022.10.30
Why Spring？
IoC：控制反转
DI：依赖注入
AOP：面向切面编程
Spring 容器，指的是IoC容器，底层是一个 BeanFactory
其中最重要：
IoC
基于 xml的配置
基于注解的配置
AOP
然后还有：整合 MyBatis。
Spring 框架
Core Container
用于instance的创建和管理。
AOP，Aspect-oriented programming实现面向切面的编程。
Spring Web就是Spring MVC
...
2022.10.30
Graph Valid Tree 的另一种做法。
判断 graph 是不是 tree
1.树中没有形成环 (nodes don’t have circle)
2.连通分量的个数为 1 (only 1 root node)
并查集代码如下：
123456789101112131415161718192021222324252627282930313233343536373839404142public boolean validTree(int n, int[][] ed
...
2022.10.29
Link: https://leetcode.cn/problems/maximal-square/
Questiondifficulty: midadj diff: 3
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example 1:
Input: mat
...
2022.10.29
Link: https://leetcode.cn/problems/sliding-window-maximum/
Questiondifficulty: highadj diff: 4
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. Y
...
2022.10.29
Link: https://leetcode.cn/problems/ugly-number-ii/
Questiondifficulty: midadj diff: 4
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
Example 1:
Input:
...
2022.10.29
Link: https://leetcode.cn/problems/bulls-and-cows/
Questiondifficulty: midadj diff: 2
You are playing the Bulls and Cows game with your friend.
You write down a secret number and ask your friend to guess what the number is. When your frien
...
2022.10.29
Link: https://leetcode.cn/problems/rotate-function/
Questiondifficulty: midadj diff: 4
You are given an integer array nums of length n.
Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation
...
2022.10.29
Link: https://leetcode.cn/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
Questiondifficulty: midadj diff: 3
Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.
You can think of the left and righ
...
2022.10.29
Link: https://leetcode.cn/problems/find-duplicate-subtrees/
Questiondifficulty: midadj diff: 4
Given the root of a binary tree, return all duplicate subtrees.
For each kind of duplicate subtrees, you only need to return the root node of an
...
2022.10.29
Link: https://leetcode.cn/problems/top-k-frequent-words/
Questiondifficulty: midadj diff: 4
Given an array of strings words and an integer k, return the k most frequent strings.
Return the answer sorted by the frequency from highest to low
...
2022.10.29
Link: https://leetcode.cn/problems/count-binary-substrings/
Questiondifficulty: easyadj diff: 4
难题，我根本就不会做。看答案勉强看会了。
Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and al
...
2022.10.29
Link: https://leetcode.cn/problems/max-chunks-to-make-sorted/
Questiondifficulty: midadj diff: 3
You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].
We split arr into some n
...
2022.10.29
Link: https://leetcode.cn/problems/all-paths-from-source-to-target/
Questiondifficulty: midadj diff: 3
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return the
...
2022.10.29
Link: https://leetcode.cn/problems/is-graph-bipartite/
Questiondifficulty: midadj diff: 5
There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array
...
2022.10.29
Link: https://leetcode.cn/problems/minimum-cost-for-tickets/
Questiondifficulty: midadj diff: 4
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Eac
...
2022.10.29
Questionlink
Given a trie data struture, implement add() and search() method, which support wildcard matching.
eg. If trie contains [“cool”, “kid”, “kindle”, “kind”]
These would match: “col”, “kind”, “**”
These won’t: “**”, “kid*”, “coo”
...
2017.05.22
Questionlink
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output =
...
2017.05.13
LoggingConecting between information and knowledge.
Information: it’s just bits
Knowledge: drives product direction
Logging is all about EventQ1. shall we log it live? what should we log? how to do it (on different platforms)?
Not live. D
...
2016.08.01
MVC PatternModel-View-Controller.
The model and controller logic are decoupled from user interface (view).
Model
business model + data access operations (i.e. data model)
View
only for displaying data (received from the controller, trans
...
2016.07.31
System design evaluation form
work solution
special cases
analysis
trade off
knowledge base
Design guideline: 4S
Scenario
ask, features, qps, DAU, interfaces
Service
split, application, module
Storage
schema, data, sql, NoSql, file syste
...
2016.07.11
AsideExample of this is the ‘categories’ list on the right hand side of the blog page. It’s always pinned on RHS, regardless of page content.
Instruction
Add to source/_includes/asides/category_list.html with the following co
...
2016.06.11
First wordDesigning a system like twitter, facebook or airbnb, first step is often User Registry.
The tables, we must use RDBMS, as it’s more reliable.
Table designFriendship table is important:
...
2016.05.08
1. Choose a frameworkAssuming we use Python to do this.
plain python?We can write a simple Python crawler with the code below:
import re, urllib
textfile = file('depth_1.txt','wt')
print "Enter the URL you wish to craw
...
2015.11.22
Questionlink
Design a 2D dungeon crawling game. It must allow for various items in the maze - walls, objects, and computer-controlled characters.
Part 1: API designSerialize:
if a certain cell has a wall to the North and West but not to
...
2015.11.21
Questionlink
输入一个数组，要求输出满足：a[0]<=a[1]>=a[2]<=a[3]>=…
Solution
O(n)，一边扫描即可。发现不符合条件的只要跟前面一个数对调就可以，
Codepublic int[] solve(int[] input) {
boolean incr = true;
int len = input.length;
int p = 1;
while
...
2015.11.21
OverviewStrategy pattern (also known as the policy pattern) is a design pattern that enables an algorithm’s behavior to be selected at runtime.
For instance, a class that performs validation on incoming data may use a strategy pattern to se
...
2015.11.18
Questionlink
partition problem is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2.
Examples
ar
...
2015.11.15
Questionlink
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multi
...
2015.11.04
OverviewResizable-array implementation of the List interface. (it’s actually an array of Object)
It’s not synced.
Underlying design
Random access – no need to traverse thru all nodes.
Circular array - Array size is pre-defined. Use head an
...
2015.10.28
OverviewTemplate method pattern is a behavioral design pattern that defines the program skeleton of an algorithm in a method, called template method, which defers some steps to subclasses.
It lets one redefine certain steps of an algorithm
...
2015.10.23
The classThe class Exception and its subclasses are a form of Throwable that indicates conditions that a reasonable application might want to catch.
The objectAn exception is an event, which occurs during the execution of a program, that di
...
2015.10.23
Nested classesBoth Static class and Inner class are called nested class.
The purpose of a nested class is to clearly group the nested class with its surrounding class, signaling that these two classes are to be used together.
Now the 2 type
...
2015.10.23
Vector in JavaVector class implements a growable array of objects.
It’s an array, not a list.
Vector VS ArrayList
Vectors are synchronized, ArrayLists are not.
Data Growth Methods (ArrayList grow by 1/2 of its size, while Vector double
...
2015.10.23
OverviewSome experienced developers don’t use protected since it cannot provide clean data hiding.
Why is that?
backgroundRemembering in the post [Java OOP] Java modifier and Access Level, we got this:
Note: Java default access setting is
...
2015.10.22
OverviewA Literal is a notation for representing a fixed value in source code.
Almost all programming languages have notations for atomic values such as integers, floating-point numbers, and strings.
eg.
int a = 1;
String s = "cat&qu
...
2015.10.22
OverviewO(n) time complexity is both reflexive, symmetric and transitive.
Reflexive PropertyThe Reflexive Property states that for every real number x, x = x.
Symmetric PropertyThe Symmetric Property states that for all real numbers x
...
2015.10.22
OverviewA comparison of all different time complexity:
Shown above: Constant, logarithmic, linear, n-log-n, quadratic, cubic, exponential ( eg. O(2^n) ).
...
2015.10.22
OverviewA UML class diagram describes the object and information structures used by your application, both internally and in communication with its users.
exampleTaken from here.
ShapeElementDescription1ClassA definition of objects that sh
...
2015.10.14
Questionlink
The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interval.
start and end are both integers, they should be assigned in following rules:
The root’s sta
...
2015.10.13
Questionlink
The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interval.
start and end are both integers, they should be assigned in following rules:
The root’s sta
...
2015.10.13
Questionlink
For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this node’s interval.
Implement a modify function with three parameter root, index and value to change the node’s value with [s
...
2015.10.13
Questionlink
For an array, we can build a SegmentTree for it, each node stores an extra attribute count to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by ele
...
2015.10.13
Questionlink
For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from sta
...
2015.10.13
OverviewSegment tree is a tree data structure for storing intervals, or segments.
Can be used to search the max/min or sum values in a range.
modify = O(log n)
query = O(log n)
build = O(n)
question list
[LintCode]
...
2015.10.08
Questionlink
Given a Binary Tree and a key, find distance of the closest leaf.
Examples:
1
/ \
2 3
/ \
5 6
/ \
7 8
/ \
...
2015.10.07
Questionlink
Given a string, print all possible strings that can be made by placing spaces (zero or one) in between them.
Input: str[] = “ABC”
Output:
ABC
AB C
A BC
A B C
Solutionrecursion.
Codepublic void print
...
2015.10.07
Questionlink
Given a matrix where every element is either ‘O’ or ‘X’, find the largest sub-square surrounded by ‘X’. (meaning that the 4 edges are filled with ‘X’)
Example Input:
{'X', 'O', 'X', 'X'
...
2015.10.07
OverviewIn East Prussia(普鲁士), people try to walk all 7 bridges w/o crossing a bridge twice.
Leonhard Euler (pronounced “oiler”) – Swiss
Euler pathAn Euler path, also called an Eulerian trail, is a walk on the graph edges of a graph whi
...
2015.10.04
Questionlink
给一个 n*m 的房间，房间里存在各种可能的墙，房间的格子里已经放了 e 个器材，要求新放一个器材，放置位置距其它 e 个器材的距离最近。Breadth-first search.
Solution
对 e 个设备 BFS, 求每个设备到每个可以放新器材的点的距离，然后叠加。
最后 O（n^2）一遍找最小值。复杂度 O（e*n^2）
As for whether we choose to check each equipment posit
...
2015.10.02
StatsFacebook has 1.5 billion monthly active users, 970 million daily active users as of June 2015.
image from statista.com.
In 2009, Facebook stores 15 billion photos for the user, which grows at 220 million per week, and 550,000 per seco
...
2015.09.02
OverviewKISS - Keep It Simple, Sweetie.
In Today’s lecture:
write a crawler
thread-saft consumer & producer
GFS, BigTable and MapReduce
Top 10 keyword/anagram using MapReduce
Log analysis
News Aggregator App
Info Collection
crawl
...
2015.08.30
2015.08.30
OverviewLaunched on Sep 15th, 1997
60 trillion individual pages. 100 million GB data.
40,000 search per second, or 3 billion search per day.
As of Feb 2015, 65% market share in US.
1. CrawlGoogle crawl from 1 page to another using Googlebot
...
2015.08.30
OverviewToday we’ll look at 6 examples of problems associated with Web Service:
how the internet works
DNS
Web server
Music Player
MP3 file
秒杀
Question 0how to solve raido-play failures
> Failure rate = % user who can't listen to
...
2015.08.28
Question 4fix MP3 problem
The process of fetching a MP3 (from CDN):
aquire MP3 link, and send request
send request to CDN
CDN receive request, find MP3
response to client
play the music
Question: in step 2, there’s more Network error, b
...
2015.08.28
OverviewThis class covers database design:
design data with class and inheritance
design a user system (Netflix 2015)
design a payment system (Yelp, BigCommerce 2015)
Question 1design account (login/out) system for our radio app.
Ste
...
2015.08.26
Question 5Continue from last post, now let’s support VIP services.
User could buy VIP services using his acccount balance.
class ProService {
int userId;
double money;
long endTime;
public addMoney(){}
pu
...
2015.08.26
ObjectsMuch of the power and flexibility of modern software analysis and design derives from its use of objects.
ClassesClasses create an abstract representation of the world, letting you discard unnecessary details.
The 3 propertiesClass
p
...
2015.08.24
Overviewdefinationthe process of defining the architecture, components, modules, interfaces and data to satisfy specified requirements.
conceptual design (macro)
logical design
physical design (micro)
Top-down designEg. MS Office, Huawei
...
2015.08.23
A bottom-up exampleExample two: design a recommendation module
A simple algo:u1={m3,m5,m7,m11}
u2={m1,m2,m3,m4,m5,m6,m7,m8,m9}
Similarity( u1, u2 ) = 3
m - music
u - user
Similarity = # of same music for different
...
2015.08.23
From Level 0 to Level 1Refer to the previous question. How can we improve???
performance
scalability
robustness
performanceA better algo: Inverted Index
Avg performance increase to ~ 20ns (with some optimization of MapReduce procedure, d
...
2015.08.23
OverviewIn Unix-like OS, a pipeline is a set of processes chained by their standard streams, so that the output of each process (stdout) feeds directly as input (stdin) to the next one.
Pipes are unidirectional byte streams which connect th
...
2015.07.23
Overview3 areas of cryptographic standard:
encryption standard
Data Encryption Standard (obsolete)
Triple DES
Advanced Encryption Standard (AES)
RSA
OpenPGP
CipherSaber
hash standard
MD5
SHA-1
SHA-2
HMAC
PBKDF2
digital signature stand
...
2015.06.09
Overviewa port is a software construct serving as a communications endpoint in a computer’s host operating system.
purpose of ports is to uniquely identify different applications or processes running on a single computer and thereby enable
...
2015.06.08
The master statementOverloading is Compile Time and Overriding is Runtime.
ExamplesOverloadingpublic static class test
{
static void Main(string[] args)
{
Foo();
Foo("test");
}
publi
...
2015.05.24
Questionlink
Sort the letters in one word by the order they occur in another in linear time.
SolutionThis
text
is
used
to
stop
you
from
looking
at
the
answer
immediately
The answer is counting sort.
Code
...
2015.05.21
Questionlink
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <-
...
2015.05.10
Questionlink
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
Credits:Special thanks
...
2015.05.10
Questionlink
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have secur
...
2015.05.10
Questionlink
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 0000000000000000000000
...
2015.05.10
Questionlink
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 ed
...
2015.05.10
Questionlink
Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100
...
2015.05.10
Questionlink
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at
...
2015.05.10
Questionlink
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function
...
2015.05.01
Questionlink
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() s
...
2015.04.15
Questionlink
table.dungeon, .dungeon th, .dungeon td {
border:3px solid black;
}
.dungeon th, .dungeon td { text-align: center; height: 70px; width: 70px;}
The demons had captured the princess (P) and imprisoned
...
2015.04.15
Questionlink
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you
...
2015.04.15
Questionlink
Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
Credit
...
2015.04.14
Questionlink
Solution
Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.
You may assume that the array is non-empty and the majority element always e
...
2015.04.14
Questionlink
N 块石头排成一行，两个玩家依次取石头，每个玩家可以取其中任意一块或者相邻的两块，最后能将剩下的石头一次取光的玩家获胜。
Solution
when n = 1, first move wins
when n = 2, first move wins
when n = 3, first move removes middle stone, wins
when n = 4, first move remove
...
2015.04.14
Questionlink
There is a pile of n wooden sticks. The length and weight of
each stick are known in advance. The sticks are
to be processed by a woodworking machine in one by one fashion. It
needs some time, called setup time, for
the machine
...
2015.04.14
Questionlink
Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 2
...
2015.04.13
Questionlink
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assum
...
2015.04.13
Questionlink
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
Credits:Special thanks to @ts for adding this problem and creating all test cases.
...
2015.04.13
Questionlink
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ? num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return
...
2015.04.12
Questionlink
Given an array of values, design and code an algorithm that returns whether there are two duplicates within k indices of each other?
SolutionWe can keep a HashMap for storing the previous occuring position of a number.
Codepu
...
2015.04.12
Questionlink
Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain o
...
2015.04.12
Questionlink
Explain how you would implement a multi-map in Java without using any collections?
SolutionThis question is pretty strange in a tech interview. But still, if you are asked, I think the most obvious solution is pointed out by
...
2015.04.12
Questionlink
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
G
...
2015.04.11
Questionlink
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 ? a2
?
c1 ? c2 ?
...
2015.04.08
Questionlink
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you bef
...
2015.04.07
Questionlink
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
...
2015.04.07
Apply for Google AdSenseMy first request of AdSense is rejected because of “Site does not comply with Google policies“. I do not know the exact reason, but I did the following things to get it through:
I registered a top-level .COM domain
...
2015.04.07
Questionlink
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the to
...
2015.04.07
Questionlink
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
...
2015.04.07
OverviewHadoop Distributed File System (HDFS) is a Java-based file system that provides scalable and reliable data storage that is designed to span large clusters of commodity servers. HDFS, MapReduce, and YARN form the core of Apache™ Hado
...
2015.02.15
ref
Question
Suppose you are handling Amazon website and you have 10 MB size home page. Optimize the homepage for a customer who has 100 kbps internet connection.
Further he asked for the customer who has 100 mbps internet connection.
Re
...
2015.02.14
What hijacks your load time1. Too Many HTTP RequestsThis is the single biggest contributor to performance problems in most web pages.
Concatenate scripts and stylesheets
Combine images with sprites (put common images into a single large i
...
2015.02.14
Website KPIThere are 3 interesting phases of a web site from an end-user performance perspective.
First Impression
OnLoad
Fully Loaded Time.
Loading TimeQuestion: what percentage of the time a user spends waiting for your page to load is
...
2015.02.14
(… continued from last post)
9. Use a Content Delivery Network (CDN)Your site’s speed is greatly affected by where the user’s location is, relative to your web server. The farther away they are, the more distance the data being transmitted
...
2015.02.14
Questionlink
/**
* Given a nested list of integers, returns the sum of all integers in the list weighted by their depth
* For example, given the list {(1,1),2,(1,10)} the function should return 10 (four 1's at depth 2, one 2 a
...
2015.02.13
Questionlink
A question by dongfeiwww:
打印一个数的所有乘数组合，从大到小，不要有重复
Print all unique combinations of factors of a positive integer. For example given 24:
24*1
12*2
8*3
6*4
6*2*2
4*3*2
3*2*2*2
SolutionSimple DFS.
Codepublic List<List<
...
2015.02.13
Questionlink
Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.
If the array before adjustment is A, the array after adjustment is B, you should mini
...
2015.02.13
Questionlink
Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.
SolutionThe solution from gfg is definitely good, but I find this graphic
...
2015.02.13
Questionlink
Develop an algorithm to schedule an executive’s day, given a list of peoplethe executive has to meet with, the amount of time they request to see theexecutive, and the priority of the meeting.
SolutionRefer to [Question] 0-1
...
2015.02.12
OverviewA Web server exclusively handles HTTP requests, whereas an application server serves business logic to application programs through any number of protocols (including HTTP).
Example: Apache Tomcatweb server + servlet container
Examp
...
2015.02.11
Questionlink
Given two (dictionary) words as Strings, determine if they are isomorphic.
Two words are called isomorphic if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all occurrences
...
2015.02.11
Easy version[Q] Design a layer in front of a system which cache the last n requests and the responses to them from the system.
Solution:
[a] When a request comes look it up in the cache and if it hits then return the response from here and
...
2015.02.10
DefinitionAn abstract class is a class that is declared abstract —it may or may not include abstract methods. Abstract classes cannot be instantiated, but they can be subclassed.
with NO abstract method?
In JDK 1.0 it was indeed necessary t
...
2015.02.09
A short answerIn Java, all classes must have a constructor.
Can abstract class have constructorYes, it can. However, if we create an instance using it, it’s error.
Consider this example:
abstract class Base {
Base() { System.o
...
2015.02.09
Questionlink
N 是一个很大的正整数——可能到 10^15 次方，
简单起见，不考虑溢出，或者假设用 python
A 是一个 array，里面存着一些正整数，up to 1000 个
从 1 - N 这 N 个数，有多少个数，不能被 A 中的任何一个数整除的？
SolutionIt’s a very difficult question.
We can’t do it like a Sieve of Eratosthenes, cuz N is
...
2015.02.09
Questionlink
You are given an array of n elements [1,2,….n]. For example {3 2 1 4 6 5 7}.
Now we create a signature of this array by comparing every consecutive pair of elements. If they increase, write “I” else write “D”.
For example
...
2015.02.09
Question 1link
Convert a BST to max heap.
SolutionThe second answer:
a simple (reversed) in-order traversal of the BST. It would produce a sorted array which is indeed a max-heap!
Question 2link
Converting a heap to a BST in O(n) time?
...
2015.02.09
SpannerSpanner is Google’s globally distributed NewSQL database, the successor to BigTable. Google describes Spanner as not a pure relational system because each table must have a primary-key column.
Currently, F1, Google’s advertisement pl
...
2015.02.09
Questionlink
Calculate the number of slices. Slice means that the difference between the maximum and minimum in the slice <= 2.
eg. Given array 3 5 7 6 3.
There’re 10: (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (0,1) (1,2) (1,3) (2,3)
...
2015.02.09
Traditional solution
2 pointers
Hash
Big DataBloom filter, refer to [Design] Big Data - Fuzzy Search url (Bloom Filter).
...
2015.02.08
Questionlink
A binary search tree is given. Find the ceiling of given key. Eg.
8
3 12
2 6 10 15
4
Ceiling is defined as:
Ceil Value Node: Node with smal
...
2015.02.08
InternetThe Internet is a massive network of networks, a networking infrastructure. It connects millions of computers together globally, and computers talk thru protocols.
The Internet is a Big Collection of Computers and Cables.
WebThe Wor
...
2015.02.08
Questionlink
有很大一个电子图书馆，里面每本书的每一页都是 OCR 转换出来的 text，所有每页大约有 5%的 error（转换错误，错误分割单词，跳脱。。。）。设计一个方法判定图书馆里是否有完全一样的书（duplicate），或者将来有书进来时判定同样的书是否已存在。
SolutionVery large string matching, we mush use hashing or similar technique. Since books have er
...
2015.02.08
Questionlink
给定一个随机函数可以按照 0.5 的概率返回 true。
要求实现一个函数随机返回任意概率的 true。
SolutionEg. 0.25 true, then should be:
generate once. If false, return false, else…
generate again, directly return.
So, always return result for the possibility larg
...
2015.02.08
Questionlink
How to serialize strings and pass it over the network and de-serialize the string?
The string may contain any possible character out of 256 valid characters.
SolutionThe difficulty is how to differentiate between data (stri
...
2015.02.08
Questionlink
How to transform a unbalanced tree into balanced tree?
SolutionSolution 1, do AVL tree balancing. Refer to [Design] BST Node Insertion / Deletion. This is of course, pretty difficult to code.
Best solution is to convert
...
2015.02.08
QuestionRT. This is a very very common requirements in the area of string manipulation. We want it to be done very efficiently.
SolutionNormally, we would use a hashmap. However, we can also use bitmask or bitmap.
Work for a-z only, we use
...
2015.02.07
Questionlink
给一个矩阵，其中 0 代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够流向任意海洋的点。 比如说
0 0 0 1 2 3 0
0 1 2 2 4 3 2
2 1 1 3 3 2 0
0 3 3 3 2 3 3
那么就要给出 第二行的 4 （这有这点出发，能够找到连通道四个 0 的区域的一条非递增路线），当然也有可能找不到这样的点，或者找到多个点。
SolutionI read online and the best solutio
...
2015.02.07
Questionlink
Given a dictionary of wrods,find the pair of word with following property:
the two word don’t have same letter.
the multiple of the two word’s length is maximum.
I give a simple O(nnk)(k is the average length of word)
...
2015.02.07
Questionlink
Given a very long list of URLs, find the first URL which is unique ( occurred exactly once ).
Must do it in one traversal.
SolutionSuggested by the top answer and second answer, using a combination of trie and linked list.
...
2015.02.07
Questionlink
If two threads are incrementing a variable 100 times each without synchronization, what would be the possible min and maximum value.
SolutionWell, max is init+200, and min is init+2. Suggested by the top answer:
P1 & P2
...
2015.02.07
Reservoir sampling is a family of randomized algorithms for randomly choosing k samples from a list of n items, where n is either a very large number. Typically n is large enough that the list doesn’t fit into main memory. For example, a li
...
2015.02.07
Questionlink
Implement a Blocking queue.
SolutionFirst thing first, the most important characteristic of a BlockingQueue is:
thread-safe BlockingQueue
Second, we need to make sure to handle the following 2 methods:
notifyAll();
wait();
...
2015.02.05
Questionlink
Multiple threads can publish and receive each other’s message:
whenever a thread publishes a message, all the other threads can receive and print out that message;
if multiple message get published, the messages should be q
...
2015.02.05
Publish–subscribe patternThe publish–subscribe pattern is a messaging pattern where senders of messages, called publishers, do not send messages directly to specific subscribers. Instead, published messages are characterized into classes wi
...
2015.02.05
Questionlink
Give a list of documents, find the minimal document set that cancover all the characters in all the documents.
eg.
“a b c h j”,
"c d”,
“a b c”
“a f g”
“a h j”
The result should be
"a b c h j"
"c d&quo
...
2015.02.05
Question
We have a history of match result of pingpong games, assume each match is <player1, player2, result, timestamp>, player1 and player2 are long type, result is a bit value (1 means player1 win).
design a algorithm to sort the
...
2015.02.05
Questionlink
Design a data structure where the following 3 functions at O(1):
1. Insert(n)
2. GetRandomElement()
3. Remove(n)
SolutionArray is best for:
random access
HashMap is best for:
Searching
insert
remove
So the answer is ar
...
2015.02.04
Collatz ConjectureThe Collatz conjecture is a conjecture in mathematics known as the 3n + 1 conjecture.
Take any natural number n.
If n is even, divide it by 2 to get n / 2.
If n is odd, multiply it by 3 and add 1 to obtain 3n + 1.
R
...
2015.02.04
Questionlink
You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers?
SolutionThis is a famous inteview question by former Amazon engineer Steve Yegge:
Abo
...
2015.02.04
Questionlink
an arbitrary tree. split it into as many subtrees as you can. thenumber of nodes of the subtree must be even.
SolutionThis is a difficult question. The idea is recursive solution, but be cautious deadling with NULL.
NULL can
...
2015.02.04
Questionlink
Given a board of snakes and ladders game, provide an algorithm to find the minimum number of dice rolls required to reach 100 from 1.
Solution 1Recommended: Graph (shortest path). ref:
k is linked to k + 1 k + 2, k + 3, k +
...
2015.02.04
Questionlink
Given a server that has requests coming in.
Design a data structure such that you can fetch the count of the number requests in the last second, minute and hour.
Solution 1Keep a record of all request timestamps, suggested
...
2015.02.03
link
Question
Given n activities with their start and finish times.
Select maximum number of activities that can be performed in one run.
Example:
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9&#
...
2015.02.01
link
Question
You are given N ranges of date offsets when N employees are present in an organization. Something like
1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day )
2-6
8-9
..
1-14
Organize an event on min
...
2015.02.01
Questionlink
有一个接口叫 void setRPS(int num);
接下来不断有 request 过来，如何实现下面的接口，返回 accept 或者 deny，
bool process(int timestamp){
}
SolutionSuggested by level 5 of this post:
maintain a variable for the number of request processed/
...
2015.02.01
Question
Given stock price of Amazon for some consecutive days. Need to find the maximum span of each day’s stock price.
Definition of ‘span’ have got 2 variant:
Variant 1link
Span is the number of consecutive days right before that day,
...
2015.02.01
Questionlink
Objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used.
SolutionExplanation from here:
Build a binary tree. Each branch in the
...
2015.01.30
Questionlink
Four rectangles are given. Find the smallest enclosing (new) rectangle into which these four may be fitted without overlapping. By smallest rectangle we mean the one with the smallest area.
GreedyGreedy placement from large
...
2015.01.29
Question
Calculate area:
AnalysisWe are only able to come up with 2 equations using the obvious relationship between semicircle and square. But we have x, y and z variables.
How do we proceed?
SolutionThanks to wpz, who came up with the
...
2015.01.29
Questionlink
Given an array of integers , replace each element with the product of the remaining elements.
Eg : Input - 1 2 3 4 Output : 24 12 8 6
Do not use division.
SolutionStore the product of the left side elements for each integer
...
2015.01.29
Trie Nodepublic class TrieNode {
boolean isLeaf;
TrieNode[] child;
public TrieNode(boolean isLeaf) {
this.isLeaf = isLeaf;
this.child = new TrieNode[26];
}
public void insert(String str)
...
2015.01.28
Questionlink
给定n种物品和一背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为C，容积为D。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或者不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。
AnalysisThis is a extended question from [Question
...
2015.01.28
Questionlink
Design a system to return an unique ID for each request.
(For most of requests, the ID value should increase as time goes, the system should handle 1000 requests per second at least. )
Note: Timestamps alone is not valid s
...
2015.01.27
ref
Prefix tree
Building a well balanced BST needs time proportional to M * log N, where M is maximum string length and N is number of keys in tree.
Using trie, search in O(M) time.
The penalty is on trie storage requirements.
Implementati
...
2015.01.27
ref
OverviewstrStr() is a classic question in CS. There are various ways to solve (which we have discussed before), this is a summarization:
naive - O(m * n)
KMP - O(n) in worst case
Rabin-Karp, rolling hash - between O(m * n) and O(m +
...
2015.01.27
ref
Suffix ArrayA suffix array is a sorted array of all suffixes of a given string.
Any suffix tree based algorithm can be replaced with an algorithm that uses a suffix array enhanced with additional information and solves the same problem
...
2015.01.27
ref
Suffix treeBoth KMP Algorithm and Rabin Karp Algorithm pre-process the pattern to make the pattern searching faster. The best time complexity that we could get by preprocessing pattern is O(n), where n is length of the text.
Now we will
...
2015.01.27
Questionlink
Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not.
For example, if 1, 2, 3, 4, 5 is a push sequence, 4, 5, 3, 2, 1 is a
...
2015.01.26
Questionlink
Consider the following class:
class MyCounter {
private static int counter = 0;
public static int getCount() {
return counter++;
}
}
Is the method thread-safe? How to make it thread-
...
2015.01.26
OverviewGoogle Suggest was launched in 2004 as a 20% time project from Google engineer Kevin Gibbs. He developed the idea on a Google shuttle bus.
Design
Use trie.
Use cache (distributed cache)
TrieJust make use of all keywords (including
...
2015.01.24
What is Memcached?Memcached is an in-memory key-value store for small chunks of arbitrary data (strings, objects) from results of database calls, API calls, or page rendering.
Free & open source
high-performance, distributed memory obj
...
2015.01.24
Questionlink
A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland.
We’ll represent the land as a two-dimensional array of altitudes and use the following model, based on
...
2015.01.20
ref
1: What are benefits of using HTTPS over HTTP?HTTPS means that you tunnel the HTTP protocol over TLS/SSL which encrypts the HTTP payload.
So the benefit is that HTTP requests and responses are transmitted securely over the wire, e.
...
2015.01.20
Definitionsource
A abstract class is declared when it has one or more abstract methods.
An interface differs from an abstract class because an interface is not a class. An interface is essentially a type that can be satisfied by any class t
...
2015.01.20
Difference
Vectors are synchronized, ArrayLists are not.
Data Growth Methods
A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.
Similarities
Both Vector and ArrayList use grow
...
2015.01.20
Questionlink
给定两个数组A，B，长度均为n，求A[0]+B[0],…,A[0]+B[n-1],…,A[n-1]+B[0],…,A[n-1]+B[n]总共n^2个数的最大的n个值。
SolutionUse a Heap and then iteratively pop 1 and push 2 elements. Until n values has been filled.
Codepublic int[] topN(int[] arr1, int[] a
...
2015.01.20
Questionlink
Given two line segments (p1, q1) and (p2, q2), check if 2 line segments intersect.
OrientationConsidering 3 pointer, orientation can be:
counterclockwise
clockwise
colinear (not considering direction)
Note that orientation
...
2015.01.19
Questionlink
Given a polygon and a point ‘p’, find if ‘p’ lies inside the polygon or not. The points lying on the border are considered inside.
SolutionPrerequisite reading: [Question] Check if two line segments intersect.
Suggested by G
...
2015.01.19
ref
Short VersionTCP is a transport-layer protocol, and HTTP is an application-layer protocol that runs over TCP.
The layersAt the very bottom of the network stack is the physical layer. This is where electrical signals or light pulses or r
...
2015.01.19
Questionlink
Given set of words that are lexicographically sorted, return lexicographic order. E.g:
abc
acd
bcc
bed
bdc
dab
The order of letters for the given example would be
a->b->c->e->d
Solution
Just form a graph(DAG)
...
2015.01.18
Questionlink
Given a binary matrix, find out the maximum size square sub-matrix with all 1s. For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0
...
2015.01.18
Questionlink
Given a string, find its rank among all its permutations sorted lexicographically.
For example, rank of “abc” is 1, rank of “acb” is 2, and rank of “cba” is 6.
SolutionLet the given string be “STRG”. In the input string, ‘
...
2015.01.18
Questionlink
Find the nodes at d distance from a certain node in a Binary Tree
SolutionThere are two types of nodes to be considered:
Nodes in the subtree rooted of the target node.
Other nodes, may be an ancestor of target, or a node in
...
2015.01.17
OverviewA blocking queue is a queue that blocks when you try to dequeue from a empty queue, or if you try to enqueue items into a full queue.
Details
BlockingQueue doesn’t accept null values. Otherwise throw NullPointerException.
Blocking
...
2015.01.12
Blocking Queue VS. Thread PoolThese are 2 very different things, however it might be a little bit confusing for a layman. I have very little knowledge about Java multi-threading. But after writing some example of thread pool and blockingque
...
2015.01.12
Blocking Queue Implementation
source
A blocking queue is a queue, so we init a queue with a pre-defined size.
BlockingQueue Class comes with Java 5, in java.util.concurrent.BlockingQueue. This example is only used to help you understand w
...
2015.01.12
Questionlink
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.
SolutionThis is a similar question to [LeetCode 124] Binary Tree Maximum Path Sum. However there’
...
2015.01.11
Questionlink
Find all the repeating substring of specified length in a large string sequence.
For e.g.
Input String: "ABCACBABC"
repeated sub-string length: 3
Output: ABC
eg.
Input String: "ABCABCA"
repeated
...
2015.01.11
Questionlink
Given a string, find if there is any sub-sequence that repeats itself. Do not reuse any char.
Eg:
1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes, a fo
...
2015.01.11
Questionlink
X and Y are strings formed by 0 or 1. Distance is define as:
D(X,Y) = Remove chars common at the start from both X & Y.
Then add the remaining lengths from both the strings.
For e.g.
D(1111, 1000) = Only First alphab
...
2015.01.11
Questionlink
Finding the longest repeated substring.
Example: “banana” ==> “ana”
SolutionThere are 2 solutions: Suffix array, and Suffix tree.
1. Suffix array. Simple code, explained here.
Bentley’s programming pearl boo
...
2015.01.11
Questionlink
Given a digit ‘3141592653’, find number of occurence of subsequence “123”. Note that the sequence occurs twice:
3141592653
1 2 3
1 2 3
Output 2.
SolutionRefer to [LeetCode 115] Distinct Subsequences.
...
2015.01.11
Questionlink
Find the number of distinct subsequences of a string (include “” as a subsequence).
For example, Input
AAA
ABCDEFG
CODECRAFT
Output
4
128
496
SolutionIn [LeetCode 115] Distinct Subsequences, we discuss finding
...
2015.01.11
Questionlink
Find a polynomial-time algorithm that takes a string of length n, and a number k, output the number of distinct k-character subsequences.
For instance, input “food” and number k=2, output should be 4. There are four dis
...
2015.01.11
Questionlink1, link2, link3.
There is an array of integers which represent heights of persons.
Given another array… Let’s call it count-array. It contain how many persons in front of him are greater than him in height.
求原数组。(原数组中元素是
...
2015.01.10
Questionlink1
给一个数组 a[n]，令 s[i]为 a[i+1..n-1]中比 a[i]大的数的数量。
求最大的 s[i]。要求 O(nlogn)
SolutionThis is very similar question to [Google] Form a Queue Given Heights. The idea is to insert elements into BST and count number of larger elements.
...
2015.01.10
Questionlink
There are many sorted arrays. Find a minimum range, so that in each array there’s at least one integer within this range.
SolutionMin-heap. source
There are k lists of sorted integers. Make a min heap of size k containing 1
...
2015.01.10
Questionlink
Reverse a stack using recursion. You are not allowed to use loops or data structure, and you can only use the following functions:
isEmpty(S)
push(S)
pop(S)
SolutionWell since we are not allowed to use additional DS or loop,
...
2015.01.10
Questionlink
Given a continuous twitter feed, design an algorithm to return the 100 mostfrequent words used at this minute, this hour and this day.
AnalysisThis is a frequent and useful problem for companies like Google and Twitter.
The f
...
2015.01.09
Questionlink
Let’s say I gave you a long String and I wanted you to tell me the most common word in that String. How would you do that?
Follow-up: how about if I gave you the entire works of Alexandre Dumas, one of the most prolific auth
...
2015.01.09
n-gramIn the fields of computational linguistics and probability, an n-gram is a contiguous sequence of n items from a given sequence of text or speech.
The items can be phonemes, syllables, letters, words or base pairs according to the app
...
2015.01.09
Questionlink
Find the substring of length 3 which is present in the reverse order from the string.
Ex: if the string is abcdcba (cba is the reverse of abc) so we should return cba.
Solution
HashMap (recommended). Hash all substrings of
...
2015.01.09
Questionlink
The input is an endless stream of English words or phrases (we refer them as tokens).
Output top N tokens we have seen so far (from all the tokens we have seen!)
AnalysisWe will discuss the following details of implementati
...
2015.01.09
Questionlink
Given a string, find the number of distinct substrings of the string. Example:
input = “aaaa”,
output = 4 (the 4 substrings are “a”, “aa”, “aaa”, “aaaa”)
input = “abcd”,
output = 10 (“a”, “b”, “c”, “d”,
...
2015.01.08
Questionlink
检查一个字符串是否包含 k 位 a 进制数的所有表示形式。
保证原字符串的所有字串都是合法的 k 位 a 进制数。
“00110, a=2, k=2” => true （包括了 00，01，10，11）
SolutionFirst find all substrings with length == k, then generate all numbers in a scale. T
...
2015.01.08
OverviewPeer-to-peer (P2P) networking is a distributed application architecture that partitions tasks or work loads between peers.
Peers are both suppliers and consumers of resources, in contrast to the traditional client-server model where
...
2015.01.07
Questionlink
Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.
For example, if the given strings are “GeeksforGeeks” and “GeeksQuiz”, the output should be 5 as longest common substring is “Geeks”.
Solutio
...
2015.01.07
Questionlink
Given a set of n jobs with [start time, end time, cost], find a subset so that no 2 jobs overlap and the cost is maximum.
Let’s assume the input is already sorted by start_time.
SolutionSomebody mentioned Interval Graph, s
...
2015.01.07
Questionlink
Input: {“firstName”:”John”,”lastName”:”Smith”,”isAlive”:true,”age” :25,”height_cm”:167.6,”address”:{“streetAddress”:”212ndStre et”,”city”:”NewYork”,”state”:”NY”,”postalCode”:”10021-3100” },”phoneNumbers”:[{“type”:”home”,”number
...
2015.01.06
ref
QuestionGiven 1 trillion messages on fb and each message has at max 10 words.
How do you build the index table and how many machines do you need on the cluster to store the index table?
One possible answerTotal data = 1 trillion _
...
2015.01.06
ref
Cluster VS. GridCluster differs from Cloud and Grid in that
a cluster is a group of computers connected by a local area network (LAN)
cloud and grid are more wide scale and can be geographically distributed.
Another way to put it is t
...
2015.01.06
ref
Distributed hash tableA distributed hash table (DHT) is a class of a decentralized distributed system that provides a lookup service similar to a hash table. (key,value) pairs are stored in a DHT, and any participating node can efficien
...
2015.01.06
Questionlink
A frog wants to cross the river n meters wide. There’re some stones, but not complete from 1 to n.
The frog has a peculiar jumping rule. If it jumps x meters on one jump, the next jump has to lie in the range {x-1, x, x+1}.
...
2015.01.02
ref 1 ref 2
Why Indexing?In database disks (we’re talking about disk-based storage devices), data is stored as blocks. These blocks are accessed atomically. It’s like a linked list with pointers to the blocks.
Because of this, searching in
...
2014.12.27
The problemIn setting up the octopress environment, we need to install dependencies like this:
gem install bundler
bundle install
First line simply installs bundler (a Ruby dependency manager). The second line is where you might face probl
...
2014.12.23
Exceptions in JavaIn Java, there are 3 categories of exceptions:
checked exceptions
Typically a user error
eg. if a file cannot be found.
These exceptions cannot simply be ignored at the time of compilation.
runtime exceptions (also cal
...
2014.12.23
OverviewPolymorphism is to use common interface instead of concrete implementation while coding.
The most common use of polymorphism in OOP occurs when a parent class reference is used to refer to a child class object.
Quick Summary:ref
A
...
2014.12.22
Questionlink
Given an array of positive numbers, find the maximum sum of a subsequence that no 2 numbers should be adjacent.
Eg. (3, 2, 7, 10) should return 13 (3+10)
Eg. (3, 2, 5, 10, 7) should return 15 (3+5+7).
SolutionIt is an m
...
2014.12.22
Sometme I found the different concepts in Ruby very confusing for beginners. So I write this post to explain some terminologies in ruby setup.
RubyGems (tool)RubyGems is a package manager for the Ruby programming language.
It is a tool to m
...
2014.12.22
Can an interface extend another interface in Java?Yes. Just remember that you should implement the methods in both interfaces.
Example in Java source code link1, link2:
public interface List<E> extends Collection<E> {
...
2014.12.22
Questionlink
整数的拆分问题
如，对于正整数 n=6，可以拆分为：
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1
现在的问题是，对于给定的正整数 n，程序输出该整数的拆分种类数(HDOJ 1028)。
SolutionThis is very similar to another question I posted before: C
...
2014.12.22
Common Root Classjava.lang.Object, link
All Java classes are derived from this common root class, that defines common behaviors.
Common behaviors include multi-threading and garbage collector etc.
Some methodsref
protected Object clone() th
...
2014.12.22
Can we overload main method in Java?Can. But only public static void main(String[] args) will be used when your class is launched by the JVM.
You can call other main() method yourself from code.
Eg.
class Simple{
public static void m
...
2014.12.22
QuestionDLL - link
Inorder - link
Given a BST, write a function that returns true if there is a triplet that sums to 0, returns false otherwise.
SolutionWe will solve the question just like we do [LeetCode 15] 3Sum. What is missing is an
...
2014.12.18
Questionlink
Given a binary tree, print it vertically. The following example illustrates vertical order traversal.
1
/ \
2 3
/ \ / \
4 5 6 7
\ \
8 9
The
...
2014.12.17
Questionlink
In a 2D matrix of dimensions M*N, find number of “equilibrium” points. A point (i, j) is said to be an “equilibrium” point only if all following conditions hold:
a) sum of rows 1…(i-1) = sum of rows (i+1)…M
b) sum of
...
2014.12.17
Questionlink
Suppose N patients and M diseases. N is sufficiently large number and M isrelatively small, say 30-ish. Each patient can have possible 0 to M kinds ofdiseases.
Given one patient’s name, show me a list of similar patients sha
...
2014.12.08
Questionlink, MIT handouts Person_A
Describe an algorithm that takes an unsorted array of axis-aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair.
Axis-aligned means that all the rectangle sides
...
2014.12.02
Questionlink
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Solution
The multiples of 3 are 3,6,9
...
2014.11.30
Questionlink
Code a hashmap which you would be happy to place into a production environment.
SolutionWe already write 2 post before:
[Question] Implement a HashMap
[CC150v5] 8.10 Implement a Hashmap
But still, this is not an easy ques
...
2014.11.04
Questionlink
Given a 2D array with only 1s and 0s, where each row is sorted.
Find the row with the maximum number of 1s. Input matrix:
0 1 1 1
0 0 1 1
1 1 1 1 // this row has maximum 1s
0 0 0 0
Output: 2
AnalysisBy using a modified
...
2014.11.01
Questionlink
给一个包含正负整数的数组，要求对这个数组中的数进行重新排列，使得其正负交替出现。首先出现负数，然后是正数，然后是负数。有多余的数的一方，就放在末尾。
如 [1, 2, 3, -4]->[-4, 1, 2, 3]，[1,-3,2,-4,-5]->[-3,1,-4,2,-5]. 要求使用O(1)的额外空间。
如果需要保持正数序列和负数序列各自原来的顺序，如何做？
如果不需要保持正数序列和负数序列各自原来的顺序，如何做？
Sol
...
2014.10.08
Question
Given a list of words, write a program to find the longest word made of other words in the list.
EXAMPLE
Input: cat, banana, dog, nana, walk, walker, dogwalker
Output: dogwalker
SolutionSearch it recursively from longest to shor
...
2014.10.02
Question
Given a lengthy document without spaces, punctuation, and capitalization:
eg: iresetthecomputeritstilldidntboot
Now add back in the punctation and capitalization.
Most of the words will be in a dictionary, but some strings,
...
2014.10.01
Question
Consider a simple node-like data structure called BiNode, which has pointers to two other nodes.
public class BiNode {
public BiNode node1, node2;
public int data;
}
The data structure BiNode could be used to r
...
2014.09.30
Question
Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x).
Implement the data structures and algorithms to support these op
...
2014.09.28
Question
Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n-m (that is, find the smallest such sequence).
SolutionReferring to this
...
2014.09.27
Question
Implement a CircularArray class that supports an array-like data structure which can be efficiently rotated.
The class should use a generic type, and should support iteration via the standard for (Object : circuLarArray) notatio
...
2014.09.26
Question
Imagine you have a 20 GB file with one string per line.
Explain how you would sort the file.
SolutionUse External Sort. For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:
Divide the file into chunks
...
2014.09.24
Question
You’reworking on the Google Chrome team when you receivea bug report: Chrome crashes on launch. What would you do?
Step 1: Understand the Scenario
How long has user seen this issue?
version of browser and OS?
Does this happen cons
...
2014.09.24
Question 1
A magic index in an array A[l.. .n-l] 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.
Question 2
FOLLOW UP: What
...
2014.09.17
Question
Implement the “paint fill” function that one might see on many image editing programs.
That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the
...
2014.09.17
Question
Given a boolean expression consisting of the symbols 0, 1, ‘&’, ‘|’, and ‘^’, and a desired boolean result value ‘result’.
Now implement a function to count the number of ways of parenthesizing the expression such that it ev
...
2014.09.17
Question
You have a stack of n boxes, with widths w., heights h, and depths d. The boxes can only be stacked on top of one another if each box is strictly larger than the box above it in width, height, and depth.
Implement a method to bu
...
2014.09.17
Question
You are given two 32-bit numbers, N andM, and two bit positions, i and j. Write a method to insert M into Nsuch that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all ofM. Th
...
2014.09.16
Question
You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams.
Given a scale, how to find the heavy bottle only scaling ONCE?
SolutionTake 1 pill from Bottle 1, 2 pills from Bottle 2, and so
...
2014.09.16
Question
Write a function to determine the number of bits (change) required to convert integer A to integer B.
SolutionUsing XOR operation, we can find out number of bits that are different.
The next important thing is to know how to cou
...
2014.09.16
Questionlink
给你一个 password 假定 6 位
有个 function, 每 call 一次就给你一个 triplet 是 password 里的随即三位(order 不变)。比如 google, 可能返回: ggl, goe, oog, ool…
问如何最有效破译这个密码?
SolutionThis is just a rough idea suggested by Level 6 of this post.
六位密码随机给三位，应该有 C
...
2014.09.16
Question
Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).
SolutionMask odd and even bits seperately.
Codepublic static
...
2014.09.16
Question
Implement a stack.
SolutionStack uses LinkedNode to implement.
Codepublic class MyStack {
Node top;
public int pop() {
if (top == null) {
return -1;
}
int returnV
...
2014.09.15
Question
Implement a function to check if a linked list is a palindrome.
SolutionThere are multiple solutions for this question.
First, maybe the simplest solution of all, is to compare the list with the reversed list (compare first half
...
2014.09.15
Question
How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element?
Push, pop and min should all operate in 0(1) time.
SolutionThis is a very tricky question.
The key is
...
2014.09.15
Question
An animal shelter holds only dogs and cats. People must adopt either the “oldest” animals, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which spec
...
2014.09.15
Question
Implement an algorithm to find the kth to last element of a singly linked list.
Do it recursively.
SolutionIterative solution is easy, recursive is not.
Codepublic static int nthToLastRecursive(LinkedListNode head, int n) {
...
2014.09.14
Question
What protocol is used for communicating with a DNS?
AnswerDomain Name System (DNS) is a hierarchical distributed naming system for computers, services, or any resource connected to the Internet or a private network. It associates
...
2014.09.12
Questionlink
Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
...
2014.09.11
Questionlink
Given a sorted set, find if there exist three elements in Arithmetic Progression or not.
SolutionThis is a rather simple Arithmetic Progression question.
To find the three elements, we first fix an element as middle elemen
...
2014.09.11
Questionlink
You have a room with n people. A celebrity walks in. Everyone knows the celebrity, the celebrity knows no one.
Non-celebrities may/may not know anyone in the room.
Give an algorithm to find the celebrity. Discuss the
...
2014.09.11
Questionlink
2d array ＊代表障碍物 ＃代表货物 空白就是正常的路
问如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍需要绕开，拿到以后要放回出发点，然后再取另一个.
＊＊＊＊＊＊＊＊＊＊
＊ # ＊
＊ ＊＊＊ ＊ ＊
＊ ＊
＊ ＊＊ ＊ ＊
＊ # # # ＊＊＊
＊＊＊＊＊＊＊＊＊＊
SolutionThis looks like a
...
2014.09.11
Question
Write a method to count the number of 2s between 0 and n.
SolutionThis is a difficult question, especially hard to come up with the correct formula. Eg.
f(279) = {(79 + 1) + 2 * f(99)} + f(79)
f(513) = {100 + 5 * f(99)
...
2014.09.10
Question
Imagine you have a square matrix, where each cell is filled with either black or white.
Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
SolutionThere is no better way to
...
2014.09.10
Question
Given a string s and an array of smaller strings T, design a method to search s for each small string in T.
SolutionThis is a very classic question of string search, favored by Google and Facebook.
The solution is suffix tree (to
...
2014.09.10
Question
Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum.
SolutionI wrote about this question before: [Question] Max Sum In A 2D Array (sub-matrix), and the solution ga
...
2014.09.10
Question
Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.
SolutionThis is very similar to another post I wrote: [Question] Shuffle An Array (Fisher–
...
2014.09.10
Question
Describe an algorithm to find the largest 1 million numbers in 1 billion numbers.
Assume that the computer memory can hold all one billion numbers.
SolutionThere’re enough discussion on Top K problems so far in this blog. The su
...
2014.09.10
Questionlink
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
(This is also on CC150v4 19.2 and CC150v4 17.2)
SolutionFirst, confirm that when the number of pieces in a line equals to the dimension
...
2014.09.09
Question
Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator.
EXAMPLE
Input: 5, 10
Output: 10
This is also on CC150v5 Q17.4.
SolutionWe can’t use >, < or if-else state
...
2014.09.09
Question
Given an integer between 0 and 999,999, print an English phrase that describes the integer (eg, “One Thousand, Two Hundred Thirty Four”).
This is also on CC150v5 Q17.7.
SolutionThe solution in book isn’t good, so I wrote the cod
...
2014.09.09
Question
Write a method to implement *, - , / operations You should use only the + operator.
SolutionFirst it’s important to write a ‘negate’ operator. The code given in the book:
public static int FnNegate(int a) {
int neg = 0;
...
2014.09.08
Question
In Java, does the finally block gets executed if we insert a return statement inside the try block of a try-catch-finally?
SolutionYes, it will.
Even when we attempt to exit within the try block (normal exit, return, continue, bre
...
2014.09.08
Question
What is the difference between Final, Finally, and finalize?
finalis a keyword.
Variable decleared as final should be initialized only once and cannot be changed.
Classes declared as final cannot be extended.
Methods declared as
...
2014.09.08
Question
Given a two dimensional graph with points on it, find a line which passes the most number of points.
SolutionFor this question, we used to use HashMap(Double, Integer) to do. However, the answer suggested in the book define its ow
...
2014.09.08
Question
Suppose you are using a map in your program, how would you count the number of times the program calls the put() and get() functions?
SolutionWrite a wrapper class upon the HashMap Class, and override the ger() and put() methods.
...
2014.09.08
Question
In terms of inheritance, what is the effect of keeping a constructor private?
SolutionIf the programmer does not provide a constructor for a class, the system will always provide a default, public no-argument constructor.
To disab
...
2014.09.08
Question
Explain what object reflection is in Java and why it is useful.
SolutionJava Reflection makes it possible to inspect classes, interfaces, fields and methods at runtime, without knowing the names of the classes, methods etc. at co
...
2014.09.08
Question
You are given the source to an application which crashes when it is run After running it ten times in a debugger, you find it never crashes in the same place The application is single threaded, and uses only the C standard library
...
2014.09.08
Question
Write a method to find the number of employees in each department.
Answerselect
Dept_Name,
Departments.Dept_ID,
count(*) as ‘num_employees’
from
Departments
left join
Employees
on
Employees.Dept_ID = Depart
...
2014.09.08
Question
What are the different types of joins? Please explain how they differ and why certain types are better in certain situations.
Implicit and explicitThe “explicit join notation“ uses the JOIN keyword. The “implicit join notation“ si
...
2014.09.08
Question
How would you load test a webpage without using any test tools?
SolutionLoad testingLoad testing is testing under normal and peak load condition. It’s also called software performance testing, reliability testing, and volume testi
...
2014.09.08
Question
Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation.
If the number can not be represented accurately in binary, print “ERROR”
SolutionConvert the integer part is easy.
The difficul
...
2014.09.07
Question
There is an 8x8 chess board in which two diagonally opposite squares have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares.
Can you use the 31 dominos to cover the entire board? Prove your
...
2014.09.07
Question
An array A[1…n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation.
The elements of A are represented in binary, and the
...
2014.09.07
Question
Write a method to compute all permutations of a string.
Do it recursively.
Solution
Get first char.
Permute the reminder of the string.
Insert that char into all possible positions.
The code is more concise that doing it ite
...
2014.09.07
Question
Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return
...
2014.09.07
Question
You have a very large array of ‘Person’ objects. Sort the people in increasing order of age.
SolutionFirst we look at the nature of this question:
large input array
sort based on age (which is between 1 and 100, this is important
...
2014.09.07
Questionlink
Given a string, convert it into a palindrome with the lease number of insertions possible.
SolutionThis is a DP question. There’re 2 approaches.
First, is direct DP. This is the nicest solution, not intuitive at first, but a
...
2014.09.06
Question
You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
Solution 1The best solution is to print inorder and preorder traversal of bo
...
2014.09.06
Question
Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node in a binary search tree where each node has a link to its parent.
Solution
If current node have a right child, return the leftmost leaf of right
...
2014.09.06
Question
You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.
SolutionKeep a l
...
2014.09.06
Question
In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of di!erent sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on
...
2014.09.06
Question
Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented.
The following are the only functions that should be used to write this program: push | pop | peek | isEmp
...
2014.09.06
Questionlink
You are given a graph and an algorithm that can find the shortest path b/w any two nodes.
Now you have to find the second shortest path between same two nodes.
SolutionFrom the top answer:
Find the shortest path betwe
...
2014.09.04
Questionlink
UTF-8 is a variable-length encoding of letters or runes. If the most significant bit of the first byte is 0, the letter is 1 byte long. Otherwise, its length is the number of leading 1’s in the first byte. If a letter is more
...
2014.09.04
Question(this question is from MIT handouts B)
Describe a technique to identify a “leader” among a group of 10 identical servers that are all connected to every other server.
There are no prior distinguishing characteristics of any of th
...
2014.09.03
Questionlink
String replace, 给一个原 string，一个 target，一个替换的新 str，把所有出现target str 的地方都换成新的 str， 长度可以任意.
SolutionIf the question asks for an in-place algo, then we can refer to Question 1.5 in CC150v4.
Question
1.5 Write a method to replace al
...
2014.09.03
Questionlink
数组排序， 排成 a1a3a5。。。这种形式。
SolutionThe are 2 solutions. The easy one is this:
sort first, then 把临近的奇数换到偶数(index)上, O(nlog n).
There’s a great O(n) solution however, not easy to think:
两两比较相邻数字，把大的数字放到下标为奇数的位置。 O(n).
Code
...
2014.09.03
Questionlink
Imagine you had a dictionary. How would you print all anagrams of a word? What if you had to do this repeatedly? Could you optimize it?
SolutionA very nice solution:
Open dictionary
Create empty hashmap H
For each word in
...
2014.09.02
Observer patternThe observer pattern is a software design pattern in which an object(subject) maintains a list of dependents(observers), and notifies them automatically of any state changes (usually by calling one of their methods).
The Obs
...
2014.09.02
Questionlink
Given an int array A[], define:
distance = A[i] + A[j] + (j-i), j >= i.
Find max distance in A[]
SolutionSolution suggested on floor 8 of this post.
distance = (A[i] - i) + (A[j] + j), so we do 2 ite
...
2014.09.02
Questionlink
Given a wordlist like this:
1. ccaa
1. baca
1. baaa
1. bbbb
and a Grid like this:
X X
XXXX
X X
XXXX
Now solve this crossword. One possible solution:
b c
baca
b a
baaa
SolutionThe corssword problem is NP-Complete, so yo
...
2014.09.01
Questionlink
Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
Write a function that takes a list of binary numbers and returns the sum of the hamming dista
...
2014.09.01
Question
How to prevent deadlock? (question from MIT handouts 1)
AnalysisPreventing one of the 4 conditions will prevent deadlock:
Removing the mutual exclusion condition, but not very possible.
The hold and wait conditions may be remove
...
2014.09.01
DefinitionA* is a computer algorithm that is widely used in pathfinding and graph traversal.
It uses a knowledge-plus-heuristic cost function like this:
f (n) = g(n) + h(n)
f (n): estimated total cost of path through n to goal
g(x) &#
...
2014.08.30
OverviewCryptographic hash function is a hash function which is considered practically impossible to invert.
The input is arbitrary length, and output is fixed length.
The input is called ‘message’ and output (the hash value) is called ‘dig
...
2014.08.30
TSP problemGiven a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
It is an NP-hard problem in combinatorial optimization.
...
2014.08.30
DefinitionFor every two-person, zero-sum game with finitely many strategies, there exists a value V and a mixed strategy for each player, such that
Given player 2’s strategy, the best payoff possible for player 1 is V, and
Given player 1’s
...
2014.08.30
Questionlink
Boggle Game:
F X I E
A M L O
E W B X
A S T U
The goal of the game is to find as many words as you can that can be formed by chaining letters together. You are given a dictionary of words are reference.
SolutionThe best sol
...
2014.08.29
First WordA cookie is a small text file that is stored by a browser on the user’s machine. Cookies are plain text; they contain no executable code.
Every time the user loads the website, the browser sends the cookie back to the server to no
...
2014.08.28
Question
Write a program that breaks up a string of words with no spaces into a string with the appropriate spaces.
Follow the following process:
Clarify the problem
Refine the solution
Code it
Last words
Clarify the problem
Consider a g
...
2014.08.28
Question
Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
SolutionThis is very difficult question. All I can say is, just memorize this solution.
It works like this:
Init 3 queues, with initial
...
2014.08.28
Questionlink
In a binary tree, if in the path from root to the node A, there is no node with greater value than A’s, this node A is visible. We need to count the number of visible nodes in a binary tree. For example, in the following tree
...
2014.08.27
Question 1link
Given a 2D array (n x m) of integers, find all duplicate rows and print their index.
SolutionThis is a google question.
Use HashMap (but make your own). Computer hash value of each row and insert into HashMap as value pair
...
2014.08.27
Questionlink
Given a permutation which contains numbers in the range [1, N], return the length of the largest cycle in the permutation.
A permutation cycle is a subset of a permutation whose elements trade places with one another.
Samp
...
2014.08.27
Questionlink
Given API: int Read4096(char* buf);
It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file. The retu
...
2014.08.27
Questionlink
Object Oriented design for Elevator in a multi-storied apartment
A Single ElevatorUse Case:
User
press a button to summon the lift
press a button to get to a specific floor
Button
floor button and level button
illuminates
...
2014.08.26
Question
How to test hashCode() function? Example:
public int hashCode(){
int result = 17 + hashDouble(re);
result = 31 * result + hashDouble(im);
return result;
}
SolutionWe need to test that the hash function is reflexive,
...
2014.08.26
TerminologiesPagingPaging is a method of writing data to, and reading it from, secondary storage for use in primary storage, also known as main memory. Paging plays a role in memory management for a operating system.
Page tableA page table
...
2014.08.26
Question
Explain the data structures and algorithms that you would use to design an in-memory file system. Illustrate with an example in code where possible.
SolutionA file system consists of Files and Directories. Each Directory contains
...
2014.08.25
Question
Design and implement a hash table which uses chaining (linked lists) to handle collisions.
SolutionI wrote this topic before (using Java source code as a reference). This time, I would like to take another (easier) approach.
The m
...
2014.08.25
Question
Design a Parking Lot.
SolutionClass hierarchy:
A parking lot has multiple Levels.
A Level has multiple Parking Spot.
A Spot can park motorcycle, car or bus, which all belongs to Vehicle.
Implement methods:
Vehicle.parkInSpot(Sp
...
2014.08.25
Question
Explain how you would design a chat server. In particular, provide details about the various back end components, classes, and methods.
What would be the hardest problems to solve?
SolutionFirst, decide the objects and methods.
...
2014.08.24
… Continued from previous post.
Overall viewThe system consists of a database, a set of clients, and a set of servers. This is not about OOD, but we need to know.
DB stores user list, chat archive. An SQL DB would be good, unless we want B
...
2014.08.24
Question
Othello is played as follows: Each Othello piece is white on one side and black on the other. When a piece is surrounded by its opponents on both the left and right sides, or both the top and bottom, it is said to be captured and i
...
2014.08.24
QuestionWhat are the advantages of binary search trees over hash tables?
Answer
More memory-efficient. (They do not reserve more memory than they need to)
For instance, if a hash function has a range R(h) = 0…100, then you need to allo
...
2014.08.23
Shared hostingShared hosting is like living in an apartment where you share a common space with your neighbors. You cannot customize anything but you share maintenance cost and responsibility with your neighbors.
Economical
Technical maint
...
2014.08.23
OverviewValue types are created on the stack, and reference types are created on the heap.
Both are stored in computer RAM.
Each thread gets a stack, while there’s typically only one heap for the application.
StackWhen a function is called,
...
2014.08.23
Question
Design a Generic Deck of Cards
SolutionA simple design:
enum Suit {
HEART, DIAMOND, SPADES, CLUBS;
}
class Deck {
List<Card> deck;
}
class Card {
Suit suit;
int num;
}
A more complex desi
...
2014.08.22
Question
给出下面这个图 设计数据结构和算法求出图中所有的正方形数量 (count the number of squares).
Solution
Pre-processing: 从每一个点开始存储上下左右四个方向最多延伸到的位置
Main algorithm: 枚举右下角位置 然后枚举正方形边长
根据预处理的延伸情况判断是否能够有一个正方形被构造出来
Total time complexity is O(n^3).
预处理可以 O(n^2) 预处理是
...
2014.08.20
Question
Count Set Bit in Binary Number.
3 = 00000011 => 2
128 = 10000000 => 1
SolutionBits counting algorithm (Brian Kernighan). Basic idea is clear 1 bit at a time.
This algorithm goes through as many itera
...
2014.08.20
Questionlink
Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.
SolutionDP
Sum(m, n, X) = Sum(m, n - 1, X - 1) +
...
2014.08.20
Implement Singlton3 ways of writing Singleton.
using EnumThis is only available since Java 6.
public enum Singleton_Enum {
INSTANCE;
}
using double checked lockingThis is lazy loaded thread-safe Singleton, which is popular durin
...
2014.08.20
Factory Method PatternFactory Method design pattern is one of the 2 most frequent topics for OOD.
Factory method pattern is a creational pattern which uses factory methods to deal with the problem of creating objects without specifying the
...
2014.08.19
Questionlink
A perfect binary tree, i.e. each node in the tree is either a leaf node, or has two children, and all leaf nodes are on the same level. Each node has an index in depth-first order.
0
/ \
1 4
/ \ / \
2 3 5
...
2014.08.19
Singleton PatternSingleton design pattern is one of the 2 most frequent topics for OOD.
Singleton pattern is a design pattern that restricts the instantiation of a class to one object.
in JavaSince Java 5.0, the easiest way to create a Sing
...
2014.08.19
Questionlink
给定一个表达式字符串，其中只包含非负整数，加法，减法以及乘法符号，例如 7+345+2+4-3-1。请写程序计算该表达式的值。
提示：可以尝试使用递归算法，程序将非常简洁易写，很适用于面试场合。
SolutionTrying to solve this problem iteratively is like suicide. The code would be lengthy and buggy, and very hard to make
...
2014.08.17
Questionlink
对于包含n个结点的二叉树（树中结点编号从1到n），已知前序和后序遍历序列，我们知道不一定能唯一的恢复这棵树。请计算出满足条件的二叉树的总数。
Example
前序遍历序列preorder：1 2
后序遍历序列postorder：2 1
一共有2棵满足条件的二叉树：
1 1
/ \
2 2
Solution
先看两种遍历的性质:
pre-order: root, left
...
2014.08.17
Questionlink
数组nums中有n个非负整数（整数用字符串表示），将它们以一定的顺序拼接，得到最大的整数。
样例：
nums: [“54”, “546”, “548”, “60”]
可以拼接得到的最大整数为”6054854654”，因此函数应该返回”6054854654”。
SolutionI will first list out 2 special cases:
{40, 20, 201} => 4020201
{40, 20,
...
2014.08.17
Questionlink
Excel中的行列数用A~Z 26个字母表示，A, B, C, D, …, Z, AA, AB, …, AZ, BA, BB, … 分别表示10进制数1, 2, 3, 4, …, 26, 27, 28, …, 52, 53, 54…。
请实现2个函数decToExcel和excelToDec，将10进制数转换为Excel数，以及将Excel数转换为10进制数。
SolutionNote the indexing starts from 1,
...
2014.08.16
Questionlink
有一个 n*m（n 和 m 都不超过 50）的棋盘，有 k 个目标格子需要访问。需要访问的格子的横纵坐标存放在数组 x[]和 y[]中(0<=x[i]<n, 0<=y[i]<m)。
遍历的规则为：
每一步只能从一个目标格子水平或者竖直跳跃移动到另一个目标格子。
连续的两步必须形成直角。即如果前一步是水平移动，那么下一步只能竖直移动。
问是否存在一种遍历顺序，使得每个目标格子有且仅被访问一次。
样例
...
2014.08.16
Questionlink
每一种语言，都有自己的字母表，类似英文的 a-z，但是顺序不相同。例如，有的语言可能是 z 是第一个之类的。现在给定这个语言的字典，请分析这个字典，得到这个语言的字母表的顺序。
例如：有如下的字母：C CAC CB BCC BA。 经过分析，得到字母表为 C->A->B。
Solutionhttp://page.renren.com/601882592/channel-noteshow-927705419
C 2. CAC 3.
...
2014.08.15
Question
Get GCD in more efficient code
Codethis is 掉渣天。
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
...
2014.08.15
Questionlink
有一个无限大的棋盘，棋盘上有一匹马，马可以从长宽分别为p和q的矩形一个角移动到对角。即假设马当前的位置为(x,y)，那么下一步可以移动到(x+p,y+q)，(x+p,y-q)，(x-p,y+q)，(x-p,y-q)，(x+q,y+p)，(x+q,y-p)，(x-q,y+p)或者(x-q,y-p)这8个位置。
问马是否能从坐标(x,y)按照上述移动规则移动到坐标(x2,y2)。
Solutionref
计算dx=x-x2,dy&#x
...
2014.08.15
Questionlink
给定一个非负整数a（不超过10^6），是否存在整数b，使得a和b的乘积全为1。如果存在，返回最小的乘积的位数。如果不存在，返回-1。
样例：a=3，存在b=37，使得3*37=111，则函数应返回3（111的位数）。
SolutionThere’s 1 equation of mod operation, which is helpful:
(a * b) mod x = ((mx+a’) * (n
...
2014.08.15
Questionlink
有n个任务需要完成（编号1到n），任务之间有一些依赖关系，如果任务a依赖于任务b和c，那么只有当任务b和任务c完成之后才能完成任务a。给定所有的依赖关系，判断这些任务是否能够完成。如果能够完成，请给出一个合法的任务完成序列。
样例：
n=5
1->2,3
3->4
上述样例中任务1依赖于任务2和任务3，任务3依赖于任务4，那么存在合法的任务完成序列4,3,2,1,5
SolutionClassic topology so
...
2014.08.15
Questionlink
有一个长度为 n 的字符串 str，有非常多的关键字 query（长度不超过 10），需要判断每个关键字是否是 str 的子串。
注意：query 是动态的输入进行查询的，预先并不知道所有的 query。
SolutionBest idea of the solution is to use Suffix Tree and similar alternatives.
Solution 1 is an nice idea using HashM
...
2014.08.14
Client/Serverlink
Client have direct and full access to the physical database based on their login string. This is the major weakness of the Client/Server paradigm. The system is vulnerable to attacks.
Because all business logic w
...
2014.08.12
Question
A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights
...
2014.08.12
HandshakingHandshaking is an automated process of negotiation that dynamically sets parameters of a communications channel established between two entities before normal communication over the channel begins.
It is usually a process that ta
...
2014.08.11
Questionlink
Given n numbers (both +ve and -ve), arranged in a circle, fnd the maximum sum of consecutive number
SolutionFirst pass: find max subarray sum.
Second pass: find min subarray sum, and subtract it from total sum.
Suggested on
...
2014.08.11
Questionlink
给定一棵完全二叉树（complete binary tree）的根结点，统计该树的结点总数。
提示：使用O(n)的递归算法统计二叉树的结点数是一种显而易见的方法，此题中请利用完全二叉树的性质，想出效率更高的算法。
SolutionSimilar to binary search, O(lgn) complexity.
The idea is, sum up 1 branch of nodes at a time. Do it recursi
...
2014.08.11
Questionlink
2.5 亿个整数中找出不重复的整数的个数，内存空间不足以容纳这 2.5 亿个整数。
AnalysisCategorized under 双层桶划分 or BitMap.
整数个数为 2^32,也就是，我们可以将这 2^32 个数，划分为 2^8 个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用 bitmap 就可以直接解决了。
But how exactly to use BitMap? 将 bit-map
...
2014.08.10
Questionlink
在海量数据中找出出现频率最高的前 K 个数，或者从海量数据中找出最大的前 K 个数，这类问题通常称为“top K”问题，
top K value
top K frequency
AnalysisStandard solution is 【分治+trie 树/hash+小顶堆/quickselect】, which I covered in another post Big Data - Top k Frequency.
...
2014.08.10
Questionlink
5 亿个 int 找它们的中位数.
AnalysisCategorized under 双层桶划分.
Idea: 首先我们将 int 划分为 2^16 个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
Details开一个大小为 65536 的 Int 数组，第一遍读取，统计 Int32 的高 16
...
2014.08.10
Questionlink
给 40 亿个不重复的 unsigned int 的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那 40 亿个数当中？
AnalysisCategorized under BitMap.
There’re 4.3 billion unsigned integers in Java. This is a perfect question to use BitMap.
申请 512M 的内存，一个 bit 位代表一个 unsigned
...
2014.08.10
Questionlink
给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
Bloom Filter自从Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被广泛用于__拼写检查，数据库系统中。。。可以实现数据字典，进行数据的判重，或者集合求交集__
基本原理及要点An empty Bloom filter is a bit array o
...
2014.08.10
OverviewA functional language allows you to write a mathematical function, i.e. a function that takes n arguments and returns a value. If the program is executed, this function is evaluated.
A purely functional program always yields the sam
...
2014.08.09
Questionlink
What is the distributed algorithm to determine the median of arrays of 1 billion integers located on different computers?
Solution
Suppose you have a master node (or are able to use a consensus protocol to elect a master from
...
2014.08.09
First difference: inclusionA process can contain multiple threads. When you open Microsoft Word, you start a process that runs Word. The OS creates a process and begins executing the primary thread of that process.
Second difference: addres
...
2014.08.09
Questionlink
testing the copy command in windows environment
SolutionThe most important point is to come up with different domains of inputs and scenarios.
Copying between:
network share
A really slow network share across the Internet
par
...
2014.08.09
Questionlink
Add two numbers (integers) without using + or plus arithmetic operator.
SolutionBit operations.
We could not do this in 1 pass, because multiple rounding issues.
So we do it in while-loop then! 2 solutions available: iterat
...
2014.08.08
OverviewComposition over inheritance in OOP is a technique by which classes achieve polymorphic behavior and code reuse by containing other classes instead of through inheritance.
BenefitsIt gives the design higher flexibility, giving busi
...
2014.08.08
Questionlink
Decimal to Hexadecimal conversion.
SolutionConvert binary to hex as a group of 4 bits.
Read code.
Codewritten by me
private final char[] hexDigits = { '0', '1', '2', '3', '4', &
...
2014.08.08
Questionlink
There is an integer array consisting positive numbers only.
Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum.
SolutionIt’s a little tricky to write the equation. Always
...
2014.08.08
OverviewProducer-consumer problem illustrates the need for synchronization in systems where many processes share a resource.
In the problem, two processes share a fixed-size buffer. One process produces information and puts it in the buffer
...
2014.08.08
OverviewThread pool is a collection of managed threads usually organized in a queue, which execute the tasks in the task queue.
Thread pool is a group of pre-instantiated, idle threads which stand ready to be given work.
A sample thread po
...
2014.08.08
Question 1link
How would you store 1 million phone numbers?
SolutionBitMap.
The key here is that 1 million phone numbers will be within some range, likely 10 million or so. 10 million bits = 10^7 bits ~ 0.12 GB. Just have a bit arra
...
2014.08.07
Questionlink
一个 distributed 的环境，有很多机器，现在你发现性能有问题，可能是网络带宽造成的，你怎么解决？ (你不能更换网络设备的前提下)
Answer
Identify problem
首先得判定是否真的是网络造成的，就算是网络问题，哪些机器之间的网络问题？ 这个得先大概了解 high level component dependency relationship，
看看是不是 cpu memory disk 都没有问题。 可以 profil
...
2014.08.07
Question
If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?
SolutionExternal Sorting and N-way merge.
Divide the file into K chunks, where X * K = 2 GB Bring each chunk i
...
2014.08.07
Questionlink
You are given the source to an application which is crashing during run time. After running it 10 times in a debugger, you find it never crashes in the same place.
What programming errors could be causing this crash? How wou
...
2014.08.07
Questionlink
Draw a graph as a graph. Assume there is graphics library to draw lines and all. Just tell how will you order the vertices such that the edges don’t intersect and they seem ordered.
SolutionThere’s no clear solution. Someone
...
2014.08.06
OverviewHTTP is an Application Layer protocol which stands for “Hypertext Transfer Protocol”. The entire World Wide Web uses it.
There’re a series of sessions in HTTP where client sends a request and server sends a reply message back to cli
...
2014.08.06
OverviewInternet protocol suite is a networking model and communications protocols used by the Internet. It is commonly known as TCP/IP.
Four abstraction layers:
Application layer
Transport layer
Internet layer
Link layer
The protoc
...
2014.08.06
Questionlink
Write an algorithm to find the ‘next’ post-order successor of a given node in a binary tree and binary search tree.
where each node has a link to its parent.
without parent pointer
Implement 2 versions of the algorithm:
...
2014.08.06
Questionlink
Facebook’s “You and Joe have 230 friends in common” feature. Sure you could use a decent caching strategy, but for now, use MapReduce.
AnalysisThis list doesn’t change frequently so it’d be wasteful to recalculate it every ti
...
2014.08.05
OverviewAmazon Web Services (AWS) is a collection of remote computing services that together make up a cloud computing platform. AWS provides a large computing capacity much faster and cheaper than building a physical server farm.
The most
...
2014.08.05
An OverviewMapReduce is a software framework, or a distributed programming model intended for processing massive amounts of data in large clusters.
Map, a function that parcels out work to different nodes in the distributed cluster.
Reduc
...
2014.08.05
Questionlink
Given a string (for example: “a?bc?def?g”), write a program to generate all the possible strings by replacing ? with 0 and 1.
Input : a?b?c?
Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.
Solution
...
2014.08.05
Upcasting and DowncastingJava permits an object of a subclass type to be treated as an object of any superclass type. This is called upcasting. Upcasting is done automatically, while downcasting must be manually done.
Example:
Cat c1 = new
...
2014.08.05
Questionlink
SolutionBasically, the formula is as follows:
number = (previous_number * constant + other_constant) mod third_constant
The three constants are carefully selected, and a typical choice is:
number = (previous_number
...
2014.08.05
Questionlink
写一个function，对于参数n，输出从0到n之间所有含5的数字。eg. func(30) 应该输出5，15，25
this is Groupon interview question
SolutionSuggested by level 10 of this forum. The key is to consider numbers as string, not numbers. Why? The key of the question
...
2014.08.05
Questionlink
Given an unsorted array of integers, you need to return maximum possible n such that the array consists at least n values greater than or equals to n. Array can contain duplicate values.
Sample input : [1, 2, 3, 4] – output
...
2014.08.04
link
A Hadoop cluster is a special type of computational cluster designed specifically for storing and analyzing huge amounts of unstructured data in a distributed computing environment.
Such clusters run Hadoop’s open source distributed pr
...
2014.08.04
OverviewModel–view–controller (MVC) is a software architectural pattern for implementing user interfaces.
From MIT handouts 3: MVC uses separate programming entities to store the data(model), display the data(view), and modify the data(cont
...
2014.08.04
Questionlink
Traveler wants to travel from city “A” to city “D”. There is a path from city “A” to city “D”. Path consists of steps, i.e. travel from city “A” to city “B”. Path is encoded as sequence of steps.
Sequence is in incorrect ord
...
2014.08.04
link
Traditional RDBMSData is organized in a highly-structured manner, following the relational model.
The need for the data to be well-structured actually becomes a substantial burden at extremely large volumes.
NoSQLA completely different
...
2014.08.04
Questionlink
You are given information about hotels in a country/city. X and Y coordinates of each hotel are known. You need to suggest the list of nearest hotels to a user who is querying from a particular point (X and Y coordinates
...
2014.08.04
Questionlink
Design a web application to represent hierarchy of solar system.
Give details of Persistence layer, business layer, presentation layer and Client-server protocol.
SolutionFirst, OOD part is very well covered in this site. T
...
2014.08.03
Question17.1 Explain what happens, step by step, after you type a URL into a browser Use as much detail as possible.
Short Answer
Browser contacts the DNS server to find the IP address of URL
DNS returns back the IP address of the site
Brow
...
2014.08.03
Questionlink
Give efficient implementation of the following problem.
An item consist of different keys say k1, k2, k3. User can insert any number of items in database, search for item using any (one) key, delete it using any key and iter
...
2014.08.03
First WordA multilayered software architecture is a software architecture that uses many layers for allocating the different responsibilities of a software product.
Layers
Presentation layera. UI layer, view layera. presentation tier in mul
...
2014.08.03
Questionlink
Given a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.
ex:
1 5 9
2 3 8
4 6 7
should print: 6 7 8 9
Solution
Make an array of booleans (or bi
...
2014.08.02
Questionlink
Output top N positive integer in string comparison order. For example, let’s say N=1000, then you need to output in string comparison order as below:
1, 10, 100, 1000, 101, 102, … 109, 11, 110, … 998, 999.
SolutionTh
...
2014.08.02
Questionlink
We have an array of 2n elements like “a1 a2…an b1 b2…bn”. WAP to rearrange the array as “a1 b1 a2 b2…an bn”
time complexity is O(n) no extra array or memory can be taken.
Input : 1 2 3 4 5 6 7 8 9 10 11 12 (even number inp
...
2014.08.01
Questionlink
Can we overriding private method in Java?
Analysis
Overriding private methods in Java is invalid because a parent class’s private methods are “automatically final, and hidden from the derived class”. source
SolutionYou can’t
...
2014.08.01
Questionlink
Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29.
AnalysisNote that this is a difficult
...
2014.08.01
Questionlink
Given an array, generate a random permutation of array elements.
SolutionO(n) time complexity.
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
...
2014.08.01
Questionlink
In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.
Write a program with:
parent pointer provided
paren
...
2014.07.31
Questionlink
You are given a string like “aaaabbbcc”, do an in place conversion which write frequency of each charater(which come continuosly) with that character.
Example:
input: aaabbbcc
output: a3b2c2
SolutionThe most important point
...
2014.07.31
Questionlink
How many points are there on the globe where, by walking one mile south, one mile east, and one mile north, you reach the place where you started?
SolutionOne point in the North Pole, and many circles in the South Pole.
Read
...
2014.07.31
Questionlink
Find Nth fibonacci number in O(logN) time complexity.
Solution
It’s a recursive sequence, where we can get the following equation:
A* [ F(1) F(0) ] = [ F(2) F(1) ]
A* [ F(2) F(1) ] = [ F(3) F(2) ] = A^2 * [ F(1) F(0) ]
A* [ F
...
2014.07.30
Questionlink
Write a program to find the anti-clock-wise peripheral (boundary) of a complete tree.
For a complete tree peripheral (boundary) is defined as
1. First the root
1. Then nodes on left edge
1. Then leaf nodes
1. Then nodes on
...
2014.07.30
Questionlink
A very basic programming puzzle is being asked in programming interviews since last few years. Which of the below two loops will run faster?
/* First */
for(i=0;i<100;i++)
for(j=0;j<10;j++)
//do somthing
/* Secon
...
2014.07.29
Questionlink
Given an array of integers find the maximum and minimum elements by using minimum comparisons.
SolutionCompare in Pairs.
If n is odd then initialize min and max as first element.
If n is even then initialize min and max as m
...
2014.07.29
Questionlink
Given preorder, construct the BST.
SolutionWe can get Inorder traversal by sorting the given Preorder traversal. So we have the required two traversals to construct the Binary Search Tree.
A very similar approach would be a
...
2014.07.29
Questionlink
Given a string, recursively remove adjacent duplicate characters from string. The output string should not have any adjacent duplicates.
Input: azxxzy
Output: ay
First “azxxzy” is reduced to “azzy”. The string “azzy” contain
...
2014.07.29
Game #1link
Two players take turns breaking a chacolate bar (rectangle-shaped consist of squares). The last to break a piece wins the game.
Design the strategy.
SolutionEach time the bar is broken, total number of pieces increase by 1.
...
2014.07.28
Questionlink
There is long list of natural numbers. Remove every 2nd no from list in 1st pass. Remove every 3rd no from list in 2nd pass. Find whether Nth natural no will exist after P passes. N and P are inputs.
Example: N is 15 and p is
...
2014.07.28
Questionlink
You are given a collection of nuts of different size and corresponding bolts. You can choose any nut & any bolt together, from which you can determine whether the nut is larger than bolt, smaller than bolt or matches the b
...
2014.07.28
Questionlink
There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an alg
...
2014.07.27
Questionlink
In how many ways can one tile a 2 X N strip of square cells with 1 X 2 dominos?
SolutionX(n+1) = X(n) + X(n-1)
It’s a Fibonacci Series with X(1) = 1 and X(2) = 2.
...
2014.07.27
Questionlink
A tree has a special property where leaves are represented with ‘2’ and non-leaf with ‘1’. Each node has either 0 or 2 children. If given preorder traversal of this tree, construct the tree.
Example: Given Pre Order string
...
2014.07.27
Questionlink
There’s a elephant, which can carry max 1000 bananas. The elephant eats a banana every 1 Km (both forward and back).
Now we want to transfer 3000 bananas to a place 1000 Km away. How many bananas can be left?
Also solved
...
2014.07.27
Questionlink
A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwar
...
2014.07.27
Questionlink
Given a RNG r(5) which generates number between 1-5 uniformly, make r(7) which generates random number between 1-7.
Solutionint rand7() {
int r = 0;
do {
int a = rand(5) - 1; //uniformly at random
...
2014.07.26
Questionlink
Pay attention on Number 3, 7, 9 and 11.
The Divisibility Rules
Divisible by:
If:
Examples:
2
The last digit is even (0,2,4,6,8)
128
...
2014.07.26
Questionlink
There are 100 people in a room. A person always speaks either lie or truth.
When asked:
1st person says => all are liars
2nd person says => at most 1 speaks truth
3rd person says => at most 2 speak truth
4th person
...
2014.07.26
General Q & Asource
Can a thread acquire more than one lock (Mutex)?Yes, if they need more resource.
Can a mutex be locked more than once?Unless it’s a recursive mutex, no.
A mutex is a lock.
What happens if a non-recursive mutex is loc
...
2014.07.26
Questionlink
Find Top k smallest element in an array.
AnalysisThere’re 2 solutions.
First solution, use a max-heap. O(nlgk) time complexity.
Second solution is called quickselect, a type of selection algorithm that’s based on quicksort.
...
2014.07.25
Mutex vs. SemaphoreMutex is a key to a toilet. One person can have the key - occupy the toilet. When finished, the person gives (frees) the key to the next person in queue.
A mutex is really a semaphore with value 1.
Semaphore is the number
...
2014.07.25
Questionlink
Find 10001st Prime Number
AnalysisUse Sieve of Eratosthenes, or 埃氏筛.
Codeprivate static final int INDEX = 10001;
private static final int LIMIT = 1000000;
private static int get10001stPrime() {
boolean[] sieveArray =
...
2014.07.25
Questionlink
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为 1-255 字节。
假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是 1 千万，但如果除去重复后，不超过 3 百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的 10 个查询串，要求使用的内存不能超过 1G。
Analysis
divide and conquer (for large input)
Quer
...
2014.07.25
TerminologiesAtomicity, Atomic OperationAtomicity is unbreakability, or uninterrupted operation.
Atomic operation helps in understanding reentrancy, critical section, thread safety, synchronization primitives, etc.
Critical SectionCritical
...
2014.07.24
Questionlink
Question One: Given a string, find the first non-repeating character in it
link
Question Two: Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating charact
...
2014.07.24
Questionlink
Convert a BST to a sorted circular doubly-linked list in-place.
Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.
One: InorderThis question can be solved with ino
...
2014.07.24
Questionlink
Predict the output of following program.
public static void main(String[] args) {
int a = 012;
System.out.println("a is " + a);
}
AnalysisPutting a 0 before an integer constant makes it an octal number
...
2014.07.24
Questionlink
The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
AnalysisWe suppose the largest such palindrome will hav
...
2014.07.23
Questionlink
Please get the least number after deleting k digits from the input number.
For example, if the input number is 24635, the least number is 23 after deleting 3 digits.
AnalysisThere’s a solution which instead of ‘delete k’,
...
2014.07.23
Questionlink
Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size).
AnalysisThere should be TWO versions of the solution.
Version A: T
...
2014.07.23
Questionlink
Bucket sort is mainly useful when input is uniformly distributed over a range. For example:
Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range. How do
...
2014.07.22
Questionlink
Given a string, find the longest substring that contains only two unique characters. For example, given “abcbbbbcccbdddadacb”, the longest substring that contains 2 unique character is “bcbbbbcccb”.
SolutionFirst, the most ba
...
2014.07.21
4 Principleslink
Encapsulation
Abstraction
Inheritance
Polymorphism
EncapsulationThe hiding of data implementation by restricting access to accessors and mutators.
AbstractionRepresentation of data in which the implementation details
...
2014.07.21
Questionlink
Quicksort is a divide and conquer algorithm. It first divides a large list into two smaller sub-lists and then recursively sort the two sub-lists. If we want to sort an array without any extra space, Quicksort is a good option
...
2014.07.21
Questionlink
Problem: Get maximum binary Gap.
For example, 9’s binary form is 1001, the gap is 2.
SolutionThis question is a good practise of binary operations.
Codewriten by me
private int solution(int num) {
int max = 0;
int b
...
2014.07.21
Ruby/gem/bundler setup (on a new machine) has always been a hassle to me. Not only that, I’ve had some confusions about developing Octopress blog on 2 different computers.
Now that I’ve had enough failures and success, I would lik
...
2014.07.21
OverviewTwo’s complement is a binary signed number representation.
Negative values are taken by subtracting the number from 2^n. This is the most common method of representing signed integers on computers.
Example
So basically ‘1111 1111’ m
...
2014.07.13
The following questions does not appear in NineChap, but they all worth reading.
Question List
Longest Substring Without Repeating Characters
Minimum Window Substring - very difficult
Scramble String
Recover Binary Search Tree
Media
...
2014.07.07
Question
Requirement: O(1) time
SolutionDo a special handle for input = 0. source
bool IsPowerOfTwo(ulong x) {
return (x & (x - 1)) == 0;
}
...
2014.07.04
Questionlink
Given an array of positive and negative numbers, find if there is a subarray with 0 sum.
eg. 4, 2, -3, 1, 6 -> return true (2, -3, 1)
eg. 4, 2, 0, 1, 6 -> return true (0)
SolutionGeneral case, idea of 前缀和:
iterate t
...
2014.07.04
Questionlink
Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
Eg. input = (1, 4, 20, 3, 10, 5), 33, output (20, 3, 10)
SolutionLike a sliding window. Note that input numbers a
...
2014.07.04
Questionlink
Given an array of integers and a number x, find the smallest subarray with sum greater than the given value.
Eg. input = (1, 4, 45, 6, 0, 19), 51, output (4, 45, 6)
SolutionSolution 1 (the better one) is based on another
...
2014.07.04
Questionlink
Write an algorithm which computes the number of trailing zeros in n factorial.
Example: 11! = 39916800, so the out should be 2
SolutionNote that a trailing zero is produced by 2 * 5.
This question basically is couting
...
2014.07.02
OverviewHashTable
HashTable is thread safe synchronized. Only 1 thread can access at a time (compromise speed).
HashTable does not allow null for key and value.
HashMap & HashSet
HashMap is not sync, but better performance.
HashMap a
...
2014.07.01
QuestionImplement a HashMap
Hint:
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capa
...
2014.07.01
Questionlink
Implement a queue by two stacks. Support O (1) push, pop, top.
SolutionQ.Push(x): S1-Push(x)
Q.Pop(): if S2.empty -> S1->S2 S2.pop()
Q.Top(): Similar with Q.Pop()
Learn and compare with another question [Question] Imple
...
2014.07.01
Questionlink
Given that integers are read from a data stream. Find median of elements read so for in efficient way.
For simplicity assume there are no duplicates. For example, let us consider the stream 5, 15, 1, 3 … The stream of outpu
...
2014.07.01
Questionlink
Implement a stack, enable O(1) Push, Pop Top, Min. Where Min() will return the value of minimum number in the stack.
SolutionUsing two stacks.
The first one is the regular stack.
The second one only store minimum numbers.
Eg:
...
2014.07.01
Questionlink
Given n buildings, each building is an rectangle located onx-axis, and indicated by (x1, x2, height). Calculate theoutline of all buildings. Output them in order.
SolutionSweeping Line Algorithm.
Sweep from left to right, alw
...
2014.07.01
Questionlink
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
For example, f
...
2014.06.30
Questionlink
You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. Write a new function that returns 0 and 1 with 50% probability each. Your funct
...
2014.06.30
Questionlink
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value.
In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights. Also gi
...
2014.06.30
Resume
Do not write anything unrelated to CS.
Do not write too long - 1 or 2 pages are fine. Senior engineer 3 pages.
Do not write low GPA
Never ever write “proficient in anything”
Big DataMost classic question is “Frequent items” (refer
...
2014.06.30
Questionlink
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. Find it.
Note: There is only one majority number in the array
Example: For [1, 2, 1, 2, 1, 3, 3] return
...
2014.06.28
Questionlink
Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array. Find it.
Note: There is only one majority number in the array
Example: For [3,1,2,3,2,3,
...
2014.06.28
Questionlink
How to find the majority elelment in an array in O(n)?
Note: The majority element is the element that occurs more than half of the size of the array
Example: For [1, 1, 1, 1, 2, 2, 2], return 1
AnalysisThis question is ca
...
2014.06.28
Questionlink
Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum.
Note The subarray should contain at least one number
Exam
...
2014.06.28
Questionlink
Given an array of integers, find the subarray with smallest sum. Return the sum of the subarray.
Note The subarray should contain at least one integer.
Example For [1, -1, -2, 1], return -3
AnalysisSame as “Max subarray”.
...
2014.06.28
Data StructureData structure is a way to manage data. It provides some methods to handle data stream. For example, DB is a DS.
Stack and Queue
Min-stack
Implement a queue by two stacks
Largest Rectangle in histogram
HashHash function
MD
...
2014.06.28
Questionlink
Given an array “nums” of integers and an int “k”, Partition the array (i.e move the elements in “nums”) such that,
All elements < k are moved to the left
All elements >= k are moved to the right
Return the par
...
2014.06.28
Questionlink
You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.
SolutionSolution 1: User count array. O(
...
2014.06.28
Number & Bit questions
Single Number
Single Number II
Single Number III
Single Number IV
Majority Number
Majority Number II
Majority Number III
Subarray questionsAlways using the idea of 前缀和.
Best Time to Buy and Sell Stock - 贪心法
Best
...
2014.06.28
Questionlink
In an array, all numbers in the array repeat twice except two numbers, which repeat only once.
Assume all the numbers are placed randomly. Find the 2 numbers.
AnalysisThe main idea of the solution is how to remove repeate
...
2014.06.28
Questionlink
Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
A topological ordering is possible if and only i
...
2014.06.27
Questionlink
Given a list of integers, which denote a permutation.
Find the previous permutation in ascending order.
Note
The list may contains duplicate integers.
Example
For [1,3,2,3], the pre
...
2014.06.27
GraphFor graph, there are only 2 high-frequency questions, which is ‘clone graph’ and ‘topology sorting’.
Question list
Clone Graph - difficult
Topology Sorting
SearchSearch have either DFS or BFS.
First, we will cover permutations and c
...
2014.06.26
Question Listlink
link2
Liar truth-teller (skip)
Toggler brain teaser
Alien abduction
Blue forehead room
Forehead numbers
Light bulb switching
Path counting (skip)
3D path counting
Toggler brain teaser“你前面站了 5 个人，他们中间只有一个人讲真话……”
这个问题比上个问题
...
2014.06.26
Questionlink
Given two strings, find the longest comment subsequence (LCS).
Your code should return the length of LCS.
Example
For "ABCD" and "EDCA", the LCS is "A" (or D or C), return 1
For "ABCD" and
...
2014.06.24
Questionlink
Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.
Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
...
2014.06.24
Dynamic ProgrammingThe fundamental of DP is ‘merorized search’. It’s easy to implement but bad for memory. And it’s generally useless in the industry.
When to use DP?
Input cannot sort
Find minimum/maximum result
Check the feasibility
...
2014.06.24
Cache AlgorithmsThis post is originally written for Cache Algo only, before I found out this 2 topics are very similar, so I changed the title to “Cache and Page Replacement Algorithms”.
Equationof memory reference time is:
T = m * T(m
...
2014.06.23
Question list
Union and Intersection of two Linked Lists
Insertion Sort List - difficult
Flatten Binary Tree to Linked List
Convert Sorted List to Binary Search Tree
Rotate List
Remove Nth Node From End of List
LRU Cache
Reverse Nod
...
2014.06.18
Questionlink
定义一个数字有以下的特征, 它可以被分成几个部分,而前面的部分相加起来的和是后面的部分.举例来说
1235813, 1+2=3; 2+3=5;3+5=8; 5+8=13;
112112224, 112+112=224;
1981100, 19+81=100;
122436, 12+24=36;
1299111210, 12+9
...
2014.06.18
Questionlink
You are given 2 eggs.
You have access to a 100-storey building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identica
...
2014.06.18
Questionlink
Implement the reversal of a singly linked list iteratively and recursively.
IterativelyFirst, the iterative solution is very common, and is listed as one of the “5 fundamental operations of linked list” in the NineChap4 post
...
2014.06.17
Master theoremIn the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations that occur in many divide and conquer algorithms. It was introduced and popular
...
2014.06.17
Questionlink
Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter.
Example:
Input: “10->15->4->
...
2014.06.17
Questionlink1, link2.
Variant 1: Given a Binary Search Tree, serialize and deserialize it.
Variant 2: Given a Binary Tree, serialize and deserialize it.
Variant 1 - Binary search treeWe must only use pre-order.
Think about why, or read
...
2014.06.16
First WordLinkedList aims to test one of the most important concepts in C++, pointers.
Unlike array, linked list does not have ‘in-place’ operations. This is very important to understand.
Type 1: Dummy NodeWhen the head is not determined, u
...
2014.06.16
Global variable?There is no such thing as a ‘global variable’ in Java.
In computer programming, a global variable is a variable that is accessible in every scope (the global environment). Some languages, like Java, don’t have global variab
...
2014.06.15
These are some additional questions that are not covered in previous NineChap posts. Some questions are non-standard and difficult to solve, and some are not found in OJ websites. But these are real questions that has been asked during inte
...
2014.06.15
Question
Given a BST, find the node that is larger/smaller than particular number
Or the question can be:
Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k. link
Ana
...
2014.06.15
Question
Implement a iterator for a binary search tree
Related question: Binary Tree Inorder Traversal
AnalysisFirst of all, what is an iterator in Java?
Java has a commonly used Iterator interface.
It is usually used like this:
Iterator
...
2014.06.14
Questionlink
Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]
Related
...
2014.06.14
4 Types of Access LevelPrivateLike you’d think, only the class in which it is declared can see it.
Package Private (default)Can only be seen and used by the package in which it was declared.
This is the default in Java (which some see as a
...
2014.06.14
Questionlink
Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree.
Inp
...
2014.06.13
QuicksortQuicksort is faster because it’s in-place sort (with O(log n) stack space).
Typical in-place sort is not stable.
MergesortMergesort uses O(n) space, thus slower.
It is stable sort.
Stability 稳定排序When sorting, if only part of the da
...
2014.06.12
First WordPermutation questions provide you with a list of items, and you build, validate and return a combination of these items. The standard solution is to sort the input first, and add items 1 by 1.
Do not try to solve the problems with
...
2014.06.12
First WordFor BST it’s very important to do insert and delete (balancing not required).
Insertion is easy, but deletion is very difficult. However, it’s a good idea to at least know the principles.
Insert a nodeSteps:
check whether new valu
...
2014.06.11
strStr QuestionImplement strStr
Before solving the problem, it’s very important to ask this questions:
Can we use system library (eg. str.substring() or indexOf())
The answer is ‘No’, but asking this question shows that you think deep int
...
2014.06.11
Questionlink
Problem: Implement a function to find the first character in a string which only appears once.For example: It returns ‘b’ when the input is “abaccdeff”.
AnalysisGreat solution from Ryan:
You can’t know that the character is
...
2014.06.10
Questionlink
Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.
Note:
This is Part II of Lowest Common
...
2014.06.10
Questionlink
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
_______3______
/ \
___5__ ___1__
/ \ / \
...
2014.06.10
Questionlink
Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.
_______6______
/ \
___2__ ___8__
/ \
...
2014.06.10
Template (BFS)BFS can be implemented using either 2 queues (replacing) or 1 queue. Of course 1 queue is better.
link
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList result = new ArrayList();
...
2014.06.10
Question listBST
Validate Binary Search Tree
Insert a Node in Binary Search Tree
Delete a Node in Binary Search Tree
Search Range in a Binary Search Tree
Additional
Recover Binary Search Tree - used global variable
Convert Sorted Ar
...
2014.06.10
Questionlink
Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]
Related
...
2014.06.10
DFSRecursion or While-Loop?We can use recursion, because unless it’s pre-order traverse, binary tree questions can be difficult.
Solving the problem is more important.
Divide & Conquer Algorithm
Merge Sort
Quick Sort
Most of Binary tree
...
2014.06.10
Sorted ArrayTemplateThere is no template.
Question list
Remove Duplicates from Sorted Array
Remove Duplicates from Sorted Array II
Merge Sorted Array
Median of Two Sorted Arrays
Recover Rotated Sorted Array
Additional
Reverse Words in
...
2014.06.09
Binary SearchRecursion or While-Loop?In general, it’s never a good idea to do binary search with recursion, because that’ll make the interview too boring.
Templatelink
This template is able to locate the first (or last) occurance of an elem
...
2014.06.08
Questionlink
<p class="font-color">
Given a <strong>rotated</strong> sorted array, recover it to sorted array in-place.
</p>
<div class="m-t-lg m-b-lg bg-color bg-img font-color">
...
2014.06.08
First WordThere are generally four levels of tests: unit testing, integration testing, system testing, and acceptance testing.
Software testing methods are traditionally divided into white-box and black-box testing.
One of the testing metho
...
2014.06.05
First WordASCII, UTF-? are encoding schemes. Unicode is character set.
Or in other words, UTF-8 is an encoding used to translate binary data into numbers. Unicode is a character set used to translate numbers into characters.
ASCIIASCII is a
...
2014.06.04
First WordJunit is open source testing framework developed for unit testing java code. It is now the default framework for testing Java development.
Is it popular?A very interesting survey shows that JUnit is THE MOST POPULAR LIBRARY FOR JA
...
2014.06.04
First WordThis post talks about how to implement DFS without recursion.
We have studied 2 kinds of DFS in the post DFS, BFS and space efficiency. We will skip “true DFS” here, and only talk about “pseudo-DFS” implementation.
Remember, space
...
2014.06.03
DifferenceBig-endian systems store the most significant byte of a word in the smallest address and the least significant byte is stored in the largest address.
Little-endian systems, in contrast, store the least significant byte in the smal
...
2014.06.03
Questionlink
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -&g
...
2014.06.03
Questionlink
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exist
...
2014.06.03
Questionlink
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial,
...
2014.06.03
Questionlink
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Stats
Adjusted Difficulty
5
Time to use
--------
Ratings/Color = 1(white)
...
2014.06.03
Questionlink
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1
...
2014.06.03
Questionlink
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a wor
...
2014.06.03
Questionlink
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial,
...
2014.06.02
Questionlink
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Stats
Adjusted Difficulty
4
...
2014.06.02
Questionlink
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
Stats
Adjusted Difficulty
5
Time t
...
2014.06.02
Questionlink
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
Stats
Adjusted Difficulty
4
Time to use
--------
Ratings/Color
...
2014.06.02
Questionlink
Sort a linked list in O(n log n) time using constant space complexity.
Stats
Adjusted Difficulty
4
Time to use
--------
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(re
...
2014.06.02
Questionlink
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Re
...
2014.06.02
Questionlink
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
d
...
2014.06.02
Questionlink
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memor
...
2014.06.01
Questionlink
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
...
2014.06.01
Questionlink
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Child
...
2014.05.31
Questionlink
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next statio
...
2014.05.31
Questionlink
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separ
...
2014.05.30
Questionlink
Sort a linked list using insertion sort.
Stats
Adjusted Difficulty
3
Time to use
--------
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
AnalysisThis question is a
...
2014.05.30
Questionlink
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dic
...
2014.05.30
Questionlink
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the pal
...
2014.05.30
Questionlink
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its
...
2014.05.29
Questionlink
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a
...
2014.05.29
First WordThis post talks about BFS, DFS and space efficiency.
AnalysisFor BFS it’s easy to understand. It is implemented with a queue. Space usage is O(width)
For DFS, there are 2 types: true DFS and pseudo-DFS. True DFS space usage is O(d
...
2014.05.29
Questionlink
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
A
...
2014.05.29
Questionlink
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all ro
...
2014.05.29
Questionlink
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in
...
2014.05.29
Questionlink
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one s
...
2014.05.28
Questionlink
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multi
...
2014.05.28
Questionlink
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algor
...
2014.05.28
Questionlink
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
Stats
...
2014.05.28
Questionlink
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
...
2014.05.28
Questionlink
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
...
2014.05.28
Questionlink
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Stats
Frequency
3
Difficulty
3
Adjusted D
...
2014.05.27
Questionlink
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the cha
...
2014.05.27
Questionlink
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Stats
Frequency
3
Difficulty
3
Adjusted Di
...
2014.05.27
Questionlink
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:Given the below binary tree and sum = 22,
5
/ \
4 8
...
2014.05.27
Questionlink
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Stats
Frequency
1
Di
...
2014.05.27
Questionlink
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:Given the below binary tree and sum = 22,
...
2014.05.27
Questionlink
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
Stats
Frequency
...
2014.05.27
Questionlink
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For exa
...
2014.05.27
Questionlink
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next
...
2014.05.27
Questionlink
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3
...
2014.05.27
Questionlink
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than
...
2014.05.26
Questionlink
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Stats
Frequency
3
Difficulty
2
Adjusted Difficulty
2
Time to use
--------
...
2014.05.26
Questionlink
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Stats
Frequency
3
Difficulty
4
Adjusted Difficulty
4
Time to use
...
2014.05.26
Questionlink
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / /
...
2014.05.26
Questionlink
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2
...
2014.05.26
Questionlink
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
...
2014.05.26
Questionlink
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtre
...
2014.05.26
Questionlink
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
...
2014.05.25
Questionlink
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,2
...
2014.05.25
Questionlink
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Stats
Frequency
1
Difficulty
...
2014.05.25
Questionlink
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Stats
Frequency
1
Difficulty
...
2014.05.25
Questionlink
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:A solution using O(n) space is pretty straight forward. Could you devise a constant space
...
2014.05.25
Questionlink
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Stats
Freq
...
2014.05.25
Questionlink
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
1
...
2014.05.25
Questionlink
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, c
...
2014.05.24
Questionlink
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
...
2014.05.24
Questionlink
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Stats
Frequency
1
Difficulty
5
Adjusted Difficulty
5
T
...
2014.05.24
Questionlink
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
...
2014.05.24
Questionlink
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number o
...
2014.05.23
Questionlink
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gra
...
2014.05.23
Questionlink
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of
...
2014.05.23
Questionlink
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partit
...
2014.05.23
Questionlink
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m,
...
2014.05.23
Questionlink
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, g
...
2014.05.23
Questionlink
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \
...
2014.05.23
Questionlink
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
</
...
2014.05.22
Questionlink
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
...
2014.05.22
Questionlink
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
St
...
2014.05.22
Questionlink
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Giv
...
2014.05.22
Questionlink
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
F
...
2014.05.22
Questionlink
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
...
2014.05.22
Questionlink
Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3],
...
2014.05.22
Questionlink
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
Stats
Frequency
4
Difficulty
2
Adjusted Difficulty
2
Time
...
2014.05.21
Questionlink
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Stats
Frequency
5
Diff
...
2014.05.21
Questionlink
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert
...
2014.05.21
Questionlink
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater t
...
2014.05.21
Questionlink
Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.
Stats
Frequency
2
...
2014.05.21
Questionlink
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If th
...
2014.05.21
Questionlink
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple
...
2014.05.21
Questionlink
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Corner Cases:
Did you consider the case where path = "/../"?
In th
...
2014.05.21
Questionlink
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 t
...
2014.05.21
Questionlink
Implement int sqrt(int x).
Compute and return the square root of x.
Stats
Frequency
4
Difficulty
4
Adjusted Difficulty
4
Time to use
----------
Ratings/Color
...
2014.05.21
Questionlink
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring.
...
2014.05.21
Questionlink
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest s
...
2014.05.20
Questionlink
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in ti
...
2014.05.20
Questionlink
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
...
2014.05.20
Questionlink
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right cor
...
2014.05.20
Questionlink
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Give
...
2014.05.19
Questionlink
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
Stats
Fr
...
2014.05.19
Questionlink
Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. Y
...
2014.05.18
Questionlink
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as m
...
2014.05.18
Questionlink
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 i
...
2014.05.18
Questionlink
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
Stats
Frequency
5
Difficulty
4
Adjust
...
2014.05.17
Questionlink
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able
...
2014.05.16
Questionlink
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution con
...
2014.05.16
Questionlink
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a charac
...
2014.05.16
Questionlink
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Stats
Frequency
3
Difficulty
4
Adjusted Difficulty
2
...
2014.05.16
Questionlink
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
Stat
...
2014.05.16
Questionlink
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return
...
2014.05.16
Questionlink
Implement pow(x, n).
Stats
Frequency
5
Difficulty
3
Adjusted Difficulty
3
Time to use
----------
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Sol
...
2014.05.15
Questionlink
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire inpu
...
2014.05.15
Questionlink
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
Stats
Frequency
4
Difficulty
3
Adjusted Difficulty
4
Time
...
2014.05.15
Questionlink
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
...
2014.05.14
Questionlink
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
Stats
Frequency
3
Difficulty
4
Adjusted Diffic
...
2014.05.14
Questionlink
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index
...
2014.05.14
Questionlink
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
Sta
...
2014.05.14
Questionlink
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
Stats
Frequency
...
2014.05.14
Questionlink
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
Stats
Frequency
2
Difficulty
4
Adjusted Dif
...
2014.05.14
Questionlink
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution n
...
2014.05.14
Questionlink
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
...
2014.05.14
Questionlink
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
Al
...
2014.05.13
Questionlink
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
...
2014.05.13
Questionlink
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
G
...
2014.05.13
Questionlink
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length =
...
2014.05.12
Questionlink
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, so
...
2014.05.12
Questionlink
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few
...
2014.05.12
Questionlink
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, retu
...
2014.05.12
Questionlink
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwi
...
2014.05.12
Questionlink
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is vali
...
2014.05.12
Questionlink
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Stats
Frequency
4
Difficulty
3
Adjusted Difficulty
5
Time to use
----------
R
...
2014.05.11
Questionlink
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the
...
2014.05.11
DefinitionA heap is a specialized tree-based data structure that satisfies the heap property:
If A is a parent node of B, then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap.
...
2014.05.11
Questionlink
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
Stats
Frequency
5
Diffficulty
4
Adjusted Difficulty
4
Time to us
...
2014.05.10
Bit operators
operator
what is means
~
invert every bit
<<
shift left (same as *2)
>>
signed shift right
>>>
unsigned shift right
^
XOR
...
2014.05.10
The HashMap
link
A hash table is made up of two parts: an array (the actual table where the data to be searched is stored) and a mapping function, known as a hash function.
The hash function is a mapping from the input space to the in
...
2014.05.10
Questionlink
Divide two integers without using multiplication, division and mod operator.
Stats
Frequency
3
Diffficulty
4
Adjusted Difficulty
4
Time to use
----------
Ratings/Color &#x
...
2014.05.10
Questionlink
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening
...
2014.05.10
Questionlink
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
Stats
...
2014.05.09
Questionlink
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Stats
Frequency
5
Diffficulty
2
Adjusted
...
2014.05.09
Questionlink
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memo
...
2014.05.09
Questionlink
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Stats
Frequ
...
2014.05.09
Questionlink
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant spac
...
2014.05.09
Questionlink
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all va
...
2014.05.09
Questionlink
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
Elements in a quadruplet (a,b
...
2014.05.03
Questionlink
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
...
2014.05.02
Questionlink
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-desce
...
2014.05.02
Questionlink
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output:
...
2014.05.02
Questionlink
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the li
...
2014.05.02
Questionlink
Write a function to find the longest common prefix string amongst an array of strings.
Stats
Frequency
1
Diffficulty
2
Adjusted Difficulty
1
Time to use
----------
Ratings/
...
2014.05.01
Questionlink
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
Stats
Frequency
4
Diffficulty
3
Adjusted Difficulty
3
Time to use
----------
Rati
...
2014.04.30
Questionlink
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Stats
Frequency
4
Diffficulty
2
Adjusted Difficulty
2
Time to use
-------
...
2014.04.30
Questionlink
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which t
...
2014.04.29
Questionlink
Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using
...
2014.04.29
Questionlink
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The f
...
2014.04.29
Questionlink
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then re
...
2014.04.29
Questionlink
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes:
I
...
2014.04.29
Questionlink
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Stats
Frequency
2
Diffficulty
4
...
2014.04.28
Questionlink
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought
...
2014.04.28
Questionlink
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
...
2014.04.27
Questionlink
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substr
...
2014.04.27
Questionlink
<p>There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
</p>
<p></p>
Stats
...
2014.04.26
Questionlink
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be les
...
2014.04.26
LeetCode Statisticslink
ID
Question
Diff
Freq
Data Structure
Algorithms
1
Two Sum
2
5
array
sort
set
Two Pointers
2
...
2014.04.25
Questionlink
Given a string of numbers, eg. “43868643”. Put ‘+’ and ‘-‘ in between, and build an expression.
SolutionIterate thru the input string and do DFS recrusively.
At each position, there’s 3 possibilities: plus, minus or do not sk
...
2013.11.21
Questionlink
两个人（A，B）参与一个游戏，规则如下：
1）一个随机的整数数列有偶数个数,a1,a2,…a2n
2）A 先从数列取数，但只能从两头取,a1 or a2n
3)然后Ｂ取数，也是只能从剩下的两头取，依此类推，两个人轮流，都只能从两头取
Output the max sum of numbers that player 1 is going to get.
SolutionThis question can be solved with DP b
...
2013.11.21
Questionlink, link.
example: A * B + C becomes A B * C +
A * (B + C) becomes A B C + *
SolutionOne of the main purpose of converting infix to postfix is to remove alll parentheses from the expression.
This is a very difficult question.
...
2013.11.20
Question
Given an unsorted array of length N, a slice is defined as a pair of numbers (P, Q) so that:
0 <= P < Q <= N
A[P], A[P+1]….A[Q] is arithmetic sequence
Example:
input = { -1, 1, 3, 3, 3, 2, 1, 0
...
2013.11.15
Questionlink
Given an array with four integers A, B, C, D, shuffle them in some order (there are 24 shuffles).
… Get the best shuffle such that
F(S) = abs(s[0]-s[1]) + abs(s[1]-s[2])+ abs(s[2]-s[3])is maximum
For example
A=5,
...
2013.11.15
Questionlink
At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be accommodated as per their schedule.
Example: Time table is like below:
Bus
...
2013.11.05