Dilbert Einstein
BAN USERRecursive approach:
private static boolean isFoldable(BinaryTree t1, BinaryTree t2) {
if (t1 == null && t2 == null)
return true;
if (t1 == null || t2 == null)
return false;
if (t1.getData() != t2.getData())
return false;
return isFoldable(t1.getLeft(), t2.getRight()) && isFoldable(t1.getRight(), t2.getLeft());
}
Recursive approach:
private static boolean isFoldable(BinaryTree t1, BinaryTree t2) {
if (t1 == null && t2 == null)
return true;
if (t1 == null || t2 == null)
return false;
if (t1.getData() != t2.getData())
return false;
return isFoldable(t1.getLeft(), t2.getRight()) && isFoldable(t1.getRight(), t2.getLeft());
}
@Vinod K
I think you misunderstood my algorithm (or misunderstood the problem - he is asking for maximum product, not maximum absolute value of product). I am separating positive values and negative values and then determining the largest values in each group. Please go through the solution I gave again. The case you are mentioning should not occur in the case of >3 elements.
If you still think there is an issue, give me a test input where my logic breaks and we can take our discussion from there.
Thanks!
@Siva Chidambaram Somu
Few things:
1) Heap space complexity in this case is 3 and not n. I am only storing 3 solution candidate values in heap at any time, not entire array
2) We can just create heap on pointers instead of actual data itself (here data is just primitive integers so hard to see this advantage, but if we were dealing with large structs, we can just maintain heap of the pointers)
3) Trade off with alternate solutions a) To check the 3 values independently => does not scale b) To sort the elements - in place sorting is time complexity wise horrible performance
Depending on what we know about input, I have one solution if all values are positive and another solution if values can be negative.
Case All positive:
--------------------
Do basic sanity checks.
check for array size:
<3 return error;
==3 return product of 3 values
> 3 : get the largest three values and return their product as answer
To get the largest 3 values, sorting is bad because of O(nlogn) complexity. Instead, initialize a min-heap array with first 3 values. Iterate through the rest of array, check each value against the top(min) value of heap, if current value is smaller, discard it but if greater then remove the min from heap and insert the current value. In the end you will have largest three in the heap. The complexity is O(n * log3). Using customized heap, we can reduce log3 as well.
Case Negative values are present:
-----------------------------------
Do basic sanity checks.
check for array size:
check for array size:
<3 return error;
==3 return product of 3 values
> 3 do two things:
1) Find largest three positive values - take their product say P1
2) Find largest (by absolute value) two negative values & one largest positve value - take their product P2
Then answer = Max (P1, P2);
The idea is, two negative values when multiplied gives positive value. Since we have three, we need to check for possibility of two negative and one positive combination.
NOTE: Handle edge cases when 1) & 2) cannot happen: e.g. if all are negative values in the array, then take product of 3 smallest (by absolute) negative values.
This is a known problem and available in CareerCup book:
1. Count the number of spaces during the first scan of the string.
2. Parse the string again from the end and for each character:
»»If a space is encountered, store “%20”.
»»Else, store the character as it is in the newly shifted location.
void ReplaceFun(char[] str, int length)
{
int spaceCount = 0, newLength, i = 0;
for (i = 0; i < length; i++)
{
if (str[i] == ‘ ‘)
{
spaceCount++;
}
}
newLength = length + spaceCount * 2;
str[newLength] = ‘\0’;
for (i = length - 1; i >= 0; i--)
{
if (str[i] == ‘ ‘)
{
str[newLength - 1] = ‘0’;
str[newLength - 2] = ‘2’;
str[newLength - 3] = ‘%’;
newLength = newLength - 3;
}
else
{
str[newLength - 1] = str[i];
newLength = newLength - 1;
}
}
}
#include <iostream>
void reverse_C_string(char* start, char* end)
{
if(end == NULL || start == NULL)
{
return;
}
while( start < end )
{
char temp = *start;
*start++ = *end;
*end-- = temp;
}
}
int main()
{
char c[] = "Given C String";
int length = strlen(c);
reverse_C_string(c,c+length-1);
std::cout<<c;
getchar();
return 0;
}
This can, as always, be solved in multiple ways.
Solution 1: Simply sort the n elements array and pick the (n-1)th element. O(sorting algo = nlogn)
Solution 2: This is a job interview question - in other words from a practical point of view the solution you come up with should be easily extended to finding any k-th largest element (instead of just 2nd)
So here is my solution for that:
I) Do basic sanity checks and check for array.size >= k. If <k then notify that there is no answer.
II) Take first k elements and then create a min-heap. From k+1 th element onwards, check with top value in heap, if it is smaller than top min-heap value, there is no way it can be in the set of k largest values in array - so discard it.
If it is greater than min-heap top value, then we got new set of k largest elements (from the elements traversed so far). So remove the min element in heap and add the new element (and heapify). Keep doing this until end of array. The min element of the heap is the answer.
Advantages: Everytime we check for min value and discard, we are avoiding checking with all other (k-1) values. Even in worst case we ended up having a value bigger than min every time (if input array is in ascending order), our insertion is now reduced to log k. So complexity = O(n log k)
I presented my version of code as well, please do take a look and comment. Thank you!
- Dilbert Einstein May 11, 2013Basic idea: Instead of doing a linear search, take advantage of +1/-1 property => Two numbers X & Y need to be at last (X-Y) distance apart in the array.
Algorithm:
1) Runner iterates through the numbers (initialized to begin of array)
2) Calculate absolute difference between current value and lookup value
3) If (difference == 0) return Runner location, else, increment Runner value by the difference -> the optimization part and continue from step 2
C++ code:
#include <iostream> // std::cout
#include <cmath> // std::abs
#include <vector> // std::vector
int determineElementPositionSpecialArray (const std::vector<int>& specialArray, int lookupValue)
{
int runner = 0;
while (runner < specialArray.size())
{
int offset = std::abs(specialArray[runner]-lookupValue);
if(offset == 0)
{
return runner;
}
runner += offset;
}
return -1;
}
int main()
{
std::vector<int> specialArray;
specialArray.push_back(3);
specialArray.push_back(4);
specialArray.push_back(5);
specialArray.push_back(4);
specialArray.push_back(5);
specialArray.push_back(6);
specialArray.push_back(5);
specialArray.push_back(4);
specialArray.push_back(3);
specialArray.push_back(2);
std::cout << determineElementPositionSpecialArray(specialArray, 6) << std::endl;
std::cout << determineElementPositionSpecialArray(specialArray, 2) << std::endl;
getchar();
return 0;
}
Could you please rephrase the question in a more understandable way. Thanks!
- Dilbert Einstein May 11, 2013Thanks Champ! :)
- Dilbert Einstein May 04, 2013I thought of the same idea. Just that giving the details of how is 'try' defined by the question poster (or interviewer) would have given better confidence. Thanks!
- Dilbert Einstein April 28, 2013The above answer is correct. I have added a answer of my own with links to explanation of algorithm - including a video lecture. Enjoy!
- Dilbert Einstein April 28, 2013Brute-force checking every pair works and easy to implement but inefficient.
Divide and conquer dynamic approach is better. Details are below:
Look for Closest_pair_of_points_problem on Wiki page for quick overview.
Look for "Lecture -9 Divide And Conquer -IV Closest Pair" in youtube - this video lecture is entirely dedicated to explaining the algorithm.
Enjoy!
@sw
For such minor details both in interview as well as real word implementation, you can ask them as requirements. If what you suggested is the given requirement, the change in the above algorithm is very trivial. Hope this helps.
@daydreamer
Sure, I am assuming you understood till the point: We need to distribute (N-M) spaces across (K-1) words. For example, 12 spaces across 4 words. How will you distribute them evenly? 3,3,3,3. ( 12 / 4). That is the x. But what if it was not exact multiple of 4? example, 14 spaces and 4 words => 4, 4, 3, 3 i.e. floor(14/4 = x) for each word. remaining 2 spaces (14%4 = y ) I just append it to first two words.
I hope this clarifies your doubt.
This is not the best solution. The phone numbers are typically 13 digits in size, should mean a vector of size 10^13. You can not just create a bit vector of same size as number of phone numbers, you can not map it back to corresponding number.
Secondly, I assume interviewer is expecting more of STORAGE - as in saving it in database or file (XML file or regular file).
void plusPlusArray (std::vector<int>& array)
{
int carry=1;
int sum=0;
for(int i=array.size()-1; i>=0; i--)
{
sum = array[i] + carry;
array[i] = (int) sum%10;
carry = sum/10;
if(carry == 0)
{
break;
}
}
if(carry)
{
// additional digit to be added
array.insert ( array.begin(), carry );
}
}
1) Basic sanity checks need to be done & dealt with accordingly: e.g. Any zeroes at the beginning of input array
2) Problem says it is integer array => Assuming no negative numbers
Please correct me if I am doing anything wrong or missing anything.
int Read(char* buf)
{
int cnt=0,total=0;
char tmpbuf[4096]={0};
do
{
cnt = Read4096(tmpbuf);
total = +cnt;
strcat(buf,tmpbuf);
}while(cnt == 4096); // break when we read less than 4096 chars (including 0)
return total;
}
You totally forgot the case of zeros and non-uniqueness of elements. I gave a solution - please correct me if I am doing any mistake. Thank you very much :)
- Dilbert Einstein September 02, 2012Assumption: All integers are unique (I explained for non-unique case below with some more assumptions)
If a zero exists:
product of non-zero values - just one value as output.
If no zeros:
take the product of all values in one iteration.
do second iteration - for each current value, o/p = product/current_value;
this will give n values of output.
If values are NOT unique:
if one zero: output=product of rest
if more than one zero: output=0 (just one output)
if no zeros: same as non-unique case (note that there will be repetition of values - assuming no deduping required.)
It is so annoying when we end up wasting time trying to figure out what the question is. Despite posting questions is useful to us, such vague questions is actually counter productive.
- Dilbert Einstein September 02, 2012Given info: Width of the page = N, A vector of words (of length K)
For simplification of logic, I assume start index = 1.
Idea: Let l_i be the length of ith word. For a meaningful sentence there must be
at least one space after every word (except the last word). Then total MINIMUM length
needed is [sum(l_i) i=1 to K] + (K-1) = M.
Sanity check: If M>N => not acceptable => error/return
If (N>M), we need to accommodate (N-M) additional spaces after first K-1 words.
Let x = (N-M)/(K-1). y= (N-M)%(K-1).
for each word of first K-1 words:
if word index is <= y => number of spaces next to it = 1+x+1; // default space + additional spaces
else word index >y => number of spaces next to it = 1+x;// default space + additional spaces
Concatenate the words into one string with spaces as defined above.
I like the soln but Observer's point seems valid. This needs to be revisited by Luv.
- Dilbert Einstein July 22, 2012@Anonymous Uninitialized does not mean this is infinite loop - the initial value is just indeterministic => can be any value => when sufficient iterations done, it can go to 0 theoretically and break the loop.
- Dilbert Einstein June 19, 2012
Assumptions:
- Dilbert Einstein May 23, 2015- All log files have a common root directory
- The UserID is logged exclusively in a line (without any other data in same line)
cd /var/log; find . -type f -name "*.log" | xargs cat | sort | uniq -c | sort -k1,1 -r | head -10
Of course replace log directory path and log file name format appropriately if given. It is also good to ask the interviewer if the assumptions are correct. If not, depending on the specifications, slight modifications need to be made to the command.