http://www.geeksforgeeks.org/find-nth-item-set-formed-sum-two-arrays/
http://www.geeksforgeeks.org/count-perfect-divisors-number/
http://www.geeksforgeeks.org/check-if-two-arrays-are-equal-or-not/
http://www.geeksforgeeks.org/make-n-using-1s-2s-minimum-number-terms-multiple-k/
http://www.geeksforgeeks.org/print-words-together-set-characters/
http://www.geeksforgeeks.org/sum-two-large-numbers/
http://www.geeksforgeeks.org/difference-of-two-large-numbers/
http://www.geeksforgeeks.org/maximum-consecutive-repeating-character-string/
http://www.geeksforgeeks.org/replace-occurrences-string-ab-c-without-using-extra-space/
http://www.geeksforgeeks.org/find-difference-between-sums-of-two-diagonals/
https://lxia.gitbooks.io/cmore/content/51_advantages_of_bst_over_hash_table.html
http://www.ahathinking.com/archives/123.html
美团2016校招笔试问题总结
给你一个字符串，这个字符串只能有两种操作左循环移动1位或者右循环移动1位，比如”abcde”进行左循环1位为bcdea,右循环1位eabcd。求经过多少次，操作返回原字符。
左循环操作和右循环操作是相反的，所以结果要么全部通过左循环操作要么全部通过右循环操作。所以分别用一个for循环即可判断，并且返回最小的。
当什么情况下是不存在的呢？我们可以弄一个Set保存每次的结果，如果这次操作后的结果不存在于Set中那么将其加入，如果存在，那么就是存在循环。向这个方向的操作即将是个循环不可能得到结果。
很简单的题目，一时短路。没想到左循环和右循环是相反的。不知道为什么没想到呢！？
1.你先画出一个栈，能用数组实现？
这个很简单，一下子就可以画出来了。就是最常规的栈结构。
然后接着问题来了，你能用链表实现它？
这个也是可以的，我们可以用双向链表，当然单向的也是可以的，一个用于指向peek另一个指向peek后面一个。
http://buttercola.blogspot.com/2016/06/align-rectangle.html
Question:给你a list of rectangle 让你把它们放在一个坐标平面上并align，从左往右放矩形，最右边有一个边界，不能超界，每个矩形提供getLength(), getWidth()，要保证每一行矩形的中心都在一条直线上，一行放不满另起一行，但是不能有overlap.
Solution:
基本的idea是首先遍历所有的rectangle, 建立一个HashMap<Integer, List<Rectangle>>, 把所有相同height的rectangle 都 group 到一起。所以这个map, key 存的是 height, value是具有相同height的rectangle。这样做的目的是相同height的rectangle需要排列在一行，因为题目要求每一行矩形的中心都在一条直线上。
然后遍历这个map, 并且开始排列矩形。因为每一行的宽度有限，相同高度的矩形可能放不到一行里面。这里的规则是尽量用最少的行数放下这些矩形。我们这里可以采取一个贪心的算法。首先对于一个高度的所有rectangle, 可以先按照宽度从小到大排序。然后我们维护每一行剩下的宽度，然后从这个list里面选择比这个剩余宽度小的最宽的矩形。这种贪心的策略不一定总能找到最小的行数存下所有的矩形，但应该大部分时候都能work.
给定一个字符串，找到最长的包含最多k个不同字符的子串，输出最长子串的长度即可。
Given two sorted arrays, we can get a set of sums(add one element from the first and one from second). Find the N’th element in the set.
int calculateSetOfSum(int arr1[], int size1, int arr2[], int size2, int N){ // Insert each pair sum into set. Note that a set // stores elements in sorted order and unique elements set<int> s; for (int i=0 ; i < size1; i++) for (int j=0; j < size2; j++) s.insert(arr1[i]+arr2[j]); // If set has less than N elements if (s.size() < N) return -1; // Find N'tb item in set and return it set<int>::iterator it = s.begin(); for (int count=1; count<N; count++) it++; return *it;}
Given a number n, count total perfect divisors of n. Perfect divisors are those divisors which are square of some integer. For example a perfect divisor of 8 is 4.
Time complexity: O(sqrt(n))
bool isPerfectSquare(int n){ int sq = (int) sqrt(n); return (n == sq * sq);}// Returns count all perfect divisors of nint countPerfectDivisors(int n){ // Initialize result int count = 0; // Consider every number that can be a divisor // of n for (int i=1; i*i <= n; ++i) { // If i is a divisor if (n%i == 0) { if (isPerfectSquare(i)) ++count; if (n/i != i && isPerfectSquare(n/i)) ++count; } } return count;}
Efficient approach (For large number of queries)
- Create a list of n consecutive integers from 1 to n:(1, 2, 3, …, n)
- Initially, let d be 2, the first divisor
- Starting from 4(square of 2) increment all the multiples of 4 by 1 in perfectDiv[] array, as all these multiples contain 4 as perfect divisor. These numbers will be 4d, 8d, 12d, … etc
- Repeat the 3rd step for all other numbers. The final array of perfectDiv[] will contain all the count of perfect divisors from 1 to n
// Pre-compute counts of all perfect divisors// of all numbers upto MAX.void precomputeCounts(){ for (int i=1; i*i < MAX; ++i) { // Iterate through all the multiples of i*i for (int j=i*i; j < MAX; j += i*i) // Increment all such multiples by 1 ++perfectDiv[j]; }}// Returns count of perfect divisors of n.int countPerfectDivisors(int n){ return perfectDiv[n];}http://www.geeksforgeeks.org/check-if-two-arrays-are-equal-or-not/
Given two given arrays of equal length, the task is to find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though.
Note : If there are repetitions, then counts of repeated elements must also be same for two array to be equal.
public static boolean areEqual(int arr1[], int arr2[]) { int n = arr1.length; int m = arr2.length; // If lengths of arrays are not equal if (n != m) return false; // Store arr1[] elements and their counts in // hash map Map<Integer, Integer> map = new HashMap<Integer, Integer>(); int count = 0; for (int i = 0; i < n; i++) { if(map.get(arr1[i]) == null) map.put(arr1[i], 1); else { count = map.get(arr1[i]); count ++; map.put(arr1[i], count); } } // Traverse arr2[] elements and check if all // elements of arr2[] are present same number // of times or not. for (int i = 0; i < n; i++) { // If there is an element in arr2[], but // not in arr1[] if (!map.containsKey(arr2[i])) return false; // If an element of arr2[] appears more // times than it appears in arr1[] if (map.get(arr2[i]) == 0) return false; count = map.get(arr2[i]); --count; map.put(arr2[i], count); } // again traverse arr2 to ensure that count // for all elelments become zero. for(int i = 0; i < n; i++) { if(map.get(arr2[i]) > 0) return false; } return true; }
Given two positive integer n and k. n can be represented as the sum of 1s and 2s in many ways, using multiple numbers of terms. The task is to find the minimum number of terms of 1s and 2s use to make the sum n and also number of terms must be multiple of k. Print “-1”, if no such number of terms exists.
Observe, the maximum number of terms used to represent n as the sum of 1s and 2s is n, when 1 are added n number of times. Also, the minimum number of terms will be n/2 times of 2s and n%2 times 1s are added. So, iterate from minimum number of terms to maximum number of terms and check if there is any multiple of k.
int minMultipleK(int n, int k){ // Minimum number of terms required to make // sum n using 1s and 2s. int min = (n / 2) + (n % 2); // Iterate from Minimum to maximum to find // multiple of k. Maximum number of terns is // n (Sum of all 1s) for (int i = min; i <= n; i++) if (i % k == 0) return i; return -1;}
Given a list of words with lower cases. Implement a function to find all Words that have the same unique character set .
// contains all unique characters of given string// in sorted order.string getKey(string &str){ bool visited[MAX_CHAR] = { false }; // store all unique characters of current // word in key for (int j = 0; j < str.length(); j++) visited[str[j] - 'a'] = true ; string key = ""; for (int j=0; j < MAX_CHAR; j++) if (visited[j]) key = key + (char)('a'+j); return key;}// Print all words together with same character sets.void wordsWithSameCharSet(string words[], int n){ // Stores indexes of all words that have same // set of unique characters. unordered_map <string, vector <int> > Hash; // Traverse all words for (int i=0; i<n; i++) { string key = getKey(words[i]); Hash[key].push_back(i); } // print all words that have the same unique character set for (auto it = Hash.begin(); it!=Hash.end(); it++) { for (auto v=(*it).second.begin(); v!=(*it).second.end(); v++) cout << words[*v] << ", "; cout << endl; }}http://www.geeksforgeeks.org/sum-two-large-numbers/
Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these two numbers.
The idea is based on school mathematics. We traverse both strings from end, one by one add digits and keep track of carry. To simplify the process, we do following:
1) Reverse both strings.
2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10.
3) Finally reverse the result.
1) Reverse both strings.
2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10.
3) Finally reverse the result.
string findSum(string str1, string str2){ // Before proceeding further, make sure length // of str2 is larger. if (str1.length() > str2.length()) swap(str1, str2); // Take an empty string for storing result string str = ""; // Calculate lenght of both string int n1 = str1.length(), n2 = str2.length(); // Reverse both of strings reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end()); int carry = 0; for (int i=0; i<n1; i++) { // Do school mathematics, compute sum of // current digits and carry int sum = ((str1[i]-'0')+(str2[i]-'0')+carry); str.push_back(sum%10 + '0'); // Calculate carry for next step carry = sum/10; } // Add remaining digits of larger number for (int i=n1; i<n2; i++) { int sum = ((str2[i]-'0')+carry); str.push_back(sum%10 + '0'); carry = sum/10; } // Add remaining carry if (carry) str.push_back(carry+'0'); // reverse resultant string reverse(str.begin(), str.end()); return str;}
Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find difference of these two numbers.
This is simple based on school mathematics. We traverse both strings from end, one by one subtract digits.
1) Reverse both strings.
2) Keep subtracting digits one by one from 0’th index (in reversed strings) to end of smaller string, append the diff if it’s positive to end of result. If difference(diff) is negative then add 10 and keep track of carry as 1 if it’s positive then carry is 0.
3) Finally reverse the result.
1) Reverse both strings.
2) Keep subtracting digits one by one from 0’th index (in reversed strings) to end of smaller string, append the diff if it’s positive to end of result. If difference(diff) is negative then add 10 and keep track of carry as 1 if it’s positive then carry is 0.
3) Finally reverse the result.
bool isSmaller(string str1, string str2){ // Calculate lengths of both string int n1 = str1.length(), n2 = str2.length(); if (n1 < n2) return true; if (n2 < n1) return false; for (int i=0; i<n1; i++) if (str1[i] < str2[i]) return true; else if (str1[i] > str2[i]) return false; return false;}// Function for find difference of larger numbersstring findDiff(string str1, string str2){ // Before proceeding further, make sure str1 // is not smaller if (isSmaller(str1, str2)) swap(str1, str2); // Take an empty string for storing result string str = ""; // Calculate length of both string int n1 = str1.length(), n2 = str2.length(); // Reverse both of strings reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end()); int carry = 0; // Run loop till small string length // and subtract digit of str1 to str2 for (int i=0; i<n2; i++) { // Do school mathematics, compute difference of // current digits int sub = ((str1[i]-'0')-(str2[i]-'0')-carry); // If subtraction is less then zero // we add then we add 10 into sub and // take carry as 1 for calculating next step if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str.push_back(sub + '0'); } // subtract remaining digits of larger number for (int i=n2; i<n1; i++) { int sub = ((str1[i]-'0') - carry); carry = 0; str.push_back(sub + '0'); } // reverse resultant string reverse(str.begin(), str.end()); return str;}
Given a string, the task is to find maximum consecutive repeating character in string.
Note : We do not need to consider overall count, but the count of repeating that appear at one place.
An efficient solution is to run only one loop. The idea is to reset the count as 1 as soon as we find a character not matching with previous.
char maxRepeating(string str){ int n = str.length(); int count = 0; char res = str[0]; int cur_count = 1; // Traverse string except last character for (int i=0; i<n; i++) { // If current character matches with next if (i < n-1 && str[i] == str[i+1]) cur_count++; // If doesn't match, update result // (if required) and reset count else { if (cur_count > count) { count = cur_count; res = str[i]; } cur_count = 1; } } return res;}
Given a string str that may contain one more occurrences of “AB”. Replace all occurrences of “AB” with “C” in str.
An efficient solution is to keep track of two indexes, one for modified string (i in below code) and other for original string (j in below code). If we find “AB” at current index j, we increment j by 2 and i by 1. Otherwise we increment both and copy character from j to i.
void translate(char* str){ int len = strlen(str); if (len < 2) return; int i = 0; // Index in modified string int j = 0; // Index in original string // Traverse string while (j < len-1) { // Replace occurrence of "AB" with "C" if (str[j] == 'A' && str[j+1] == 'B') { // Increment j by 2 j = j + 2; str[i++] = 'C'; continue; } str[i++] = str[j++]; } if (j == len-1) str[i++] = str[j]; // add a null character to terminate string str[i] = '\0';}http://www.geeksforgeeks.org/find-difference-between-sums-of-two-diagonals/
Given a matrix of n X n. The task is to calculate the absolute difference between the sums of its diagonal.
We can optimize above solution to work in O(n) using the patterns present in indexes of cells.
int difference(int arr[][MAX], int n){ // Initialize sums of diagonals int d1 = 0, d2 = 0; for (int i = 0; i < n; i++) { d1 += arr[i][i]; d2 += arr[i][n-i-1]; } // Absolute difference of the sums // across the diagonals return abs(d1 - d2);}https://lxia.gitbooks.io/cmore/content/51_advantages_of_bst_over_hash_table.html
Hash Table supports following operations in Θ(1) time. 1) Search 2) Insert 3) Delete The time complexity of above operations in a self-balancing Binary Search Tree (BST) (like Red-Black Tree, AVL Tree, Splay Tree, etc) is O(Logn). So Hash Table seems to beating BST in all common operations. When should we prefer BST over Hash Tables, what are advantages. Following are some important points in favor of BSTs.
- We can get all keys in sorted order by just doing Inorder Traversal of BST. This is not a natural operation in Hash Tables and requires extra efforts.
- Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs. Like sorting, these operations are not a natural operation with Hash Tables.
- BSTs are easy to implement compared to hashing, we can easily implement our own customized BST. To implement Hashing, we generally rely on libraries provided by programming languages.
- With BSTs, all operations are guaranteed to work in O(Logn) time. But with Hashing, Θ(1) is average time and some particular operations may be costly, especially when table resizing happens.
Given an infinite stream of characters and a list of strings
words, create a function that call an external api alert() when a word in d is recognized during the processing of the stream.
Example:
words = ["ok", "test", "one", "try", "trying"]stream = "abcokdeftrying..........."alert() is called three times (k, y and g).
Note that
Using triesalert() is called once at most for each character in the stream.http://www.ahathinking.com/archives/123.html
题：从一个字符串中找到一个连续子串，该子串中任何两个字符不能相同，求子串的最大长度并输出一条最长不重复子串。
本节从最直接的方法逐步优化，渐进探索了四种实现方式，并最终找到时间复杂度为O(N)，辅助空间为常数的方案，内容如下：
==基本算法 使用Hash==
==DP方案==
==DP + Hash 方案==
==DP + Hash 优化方案==
基本算法 使用Hash
要求子串中的字符不能重复，判重问题首先想到的就是hash，寻找满足要求的子串，最直接的方法就是遍历每个字符起始的子串，辅助hash，寻求最长的不重复子串，由于要遍历每个子串故复杂度为O(n^2)，n为字符串的长度，辅助的空间为常数hash[256]。
美团2016校招笔试问题总结
给你一个字符串，这个字符串只能有两种操作左循环移动1位或者右循环移动1位，比如”abcde”进行左循环1位为bcdea,右循环1位eabcd。求经过多少次，操作返回原字符。
左循环操作和右循环操作是相反的，所以结果要么全部通过左循环操作要么全部通过右循环操作。所以分别用一个for循环即可判断，并且返回最小的。
当什么情况下是不存在的呢？我们可以弄一个Set保存每次的结果，如果这次操作后的结果不存在于Set中那么将其加入，如果存在，那么就是存在循环。向这个方向的操作即将是个循环不可能得到结果。
很简单的题目，一时短路。没想到左循环和右循环是相反的。不知道为什么没想到呢！？
1.你先画出一个栈，能用数组实现？
这个很简单，一下子就可以画出来了。就是最常规的栈结构。
然后接着问题来了，你能用链表实现它？
这个也是可以的，我们可以用双向链表，当然单向的也是可以的，一个用于指向peek另一个指向peek后面一个。
http://buttercola.blogspot.com/2016/06/align-rectangle.html
Question:给你a list of rectangle 让你把它们放在一个坐标平面上并align，从左往右放矩形，最右边有一个边界，不能超界，每个矩形提供getLength(), getWidth()，要保证每一行矩形的中心都在一条直线上，一行放不满另起一行，但是不能有overlap.
Solution:
基本的idea是首先遍历所有的rectangle, 建立一个HashMap<Integer, List<Rectangle>>, 把所有相同height的rectangle 都 group 到一起。所以这个map, key 存的是 height, value是具有相同height的rectangle。这样做的目的是相同height的rectangle需要排列在一行，因为题目要求每一行矩形的中心都在一条直线上。
然后遍历这个map, 并且开始排列矩形。因为每一行的宽度有限，相同高度的矩形可能放不到一行里面。这里的规则是尽量用最少的行数放下这些矩形。我们这里可以采取一个贪心的算法。首先对于一个高度的所有rectangle, 可以先按照宽度从小到大排序。然后我们维护每一行剩下的宽度，然后从这个list里面选择比这个剩余宽度小的最宽的矩形。这种贪心的策略不一定总能找到最小的行数存下所有的矩形，但应该大部分时候都能work.
给定一个字符串，找到最长的包含最多k个不同字符的子串，输出最长子串的长度即可。
Example：
给出字符串”eceba”，k = 2
输出答案3，最长包含最多2个不同字符的子串为”ece”
给出字符串”eceba”，k = 2
输出答案3，最长包含最多2个不同字符的子串为”ece”
最暴力的做法是穷举所有可能的子串，一共有n^2级别个不同的子串，然后对于每一个子串统计有多少不同的字符，如果少于k个就更新答案。这是一个三重循环的穷举，复杂度是O(n^3)。聪明的读者肯定想到了第二重和第三重循环可以合并，因为之前的统计信息可以继续使用而不需要每一次重新统计。这样的话穷举子串的开始位置和结束位置，复杂度是O(n^2)。如果在面试时提出了这个算法，面试官首先会表示认同，然后希望你进行优化。我们来看看如何进行优化。
在统计的过程中我们可以发现，当穷举的开始位置改变时我们会选择重新统计，但其实当开始位置改变时，我们之前记录的大部分信息都是有用的，我们只需在原有的统计结果上稍作修改。我们在两层for循环的时候其实会发现我们内层的fo循环其实并不需要每次都再重复遍历。比如外层for循环指针i每次向前移动变成i+1的时候，内层for循环的j没必要每次都退回到i的位置，其实是可以保留在j的位置不变的。因为可以证明对于从i+1到j-1这些情况都不会出现重复的元素，所以我们只用考虑从i+1到j就可以了。
分析一下这个算法的时间复杂度，虽然我们会用到两重循环（请看参考程序），但是因为这两个指针只增不减，每次循环指针增加1，因此while循环总共只会进入n次（n = s.length( ))，所以时间复杂度是O(n)。
这是一道很有区分度的题目，有O(n^3),O(n^2),O(nlogn)（follow up）,O(n)时间复杂度的做法。先提出一种可行算法，通过一步步分析、优化，最后提出O(n)的最优算法并完成代码就可以达到hire的程度。
找到一种不需要构造二叉树的方法。
For example：
“9,3,4,#,#,1,#,#,2,#,6,#,#”
是下面这颗二叉树的先序遍历。其中＃代表空节点。
For example：
“9,3,4,#,#,1,#,#,2,#,6,#,#”
是下面这颗二叉树的先序遍历。其中＃代表空节点。
一棵合法的二叉树去掉某个叶子节点后仍是合法的二叉树。在给出的字符序列中，叶子节点有很明显的特征，即叶子节点之后一定紧跟两个空节点＃。通过不断的把number,#,#的子串缩成空节点#(把number,#,#子串替换为#)，如果最后字符序列可以缩短到只有一个字符＃，那它就是我们要找的合法的先序遍历了。
此题可以用暴力搜索解决，但线性复杂度算法也不难想到。写出以上解法，可以达到hire, 而如果用stack解法，则可以 storng hire.
public boolean isValidSerialization(String preorder) { String s = preorder; boolean flag = true; while (s.length() > 1) { int index = s.indexOf(",#,#"); if (index < 0){ flag = false; break; } int start = index; while (start > 0 && s.charAt(start - 1) != ',') { start --; } if (s.charAt(start) == '#') { flag = false; break; } s = s.substring(0, start) + s.substring(index + 3); } if (s.equals("#") && flag) return true; else return false; }
