How I Coded For 159 Days Straight and Got a Job



How I Coded For 159 Days Straight and Got a Job

Sorry for the click bait, I just couldn't help myself. Mike and I actually spent some time debating what would be better, 'How I Coded For 159 Days Straight and Got A Job', 'How I got Rejected From 40 Companies and Still Got A Job', etc. The possibilities were endless.

Here's the good stuff though:

159 day streak on GitHub (starting from App Academy)

139 job application sent out

94 companies that ignored me

40 rejections

11 phone screens

9 final interviews

5 offers

1 job


Read full article from How I Coded For 159 Days Straight and Got a Job


一个简单的任务执行引擎设计 - JavaNerd - 博客园



一个简单的任务执行引擎设计 - JavaNerd - 博客园

最近做的一个项目是一个数据库服务化的管控平台,用时髦一点的名词来说是一个DBaaS产品。这种面向云化的产品,呈现给最终用户的体验是提供一个管理页面,把数据库的生命周期,监控等功能通过WEB页面或者Open API暴露给用户或者第三方的程序,常见的产品类似于阿里云或者AWS的RDS。而我们的做的产品实际上是一个分布式的数据库服务平台,除了底层的存储,还有上层的proxy去完成分库分表,读写分离等操作。

对于终端用户来说,使用的是一个数据库连接,但实际上在后面,会有很多系统一同工作。例如当用户创建一个RDS的时候,会去创建底层的数据库实例(MySQL,SQL Server等),Loader Blance,Proxy等,而这些组件其实也是由其他系统通过Open API或者RPC的方式暴露给上层应用。作为Paas或者DBaaS的最上层的产品,免不了会调用其他的系统接口去申请资源。那么在代码实现上会碰到一个问题,当依赖多个系统的时候,依次调用各个系统的的过程中,如果中途出错,错误处理比较难。


Read full article from 一个简单的任务执行引擎设计 - JavaNerd - 博客园


LeetCode 514. Freedom Trail | 行走的轮子



LeetCode 514. Freedom Trail | 行走的轮子

In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring", and use the dial to spell a specific keyword in order to open the door.

Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at 12:00 direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at 12:00 direction and then by pressing the center button.
At the stage of rotating the ring to spell the key character key[i]:
You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. The final purpose of the rotation is to align one of the string ring's characters at the 12:00 direction, where this character must equal to the character key[i].
If the character key[i] has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you've finished all the spelling.


Read full article from LeetCode 514. Freedom Trail | 行走的轮子


Unsafe类初探 | 行走的轮子



Unsafe类初探 | 行走的轮子

从这个类的名字Unsafe上来说这个类就是一个不安全的类,也是不开放给用户直接使用的(当然我们还是可以通过其他一些方法用到)。
这个类在jdk源码中多个类中用到,主要作用是任意内存地址位置处读写数据,外加一下CAS操作。它的大部分操作都是绕过JVM通过JNI完成的,因此它所分配的内存需要手动free,所以是非常危险的。但是Unsafe中很多(但不是所有)方法都很有用,且有些情况下,除了使用JNI,没有其他方法弄够完成同样的事情。
至于研究它的起因,是因为我最近在看jdk8的ConcurrentHashMap,这个版本的主要函数就是用过Unsafe来完成的。

Unsafe类的调用

Unsafe类是一个单例,调用的方法为getUnsafe,如下。可以看到,虽然是可以调用,但是会有一步判断,判断是不是内部会检查该CallerClass是不是由系统类加载器BootstrapClassLoader加载。由系统类加载器加载的类调用getClassLoader()会返回null,所以要检查类是否为bootstrap加载器加载只需要检查该方法是不是返回null。


Read full article from Unsafe类初探 | 行走的轮子


MySQL-InnoDB索引与算法 | 天遥的码农日常



MySQL-InnoDB索引与算法 | 天遥的码农日常

B+树的常识

首先我们来介绍一下B+树。B+树是一种平衡树,而与普通的树不同的是:

  1. B+树的叶子节点包含所有数据,并且叶子节点有序的用双向循环链表进行连接,因此可以实现从根节点读,也可以从叶子节点遍历。
  2. B+树的每个非叶子节点有n棵子树则有n个关键字(不同于B树的靠关键字之间的缝隙来定义指针,而直接由关键字定义指针)
  3. 所有非终端节点可以看成是索引部分,节点中仅含有其子树根节点最大(或最小)关键字
    那么B+树的优势也就可以看出来了:
  4. B+树中非叶子节点并不包含指向竿见自具体信息的指针,因此内部节点比B树更小,因此一次性读入内存更多的关键字,IO的读写次数也就降低了。
  5. 查询效率稳定,因为对于每一次查询,都需要从根节点走到叶子节点才能拿到具体指向文件的信息,所以关键字查询的路径长度相同。
  6. B+树方便扫库,从叶子节点扫一遍就行,不用采用中序遍历之类的
  7. B+树支持range-query非常方便,这是主要原因。(举个例子:要查5-10之间数据,第一次查5.再一次查10,然后串起来遍历就行,而B树就很麻烦了)
    B+树的劣势在于树的高度会比B树高一些,对于频率查询B树也更好,因为可以将频率高的节点上升。


Read full article from MySQL-InnoDB索引与算法 | 天遥的码农日常


[LeetCode] 501. Find Mode in Binary Search Tree 解题报告 - 萌萌小七的专栏 - CSDN博客



[LeetCode] 501. Find Mode in Binary Search Tree 解题报告 - 萌萌小七的专栏 - CSDN博客

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

   1     \      2     /    2 

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).


这个题咋看之下还是有点难度,题意是要我们需找树种出现最多的节点,一开始还真是没有头绪。

经过仔细分析以后,我们会发现,对于本题中的二叉搜索树,节点的排列是有顺序的,左节点<=当前节点<=右节点。也就是说,假设这样一种情况(可能不严谨,但是足够说明问题):存在大于等于3个的连续相同的节点,且当前节点存在左右子树,那么相同的三个节点一定是:当前节点、左子树中最大的节点和右子树中最小的节点。

这里我们容易想到的是中序遍历(对于整个树,先遍历左节点,再遍历中间节点,最后遍历右节点),使用中序遍历遍历二叉搜索树,可以获得一个从小到大的排好序的升序序列。

分析到这里,题目就转化成了,给定一个升序序列,寻找重复次数最多的数字,这就非常简单了。


代码如下,需要注意的是第20行,是处理遍历完整棵树以后,可能最后一段是相同的且最长的,这样一种情况的。


Read full article from [LeetCode] 501. Find Mode in Binary Search Tree 解题报告 - 萌萌小七的专栏 - CSDN博客


Longest Bitonic subarray in an array



Longest Bitonic subarray in an array

Array is said to be bitonic if the elements in the array are first increasing and then decreasing. A sequence sorted in increasing order considerd bitonic with decreasing part as empty. Smilarly,  a sequence sorted in deccreasing order considerd bitonic with increasing part as empty.

Example 1

INPUT:
arr[] = {4, 7, 9, 20, 13}

OUTPUT:
5
The above array is bitonic as the elements are first increasing till 20 and then decreasing

Example 2

INPUT:
arr[] = {18, 8, 10, 15, 14, 13}

OUTPUT:
5
The longest bitonic subarray is of length 5 and the bitonic subarray is {8, 10, 15, 14, 13}

Time Complexity: O(n)
In this method the main idea is to maintain two arrays I[] and D[]
a. I[i] stores the length of the longest increasing subarray from left to right ending at arr[i]
b. D[i] stores the length of the longest decreasing subarray from right to left starting at arr[i]
c. maximum length of the bitonic subarray is maximum of (I[i]+D[i]-1).


Read full article from Longest Bitonic subarray in an array


Find Influencer



Find Influencer

public interface InfluencerFinder {

/ Given a matrix of following between N LinkedIn users (with ids from 0 to N-1): followingMatrix[i][j] == true iff user i is following user j thus followingMatrix[i][j] doesn't imply followingMatrix[j][i]. Let's also agree that followingMatrix[i][i] == false Influencer is a user who is: - followed by everyone else and - not following anyone himself This method should find an Influencer by a given matrix of following, or return -1 if there is no Influencer in this group. / int getInfluencer(boolean[][] followingMatrix)

Analysis

The most naive method is using two loops to check if the user is an influencer. Time complexity of this method is O(n^2)

However, it is easy to prove that there is only one influencer. So we can start from the first user, all the user followed by him is impossible to be an influencer. In the mean time, if any one follows him, he is impossible to be an influencer. So think like we are traverse on the matrix. Time complexity of this method is O(n)

Another interesting way to think of this question is that, since all column are independent to each other. We can parallelly sum the column up. All the columns that sum up to N - 1 can be one possible influncer. Why we should check by column instead of row? Because few users will be followed by everyone else. However, lots of people may not follow anyone. Then we only need to check if they actually do not follow anyone. There are a coulple of ways to parallel it.

  1. Divide the columes and spawn threads to compute them.
  2. Use some thing list ISPC tasks to parallel them, we can make use of SIMD as well.
  3. Use MapReduce to parallel.


Read full article from Find Influencer


Find subsets whose sum=target



Find subsets whose sum=target

Problem: Given a set of numbers (in an integer array), the partition problem is to find a subset of the numbers that add up to a specific target number. For example, there are two ways to partition the set {1, 3, 4, 5} so that the remaining elements add up to 5.

{1, 4}

{5}

By contrast, there is no way to partition the set {1, 3, 4, 5} to get 11. Write a function NumberOfPartitions which takes an array of integers, and a target number, and returns the number of partitions of that set of integers which add up to the target.

int numPartitions(int[] array, int target);

Example: arr = {1, 3, 4, 5}, numPartitions(arr, 5) => 2, numPartitions(arr, 11) => 0

Problem

