题目
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
167. Two Sum II - Input array is sorted
题目
Given an array of integers that is already sorted in ascending order, 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 less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
程序员能力矩阵
转自Programmer Competency Matrix
注意:每个层次的知识都是渐增的，位于层次n，也蕴涵了你需了解所有低于层次n的知识。
计算机科学 Computer Science
Working with someone who has a good topcoder ranking would be an unbelievable piece of luck!
有一个黑客排行榜排名靠前的同事将会是一件无比幸运的事情。
| 2^n (Levenl 0) | n^2 (Level 1) | n(Level 2) | log(n) (Level 3) | |
|---|---|---|---|---|
| 数据结构 | 不知道数组和链表的差异 | 能够解释和使用数组，链表，字典等，并且能够用于实际的编程任务。 | 了解基本数据结构时间和空间的折中，比如数组vs 链表，能够解释如何实现哈希表和处理冲突，了解优先队列及其实现。 | 高等的数据结构的知识，比如B-树、二项堆、斐波那契堆、AVL树、红黑树、伸展树、跳跃表以及前缀树等。 |
| 算法 | 不能够找出一个数组各数的平均值(这令人难以置信，但是我的确在应聘者中遇到过) | 基本的排序，搜索和数据的遍历和检索算法。 | 树，图，简单的贪婪算法和分而治之算法，能够适度了解矩阵该层的含义。 | 能够辨识和编写动态规划方案，良好的图算法知识，良好的数值估算的知识，能够辨别NP问题等。 |
| 编程体系 | 不知道何为编译器、链接器和解释器。 | 对编译器、链接器、解释器有基本的了解。知道什么是汇编代码以及在硬件层如何工作。有一些虚拟内存和分页知识。 | 了解内核模式vs用户模式,多线程，同步原语以及它们如何实现，能够阅读汇编代码。了解网络如何工作，了解网络协议和socket级别编程。 | 了解整个程序堆栈、硬件(CPU+内存+中断+微码)、二进制代码、汇编、静态和动态链接、编码、解释、JIT（just-in-time）编译、内存碎片回收、堆、栈、存储器编址… |
292. Nim Game
题目
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
8. String to Integer (atoi)
题目
Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (2^31 − 1) or INT_MIN (−2^31 ) is returned.
6. ZigZag Conversion
题目
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)
1 | P A H N |
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
458. Poor Pigs
题目
There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.
Answer this question, and write an algorithm for the follow-up general case.
Follow-up:
If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the “poison” bucket within p minutes? There is exact one bucket with poison.