dreamchaser1984
BAN USER- 6of 8 votes
AnswersGiven an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.
- dreamchaser1984 in United States
For Ex:
Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]
n -> 2
Out put -> [100, 0] or [100, 2]
Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 3of 3 votes
AnswersFind popular item in sorted array of natural numbers.
- dreamchaser1984 in United States
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm
There are 2 problems here:
1) Given a string and dictionary of words, add spaces to create sentence with words.
2) Create all combinations of string and check if a sentence can be formed using dictionary as explained in #1.
#1 is straightforward can be implemented in O(N).
#2 is n^n, how to optimize it.
One solution is to create suffix tree and discard all strings which can not be formed sentence.
For ex:
if Dictionary has words "java", "code", "here"
All possibilities which do not start with "j", "c" or "h" can be discarded.
Same logic cabe recursively applied to discard further possibilities and pass string to #1 only which can be converted to valid sentence.
Hope writing code should not be difficult.
This one is easy. Idea is to find the very first number, i.e, at the index of decrement count from left to right, or increment count from right to left.
Create another array to hold numbers in increasing order, set visited index by setting -1.
Once initial index is set, now its just traversing through string and incrementing or decrementing to next available index in store.
void PrintNumbers(string str) {
if (str.length() == 0) {
return;
}
int dCount = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == 'D') {
dCount++;
}
}
vector<int> nums;
for (int i = 0; i <= str.length(); i++) {
nums.push_back(i+1);
}
cout << endl << nums[dCount] << " ";
nums[dCount] = -1;
int iCount = dCount+1;
dCount--;
for (int i = 0; i < str.length(); i++) {
if (str[i] == 'I') {
cout << nums[iCount] << " ";
nums[iCount++] = -1;
}
else {
cout << nums[dCount] << " ";
nums[dCount--] = -1;
}
}
cout << endl;
}
just one
- dreamchaser1984 March 01, 2015I came up with same solution.
- dreamchaser1984 March 01, 2015If value is common between 2 consecutive elements, it means its repeated n/8 times not n/4 times. What if the reputation is exactly from n/8 to n/4?
- dreamchaser1984 February 25, 2015
Store incoming numbers in balanced binary search tree.
- dreamchaser1984 February 21, 2016IsNumberPresent, go through each node, find difference and search for difference in BST.
Space complexity O(N) and time complexity O(N * logN)
Question makes you think that you need to store computed sum, problem with that approach is, its N^2 solution to store a number, no matter which data structure you chose to store.