  1. Can we have duplicate key in the array?


Read full article from Find subsets whose sum=target


Simplify Transactions



Simplify Transactions

Given n people who owe various amounts of money to each other, simplify the transactions they make between themselves such that there are no more than n transactions and everyone is fairly paid.

Example:

There are four people: sam, jim, bob, sarah

Format is of the form [(from, to, amount)]

Input:

  [("sam","jim",200),("sam","bob",110),("jim","bob",50),("jim","sarah",20),("bob","sarah",30),("sarah","sam",120)]  

This means sam owes jim 200, sam owes bob 110, jim owes bob 50, jim owes sarah 20, bob owes sarah 30, and sarah owes sam 120.

Sample Output:

  [("sarah","sam",70),("sam","jim",260),("jim","bob",130)]  

This means sarah pays sam 70, sam pays jim 260, and jim pays bob 130.

To see why this is correct consider jim. Originally he was going getting 200 and paying 50+20. So overall he was getting 200 - (50 + 20) = 130.

With the simplified transactions he is getting 260 and paying 130. So overall he is getting 260 - 130 = 130.

This same check can be applied to each person to see that this simplification is fair.


Read full article from Simplify Transactions


Continuous Subarray Sum to Target Value



Continuous Subarray Sum to Target Value

Given an array of integers, find a continuous subarray which sums to a given number, d return the index pair.

Example: {3, 1, 5, 6, 2, 5, 3}, target sum is 12, should return {1, 3}, which means 1+5+6=12

Analysis

If the array only contains non-negative numbers, it can be solved using sliding window. However, if it can contain negative values, then sliding window can fail.

The most naive method is to start from each element and add till the end to check if there is a continous subarray starting from this element that can sum to the given value. The time complexity is O(N^2).

However, it is possible to improve this by using a map. The idea is to store the sum from index 0 to i as the key. We can denote it as sum[i]. In this way, when given a new number, we only need to check if sum[j] - target exists in the map. If it exist in the map, it means that num[i+1] to num[j] sums up to target.


Read full article from Continuous Subarray Sum to Target Value


leetcode 341 Flatten Nested List Iterator 以及其他Iterator合集--next,stack,括号,iterator,listadd



leetcode 341 Flatten Nested List Iterator 以及其他Iterator合集--next,stack,括号,iterator,listadd

Iterator其实就是一个单链表,无法回头看。java里很多数据结构都有这个接口,使用时需要initalize,得到一个iterator. 调用next()返回的是一个object, 指向的是下一个未访问过的部分。 hasnext()返回的是boolean, 表示是否走到了结尾。


Read full article from leetcode 341 Flatten Nested List Iterator 以及其他Iterator合集--next,stack,括号,iterator,listadd


Linkedin Technical Interview – 77 Questions | Yaozong's Blog



Linkedin Technical Interview – 77 Questions | Yaozong's Blog

1. Iterating through a k-dimensional array given size of each dimension in an array.
2. Binary Tree Upside down (Leetcode 156)
3. Count the number of occurrences of an element in a sorted array (Binary Search)
4. Determine if a string is a number (handle signed / unsigned, floating point, any number of digits) (Leetcode 65 without considering exp)
5. Isomorphic strings (Leetcode 205)
6. Two-sums (Leetcode 1, 167, 170)
7. Parenthesis matching (Leetcode 20)
8. Search a sorted array for the first element larger than k. (Binary search)
9. Create a stack with the usual push(), pop(), but with an additional function getMiddle() that returns the middle element of the stack in constant time. (Vector-implementation) (See also Leetcode 155)
10. Implement pow(a,b) (Leetcode 50)
11. Shortest word distance (Leetcode 243, 244, 245)
12. 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,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1), Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3). (See myblog)

Read full article from Linkedin Technical Interview – 77 Questions | Yaozong's Blog


水中的鱼: [Leetcode] Maximum Length of Pair Chain, Solution



水中的鱼: [Leetcode] Maximum Length of Pair Chain, Solution

You are given  n  pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair  (c, d) . Chain of pairs can be formed in this fashion. Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order. Example 1: Input: [[1,2], [2,3], [3,4]] Output: 2 Explanation: The longest chain is [1,2] -> [3,4] Note: The number of given pairs will be in the range [1, 1000]. [Thoughts] [Code] 1: int findLongestChain(vector>& pairs) { 2: if(pairs.size() == 0) return 0; 3: 4: std::sort(pairs.begin(), pairs.end(), comp); 5: 6: int count = 1; 7: vector& pair = pairs[0]; 8: for(int i =1; i pair[1]) { 10: count ++; 11: pair = pairs[i]; 12: } 13: } 14: 15: return count; 16: } 17: 18: static bool comp(vector& a, vector& b) { 19:

Read full article from 水中的鱼: [Leetcode] Maximum Length of Pair Chain, Solution


List Strong Component



List Strong Component

Given a list of nodes in a doubly linked list. All nodes that are neighbor in the original doubly linked list forms a strong component. Given only the list of nodes, what's the number of strong component?

Example:

The underlying doubly linked list looks like: 1 <-> 2 <-> 4 <-> 7 <-> 9 <-> 11, but this are not given as the input.

The input is a list of nodes: 1, 2, 7, 9, 11. There should be 2 strong component. {1, 2}, {7, 9, 11}

Analysis

The idea is to first add all nodes in the list into a set. Then start from one node, and remove the node and all connected nodes from the set.

Compleixty

Time: O(N)

Space: O(N)


Read full article from List Strong Component


2017 Men’s Conference @ROLCC – Fishercoder



2017 Men's Conference @ROLCC – Fishercoder

  • Sources of pressure: family, job, connections, etc.
  • How to win over pressure:
  • Belief in God (确认主的同在)
  • Removal of pessimism (除去消极思想)
  • Be committed in routine (在小事上忠心)
  • Pray for God's lead (祷告寻求神的带领)
  • What if we fail:
  • Accept truth (接受事实)
  • Be humble to learn (存谦卑的心学习)
  • Faith in God's ability (确信神永不误事)
  • Questions to discuss in your group:
  • What's the most pressing pressure you're facing right now? (在你现在的环境中,你所面对最大的压力是什么?)
  • What's your normal way of handling pressure? Is it effective? (你通常面对压力的方法是什么?有效么?)
  • What's the most helpful message you heard today? (你觉得今天的信息对你最有帮助的一点是什么?)

  • Success

  • How do you define success? (什么是成功?)

  • Principles of being successful:
  • (认识自己的长处与短处)
  • (要有清楚的目标)
  • 学习做一个解决问题的人
  • 不要怕失败
  • 要有热情
  • 要为每天的生活做选择
  • 从成功到有意义
  • 从物质到价值
  • 从追求到给予
  • 从堆积到培育
  • 讨论问题
  • 请分享一下你现阶段的生命目标?什么是你的热情所在?你觉得最大的难处是什么?
  • 有哪些事是你正在做来达成目标,去除拦阻的?

  • Connections

  • A good web of connections is the KEY to happiness

  • Principles of dealing with connections:
  • In family:
  • What they want is your time and attention! Put your laptop and cellphones away! Just spend time with them!
  • Love your wife, never ignore her
  • 爱,就是用心去注意她
  • 要常纪念妻子的爱与付出
  • 爱火是可以重燃的
  • Be kind/nice/patient to your wife, your children will mimic you and have the same attitude to their mom
  • If you're rude, inpatient to your wife, then your children will be the same to their mom, and then their future spouses, this will have permanent damage!
  • 要教养你的儿女,不要缺席
  • 明白"属灵的头"的角色
  • 用生活的榜样来教导
  • 按孩子的需要来带领
  • 要花时间陪伴他们
  • Have daddy-daughter date time! Set it up as a weekly routine, just spend time together, no interruptions, this is the key to building a strong parent-child relationship!
  • In workplace:
  • 要学习与人相处共事
  • 对上司保持良好的沟通
  • 对同事保持团队的互动
  • 要选择你要相处的人群
  • 要学习去帮助别人
  • 关系就是通路
  • Questions to discuss in your small group:
  • In your personal life, what's your most tough questions in handling connections/relationships?

  • Wealth

  • Wealth for Christians

  • Principles for Christians wealth manangement:
  • 确认神是我们一切所有的主
  • 作神忠心又有见识的管家
  • 要殷勤筹划
  • 要慷慨奉献
  • 要拜托债务
  • 储蓄与投资
  • 投资在永恒
  • 提早退休,投身服事
  • 遗产规划,让钱财被神所使用

Read full article from 2017 Men's Conference @ROLCC – Fishercoder


Array Monotonic · LintCode题解



Array Monotonic · LintCode题解

Array Monotonic

Question

给一个数组array,判断该数组是否是单调的。如果数字都相同为true。

+

Solution

这道题很简单,假设数组单调增或者单调减,然后逐个元素比较判断即可。唯一的trick就是首先要找出该数组是增还是减的假设。当元素个数大于等于3个时,首先比较第一个元素和最后一个元素的大小,如果第一个元素大,则假设数组递减,否则假设数组递增。如果相等,则去判断数组中元素是否全部相等。

+

conor case:当数组元素小于3个时:如果0个元素,则false,1或者2个元素,则true(2个元素不是增就是减)。


Read full article from Array Monotonic · LintCode题解


algorithm - Amortized analysis of an ordered stack - Stack Overflow



algorithm - Amortized analysis of an ordered stack - Stack Overflow

I was working through a tutorial sheet I found online and came across a question I couldn't figure out how to solve.

http://www.bowdoin.edu/~ltoma/teaching/cs231/fall08/Problems/amortized.pdf

An ordered stack S is a stack where the elements appear in increasing order. It supports the following operations:

Init(S): Create an empty ordered stack.

Pop(S): Delete and return the top element from the ordered stack.

Push(S, x): Insert x at top of the ordered stack and re-establish the increasing order by repeatedly removing the element immediately below x until x is the largest element on the stack.

Destroy(S): Delete all elements on the ordered stack.

Argue that the amortized running time of all operations is O(1). Can anyone help?


Read full article from algorithm - Amortized analysis of an ordered stack - Stack Overflow


Leetcode: Ternary Expression Parser - neverlandly - 博客园



Leetcode: Ternary Expression Parser - neverlandly - 博客园

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).    Note:    The length of the given string is ≤ 10000.  Each number will contain only one digit.  The conditional expressions group right-to-left (as usual in most languages).  The condition will always be either T or F. That is, the condition will never be a digit.  The result of the expression will always evaluate to either a digit 0-9, T or F.  Example 1:    Input: "T?2:3"    Output: "2"    Explanation: If true, then result is 2; otherwise result is 3.  Example 2:    Input: "F?1:T?4:5"    Output: "4"    Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:                 "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"            -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"            -> "4"                                    -> "4"  Example 3:    Input: "T?T?F:5:3"    Output: "F"    Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:                 "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"            -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"            -> "F"                                    -> "F"
复制代码

