http://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/
http://www.geeksforgeeks.org/maximum-difference-between-frequency-of-two-elements-such-that-element-having-greater-frequency-is-also-greater/
Method 2 (Use Hashing and Sorting):
The idea is to find all the distinct elements and store in an array, say dist[ ]. Sort the distinct element array dist[] in increasing order. Now for any distinct element at index i, for all index j such that i > j > 0, find the element between index 0 to i-1 having minimum frequency. We can find frequency of an element in same way as method 1, i.e., storing frequencies in a hash table.
So do this for all i and find the maximum difference. To find the minimum frequency for all i maintain a prefix minimum.
http://www.geeksforgeeks.org/find-if-n-can-be-written-as-product-of-k-numbers/
http://www.geeksforgeeks.org/sort-array-converting-elements-squares/
Given a array of both positive and negative integers ‘arr[]’ which are sorted. Task is to sort square of the numbers of the Array.
http://www.geeksforgeeks.org/sum-dependencies-graph/
http://www.geeksforgeeks.org/seeds-of-a-number/
Maximize sum of consecutive differences in a circular array
http://www.geeksforgeeks.org/count-all-pairs-of-an-array-which-differ-in-k-bits/
面试题应该来源实践
How to generate all subarrays?
We can run two nested loops, the outer loop picks starting element and inner loop considers all elements on right of the picked elements as ending element of subarray.
We can run two nested loops, the outer loop picks starting element and inner loop considers all elements on right of the picked elements as ending element of subarray.
void subArray(int arr[], int n){ // Pick starting point for (int i=0; i <n; i++) { // Pick ending point for (int j=i; j<n; j++) { // Print subarray between current starting // and ending points for (int k=i; k<=j; k++) cout << arr[k] << " "; cout << endl; } }}http://www.geeksforgeeks.org/maximum-difference-between-frequency-of-two-elements-such-that-element-having-greater-frequency-is-also-greater/
Given an array of n positive integers with many repeating elements. The task is to find maximum difference between the frequency of any two different elements, such that the element with greater frequency is also greater in value than the second integer.
The naive approach can be, find the frequency of each element and for each element find the element having lesser value and lesser frequency than the current element.
int maxdiff(int arr[], int n){ unordered_map<int, int> freq; // Finding the frequency of each element. for (int i = 0; i < n; i++) freq[arr[i]]++; int ans = 0; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq[arr[i]] > freq[arr[j]] && arr[i] > arr[j] ) ans = max(ans, freq[arr[i]]-freq[arr[j]]); else if (freq[arr[i]] < freq[arr[j]] && arr[i] < arr[j] ) ans = max(ans, freq[arr[j]]-freq[arr[i]]); } } return ans;}The idea is to find all the distinct elements and store in an array, say dist[ ]. Sort the distinct element array dist[] in increasing order. Now for any distinct element at index i, for all index j such that i > j > 0, find the element between index 0 to i-1 having minimum frequency. We can find frequency of an element in same way as method 1, i.e., storing frequencies in a hash table.
So do this for all i and find the maximum difference. To find the minimum frequency for all i maintain a prefix minimum.
int maxdiff(int arr[], int n){ unordered_map<int, int> freq; int dist[n]; // Finding the frequency of each element. int j = 0; for (int i = 0; i < n; i++) { if (freq.find(arr[i]) == freq.end()) dist[j++] = arr[i]; freq[arr[i]]++; } // Sorting the distinct element sort(dist, dist + j); int min_freq = n+1; // Iterate through all sorted distinct elements. // For each distinct element, maintaining the // element with minimum frequency than that // element and also finding the maximum // frequency difference int ans = 0; for (int i=0; i<j; i++) { int cur_freq = freq[dist[i]]; ans = max(ans, cur_freq - min_freq); min_freq = min(min_freq, cur_freq); } return ans;}
Given a positive number n, we need to print exactly k positive numbers (all greater than 1) such that product of those k numbers is n. If there doesn’t exist such k numbers, print -1 . If there are many possible answer you have to print one of that answer where k numbers are sorted.
void kFactors(int n, int k){ // A vector to store all prime factors of n vector<int> P; // Insert all 2's in vector while (n%2 == 0) { P.push_back(2); n /= 2; } // n must be odd at this point // So we skip one element (i = i + 2) for (int i=3; i*i<=n; i=i+2) { while (n%i == 0) { n = n/i; P.push_back(i); } } // This is to handle when n > 2 and // n is prime if (n > 2) P.push_back(n); // If size(P) < k, k factors are not possible if (P.size() < k) { cout << "-1" << endl; return; } // printing first k-1 factors for (int i=0; i<k-1; i++) cout << P[i] << ", "; // calculating and printing product of rest // of numbers int product = 1; for (int i=k-1; i<P.size(); i++) product = product*P[i]; cout << product << endl;}http://www.geeksforgeeks.org/sort-array-converting-elements-squares/
Given a array of both positive and negative integers ‘arr[]’ which are sorted. Task is to sort square of the numbers of the Array.
- Divide the array into two part “Negative and positive “.
- Use merge function to merge two sorted arrays into a single sorted array.
public static void sortSquares(int arr[]) { int n = arr.length; // first dived array into part negative and positive int k; for(k = 0; k < n; k++) { if(arr[k] >= 0) break; } // Now do the same process that we learn // in merge sort to merge to two sorted array // here both two half are sorted and we traverse // first half in reverse meaner because // first half contain negative element int i = k-1; // Initial index of first half int j = k; // Initial index of second half int ind = 0; // Initial index of temp array int[] temp = new int[n]; while(i >= 0 && j < n) { if(arr[i] * arr[i] < arr[j] * arr[j]) { temp[ind] = arr[i] * arr[i]; i--; } else{ temp[ind] = arr[j] * arr[j]; j++; } ind++; } while(i >= 0) { temp[ind++] = arr[i] * arr[i]; i--; } while(j < n) { temp[ind++] = arr[j] * arr[j]; j++; } // copy 'temp' array into original array for (int x = 0 ; x < n; x++) arr[x] = temp[x]; }
Simple solution is to first convert each array elements into its square and than apply any “O(nlogn)” sorting algorithm to sort the array elements.
http://www.geeksforgeeks.org/a-permutation-where-each-element-indicates-either-number-of-elements-before-or-after-it/
Given an array of n elements. The task is to check whether a permutation of given array exists, such that each element indicate number of element present before or after it. Print “Yes” if exists, else print “No”.
The idea is to use hashing. Observe, for each index i in the array, arr[i] can have value i or n – i. We traverse the given array and find the frequency of each element present in the array. Now, for each index i, check availability of value i and n-i and accordingly decrement the frequency. Note that an item with value i can either go to index i or n-i-1. Similarly, an item with value n-i-1 can go to either index i or n-i-1.
{ int n = arr.length; int[] freq = new int[n]; // Finding the frequency of each number. for (int i = 0; i < n; i++) freq[arr[i]]++; for (int i = 0; i < n; i++) { // Try to find number of element before // the current index. if (freq[i]!= 0) freq[i]--; // Try to find number of element after // the current index. else if (freq[n-i-1]!= 0) freq[n-i-1]--; // If no such number find, return false. else return false; } return true; }http://www.geeksforgeeks.org/sum-dependencies-graph/
Given a directed and connected graph with n nodes. If there is an edge from u to v then u depends on v. Our task was to find out the sum of dependencies for every node.
Idea is to check adjacency list and find how many edges are there from each vertex and return the total number of edges.
void addEdge(vector <int> adj[], int u,int v){ adj[u].push_back(v);}// find the sum of all dependenciesint findSum(vector<int> adj[], int V){ int sum = 0; // just find the size at each vector's index for (int u = 0; u < V; u++) sum += adj[u].size(); return sum;}
A Seed of a number n is a number x such that multiplication of x with its digits is equal to n. The task is to find all seeds of a given number n. If no seed exists, then print the same.
The idea is to traverse all numbers from 1 to n/2. For every number being traversed, find product of digits with the number. An important optimization done in below program is to avoid re-computations of digit products. We store the products in an array. If a product has already been computed, we return it, else we compute it.
We can further optimize above code. The idea is to make a call to getDigitProduct(i) only if i is divisible by n
const int MAX = 10000;int prodDig[MAX];// Stores product of digits of x in prodDig[x]int getDigitProduct(int x){ // If x has single digit if (x < 10) return x; // If digit product is already computed if (prodDig[x] != 0) return prodDig[x]; // If digit product is not computed before. int prod = (x % 10) * getDigitProduct(x/10); return (prodDig[x] = prod);}// Prints all seeds of nvoid findSeed(int n){ // Find all seeds using prodDig[] vector<int> res; for (int i=1; i<=n/2; i++) if (i*getDigitProduct(i) == n) res.push_back(i); // If there was no seed if (res.size() == 0) { cout << "NO seed exists\n"; return; } // Print seeds for (int i=0; i<res.size(); i++) cout << res[i] << " ";}
Given an array of n elements. Consider array as circular array i.e element after an is a1. The task is to find maximum sum of the difference between consecutive elements with rearrangement of array element allowed i.e after rearrangement of element find |a1 – a2| + |a2 – a3| + …… + |an – 1 – an| + |an – a1|.
The idea is to use Greedy Approach and try to bring elements having greater difference closer.
Consider the sorted permutation of the given array a1, a1, a2,…., an – 1, an such that a1 < a2 < a3…. < an – 1 < an.
Now, to obtain the answer having maximum sum of difference between consecutive element, arrange element in following manner:
a1, an, a2, an-1,…., an/2, a(n/2) + 1
We can observe that the arrangement produces the optimal answer, as all a1, a2, a3,….., a(n/2)-1, an/2 are subtracted twice while a(n/2)+1, a(n/2)+2, a(n/2)+3,….., an – 1, an are added twice.
Consider the sorted permutation of the given array a1, a1, a2,…., an – 1, an such that a1 < a2 < a3…. < an – 1 < an.
Now, to obtain the answer having maximum sum of difference between consecutive element, arrange element in following manner:
a1, an, a2, an-1,…., an/2, a(n/2) + 1
We can observe that the arrangement produces the optimal answer, as all a1, a2, a3,….., a(n/2)-1, an/2 are subtracted twice while a(n/2)+1, a(n/2)+2, a(n/2)+3,….., an – 1, an are added twice.
int maxSum(int arr[], int n){ int sum = 0; // Sorting the array. sort(arr, arr + n); // Subtracting a1, a2, a3,....., a(n/2)-1, an/2 // twice and adding a(n/2)+1, a(n/2)+2, a(n/2)+3,. // ...., an - 1, an twice. for (int i = 0; i < n/2; i++) { sum -= (2 * arr[i]); sum += (2 * arr[n - i - 1]); } return sum;}http://www.geeksforgeeks.org/count-all-pairs-of-an-array-which-differ-in-k-bits/
Given an array of size n and integer k, count all pairs in array which differ in exactly K bits of binary representation of both the numbers.
This approach is efficient for the cases when input array has small elements and possibly many repetitions. The idea is to iterate from 0 to max(arr[i]) and for every pair(i, j) check the number of set bits in (i ^ j) and compare this with K. We can use inbuilt function of gcc( __builtin_popcount ) or precompute such array to make the check faster. If number of ones in i ^ j is equals to K then we will add the total count of both i and j.
long long kBitDifferencePairs(int arr[], int n, int k){ // Get the maximum value among all array elemensts int MAX = *max_element(arr, arr+n); // Set the count array to 0, count[] stores the // total frequency of array elements long long count[MAX+1]; memset(count, 0, sizeof(count)); for (int i=0; i < n; ++i) ++count[arr[i]]; // Initialize result long long ans = 0; // For 0 bit answer will be total count of same number if (k == 0) { for (int i = 0; i <= MAX; ++i) ans += (count[i] * (count[i] - 1)) / 2; return ans; } for (int i = 0; i <= MAX; ++i) { // if count[i] is 0, skip the next loop as it // will not contribute the answer if (!count[i]) continue; for (int j = i + 1; j <= MAX; ++j) { //Update answer if k differ bit found if ( __builtin_popcount(i ^ j) == k) ans += count[i] * count[j]; } } return ans;}int bitCount(int n){ int count = 0; while (n) { if (n & 1) ++count; n >>= 1; } return count;}// Function to count pairs of K different bitslong long countPairsWithKDiff(int arr[], int n, int k){ long long ans = 0; // initialize final answer for (int i = 0; i < n-1; ++i) { for (int j = i + 1; j < n; ++j) { int xoredNum = arr[i] ^ arr[j]; // Check for K differ bit if (k == bitCount(xoredNum)) ++ans; } } return ans;}面试题应该来源实践
我觉得面试题应该来源于实践的，而这类题目却与实践大大脱节，它考察的是一个人有没有刻意去准备。我可以立刻想到一些实用的面试题，都是实践中遇到的：
1.在一块矩形区域内随机选取一些点，要求任意两个点之间的距离不小于一个值
这个是一个同事做的一款手机游戏中的一关，它要在屏幕上随机位置生成一些鬼火，然后用多个手指 点同时把所有的鬼火都点上，就可以过关了。大概随机出5到6个点就够了，如果点数更多可以加大难度。因为位置随机，如果两个点靠得太近，手指的姿势会很别扭，会很不好点。
回到题目，菜鸟级别应该立马可以想到最暴力的方法，随便生成一些点，然后做校验，如果满足条件就退出，否则再随机生成一批数据。分析一下复杂度，生成数据O(n)，校验数据O(n^2)。如果能想着排序之类的方式去把校验过程的复杂度优化，就是不错的引导。面试应该这种开放式的讨论，不是考察面试者准备的怎么样。
由于校验后不一定满足，可能很多计算都是浪费的。所以，杀一点脑细胞的方式就会再继续思考。在构造的时候就生成满足条件的点。
比如我们可以对矩形区域打一些格子，然后用一个二维数组来标记这些格子。格子的直径的两倍大于要求的距离。然后我们来随机选格子而不是选点。选完一个格子以后，就将它周围格子标记起来，下一次随机选格子的时候，不能选择被标记的格子。最后从选择的格子中去取点，每个格子取一个，由于格子间距离是能保证大于一定值的，最终选取的任意两个点间的距离也是不小于一个值的。
当然，这不是最优解。我可以告诉你工程中最简单的做法，我同事的做法：自已用手在屏幕上点了一些点（感觉大概两个之间距离差不多就行），记录下坐标，存到数组里。然后使用的时候随便到从中取一些就行了......这才是高大上，丝毫不装逼。
2.有很多大小不一的小矩形，如何将它们填充到一个大矩形里面，使得填充得尽量的满，空间利用率尽量高。
做过游戏的人应该都知道texture packer，就是合图啦。把许许多多的小图合到一张大图里，抽象出来就是上面这个问题。
任选一个小矩形，放进去，大矩形剩下的区域就可以分为两个矩形，有两种分法。然后对子矩形递归地执行这个划分过程，就可以得到所有可能的方法。这是暴力的做法。
但是这状态数增长得太夸张，然后就应该思考有什么规律能利用到，比如按从大到小先将小矩形排序。
其实，有更好的答案：问google。这才是最工程的做法，绝对比自己闷着头想来得容易。
