ashot madatyan
BAN USERThis problem is the same as the one posted at
w w w .careercup.com/question?id=12962672
See my implementation there.
@deepak
Already fixed - just missed the cast to type int of the pointers.
int a;
int *pa = &a;
int *ps = pa+1;
int sz = (int)ps - (int)pa; // the size of the variable @a
Yeap, that's a classic problem, no doubt and no arguing there. What I wanted to communicate was what will you, as an interviewee, answer to the question posed by me - how would you generalize the solution and what is the reasoning behind it.
- ashot madatyan June 18, 2012Hey guys. Finding the solution to this specific problem is not a big deal, what is interesting here is the algorithm, especially when considering the number of people grows. Can you generalize and scale the algorithm - I think this is what actually the problem setter wants to see here. For example, how would yoou go with the series like: 1, 2, 5, 10, 12, 16, 20, 22, etc ?
- ashot madatyan June 18, 2012@Evgeny.
Thx for clarification, your definition of splitting the image is much more elaborate than the original. So, do you mean that each neighboring square shares a single vertical/horizontal line of pixels?
Yes, that's correct. I just showed an algorithm that I implemented long ago for one of my programs where there was a limitation not to have any element in its proper position in the final shuffled set. If we still want to have such elements, we can simply change the range from (i+1) to (i), and this will allow selecting the proper element for the given position.
- ashot madatyan June 16, 2012Well, it depends upon what the problem means by "16 squares", how do you define them and use (e.g. how do you shuffle those small squares). Anyway, the solution that I have provided does not break anything in the original problem description. Maybe, the problem shall be defined more clearly in terms of DS's and use cases.
- ashot madatyan June 15, 2012for i = 0 to 51
generate a random number in the range (i+1 to 51): @next_idx
swap the elements at the indices i and next_idx
Just enumerate (assign consecutive numbers to) each of the 16 small squares and use the square numbers to rearrange them to get the original picture. In this case, each of the small square would have numbers 0-15.
- ashot madatyan June 15, 2012The problem statement is just "find the second largest", and this does not imply that we are to create an effective query structure, for which the solution with BST's would be one of the ways to go with. So, given the statement itself (for one time query) the use of an additional O(N) storage is not that what I think was expected by the interviewer.
- ashot madatyan June 15, 2012@kuldeep
Yes, that was a nice catch, thanks for that.
See my implementation that properly handles all the stuff that you make assumptions for.
- ashot madatyan June 11, 2012I presume the using tree is an overkill here, because it can be done with more effective time and space complexities - see the implementation at the link provided in my post. The solution with a tree assumes O(N*logN) time and O(N) space complexities. Moreover, the time complexity will be even worse with unbalanced trees.
- ashot madatyan June 10, 2012See my implementation of this problem with O(N) time and O(1) space efficiency at the following link codepad.org/5kpsGjK6
- ashot madatyan June 10, 2012I have not actually solved that, and it is not a so trivial task to be done within the given space constraints. See the wiki article for the in-place matrix transposition at en.wikipedia.org/wiki/In-place_matrix_transposition
BTW, the original problem does not state that the matrix is square (see the series a1 a2 a3 a4... an), which means that it may be arbitrarily long.
Transposing a square matrix works OK, but have you tried the series where the row and column count are not equal? Try to run it with the series similar to
a1 a2 a3 a4 a5
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
@Thirumal.
U are not actually incrementing the array name (b) because in the function " void foo( int b[][3]) " you will actually be passed a copy of the pointer pointing to the original array. So, incementing this pointer does not actually change the array's location - instead, the copy of the pointer is changed by the ++b operator.
The answer is b) and a memory leak :).
- ashot madatyan June 06, 2012First, you will have to cast the pointer to int (&i) to a pointer to char (char*). As soon as you do it and increment it, you will be addressing the byte #1 (second byte) of the original int. So, the actual output will depend on the size of int and the endianness of the machine this code is compiled for.
- ashot madatyan June 06, 2012++b - this actually makes it point to the memory location starting at the second row of the original matrix, i.e. {4, 5, 6}
With the new pointer and using the [1][1] dimensions we will be addressing (accessing) the memory location [2][1] in the original matrix, i.e. element with value 7 in the row {7,8,9}.
So, after the call to foo function we have a modified matrix { 1,2,3} , { 4,5,6},{9,8,9}, and the call to "printf("%d" , a[2][1]);" will actually print 9.
So , the correct answer is B.
@Sathya
What do u mean by "brute force" and could you please point me in the original problem posting to any constraints (time or space). On the other hand, I would appreciate if the comments are in more the constructive form rather than what was stated by you. I believe that the comments like "your solution has some drawbacks (specific), and I suggest to improve it to this" are more welcome in this type of forums.
Thanks,
Ashot
If two strings are anagrams, then they shall be the same strings as soon as they are sorted.
Using this approach, you can use the following algorithm
to arrange all the anagram strings of the string array.
For each string @s in the string array @sa
sort the string @s and form @skey
use the @skey to insert this string @s into a hash table @HT of the form <string, vector<string> >
After all the strings are inserted into the @HT, just print out the @HT.
And here codepad.org/YhV1wjgY you can find the implemenatation that contains solutions both with and without hash table.
- ashot madatyan June 05, 2012This is a double posted question. Please see my solution at the link below:
question?id=13786675
Recursive calls are considered to be implicit loops, so this is not a solution that meets the constraints (w/o loops)
- ashot madatyan June 04, 2012See my implementation at codepad.org/ueUOmYjE
Look up the function "void bst_BFS_spiral(Node *pNode, bst_visit visit) " that implements the spiral traversal of the BST.
If the given input string contains only lower case and alpha symbols, then below is the straightforward implementation:
#include <stdio.h>
void first_unique(char buf[], int cnt)
{
char syms[26] = {0,};
int i;
for (i = 0; i < cnt; ++i){
syms[buf[i] - 'a']++;
}
for (i = 0; i < cnt; ++i){
if (syms[buf[i] - 'a'] == 1){
printf("%c at %d\n", buf[i], i);
return;
}
}
}
int main()
{
int cnt;
char buf[] = {'a', 'a', 'u', 'b'};
cnt = sizeof(buf)/sizeof(buf[0]);
first_unique(buf, cnt);
return 0;
}
Use TMP - Template Meta Programming, to get the required functionality.
#include <iostream>
template<int N>
struct NumberGeneration{
static void out(std::ostream& os)
{
NumberGeneration<N-1>::out(os);
os << N << std::endl;
}
};
template<>
struct NumberGeneration<1>{
static void out(std::ostream& os)
{
os << 1 << std::endl;
}
};
int main(){
NumberGeneration<100>::out(std::cout);
}
Assuming matrix is 0-based, i.e. the first element is at mat[0][0]
1. Use the first row and first column as table headers to contain row and column info respectively.
1.1 Note the element at mat[0][0]. If it is 1, it will require special handling at the end (described later)
2. Now, start scanning the inner matrix from index[1][1] up to the last element
2.1 If the element at[row][col] == 1 then update the table header data as follows
Row: mat[row][0] = 1;
Column: mat[0][col] = 1;
At this point we have the complete info on which column and row should be set to 1
3. Again start scanning the inner matrix starting from mat[1][1] and set each element
to 1 if either the current row or column contains 1 in the table header:
if ( (mat[row][0] == 1) || (mat[0][col] == 1) ) then set mat[row][col] to 1.
At this point we have processed all the cells in the inner matrix and we are
yet to process the table header itself
4. Process the table header
If the matt[0][0] == 1 then set all the elements in the first column and first
row to 1
5. Done
Time complexity O(2*((n-1)(m-1)+(n+m-1)), i.e. O(2*n*m - (n+m) + 1), i.e. O(2*n*m)
Space O(1)
And here is the link to my iplementation of the above algo:
codepad.org/fycIyflw
@Raj: Use a binary calculator to see what the 0x55 and 0xAA look like in binary.
1. Mask out all the even bits in the char: ch & 0xAA
2. Mask out all the odd bits in the char: ch & 0x55
Now you have two values - the masked odd and even bits of the original number. So, all you have to do now is to use a biwise OR operation to combine these two values, having shifted by 1 position to the left and to the right the respective temp numbers.
Hope that answered your question.
The behaviour of this type of self-assignment is undefined and dependent on the compiler implementation. So, the result may be either 0, or 10, or even a not-compilable code. The undefined behaviour happens due to missing sequence point in the evaluation of expression "count = count++;"
You can read it @en.cppreference.com/w/cpp/language/eval_order
You can safely ignore the last lines containing NULL chars, they were meant for other stuff, which I had no time to implement(character unerlining, etc). Moreover, we can reduce the width of the chars printed by using only 4 clumns instead of 5.
Sample output is below (hope the edit box will not screw it :))
_ _ _ _ _ _ _ _
| | | _| _| |_| |_ |_ | |_| |_|
|_| | |_ _| | _| |_| | |_| _|
See my implementation and the sample output @codepad.org/DShK94iy
- ashot madatyan May 22, 2012@anonymous: I believe the below pseudocode answers your question
// arr - the resulting array after sorting and merging the arrays A and B
// N - the size of the array arr
// s - the start index in the sorted/merged array
// e - the end index in the sorted/merged array
// d - the difference to be found
s = 0;
e = N;
while (s < e){
val = arr[s] - arr[e];
if (val == d)
print the arr[s] and arr[e]
++s;
--e;
else if (val > d)
s++;
else
e--;
}
@anonymous: I believe the below pseudocode answers what I meant and what you could not follow.
// arr - the resulting array after sorting and merging the arrays A and B
// N - the size of the array arr
// s - the start index in the sorted/merged array
// e - the end index in the sorted/merged array
// d - the difference to be found
s = 0;
e = N;
while (s < e){
val = arr[s] - arr[e];
if (val == d)
print the arr[s] and arr[e]
++s;
--e;
else if (val > d)
s++;
else
e--;
}
Your solution (2 pointers/indices) shall work properly only when the two arrays (A && B) are sorted and merged, and I am not sure about your algo - will that work for all cases as required in the original problem statement?
Consider the cases:
A < B
A > B
A and B overlap on the left
A and B overlap on the right
Moreover, this solution changes the original order of the arrays A and B. Another point is whether that algo can find all the valid pairs ?
Correct, but consider the situation if we are given the arrays A and B and they are fixed and you are supposed to continuously find all the pairs of elements with the given difference (array C in our case). In that case, the lookup is constant O(1) and you will not need to re-walk all the possible pair of elements of both arrays (A and B). So, this algo is much more better when the efficient lookup is at the question.
- ashot madatyan May 21, 20121. Maintain the current possible pivot index (for either odd or even count of current elements) - @pidx
2. With each new coming char (@ch) at index @i and as long as a pivot index is set (@pidx != -1), check
to see if it can be an element in a palindromic sequence up to now.
Check is done using the idea of whether the current element is the same
as the one equaly distant as the current one is from the pivot index.
If the two elements are the same and the first element is at index 0, then we
have a palindrome with this current char.
If the current element does not contribute to a palindromic sequence, then
reset the previous @pidx (if any set) and check whether this one can be a
new pivot index.
The time complexity of the above algorithm is O(1) sinece we compare the current
char only with its potential match coming before it.
And here codepad.org/RtXisXzi you can find the implementation of the algorithm along with the driver program and the output.
- ashot madatyan May 21, 20121. Calculate all the possible differences of A[i] and B[j]. This is i*j operations.
2. Put all the diffs in a HashTable @HTD
3. Now, walk through the array C and look up its value in @HT. This is k operations since look up in HT is O(1).
(smirk). Is that all that you wanted to contribute to the current discussion?
I think this is the classic scenario of the politely contracted quote "have something to say and have to say something". So, what's your case, can you guess ? :)
This solution does not meet the requirement of space not exceeding the height of the taller tree. Pushing initially all the left nodes of both BST's onto the stacks already breaks that limitation.
- ashot madatyan May 19, 2012Moreover, though it is not implicitly stated, I think there is a restraint not to modify any of the BST's. On the other hand, if there is no such restraint, we can merge both BST's in-place and do in-order to print all the nodes.
- ashot madatyan May 19, 2012@nix
"you cant gaurantee that the dest has been swapped out to its correct index"
The above algo keeps swapping the values (src->dest->src->dest...) until the final element that has been replaced gets into its correct position. The only shortcoming of this algo at the moment that I can see (and yes, I agree that it does not work properly for all cases, folks, thanks for noting that) is that you have to somehow correctly guess the next element that needs to start the swapping series. I will try to improve that logic as long as I have some spare time to invest into it.
This one should give you at least a warning - " char *p = "abc"; " because you are trying to assign a pointer to a non-constant data to a literal constant.
And the "reason behind it" is that the data is constant and cannot be changed.
:) Yes, technically speaking that is correct - if the two values do not get ever equal, then it is going to loop forever. But, actually this algorithm ensures that they finally get equal to each other.
The idea behind this algo is that every element at the current index (except the first and the last) has it's definite destination, so there can be no two indices (say K and L) that would map to the same index (say D).
So, could you please provide your test input to make this condition fail forever.
Sorting arrays is O(N log N) at best, while the requirement is O(N). See my implementation using the bitwise XOR, which is considered to be the most efficient solution for this.
- ashot madatyan May 16, 2012This can be done in O(N) time and with O(1) space using a simple bitwise XOR like below.
bool is_valid_permutation(int a[], int b[], int cnt)
{
int XOR = 0;
int i;
for (i = 0 i < cnt; i++){
XOR = XOR ^ a[i];
XOR = XOR ^ b[i];
}
return (!XOR)
}
That's correct, thanks for noting that. Already fixed.
- ashot madatyan May 16, 2012
Just a small correction - we will need 1023 elements in the array instead of 1024. So, given that and the counting sort algo, you can easily solve it in O(N) time.
- ashot madatyan June 21, 2012