My First Solution:

Use Stack and String operation, from the back of the string, find the first '?', push the right to stack. Depends on whether the char before '?' is 'T' or 'F', keep the corresponding string in the stack


Read full article from Leetcode: Ternary Expression Parser - neverlandly - 博客园


LC439. Ternary Expression Parser - freeCookie🍪 Blog



LC439. Ternary Expression Parser - freeCookie🍪 Blog

LC439. Ternary Expression Parser

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9?:T and F (T and F represent True and False respectively).

Example:

Input: "T?T?F:5:3"    Output: "F"    Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:                 "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"            -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"            -> "F"                                    -> "F"  

实现?:这个表达式,记录?和:的位置,利用count找到最外层的表达式,利用recursion一层一层操作。


Read full article from LC439. Ternary Expression Parser - freeCookie🍪 Blog


Leetcode 499. The Maze III 题解 | To.Plant.a.Tree



Leetcode 499. The Maze III 题解 | To.Plant.a.Tree

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up (u), down (d), left (l) or right (r), but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a hole in this maze. The ball will drop into the hole if it rolls on to the hole.

Given the ball position, the hole position and the maze, your job is to find out how the ball could drop into the hole by moving shortest distance in the maze. The distance is defined by the number of empty spaces the ball go through from the start position (exclude) to the hole (include). Output the moving directions by using 'u', 'd', 'l' and 'r'. Since there may have several different shortest ways, you should output the lexicographically smallest way. If the ball cannot reach the hole, output "impossible".

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The ball and hole coordinates are represented by row and column indexes.

Example 1

Input 1: a maze represented by a 2D array

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

Input 2: ball coordinate (rowBall, colBall) = (4, 3)
Input 3: hole coordinate (rowHole, colHole) = (0, 1)

Output: "lul"
Explanation: There are two shortest ways for the ball to drop into the hole.
The first way is left -> up -> left, represented by "lul".
The second way is up -> left, represented by 'ul'.
Both ways have shortest distance 6, but the first way is lexicographically smaller because 'l' < 'u'. So the output is "lul".


Read full article from Leetcode 499. The Maze III 题解 | To.Plant.a.Tree


Leetcode 394. Decode String 题解 | To.Plant.a.Tree



Leetcode 394. Decode String 题解 | To.Plant.a.Tree

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".


Read full article from Leetcode 394. Decode String 题解 | To.Plant.a.Tree


LeetCode – Decode String (Java)



LeetCode – Decode String (Java)

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".  s = "3[a2[c]]", return "accaccacc".  s = "2[abc]3[cd]ef", return "abcabccdcdcdef".  

Java Solution

The key to solve this problem is convert the string to a structured data structure and recursively form the return string.


Read full article from LeetCode – Decode String (Java)


Leetcode 394. Decode String 字符串解码 解题报告 - MebiuW的专栏 - CSDN博客



Leetcode 394. Decode String 字符串解码 解题报告 - MebiuW的专栏 - CSDN博客

意思是在字符串当中,有一个特殊的格式 — k[S],遇到这种状况,需要把S重复k次,注意是可以嵌套的

在这次解题当中,我是使用了栈的方式,去解决这个问题。分别使用了一个全局的已解码的字符串Builder,另外对于为解码的,使用栈来暂存。

符号'['控制进栈,分别进入计数数字和之前尚未解码的字符串
符号']'控制出站,出栈当前计数,并且将未解码的字符串进行重复,再链接上一个未解码的字符串

注意栈空的时候证明当前嵌套解码完毕,需要添加到全局当中,反之基于暂存。


Read full article from Leetcode 394. Decode String 字符串解码 解题报告 - MebiuW的专栏 - CSDN博客


爬虫框架设计 - JavaNerd - 博客园



爬虫框架设计 - JavaNerd - 博客园

最近的一个项目是写一个爬虫框架,这个框架主要采用Master-Slave的结构,Master负责管理要爬取的Url和已经爬取过的Url,Slave可以有多个,主要负责爬取网页内容,以及对爬取下来的网页内容进行持久化的工作。整个项目用Thrift作为RPC通信框架。


Read full article from 爬虫框架设计 - JavaNerd - 博客园


[LeetCode]436 Find Right Interval - JavaNerd - 博客园



[LeetCode]436 Find Right Interval - JavaNerd - 博客园

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.

For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

  1. You may assume the interval's end point is always bigger than its start point.
  2. You may assume none of these intervals have the same start point.

 

Example 1:

Input: [ [1,2] ]    Output: [-1]    Explanation: There is only one interval in the collection, so it outputs -1.  

 

Example 2:

Input: [ [3,4], [2,3], [1,2] ]    Output: [-1, 0, 1]    Explanation: There is no satisfied "right" interval for [3,4].  For [2,3], the interval [3,4] has minimum-"right" start point;  For [1,2], the interval [2,3] has minimum-"right" start point.  

 

Example 3:

Input: [ [1,4], [2,3], [3,4] ]    Output: [-1, 2, -1]    Explanation: There is no satisfied "right" interval for [1,4] and [3,4].  For [2,3], the interval [3,4] has minimum-"right" start point.


解法: 把这些interval按照start从小到大排序,然后对每一个interval用其end去在排好序的队列里面做二分查找,
找到符合要求的一个interval。代码:

Read full article from [LeetCode]436 Find Right Interval - JavaNerd - 博客园


436 Find Right Interval | 打满鸡血来刷题



436 Find Right Interval | 打满鸡血来刷题

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.

For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

  1. You may assume the interval's end point is always bigger than its start point.
  2. You may assume none of these intervals have the same start point.

Read full article from 436 Find Right Interval | 打满鸡血来刷题


Leetcode 436. Find Right Interval 找区间 解题报告 - MebiuW的专栏 - CSDN博客



Leetcode 436. Find Right Interval 找区间 解题报告 - MebiuW的专栏 - CSDN博客

题目给了一堆[起始位置,结束位置]的数组,定义了一个个区间

任务则是要求对于给定的第I个区间,找到一个最小的j,这里的j的起始位置大于等于I的结束为止

其实暴力一点可以直接搜索,但是这里还不需要

这里使用了Java中的TreeMap
首先将所有起始位置和他的序号放入TreeMap(key是位置I的起始位置,value是I)当中

随后遍历每个位置的结束为止,使用TreeMap的方法,使用当前序号结束位置的大小找到TreeMap中第一个大于等于其结束位置的Entry,如果存在则取出value,不然就返回-1


Read full article from Leetcode 436. Find Right Interval 找区间 解题报告 - MebiuW的专栏 - CSDN博客


JSON字符生成json对象时的转义问题 | 媛媛的小窝



JSON字符生成json对象时的转义问题 | 媛媛的小窝

JSON字符生成json对象时的转义问题

最近在做新项目的时候,发现从服务器端返回的json格式数据,无法被正确解析。

捣鼓了半天才解决,所以整理了一下查询的文档,写了这篇文章


转义字符(\)对JavaScript中JSON.parse的影响概述

JSON是一个提供了stringify和parse方法的内置对象,前者用于将js对象转化为符合json标准的字符串,后者将符合json标准的字符串转化为js对象,本文为大家介绍下转义字符对JSON.parse方法的影响。

按照ECMA262第五版中的解释,JSON是一个提供了stringify和parse方法的内置对象,前者用于将js对象转化为符合json标准的字符串,后者将符合json标准的字符串转化为js对象。

一般来说在JSON.parse的参数包含转移字符的时候会遇到两次转义的问题,其实第一次是字符串本身的转义,第二次是将真正转为js对象的转义。


Read full article from JSON字符生成json对象时的转义问题 | 媛媛的小窝


[TDD] leet code 220. Contains Duplicate III | In 91 - 點部落



[TDD] leet code 220. Contains Duplicate III | In 91 - 點部落

leet code 最後的瓶頸,果然還是在演算法的效能資料結構的選擇型別運算可能溢位的基本觀念。

如果要我選擇產品程式碼的寫法,我可能還是會為了可讀性,而選擇用前面 HashSet + IEqualityComparer 的作法。不過,目前的 while 迴圈也還算清楚,但練習 leet code 就是單純逼出自己搾出效能的極限,挺有趣的!

效能當然還有優化的空間,但可能要手刻 java 的 TreeSet 資料結構會比較有機會一點。


Read full article from [TDD] leet code 220. Contains Duplicate III | In 91 - 點部落


220. Contains Duplicate III | Nine notes



220. Contains Duplicate III | Nine notes

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


Read full article from 220. Contains Duplicate III | Nine notes


LeetCode 220 Contains Duplicate III - 简书



