The Artist
BAN USEReven swapping will require 3 moves (if we think of moves as the assembly language mov from one register to another) :P anyway can't justify any solution unless the real meaning of moves is known... this is the type of question where you ask the interviewer: "Can you please elaborate on what do you mean by moves, if possible with an example?" Funnily enough the question consists of examples of kind of arrays, which was absolutely clear from the question statement (array of size N with rand elements from 1-N, all numbers should be present), but nothing about moves...
- The Artist November 27, 2012Nope. It's max heap. Insert the first 100 distances in the max heap thus the root node will have the maximum of the 100 distances. For every following distance check if the distance is less than the root (max) distance in the heap. If it is less delete the root and insert the new distance.
- The Artist November 27, 2012i don't know what exactly is meant by 'moves'...but shouldn't just going through the array and checking if a[i] != i + 1, that should be the minimum number of moves
- The Artist November 26, 2012if you are willing to use the API (methods) in the String class provided by C# then why not just use the Contains() method that support wild card search (which will make the solution even more ridiculous than yours) or why not split the pattern string with ' * ' character iterate througjh the splitted string array find the index of the current iterator value in the given string then search for the next iterator value in the substring from index of current iterator + iteratorValue.Length till the string end. This will as much ridiculous as your solution but much more neater code.
- The Artist November 26, 2012A max heap of size 100 is better than the array implementation for array contant will be 100log100 while for max heap it will be just log100
- The Artist November 26, 2012What Travis is presuming i guess is that God will not allow a liar to guard the doors to heaven (i wish it was Stairways to Heaven instead) :P
- The Artist November 23, 2012@siva: extension is not feasible.
@andi: how about using reflection?
@Varun: if you really want to do the pattern search then you can also use regular expressions (in Java, C#), In that case programatically creating the pattern itself will be the only tough part. personally i liked the trie way assuming you don't have any APIs (which is what the interviewer must be expecting)
- The Artist November 20, 2012@kat: string manipulation is a highly process (and memory) intensive task...my suggestion above (hashtable with linked list) would be a better option
- The Artist November 18, 2012i did not think of the duplicate words...in that case with no extra space i could not think of any solution :(
- The Artist November 15, 2012i don't understand why it was downrated...hashing may be a good option to keep a track of chars already found if no space constraint is mentioned.
- The Artist November 15, 2012Consider all unicode characters and your method will fail severely. A hash map would be better to keep track of already found chars and a linked list of chars or a string builder/buffer (in c#/java) to create the output string would be the best option to go for if there;s no space constraint.
- The Artist November 15, 2012Assumptions:
1. Word here means the english word and not 8bytes.(seperated by a single space character)
2. Number of words in the file < RAND_MAX.
Here's what you can do:
1. Count the number of spaces (say x)in the file => no of. words = x + 1
2. y = rand() % (x + 1)
3. return the word after y-1 spaces
@fallen_angel: see the comments to my original response.
- The Artist November 15, 2012@Jas: consider the example given in the question where you convert 'coverage' to 'converge'. In that case the sum will be two. Basically here you are taking one character of the given string and replacing it with any other alphabet.
- The Artist November 15, 2012looks like a high school combinatrics problem rather than an Amazon one. total number of possible combinations will be C(n,1)*C(m+1,1)+C(n,2)*C(m+1,2) where n = number of special characters and m= length of the string. use the same logic to find all the possible combinations. converting the given string to a linked list rather than an array would be much more efficient for insertion and string manipulationpurpose.
- The Artist November 14, 2012i think you missed the point in the question where it says that the order does not match which can result upto a max of (40!)/(2^14) possible combinations which is humungous.
- The Artist November 14, 2012@Anjana: sum=2 should be considered when the size of the dictionary word is same as the given string
@Eric: that could be a decoy. I did not find much help from the sorted list.
and i think my above solution will work for any difference just the sum value need to be modified
- The Artist November 12, 2012here's a O(n*m) (n=no of words in the dictionary, m = max length of the word)complex solution with space O(52). Perform the following steps:
1. Take all the words from the lis with length same as the given word or +/- 1
2. Create a letter count array/map of the given word (for eg if the word is "coverage" then a=1, c=1, e=2, g=1, r=1, v=1) (say a[26] contains the letter count from a to z)
3. take each word from step 1. create its letter count array (say b[26]
4 for i = 1 to 26 sum += abs(a[i]-b[i]). each word with sum value = 1 or 2 will be the required word.
@amir: just considering the right and below positions may not suffice for example
1 50 1 50
50 1 50 1
50 1 1 50
50 50 50 1
agree to mike above...10 bit integer means just 1024 distinct values and count sort is the best way. mike's suggestion to the second part can be achieved with an array of structures with struct definition as follows
typedaf struct array_element
{
object obj; //origianal original def
array_element next;
}
define an array like below
array_element a[1024];
where a[i] = first pair in the given list with integer value i. all following pairs with int i should be stored in as the next node of a[i] and so on
@kartick vvs: you are funny
- The Artist November 09, 2012@sonesh: how can the sum of two non negative be less than any one of the number 3/4 th time?
- The Artist November 09, 2012can you also update the question with the output for your example array with some value of k (say 30). i still have a problem understanding the sort part with any order...
- The Artist November 09, 2012I am assuming that the question doesn't talk about intermittent data ie like last 10 second data or last 3 hours data...How about a bounded queue of size 86400 each node having the count of events in each second of the last 1 day..In addition to this you keep a reference to 1st, 82800th (86400-3600) and 86340th (86400-60) node, and 3 counts (one for last day,d; one for last hour,h; one for last minute,m). Say you already have the entire queue filled: so here's what you'll do every second. a = deque; queue(s)
d = d + s - a;
m = m + s - node(86340).data
h = m + s - node(82800).data
also the three referenced node need to be updated. s is the number of events in the last second
the word sort and any order doesn't go together...i am hoping you meant 'arrange' rather than sort and that the element on the left and right of k are not sorted. what the interviewer is asking is exactly what quick sort does after selecting the pivot. in your case the pivot will be k. if we have an external array and couple of pointers then this is what i'll do..in the first pass through the array count number of elements less than k(say x), number of them equal to k (say y) then number of element greater than k will be n - x - y. Now fill the external array from position x to y-1 with k. on the second pass of the array if you find an element less than k fill it in a position less than x and if you find something greater than k fill it at a position greater than = x+y-1
- The Artist November 09, 2012Compilation error as you need to include time.h...After you add that it will always print error since a and b are unsigned integers therefore c will always be >= a and >= b...also rand function generates integers >=0
- The Artist November 09, 2012@Romero: Your answer has the following problem. I'll let you figure out where and why.
1. Would not compile;
2. Will go into infinite loop fol all n < 1 and also n=2;
3. Will return wrong answers for all +ve even numbers > 2;
a recursive question cannot become more simpler. below is your function:
int F(int n)
{
int x;
if (n < 1)
return -1;
if (n == 1)
return 1;
if (n % 2 == 0)
return F(n/2);
x = (n-1)/2;
return F(x) + F(x+1);
}
also rather than returning -999 you might want to return something that you will be sure of is not a solution (say for example n-1) what if the solution itself is -999?
- The Artist November 06, 2012hmm...look at my comment below on CodePredator's solution. Searching for the number and finding the next successor was out of question as you don't know whether the number is present in the tree or not...
- The Artist November 06, 2012Nice but not the best. The worst case time taken for this algorithm will be O(n) (when there is no element bigger than the given number or the biggest number in the tree is the answer) which makes it a O(n) algorithm. Now if searching for anything in a binary search tree is taking more than O(h) time than you should really think twice. In the above algorithm you are blindly attacking the root->left which is not required if root->data was less than the given number. In that case you already know that the number you are searching for lies, if present, in the right sub tree of the root element
- The Artist November 06, 2012aren't you being funny rick...if searching for something in a binary search tree is taking more than O(h) time then you are definitely doing something wrong.
- The Artist November 06, 2012Its becoming hopehesless..After going through couple of questions today, I feel like people should first try to learn some form of a human comprehendible language properly before attempting to become a machine linguist. Reminds me of my highh school chemistry teacher who used to get pissed off at students who were preparing for the toughest engineering entrance exams but could not even perform a simple math calculations correctly.
- The Artist November 05, 2012it is no way a linear time question...if you disagree to that do post the code...
- The Artist November 05, 2012@rbhavya62: you really got to work on your english...atleast post questions that's comprehendible...
- The Artist November 05, 2012@ eyeonu.imtiyaaz: Can you please be little more clear on what do you mean by sorted array implemented as ring buffer? Does that mean that the least element can occur at any position and as it's a ring buffer you can traverse starting from the least element position to get the ascending list?
@CodeSpace: What do you mean by 'inversely rotated/half rotated? Can you explain what are you trying to do in those 4 if statement above? Is that a simple binary search that you are doing or have you modified BS for the ring buffer stuff?
it becomes more complicated in a scenario like this:
input string = "aabbccccdddd" and n=2. in this case you need to remove one 'c' and 1 'd'. how do you handle all such scenarios programmatically?
yeah, i read that...good learning :)
- The Artist October 31, 2012true...thanks for the correction. in that case the heap algorithm by lfenjoy9 would also not work, will it?...got to rethink the algorithm
- The Artist October 31, 2012but what if all the matrices are nxn matrix
- The Artist October 30, 2012i don't think so that there can be a way to handle the problem (water loo vs waterloo) you are mentioning...to handle such issues the problem statement would need modification
- The Artist October 30, 2012can you please explain a little more on the explicitly maintained stack and how would it be more efficient than the recursive stack? is it just because the recursive stack will maintain local variables at each recursion?
- The Artist October 30, 2012What you need to remember while erasing elements is that when you start removing the char that appeared the most number of time, you will also have to remove the characters that appeared second highest number of time if the most frequent char number equalled the 2nd most frequent elements. this will repeat at every level (when 3rd highest level is reached you will have to start erasing 3 char to actually reduce the roughness by 1). I'll post the code for this one once i find some time,
- The Artist October 30, 2012i don't quite get you...for product of n matrices you got to have n-1 multiplications, no matter how you group the matrices (is there a shortcut formula to multiply three or more matrices simultaneously?).
- The Artist October 30, 2012true...had there been 9 balls and we knew whether the balls where heavier or lighter then we could have done it in 2 steps.
- The Artist October 23, 2012simply mind baffling...i'll skip the question :P
- The Artist October 23, 2012awesome question...it is a brain twister rather than a teaser.(ref tongue twisters :P)
- The Artist October 23, 2012
i think the customer specified properly but the bussiness analyst is incompetent as he can't clearly restate the problem statement :P
- The Artist November 27, 2012