LeetCode 220 Contains Duplicate III - 简书

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

注意题目中一旦出现,当两者距离at most k等constraint时,都可以考虑使用sliding window的方法,每次仅保留window size=k的元素,判断完后再移动并更新window。

思路一:naive thinking
考虑排序,但排序时也得带上index,即需要记录排序前各个元素原先的下标。排序后,check数组中是否存在符合at most t & at most k的元素。

思路二:基于sliding window
顺序扫描数组,每次仅保存size=k的滑动窗口,并用TreeSet或bucket存储窗口中现有的元素,加入新元素后判断是否与集合中元素满足difference<=t的条件。注意窗口的更新,如何维护treeset或bucket(加入新元素的同时,删除最早加入的元素)。

这里要注意为什么需要使用treeset与bucket,而不是queue?原因是treeset和bucket具有根据input value快速查找的能力,若新加入的元素为nums[i],
则treeset可以通过floor与ceiling在O(log k)的时间复杂度下查找最相近的元素。

Long floor = set.floor((long) nums[i]);         Long ceiling = set.ceiling((long) nums[i]);

bucket可以在O(1)时间复杂度下查找,原因是将出入分成了大小为t+1的桶,这里类似于hashmap,可以根据输入大小nums[i]直接反查在哪个桶中。

long remappedNum = (long) nums[i] - Integer.MIN_VALUE;  long bucket = remappedNum / ((long) t + 1);

Read full article from LeetCode 220 Contains Duplicate III - 简书


leetcode 220: Contains Duplicate III - 西施豆腐渣 - CSDN博客



leetcode 220: Contains Duplicate III - 西施豆腐渣 - CSDN博客

Contains Duplicate III

Total Accepted: 633 Total Submissions: 4437

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

[思路]

维持一个长度为k的window, 每次检查新的值是否与原来窗口中的所有值的差值有小于等于t的. 如果用两个for循环会超时O(nk). 使用treeset( backed by binary search tree) 的subSet函数,可以快速搜索. 复杂度为 O(n logk)


Read full article from leetcode 220: Contains Duplicate III - 西施豆腐渣 - CSDN博客


LeetCode 385. Mini Parser · Shell32



LeetCode 385. Mini Parser · Shell32

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9[- ,].

Example 1:

1
2
3
4
5
> Given s = "324",
>
> You should return a NestedInteger object which contains a single integer 324.
>
>

Example 2:

1
2
3
4
5
6
7
8
9
10
> Given s = "[123,[456,[789]]]",
>
> Return a NestedInteger object containing a nested list with 2 elements:
>
> 1. An integer containing value 123.
> 2. A nested list containing two elements:
> i. An integer containing value 456.
> ii. A nested list with one element:
> a. An integer containing value 789.
>

题目要求把一个合法的字符串转换为对应的嵌套的数据格式, 一开始我想使用递归, 但是在处理嵌套的问题上遇到了麻烦, 所以改为使用栈来做.

把每一层嵌套视为栈的一个元素, 每遇到一个[就入栈一个新的NestedInteger, 然后遇到数字就把它加入到栈顶的NestedInteger中去, 遇到]就把栈顶的元素弹出, 加入到新的栈顶中, 如果弹出栈顶后栈为空说明处理结束.


Read full article from LeetCode 385. Mini Parser · Shell32


[LeetCode] 385. Mini Parser



[LeetCode] 385. Mini Parser

Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:
  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9[- ,].
Example 1:
Given s = "324",    You should return a NestedInteger object which contains a single integer 324.  
Example 2:
Given s = "[123,[456,[789]]]",    Return a NestedInteger object containing a nested list with 2 elements:    1. An integer containing value 123.  2. A nested list containing two elements:      i.  An integer containing value 456.      ii. A nested list with one element:           a. An integer containing value 789.

Thought process:
Iterate through the string. There are five cases:
  1. Digit: keep track of current number.
  2. [: push the current NestedInteger onto stack and create a new NestedInteger.
  3. -: set sign to -1.
  4. ,: if the previous character is a digit, add the number into current NestedInteger. If the previous character is ], add the current NestedInteger to previous NestedInteger.
  5. ]: current NestedInteger is finished. Pop the NestedInteger from top of the stack.

Read full article from [LeetCode] 385. Mini Parser


LeetCode Contest 42 | 叶某人的碎碎念



LeetCode Contest 42 | 叶某人的碎碎念

今天晚上在朋友家做好饭已经过了比赛时间了,我们是边吃着饭边喝着酒来写代码。牛肉炖土豆是一如既往的美味,新尝试的豆腐煮白菜也很不错。这次朋友买了Habanero,辣味惊人,我是打着喷嚏做菜的😢


Read full article from LeetCode Contest 42 | 叶某人的碎碎念


LeetCode 421 Maximum XOR of Two Numbers in an Array 解题报告 - hanzheng992的博客 - CSDN博客



LeetCode 421 Maximum XOR of Two Numbers in an Array 解题报告 - hanzheng992的博客 - CSDN博客

暴力解什么很显然, 可以直接在O(n^2)的时间内进行两两计算, 并且保存最大值, 代码什么的也不说了, 很简单.

Better Solution

对输入的数组, 我们将其中的元素根据最高位的值分为两类, 最高位为0的一类, 最高位为1的一类, 如果两类都不为空, 那么该问题的最终结果一定是从第一类中找一个数和第二类中的一个数进行异或得到的结果.

那么此题就可以优化为, 从两个数列中各取一个数, 求两个数按位异或结果的最大值. 因此, 我们可以设计一个helper函数帮我们处理.

那么, 我们可以根据次高位再将数继续分成两类, 因此, 我们可以得到四个类, arr00, arr01, arr10, arr11. 那么最终的解一定在(arr00, arr11), (arr10, arr01)中; 如果存在空集, 那么最终的解一定在(arr00, arr01), (arr11, arr10)中.

平均时间复杂度分析, 假设O(n)表示helper函数的时间复杂度, 其中n表示传入helper两个数列的总长度. 那么我们有 O(n) = n + 2 * O(n/2), 化简后可得 O(n) = O(n log n) + O(n) = O(n log n)


Read full article from LeetCode 421 Maximum XOR of Two Numbers in an Array 解题报告 - hanzheng992的博客 - CSDN博客


github, ready to go? | Frank's Notes



github, ready to go? | Frank's Notes

假期的时候给一个 golang 开源项目 s 贡献了代码,快两个月了,时间也有点久远了😂 我发现给 golang 项目贡献代码的姿势跟给其他语言贡献代码的姿势不太一样,而我当时只是 hack 了一下,也没记录下来,这不,给自己挖坑了,最近又有一位朋友问我怎么给 github 上的 golang 项目贡献代码,为什么会有这样的问题呢,难道 golang 很特殊?听我一一道来。


Read full article from github, ready to go? | Frank's Notes


521. Longest Uncommon Subsequence I – KelvinMao Blog



521. Longest Uncommon Subsequence I – KelvinMao Blog

Description Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings. A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string. The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1. Example 1: Input: "aba", "cdc" Output: 3 Explanation: The longest uncommon subsequence is "aba" (or "cdc"), because "aba" is a subsequence of "aba", but not a subsequence of any other strings in the group of two strings. Note: 2.Only letters from a ~ z will appear in input strings.

Read full article from 521. Longest Uncommon Subsequence I – KelvinMao Blog


leetcode-solutions/26. Remove Duplicates from Sorted Array.md at master · nekocode/leetcode-solutions · GitHub



leetcode-solutions/26. Remove Duplicates from Sorted Array.md at master · nekocode/leetcode-solutions · GitHub

然而我并没有提交该代码。首先是题目不允许分配新的内存来解题,其次是我忽略了题目的一个信息,就是数组是有序的。好吧,重新做这道题,用 dupLen 来储存重复数字的数量,动态将未重复的数字往前挪,算法复杂度 O(N)。


Read full article from leetcode-solutions/26. Remove Duplicates from Sorted Array.md at master · nekocode/leetcode-solutions · GitHub


Research Blog: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken



Research Blog: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

I remember vividly Jon Bentley's first Algorithms lecture at CMU, where he asked all of us incoming Ph.D. students to write a binary search, and then dissected one of our implementations in front of the class. Of course it was broken, as were most of our implementations. This made a real impression on me, as did the treatment of this material in his wonderful Programming Pearls (Addison-Wesley, 1986; Second Edition, 2000). The key lesson was to carefully consider the invariants in your programs.

Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. Once I tell you what it is, you will understand why it escaped detection for two decades. Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.

Read full article from Research Blog: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken


Amazon OA1 – cyqz Blog for LeetCode and my life



Amazon OA1 – cyqz Blog for LeetCode and my life

一些reasoning题目的总结

  1. QPS – TSV; IHK -> ? : LKN(都是加3)
  2. 46->64; 82->? : 100(相差18) 或者 28(镜像)
  3. EAGLE -> FZHKF ; THANKS -> ?   UGBMLR (+1, -1, + 1, -1,+1)
  4. FASTER-> HCUVGT;SLOWER-> ?  UNQRYT (都是加2)
  5. 985 -> 874; 763 -> ? 652 (-1)
  6. 865->532; 976 -> 643(-3)
  7. ADBC -> EHFG; ILJK -> ? MPNO (+ 4)
  8. JOHN – > LSNV; MARK -> ? OEXS (+ 2, +4, + 6, + 8以此类推)
  9. COMPUTER -> PMOCRETU; TELEVISION -> ? ELETNOISI(中间切一刀,然后每个字母的顺序反一下)
  10. A17R-> D12P ; G7N : ?  (A + 17 = R, D + 12 = P)
  11. COMPUTER -> GKQLYPIN ; SENATE ->WARWXA?
  12. KPQR->LRTV; DGHY -> ? EIKC (前后加减1,2,3,4)
  13. ACFJ -> CEHL ; PRUY -> ? RTWA (前后加减2,3,4, 第一个和第二个相差2)
  14. VAILANT -> UBKJZOS; TRANSCEND -> ? 
  15. 27 -> 24; 64-> ? 60 (24 = 3^3 – 3, 60 = 4 ^ 3 – 4)
  16. MQD -> KRK ; SWM -> ? TXQ (斜下角,+5, -6, +7)
  17. AD5 : ED9 求和 (A + D = 5, E + D = 9)
  18. BGL-> DIN; MRW-> ? HLR (?我觉得是上面 + 2 = 下面)
  19. PRS TVX FIK LME
  20. JLP LNT TVZ DFJ (我觉得选第二个,因为其他的都是 + 2, + 4)
  21. ABIJ DEHI MNQR STWX(选第一个,因为数字间间隔不一样)
  22. ADP QTS HKR STE(ADP ? 因为ADP都是完全平方数?或者是QTS,因为位于的结果不是0)
  23. RHCAI OEST HNDA ADEH
  24. ADF MPR ILN BDE(BDE, 因为其他的都是+3, + 2,这个是+2, +3)
  25. STV XYA KKT BDE (KKT, 两偶一奇,两奇一偶)
  26. 956 794 884 678 (678, 前面加起来都是20)
  27. 1,4,16 ; 17,20,24 ;8,11,18 ;19,20,5(应该是4,因为只有4的差值不是3的倍数)
  28. AE5 DF6 HN14 KP2 (KP2 因为P  != 2)
  29. HIK DGJ LPT SUW -》HIK (因为不是等距)
  30. LKJI XYWV WVUT KJIH (XYWV因为其他都是逆序)
  31. 2,3,7,8,13,14,-? (20)(1,4,1,5,1,6 相差)
  32. 0 1 1 2 4 8 (16)(16是前面数字的总和)
  33. 3,6,18,108 (18*108 =  1944)
  34. 1,1,4,2,13,3,40,4 (121,这个题目好难啊,1 + 3的一次方=4, 4 + 3的2次方 = 13, 13 + 3 的三次方 = 40, 40 + 3的四次方 = 121)
  35. 3 7 13 21 ?(31)(4,6,8,10增加)
  36. 5 11 19 29 ? (41)(6,8,10,12)
  37. 0 2 6 12 20  ?(36 或者30 前一个是相差2的几次方,后一个是每个相隔相差2)
  38. 5 9 16 29 (54)(5*2-1, 9*2-2, 16*2-3, 29*2-4)
  39. 4 12 6 18 12 36 30 (90)(奇数位乘以三)
  40. 1 5 (8) (1 + 22 = 5, 5 + 21 = 7 ,7 + 20 = 8)
  41. D,H,L,? P (相同的间隔)
  42. 10 14 23 39 64(100) (间隔为4,9,16,25,后面应该是36)
  43. 10 74 202 394 650(间隔为64的倍数)
  44. 2 8 5 6 8
  45. 16 30 46 62
  46. 1:4:27:256:? 3125 (n的n次方)
  47. 2, 5, 26,(677)(规律是当前数字是前一个数字平方加1)
  48. ASSERTIVENESS-> SENSSAEVISTRE ; MULTINATIONAL -> ?
  49. 4,5,12,8,9 => 3,4,1,7,8问 13, 21, 13, 2, 1, 9 => ?都减一
  50. PRS, TVX, FIK, LME 瞎猜的 (不会)
  51. 5 9 16 29 ( 54)
  52. 52. 5 9 16 29 ( )
  53. 53.1 5 7 ( 8)
  54. 2 8 5 6 8 ( 4) 11
  55. 0 1 1 2 3 7 ( )0 1 1 2 3 7 ( )

 

应用题:

方向题目

  1. If northwest becomes east, northeast becomes south, and so on, what does southeast become?   WEST
  2. Lily can't find her home, she is 25 yards southwest of her home, then she walked 20 yards toward north, where is her home from her now? (15 yards, east)
  3. 一个面朝北的朋友,先左走15m,然后一个about-turn走了30,这货在哪?(about turn大概是向后转的意思,那就是south 30m)
  4. 小明往东南走4 miles,往西走8 miles, 再往西北走4 miles。现在小明离出发点是什么方位?(west)
  5. 小明面朝南,往左走20miles, 再往右走 10miles, 再往左走30miles。 现在小明离出发点是什么方位?东南(记住,用左右的时候要注意朝向,因为位置已经变了)
  6. 南5西4南7东4北5,问方向、离原点距离(南2)
  7. 一个楼有3层,每个level 坐一些人,第二层能坐最多,一共坐66个人。给了两个条件求第二层坐 了多少人。
    • 1,其中有一层坐了21 人。
    • 2,第二层比其中一层多座了2人 (22人)
    • 推断一个人的年龄 (1)知道所有人的平均年龄 (2)所有人年龄都一样,问(1)和(2)怎么来推断这个人的年龄 (什么鬼,不是应该所有都一样么)

印度公司题目

有个是问印度公司在radio上做广告,记忆没错的话,选B。大意是,radio覆盖面广,公司向推广自己的,应该去上面做广告。It has been proven by research that in India, a company which purchases saturation radioadvertising will get maximum brand recognition.

(saturation advertising是指同一个广告反复宣传,就好像脑白金的洗脑歌一样。。而研究表明通过这种广播,可以收获最大的品牌认同度)

  1. 高品牌认同度使公司获得更高的市场份额(研究说的是宣传与认同度的关系,没有涉及市场份额)(品牌认知度和市场份额的关系未在题目条件中提及,无关联)
  2. 广播有不错的听众基础,如果公司想提高他们的知名度认同度,应该考虑通过这种方式.
  3. 为了达到最大的品牌宣传效果,公司不应该考虑广播之外的宣传方式 (广播频率max导致宣传效果max也只是广播频率的影响,并不代表其他宣传渠道如何)。(并未说明其他广告渠道对最大化品牌认知度的贡献,所以不该武断排除其他一切非收音机渠道的广告策略)
  4. 在印度,品牌认同更看宣传的where,而不是质量 (同样原文没提到质量和效果之间的关系)(题目条件未提及广告质量,无关联)

环保公司问题

选择是否将候选公司放到一个环保list上,条件

  1. hava ECC (一种认证)
  2. 生成了至少三种solar 产品 (如果不满足,但是有一种产品正在试验中,那就推荐给COO)
  3. none of their products are from synthetic
  4. headquater in Texas
  5. product 都由 A -certificate    (如果不满足,则推荐给director of the company)
  6. donot have legal dispute or pending against them

如果不满足2,但是有一种产品正在试验中:推荐给COO

如果不满足5:推荐给Director of the company

 

 

录用 PM

一个公司要招PM,合理的candidate需满足以下条件:

1. 本科是学CS的
2. 有MBA学位
3. 本科GPA 3.0+
4. 如果没有MBA学位,但是工作5年以上,需上报HR
5. 本科不是学CS,但是在CS相关工作3年以上,上报HR

那么,请问:闰土本科学热水锅炉维修的,GPA 4.0,没有念过MBA,在Google修了5年的锅炉,当
了3年的程序员,则应该: D

A. 录用
B. 不录用
C. 条件不充分
D. 上报HR  (因为没有MBA学位,但是工作五年以上,所以上报HR)

 

-》

另一个条件:

  1. 候选人必须有硕士学位,且GPA为A
  2. 必须有两年以上工作经验,
  3. 若1不满足报告director

小明从事某工作三年,有CS和MBA,本科GPA为A-则:报告主管。

-》

又一个条件条件是:

  1. Master in commerce and at least B / have CPA
  2. 年龄大于20 ,小于25
  3. 流利的英语和西班牙语.
  4. 愿意付125刀押金
  5. 愿意承诺为公司工作5年
  • 如果1不满足-> refer to M director
  • 如果4不满足 -> refer to chair man .

快递收费(没有完全)

快递费要不要收的问题。条件是

  1. 地区code 大于10一类,小于10 另一类
  2. 商品价格超过500
  3. 不是deal的时候买得
  4. 之前没有bulk 超过5%的折扣. 1point3acres.com/bbs
  5. 客户有优良购买记录3年
  • 如果不满足2,那么要是他满足地区code小于10,收10刀,大于10,收8刀。
  • 如果不满足3,那么region code小于10,收5刀,大于10,收12刀

来了一个老头,买了150刀的东西,不是deal的时候买的,也没有之前折扣。问他可不可以不付运费。
若不满足两条,则必须付全款。

选:附全款30刀

 

四人位置

There are four coordinators named Lily, Cathy,Mary and Nina. Each coordinator is at a different corner of the rectangle meeting hall. A coffee vending machine is situated at one of the corners and a restroom at another corner of the meeting hall. Lily and Cathy are at either sides of the white board, which is situated at the center of the side  which is opposite to the side at whose corners the coffee vending machine and the restroom are located. Coordinator Mary is not at the corner where the restroom is located.
Which of the following cannot be true?

  1. Lily is not on the side of the hall where the white board is placed
  2. Nina is adjacent to the restroom at one corner
  3. Cathy is at the corner, adjacent to the coffee vending machine.
  4. Mary is adjacent to the coffee vending machine, at one corner of the hall
  5. Lily is at the corner, adjacent to the coffee machine

这个问题选一,因为这个题目里面mary在vending machine 和Nina在 washingroom 旁边是确定的,Lily和Cathy在mary和nina对面的白板的两侧,但是位置可以互相变化

出差问题

说有M1,M2,M3,M4,M5和W1,W2,W3。出差必须派至少三男一女。M1和M3不能共存,M4和W2不能共存。

  • 第一问问如果派了M2和M3和W2,还可以派谁 M5
  • 第二问问如果M1 M2去了,还可以派谁。

    M4 M5 W1 W3 或者M5,w1, w2,w3

  • 第三问如果去了四个男生,那么谁不能选。W2,因为M4肯定去了

 

八仙桌问题:

A, B, C, D, E, F, G H are sitting around a round table. 'F' is two places to the right of 'C', 'A' and 'E' are on either side of 'G', 'B' and 'H' are opposite to each other. 'C' is facing north.anti clock direction possible arrangement AHCDFBEG

一圆桌坐八人ABCDEFGH. F在C右边两位,AE坐G两边, BH面对面:

  • 问D对面是谁?G
  • 以下哪两人坐对面?D&G
  • 谁坐D旁边?C
  • AB不坐隔壁, F对面坐A, 反时针方向可能的坐法?AHCDFBEG之类的

6人桌问题

6人团团坐问题,有六个人 GASMNR, 注意理解 G, A,S 两两不能对坐,所以总体来说分两种情况,GAS三人间隔而坐,或者GAS全都挨着坐。所有团团做的问题都围绕此基础展开。有一题说R 在A S 中间,问你R对面是谁。还有就是 G左右是A R,问A 对面是谁。

这个题主要是,GAS有两种坐法,第一种是一起坐,第二种是间隔坐

所以如果R在AS中间,R对面一定是G

如果G左右是AR, A对面一定是M或者N

 

 

炒鱿鱼问题

Saira一直是受同事敬仰的好员工,直到她因为bipolar综合征带来的问题需要休假一段时间,不久后他就被炒鱿鱼了,公司给出的理由是他的病情导致他工作效率差,而且会无意识的冒犯上级,(这个病的症状之一就是在无意识的情况下各种刷花说个不停)最终法院裁定,她被炒鱿鱼,是因为公司相信了关于这种病的种种myth(相当于歧视)。问那个选项是对的

答案:Saira被炒鱿鱼不是因为她自己有错(其他几个选项都是空穴来风)

 

 

 

 

 

 

 

最近的地里的面经

QDXM:SFYN :: UIOZ:? (WKPA) (+ 2 + 2 + 1 +1)

24:50 :: 102:? (206).(2n  + 2)

BAD,FEH,(POS),TSV 找不同

ABDC,(MNPQ),PQSR,STVU

JLP,(LNT),TVZ,DFJ (只有LNT 是+2+6,其他都是+2+4)

MARKET-> 12-26-17-10-4-19. PRODUCT? ——》全都减一 OQNCTBS

EAGLE->FZHKF. THANKS->? UGBMLR(+1,-1,+1,-1….)

2, 3, 7, 8, 13, 14, (20) (1,4,1,5,1,6)

82, 97, 114, 133, (154)

8,8,15,23,38 -? (据说是地里的难题 8+8 -1 = 15, 15 + 23 = 38; 38 +23 -1 = 60)

Dj: WQ :: FK ——》UP(+6, -6, +5, – 5)

ASSERTIVENESS:SENSSAEVISTRE  :: MULTINATIONAL:(ANOLUMITALNIT)

运算符问题:

The given signs denote the following operations / relationships.

1. A-B means A plus B; 2.A#B means A multiplied with B; 3. A/B means A is greater than or equal to B. 4.A?B means A is less than B. On the basic of this information, and assuming that the given statements are true, find out which of the two conclusions (I and II) is/are definitely true.
STATEMENTS:
(V#X)/(V-X), X?Y, and Z/Y.
Conclusions:
I. X?Z
II. (V-X)?(V#X)

只有I 对,因为II还可能相等
13. Buyme网站题目
14. B taller than Salley? 条件1:R=B=S。条件2:S<R
15. How old of Grace? G=3T+B; B=T+15;.1point3acres缃�
后面是运费问题,M1M2M3M4M5W1W2W3分配任务,石油公司代理问题。

五男三女问题,太阳能公司问题,招聘问题

reasoning的题我碰到面经里有的是:四个角四个人那个题;给一堆条件问你要不要付运费的题;给一堆条件问你要不要录取这个人;俩网络公司选最高bid的人必须买的题

改错:考到了sort(descending 和ascending)都考了,还考了从数组里面删去一个elem

 

 

 

 

 

 

 

 

 

 

 

 

OA2 CODING

OA1:1. K Closest Points to Origin;
2. LongestPalindrome;
3. Maximum Minimum Path; 
4. Merge Two Sorted List;
5. optimal weights;
6. Overtap rectangle;
7. Reverse Second Half of Linked List;
8. serch 2D matrix;
9. sliding window minimum;.
10. Subtree;
11. valid parentheses
还有老三道最近没出现过估计不会考了

OA2:1. DayChange;
2. Greatest Common Divisor;
3. Insert Into CycleList;
4. LRUMissCount;
5. Maze;
6. BST MinPathSum.java
7. RotateMatrix;
9. RoundRobin;
10. ShortestJobFirst;
11. Sametree;
12. Subtree;
13. valid parentheses;
14. Tree Amplitude和ArithmeticSequence这俩老的也没怎么考了


Read full article from Amazon OA1 – cyqz Blog for LeetCode and my life


Amazon OA2 – 长方形覆盖 – cyqz Blog for LeetCode and my life



Amazon OA2 – 长方形覆盖 – cyqz Blog for LeetCode and my life

给两个长方形的topLeft和bottomRight坐标, 判断这两个长方形是否重叠

Rectangle Overlap。这题和leetcode 算相交面积的区别:它帮你定义好两个类,一个叫Point,一个叫Rectangle,Rectangle包括左上右下两个Point, Point包括x, y的值, 这种细节并不影响程序,总之一句判断直接通过了全部20多个case.


Read full article from Amazon OA2 – 长方形覆盖 – cyqz Blog for LeetCode and my life


JSolved: Finding out running Maximum element from stack



JSolved: Finding out running Maximum element from stack

Finding out running Maximum element from stack

You have an empty sequence, and you will be given  queries. Each query is one of these three types:
  • 1 num  Push the element x into the stack.
  • 2          Delete the element present at the top of the stack.
  • 3          Print the maximum element in the stack.

For each query of type 3 return the max element from the current stack.
Input:

Read full article from JSolved: Finding out running Maximum element from stack


JSolved: Surpasser Count of each element in an array



JSolved: Surpasser Count of each element in an array

Given an array of distinct integers, for each element of the array count the number of elements to the right that are greater than that element.
A surpasser of an element of an array is a greater element to its right, therefore x[j] is a surpasser of x[i] if i < j and x[i] < x[j].
Example:
input = [6, 5, 4, 7, 2, 8, 0]
output= [2, 2, 2, 1, 1, 0, 0]
  
Approach 1:
Simplest approach to iterate every time throught the array and find out greater element to it's right. This approach would require O(n^2) complexity and no space complexity.
 
Approach 2:
We can use O(n)  extra space and solve this efficiently. Priority queue can be used here to store the element in sorted order so that we can check the number of greater element in faster manner. So the complexity will be similar to the time required to push element to priority queue and removing from the same to check for greater element.
Steps:
  • Start from rear end of array, pick one element each time
    1. Check if queue head is greater than current element 
    2. if yes means all the element in queue are greater than current element.
      • Save the size of queue as output for specific index of input array
    3. if no then remove element from queue and store it to stack for temporaty storage.
    4. Go to step 1 again

Read full article from JSolved: Surpasser Count of each element in an array


Puzzle - A surpassing problem



Puzzle - A surpassing problem

Another week, another interesting puzzle. This puzzle is taken from a programming exercise posed by Martin Rem in 1988

A Surpassing Problem

By definition, a surpasser of an element of an array is a greater element to the right, so x[j] is a surpasser of x[i] if i < j and x[i] < x[j]. The surpasser count of an element is the number of surpassers. For example, the surpasser count of the string GENERATING are given by

G E N E R A T I N G

5 6 2 5 1 4 0 I 0 0

The maximum surpasser count is 6. The first occurrence of the letter E has six surpassers, namely N, R, T, I, N, and G. Rem's problem is to compute the maximum surpasser count of an array of length n > 1 and to do so with an O(n log n) algorithm.


Read full article from Puzzle - A surpassing problem


如何正确的写出二分查找 | qianzui's blog



如何正确的写出二分查找 | qianzui's blog

还记得Jon Bentley关于二分查找的那句著名言论吗?————90%以上的程序员无法正确无误的写出二分查找代码!几年前刚毕业的时候无意间看到这句话的时候,还有点不以为然,感觉就是一个普通的分治法的算法嘛,有这么夸张?
今天在看SparseArray源码的时候,碰巧发现一个设计的很巧妙的二分查找算法。先看代码:

Read full article from 如何正确的写出二分查找 | qianzui's blog


Cat in Chinese: 理想的技术面试过程



Cat in Chinese: 理想的技术面试过程

从在大学里面试社团大一新生,到加入百度后帮公司面试候选人,我觉得我对面试这件事一直不得要领。百度提供面试培训,也允许参考或使用题库,但我还是觉得不知道如何判断给不给一名候选人通过我这关。偶尔我会遇到非常优秀的实习生候选人,我能十分确定我要给他过,甚至想方设法确保他能来。其它时候,我觉得我的判断随机性太大,或许还不如一枚硬币做得好。

在百度做二面的时候,我往往会问一些组合问题,就是候选人需要有扎实的基础加上一定的解题能力才能做出来的。我假设一面的面试官已经问过基础问题,所以我不会再问基础问题。结果通常是,候选人的基础不够扎实,会作出一些错误的假设,甚至面对组合问题就无从下手,不知道如何分解为更小的问题然后再一步一步来解决。我不知道是否应该期望候选人全部答对,但答对小部分的状况让我无从判断。

为此我开始跟其它人讨论面试经验。Acumon 说应该针对候选人说他擅长的领域来提问,而且使用开放性问题以便了解候选人的思考方式,但我发现我遇见的大多数候选人都不清楚自己擅长什么,或者是他们自认为的强项无法达到我的预期。后来在上海跟 Winter 和 Hax 聊天时发现一个可怕的现实:大多数前来应聘的前端工程师都无法回答「position 属性取值都有哪些」以及「display 属性取值都有哪些」。随后我尝试在我的面试中先问这两个问题,发现确实有些人回答不出来取值,更多人则是无法准备描述常见取值的作用。(我甚至不把 inline-block 和 fixed 归类到常见取值里面。)遇到如此基础的问题都回答不出来的候选人,我通常会跟他告诉他正确答案,再问一些基础问题然后给他一些学习建议,最后很礼貌地送他走。

状况在我到达豌豆荚后有所改善。不是来应聘的人都非常优秀,而是我开始有感觉了。关键原因我觉得是我们不着急招人。现在我们还能应付手头上的工作,也没有快速扩张的需求,所以我们只有在遇到最合适的人选时才邀请他加入。我相信我前面的两位面试官做得足够好,然后我可以放胆地去考量「懂不懂」之外的其它方面。准确来说,这甚至不是一种考量,我只想知道我跟这个人一起工作是否会很愉快。我会以工作上遇到问题时同事跟同事间讨论的方式去跟他进行讨论,有可能是工作上实际遇到的问题,也有可能是刻意设计出来的有趣问题。(我觉得在一个充满活力的工作环境中,同事之间互相找些稀奇古怪的问题来讨论是很正常的,大家也会享受这类挑战。)如果我感觉跟他讨论问题是很愉快的过程,他能够提出有趣的想法,甚至能告诉我一些原本我不知道的事情,我肯定会给他很正面的面试评价。

作为面试者

换个角度来说,如果你作为面试者发现自己在面试的过程中能够进入这种状态,感觉如同跟同事讨论问题一样放松,那么你应该对面试结果充满信心。至少根据我个人的经验来说,感觉如同轻松愉快讨论的面试我都能得到面试官不错的评价。我明白要做到这一点很不容易,很多人在面试时都会很紧张,甚至会假设面试官一定会用各种难题来考自己,这种心态其实会把自己放在不利的位置上。我过去的经验是,我越不在乎的面试,往往我越能放松地跟面试官随便聊,结果反而越好。我很在乎的面试,反而有时候会高估面试官问题的难度,结果简单的问题没给出简单的答案,最后得到的评价反而不好。

在百度大厦的时候,我喜欢穿越二层平台,因为那里有很多小圆桌,也有很多人会选择在那里进行讨论或者面试。如果你对肢体语言有点最基础的了解,或者你就是在这方面有感觉,你会发现在那里很容易看得出哪些桌是同事间的讨论,哪些桌是在面试,以及谁是候选人。同事之间的讨论,往往大家都会很放松;面试的话,面试官也会很放松,但面试者通常处于比较紧张的状态,身体会略为前倾,就算不需要写字也会把手放在桌子上,用于支撑上半身的重量。对于有经验或者有感觉的面试官来说,这种肢体语言会传递一种不好的信号,那就是你太想要这份工作了,就算更深入的沟通后可能你会发现这份工作不适合你,但你还是会追求这个机会。


Read full article from Cat in Chinese: 理想的技术面试过程


程序员如何避免面试被坑? - 知乎



程序员如何避免面试被坑? - 知乎

昨天google面试,今天HR跟我说面试不理想。。。
觉得有一部分是自己水平真的不够吧,还有一部分是被坑了。
以我的水平一面过不去这到底要招怎么样的人啊!
(至少我觉得一面什么至少没问题的吧。毕竟还是算清华计算机系年级里写程序差不多前10%的人吧。计算机系!算叉院我被虐成马了。)
先说让我自我介绍,我不知道介绍什么,就说了我之前做过的项目。
然后他开始说,面试想考察我们的思路,具体结果不重要。
然后问了我一个非常简单的题。
我就回答他就用BFS就好了。
然后他开始问我,怎么存图?
我当时就慌了。
卧槽这什么问题。卧槽这是google面试么?
我说错什么了卧槽,这尼玛就算我答对了也跪了啊!
然后我就开始说考虑到一般社交网络是稀疏图所以用邻接表,然后说了说邻接表怎么存。。。
然后让我撸一个邻接表。让我撸了一个BFS。
我因为之前已经比较慌了就有点犯SB了。
后来他又问了我一个问题吧,大概是验证XX理论
我就说这也好办,BFS稍微改改就行
然后他问我真的吗?真的吗?
我想了5分钟告诉他好吧我错了应该对每个点验证一遍这个性质
卧槽我勒个擦我当时觉得自己一定是慌得要死了
但是我觉得这个问题就是我顺着他的思路稍微想了想然后就是稍微错了一点
我都是秒答的啊!
后来他问了我一道数论题
然后我根本做不出来
然后他说没指望我做出来就做暴力搜索就好了
然后开始说怎么优化
我脑抽根本没想到他说的是要做剪枝
因为我觉得这些都是显而易见的啊
然后整场面试就这么崩了

我想问问大家。。。我这样子算是被坑了么?
我自己这里面做的除了第一步就开始慌了还有什么问题么?
我在这次面试中应该如何应对是更好的?

===================和人讨论觉得是我自己自我介绍的时候就崩了,现在贴一下自己的自我介绍=================
我自己大二的时候实现过一个自己的小语言,然后后面在face++等一些公司实习过吧,个人比较喜欢C++,因为我觉得是静态类型的命令式语言里面最好hack的


===================又想到一件事=============
我感觉可能确实学OI的人对这方面是有很多思维上的问题的。
比如这个问题,我说是一个类似背包的问题,但是我没说真的用DP递推做啊。
虽然这个数量级有点大但是他确实可以抽象成DP啊!
我扯了一个名词叫记忆化搜索然后估计他也没理解。
(当然我以为他理解了我就没解释)
感觉是我把一些OI上常用的名词带了进去,就跪了。
OI讨论问题的风气一直是"这个用XX算法搞一下就好了"
然后被说的人觉得灵光一现就会做了
或者不会做就会问,为啥用这个算法?
那个人就会说数学解释
基本没人会聊到一些实现相关的东西
感觉这也是一部分吧
不应该把这种口气带到面试上来,一般给人讲题确实习惯了这种口气了

Read full article from 程序员如何避免面试被坑? - 知乎


淘宝面试的几个算法题 - 乐在其中/Leo在其中 - ITeye博客



淘宝面试的几个算法题 - 乐在其中/Leo在其中 - ITeye博客

一、给你1副扑克牌,你怎么发牌给4个人?

 我:首先扑克牌可以排序,其次,可以每次产生1个随机数,然后把该随机数对应的牌发出去,每次发的牌轮流给第1个人、第2个人。。。  奥,不对,这样可能导致已经发出去的牌再次被发出去!  (进入沉思~) 

他: Smilence...

我:(随即就给出可行的低效解) 可以这样嘛,首先声明,不考虑效率的前提下,可以这样做:把每张牌维护成一个结点,串联成一个链表。每次还是产生随机数,对当前牌的张数取余得到N,从单链表的头结点开始next指针访问N次,最终指向结点p,把p结点从链表中删除,并将对应的牌发给第(i++)%4+1个人;这样循环下去直到链表为空。

他:你这样做的确是可以实现发牌,可是效率低了点,那还有没有更好的方法呢?

1分钟过去了。。。

他:或许你可以考虑这样的算法,还是每次产生随机数,把对应的牌发出去,然后将此数字标记,以后再随机到这个数字了就不发,继续随机

我:(马上指出)那你发到最后的时候,岂不是一直在那里随机,很少有机会能随机到你想要的剩下的没发出去的那几个数字?

他:那也是的,那你有更好的方法吗? 

我:(好好思考一番后) 还可以这样做,把54张扑克牌维护成54个元素的char的数组,然后产生54个随机数,均对4取余,分别存入这个数组的54个单元中,然后遍历这个数组,对应数字为0的牌发给第1个人,对应数字为1的牌发给第2个人。。。  当然了,这样做,可能会有人多拿牌,有人少拿牌,强制从拿牌多的人那里抽取足量的牌。 哎,这样好像不大好办,还要算拿多少牌回来,容我再想想 

他:没啊,我觉得这个算法挺好的啊 

我:(想了半天,最终也没想出更好的) 

他:你这方法还不错的,算法复杂度O(n) 

我:那再最终总结下,

数组也不用了,维护一个计数值card_count,初试为1,表示第1张牌;

维护4个计数值count[1]、count[2]、count[3]、count[4],初始均为0,当相应的人被发到牌后就++,用来表示4个人各自当前的牌数; 

然后产生一个随机数r%=4,若r为n,则将第count张牌发给第n+1个人,count [n+1]++;

检查count[1]、count[2]、count[3]、count[4],哪个数达到了54/4+1就不再对那个人发牌,然后只产生其余3个人对应的随机数;

继续以上发牌,直到card_count达到54为止; 

他:满意地笑了笑

 

二、对于刚刚发牌的算法中用到的随机算法,你怎么定随机种子? 

我:随机种子一般都是采用当前系统时间或者设备编号之类的,采用系统时间是为了种子的随机性,保证伪随机数产生得比较"随机";用设备号的情况一般是多个设备跑同一个算法,都用到了随机数的时候,比如几台机器组网通信,要做到CSMA,需要随机退避,而因为随机数生成程序的随机是伪随机,如果这几台机器每次都随机到一样的数,那么当发生冲突的时候,他们再随机同样长度的时间来退避,结果还会是冲突,而因为这些机器的编号(比如IP地址)不一样,那么用来作为种子,就会各自采用不同组的伪随机数,就能达到随机退避的效果了!

他:恩,那你说的用系统时间作为种子,是怎么做到的呢?

我:系统调用啊,比如Windows编程,利用提供的

time

time()之类的API就可以得到当前系统时间了,因为每次运行的时间不同,所以产生的随机数也就比较"随机"了。

 

他:可以的,不过如果说这个发牌的程序需要运行很多很多次,而因为算法复杂度不高,所以每次都是很快就运行完了,第二次运行的时候,获得的系统时间基本上没变,那是不是每次产生的随机数都比较确定?不够"随机"?该怎么解决?

我:额。。。(好久以后)不清楚啊,既然时间没变的话,那当然没办法了,要不再结合其他可变的参数组合成为种子?

他:(自己都在那里偷笑了)哈哈哈,这还不简单,你每次发牌之间用一个延时函数隔开,保证系统时间有变化不久可以了?

我:- -b

 

三、给你十亿个数,如何找出其中最小的100个数?

我:(刚听完这个问题,我已经暗暗窃喜了,因为这个问题之前在其他地方已经看到过了) 于是镇定地回答,这个嘛,我知道,用堆排序就能迅速找出!

他:别告诉我堆排序,我要的是过程,整个过程,而不是一句提示。

我:好吧, 用这10亿个数中的前100个数先建立一个堆。(被打断)

他:别告诉我建一个堆,我要你建给我看,你怎么建!

我:。。。(只好拿出草稿纸,画了图比划给他看)建好了堆,而且是(大顶堆还是小顶堆?我思考了一下,马上说)大顶堆!,这样一来,堆顶就是这100个数中最大的那个了,是不是?

他:恩。

我:然后对于剩下的"10亿-100"个数,每个先和堆顶的元素比较大小,比堆顶大的数直接扔掉不要,比堆顶小的数把堆顶替换掉,然后进行一次堆的插入元素的算法,让新的100个数重新成为一个大顶堆,就这么继续下去,直到10亿-100个数都比较完,剩下还在堆里面的100个数就是10亿个数中最小的那100个了!

他:不错,那你觉得你的算法的复杂度咋样?

我:对于求n个数中的前m个最小的数而言,我先建堆,复杂度是O(m),而对于后面的(n-m)个数,最坏情况下每个数都要插入到堆中一次,堆中插入元素的算法时间复杂度最坏情况下是O(logm),所以最后是O(m)+(n-m)*O(logm)=O(m)+O((n-m)logm)=O((n-m)logm+m);

而如果是简单地先对10亿个数排序再取前100个的算法的话,即使用的是快排,那也是O(nlogn);

在n比m大这么多的前提下,显然算法复杂度不是一个数量级的~

 

四、有个10亿行*100列的二维字符数组,每行可以看成是一个字符串,怎么把这100亿个字符串按字典序排序?

我:&*¥(*palapala...

他:你理解错我的意思了,是这样的:¥……&&*)(

我:奥,这样啊,那可以这样做,因为10亿个字符串,内存肯定不够用,所以需要用到归并排序。

他:什么归并排序?

我:归并排序嘛,就是(*)&%%……

他:恩,然后呢?

我:反正有了归并排序后,只要先把每个分组各自排序,再归并就可以了,所以现在只讨论内存里可以放下的一个分组的排序,因为数量可能还是比较多,所以可以这样做:对于每一个字符串,维护其指针,根据每个字符串的第0列(也就是第一个元素)的大小对其指针进行排序,第0列相同的,就再比较第1列,第1列还是相同的,再比较第2列。。。

他:好吧。

 

面完了就差不多拿到了口头offer,我的处女面啊,虽然紧张了些,不过表现得还算可以了。

 

一个月后。。。

  

终于在一个不经意的时间才意识到了当初被面的各种问题的含义和用处!

首先是发牌问题,因为数据平台部门需要用到HTTP服务器,而这些HTTP服务器能够提供一种类似于反向代理的功能,所谓反向代理,和代理的功能刚相反。代理是将多个的,不同的用户的HTTP请求转交给WEB服务器,然后从WEB服务器端获得应答后,再把应答给用户;而反向代理则是将1个用户的HTTP请求分配给多个WEB服务器中的其中1个,也就是运行在WEB服务器集群前面的那个用于实现负载均衡和HTTP请求分配功能的那个。而这个反向代理的功能,就是类似于"发牌",只不过它发的牌是用户的HTTP请求罢了!

其次是大数据量的排序、搜索信息等问题,这个是因为数据平台部门每天都要接触海量的数据,需要把大量日志等信息拉到数据仓库Hadoop上进行处理、数据挖掘等,这个数据传输、转存以及挖掘的过程就需要对大数据量运算的了解。 


Read full article from 淘宝面试的几个算法题 - 乐在其中/Leo在其中 - ITeye博客


算法 | deadend



算法 | deadend

原题hihoCoder 1078 : 线段树的区间修改

题意

给定n个商品及其初始价格,存在两种操作:

  • 修改价格:修改区间[l, r]内的价格为新价格np
  • 查询价格:查询区间[l, r]内的总价格

题目中所有价格均大于0。

思路

线段树、区间更新。线段树每个节点维护一个标志位,实现其子节点的延迟更新,从而避免每次都更新操作都要对所涉及的节点全部更新一遍。


Read full article from 算法 | deadend


five-essential-phone-screen-questions - steveyegge2



five-essential-phone-screen-questions - steveyegge2

I've been on a lot of SDE interview loops lately where the candidate failed miserably: not-inclined votes all around, even from the phone screeners who brought the person in initially.

It's usually pretty obvious when the candidate should have been eliminated during the phone screens. Well, it's obvious in retrospect, anyway: during the interviews, we find some horrible flaw in the candidate which, had anyone thought to ask about it during the phone screen, would surely have disqualified the person.

But we didn't ask. So the candidate came in for interviews and wound up wasting everyone's time.

Antipatterns

I've done informal postmortems on at least a hundred phone screens, many of them my own. Whenever a candidate bombs the interviews, I want to know what went wrong with the screen. And guess what? A pattern has emerged. Two patterns, actually.

The first pattern is that for most failed phone screens, the candidate did most of the talking. The screener only asked about stuff on the candidate's resume, and the candidate was able to talk with passion and enthusiasm about this incredibly cool thing they did, blah blah blah, and the screener was duly impressed.

That's how many/most phone screens go wrong.

The right way to do a phone screen is to do most of the talking, or at least the driving. You look for specific answers, and you guide the conversation along until you've got the answer or you've decided the candidate doesn't know it. Whenever I forget this, and get lazy and let the candidate drone on about their XML weasel-pin connector project, I wind up bringing in a dud.

The second pattern is that one-trick ponies only know one trick. Candidates who have programmed mostly in a single language (e.g. C/C++), platform (e.g. AIX) or framework (e.g. J2EE) usually have major, gaping holes in their skills lineup. These candidates will fail their interviews here because our interviews cover a broad range of skill areas.

These two phone screen (anti-)patterns are related: if you only ask the candidate about what they know, you've got a fairly narrow view of their abilities. And you're setting yourself up for a postmortem on your phone screen.

Acid Tests

In an effort to make life simpler for phone screeners, I've put together this list of Five Essential Questions that you need to ask during an SDE screen. They won't guarantee that your candidate will be great, but they will help eliminate a huge number of candidates who are slipping through our process today.

These five areas are litmus tests -- very good ones. I've chosen them based on the following criteria:

1) They're universal - every programmer needs to know them, regardless of experience, so you can use them in all SDE phone screens, from college hires through 30-year veterans.

2) They're quick - they're areas that you can probe very quickly, without eating too much into your phone-screen time. Each area can be assessed with 1 to 5 minutes of "weeder questions", and each area has almost unlimited weeder questions to choose from.

3) They're predictors - there are certain common "SDE profiles" that are easy to spot because they tend to fail (and I mean really fail) in one or more of these five areas. So the areas are amazingly good at weeding out bad candidates.

You have to probe all five areas; you can't skip any of them. Each area is a proxy for a huge body of knowledge, and failing it very likely means failing the interviews, even though the candidate did fine in the other areas.

Without further ado, here they are: The Five Essential Questions for the first phone-screen with an SDE candidate:

1) Coding. The candidate has to write some simple code, with correct syntax, in C, C++, or Java.
2) OO design. The candidate has to define basic OO concepts, and come up with classes to model a simple problem.
3) Scripting and regexes. The candidate has to describe how to find the phone numbers in 50,000 HTML pages.
4) Data structures. The candidate has to demonstrate basic knowledge of the most common data structures.
5) Bits and bytes. The candidate has to answer simple questions about bits, bytes, and binary numbers.

Please understand:   what I'm looking for here is a total vacuum in one of these areas. It's OK if they struggle a little and then figure it out. It's OK if they need some minor hints or prompting. I don't mind if they're rusty or slow. What you're looking for is candidates who are utterly clueless, or horribly confused, about the area in question.

For example, you may find a candidate who decides that a Vehicle class should be a subclass of ParkingGarage, since garages contain cars. This is just busted, and it's un-fixable in any reasonable amount of training time.

Or a candidate might decide, when asked to search for phone numbers in a bunch of text files, to write a 2000-line C++ program, at which point you discover they've never heard of "grep", or at least never used it.

When a candidate is totally incompetent in one of these Big Five areas, the chances are very high that they'll bomb horribly when presented with our typical interview questions. Last week I interviewed an SDE-2 candidate who made both of the mistakes above (a vehicle inheriting from garage, and the 2000-line C++ grep implementation.) He was by no means unusual, even for the past month. We've been bringing in many totally unqualified candidates.

The rest of this document describes each area in more detail, and gives example questions, and solutions.


Read full article from five-essential-phone-screen-questions - steveyegge2


Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts