|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On October 21 2013 06:01 EscPlan9 wrote:Show nested quote +On October 21 2013 02:34 phar wrote:On October 20 2013 22:33 Mstring wrote:On October 20 2013 21:58 gedatsu wrote:On October 20 2013 09:18 EscPlan9 wrote:On October 20 2013 04:58 spinesheath wrote:On October 20 2013 04:33 phar wrote:On October 20 2013 02:38 gedatsu wrote:On October 20 2013 02:07 phar wrote:On October 20 2013 01:03 gedatsu wrote:
[quote]
Suppose arr = [2000000000,2000000000,1]
Your hash vector will get really long. Not only that, but the function will fail due to hash collisions. So two open things to solve: 1) What if input is larger than memory 2) What if two numbers hash to the same hash value He can't get hash collisions as he is using the value itself as its hash. But yeah, with a more sane hash function you can get collisions. Use the built-in hash table here. Yea sorry I was getting a step ahead of himself. I meant that after he solves the problem you pointed out (identity hash function), he will then have to solve the problem of hash collisions. The idea is to not try to implement the hashtable yourself, but to just use an existing one instead. Those come with built in strategies for collisions. I'm very confused by the responses here. I wasn't implementing a hash table myself. I was using built-in hash structures found in most languages, in the code above it was Javascript. If a key is found, you can detect it and handle it however you want - in this case all I do is change the value because I found another instance of the element. If a key is not found, one is created. Pretty simple... As to "what if two numbers hash to the same hash value"? How does that even matter. Like if you run the code above, you'll find out the Keys '1', '2', and '3' all have a value of 2, and the Key '4' has a value of 1. The crux of the problem was to find non-duplicate elements in an array. So all non-duplicate elements would have a value of 1... and that's it. It doesn't matter if they hash to the same value - as long as the value is 1 in my solution, then we found a unique element in the array. I've never used javascript so I may be wrong, but it seems like you're not using a hash table at all. Instead you're just using a regular array and naming it "hash". That is not what a hash table is. Lol! If only you spent ten seconds googling before you posted so you could have known just how wrong you indeed are XD He's not entirely wrong. It's not an array, but it's also not a hash table. It's object (why [object Object] of course, what else is there in js? lol), which has a few key differences from an actual hash table. See here for more detail: http://stackoverflow.com/questions/368280/javascript-hashmap-equivalent Javascript is pretty lol indeed. Yes, to be 100% accurate, it is not a hash table. It is just an object that can be used similarly to a hash table. I've been using Javascript exclusively at work lately so I happened to write it in Javascript. If I remember correctly, Perl also can make use of hash tables just as simply.
idk about js and perl, but in python you can. the responses to your solution were brain-exploding indeed.
|
On October 22 2013 02:45 waxypants wrote:Show nested quote +On October 21 2013 06:01 EscPlan9 wrote:On October 21 2013 02:34 phar wrote:On October 20 2013 22:33 Mstring wrote:On October 20 2013 21:58 gedatsu wrote:On October 20 2013 09:18 EscPlan9 wrote:On October 20 2013 04:58 spinesheath wrote:On October 20 2013 04:33 phar wrote:On October 20 2013 02:38 gedatsu wrote:On October 20 2013 02:07 phar wrote:
[quote]
Not only that, but the function will fail due to hash collisions. So two open things to solve:
1) What if input is larger than memory
2) What if two numbers hash to the same hash value He can't get hash collisions as he is using the value itself as its hash. But yeah, with a more sane hash function you can get collisions. Use the built-in hash table here. Yea sorry I was getting a step ahead of himself. I meant that after he solves the problem you pointed out (identity hash function), he will then have to solve the problem of hash collisions. The idea is to not try to implement the hashtable yourself, but to just use an existing one instead. Those come with built in strategies for collisions. I'm very confused by the responses here. I wasn't implementing a hash table myself. I was using built-in hash structures found in most languages, in the code above it was Javascript. If a key is found, you can detect it and handle it however you want - in this case all I do is change the value because I found another instance of the element. If a key is not found, one is created. Pretty simple... As to "what if two numbers hash to the same hash value"? How does that even matter. Like if you run the code above, you'll find out the Keys '1', '2', and '3' all have a value of 2, and the Key '4' has a value of 1. The crux of the problem was to find non-duplicate elements in an array. So all non-duplicate elements would have a value of 1... and that's it. It doesn't matter if they hash to the same value - as long as the value is 1 in my solution, then we found a unique element in the array. I've never used javascript so I may be wrong, but it seems like you're not using a hash table at all. Instead you're just using a regular array and naming it "hash". That is not what a hash table is. Lol! If only you spent ten seconds googling before you posted so you could have known just how wrong you indeed are XD He's not entirely wrong. It's not an array, but it's also not a hash table. It's object (why [object Object] of course, what else is there in js? lol), which has a few key differences from an actual hash table. See here for more detail: http://stackoverflow.com/questions/368280/javascript-hashmap-equivalent Javascript is pretty lol indeed. Yes, to be 100% accurate, it is not a hash table. It is just an object that can be used similarly to a hash table. I've been using Javascript exclusively at work lately so I happened to write it in Javascript. If I remember correctly, Perl also can make use of hash tables just as simply. idk about js and perl, but in python you can. the responses to your solution were brain-exploding indeed.
Do you really think it is "brain-exploding indeed" to not assume that something declared as being equal to {} (with such brackets being used to initialize arrays in the C family, by far the world's primary group of programming languages), and being indexed as an array, is in fact not an array but an entirely different and more complex data structure?
Your brain must explode quite often, then. My condolences.
|
What GUI builder should I choose for Java? Is this one good?
|
On October 22 2013 03:36 gedatsu wrote:Show nested quote +On October 22 2013 02:45 waxypants wrote:On October 21 2013 06:01 EscPlan9 wrote:On October 21 2013 02:34 phar wrote:On October 20 2013 22:33 Mstring wrote:On October 20 2013 21:58 gedatsu wrote:On October 20 2013 09:18 EscPlan9 wrote:On October 20 2013 04:58 spinesheath wrote:On October 20 2013 04:33 phar wrote:On October 20 2013 02:38 gedatsu wrote:
[quote]
He can't get hash collisions as he is using the value itself as its hash. But yeah, with a more sane hash function you can get collisions. Use the built-in hash table here. Yea sorry I was getting a step ahead of himself. I meant that after he solves the problem you pointed out (identity hash function), he will then have to solve the problem of hash collisions. The idea is to not try to implement the hashtable yourself, but to just use an existing one instead. Those come with built in strategies for collisions. I'm very confused by the responses here. I wasn't implementing a hash table myself. I was using built-in hash structures found in most languages, in the code above it was Javascript. If a key is found, you can detect it and handle it however you want - in this case all I do is change the value because I found another instance of the element. If a key is not found, one is created. Pretty simple... As to "what if two numbers hash to the same hash value"? How does that even matter. Like if you run the code above, you'll find out the Keys '1', '2', and '3' all have a value of 2, and the Key '4' has a value of 1. The crux of the problem was to find non-duplicate elements in an array. So all non-duplicate elements would have a value of 1... and that's it. It doesn't matter if they hash to the same value - as long as the value is 1 in my solution, then we found a unique element in the array. I've never used javascript so I may be wrong, but it seems like you're not using a hash table at all. Instead you're just using a regular array and naming it "hash". That is not what a hash table is. Lol! If only you spent ten seconds googling before you posted so you could have known just how wrong you indeed are XD He's not entirely wrong. It's not an array, but it's also not a hash table. It's object (why [object Object] of course, what else is there in js? lol), which has a few key differences from an actual hash table. See here for more detail: http://stackoverflow.com/questions/368280/javascript-hashmap-equivalent Javascript is pretty lol indeed. Yes, to be 100% accurate, it is not a hash table. It is just an object that can be used similarly to a hash table. I've been using Javascript exclusively at work lately so I happened to write it in Javascript. If I remember correctly, Perl also can make use of hash tables just as simply. idk about js and perl, but in python you can. the responses to your solution were brain-exploding indeed. Do you really think it is "brain-exploding indeed" to not assume that something declared as being equal to {} (with such brackets being used to initialize arrays in the C family, by far the world's primary group of programming languages), and being indexed as an array, is in fact not an array but an entirely different and more complex data structure? Your brain must explode quite often, then. My condolences.
1) It's obviously not C. It seems there are at least a handful of languages which use this syntax for associative arrays.
2) There is an obvious array declaration right above which uses a different bracket syntax.
3) Everybody (not just you) seemed to be assuming that { } was syntax for a naive dynamic sparse array, which is quite a weird assumption.
4) It's fine to not know the syntax, but instead of checking, people started making weird assumptions and stating things as fact as if they actually knew. This, leading up to a condescending post boiling down to "learn your data structures bro".
Ok my brain didn't explode, but it hurt a little bit while skimming through the posts.
|
Is there anything like a "light-weight" C compiler? I want to re-teach myself C in my free time, but I don't want to install a bunch of resource-heavy software. Any suggestions?
|
On October 19 2013 20:07 wherebugsgo wrote:Show nested quote +On October 19 2013 16:33 spinesheath wrote:On October 19 2013 15:55 wherebugsgo wrote:
You're given an array of numbers such that every element in the array is duplicated except for one. Provide an efficient algorithm to determine the singleton element. Is that the exact wording of the question? Does "duplicated" mean that the duplicate and the original are in unrelated slots of the array, or are they adjacent? Can there be multiple sets of duplicates of the same number, as in 2, 4, 6 of the number? What range are the numbers from? Then there also is the question how one defines efficient. It's an inefficient use of programmer time if you don't just use some stupid algorithm that works and is easy to read and understand. Unless that piece of code is a performance bottleneck that needs to be faster. But I'm going to assume that low execution time is the goal here anyways. I paraphrased, but basically you can expect to encounter two of every element in the array except for one element. The array is unsorted and the duplicates can appear anywhere. There won't be multiple (read: more than 2) instances of the same number, though the answer would remain the same for even-number duplicates-i.e. you could have 4 of the same number and 2 of another and 6 of another and finding the singleton still works the same. There is no specification on the range of the numbers, though you can assume that you won't need multiple data structures to represent a single number. i.e. if it makes it easier for you, assume they are 32 bit ints or whatever. My first solution required O(nlogn) time, and O(1) space. I pretty quickly realized that the time complexity can be improved to O(n) time and there's a relatively simple way of doing that by adding a data structure that takes O(n) space, but the "brilliant" answer (as the interviewer described it-I'd call it elegant) requires no additional space and is also O(n) time. + Show Spoiler [my shitty answer] +Sort the array, then step through the array until you find that two consecutive elements are not the same. Sorting takes O(nlogn) time and stepping through the array takes O(n) time; O(nlogn + n) is in O(nlogn).
You could use radix sort and get an O(n) sort, I suppose. Instead of sorting the array, maintain a hash table and a second sum variable. Iterate through the array and for each integer, check if it's in the hash table. If it isn't, then add it to the sum, and store it. If it is, then subtract it from the sum. When we've gone through the entire array, the singleton is the only element we never subtracted, thus the sum variable is the singleton.
This works in O(n) time since hash accesses are O(1), and we need O(n) space for the hash table.
Just iterate through the array and XOR everything together. A[0] XOR A[1] XOR .... XOR A[n]. The result of this computation is the singleton element.
This works since XOR is commutative and associative. a XOR a is just 0, and 0 XOR a is a. Since all of the elements are duplicated except one of them, all the duplicates will XOR out to 0 and then the singleton will be left at the end.
This holds true also for arrays in which you have even multiples of elements, not just duplicates, though it fails when there are odd multiples.
If you guys like this sort of stuff or need interview practice, here's a few more interesting problems I encountered at career fairs/interviews and company visit sessions: 1. This problem is similar to the one I posed before, but it has a pretty major twist. The problem statement is to find the missing integer in the array with the following rules: a. An array A contains every integer from 0 to N except for one of them. b. The elements of the array A may appear in any order. c. We can't actually access an entire element of the array all at once. In other words if you index the array you won't get back the whole element. + Show Spoiler +in other words, normally if you access an array element at index i, you would call A[i] and you would be returned the element at the ith position in A. In this problem you can't do that. Instead, what you can do is ask for the jth bit of the ith element of the array. In other words, I could ask for the 4th bit of the first element of A, and I would be returned the bit in the 4th position of the element ordinarily given by A[0]. d. The algorithm must return the missing integer by looking through at most O(N) bits. 2. Give an approach (or code) to writing an equivalent of the C function atoi. + Show Spoiler +I've also been asked how to implement strlen If you're not a C programmer, atoi is a function that converts an ASCII string to an integer. Describe the limitations or shortcomings of your approch (or code) in as much detail as you can. 3. Suppose we have a function that computes rand2() (i.e. a fair coin toss-it outputs 1 or 2 with equal probability). Design an algorithm that uses this function to simulate a fair die roll, i.e. a function that should output a random number from 1 to 6 with equal probability.
I don't really understand the bit lookup constraint on problem 1. What do you mean by "looking through at most O(N) bits". O(N) is not an amount, it's a complexity. So are you trying to say "at most N bits", or are you trying to say that the number of lookups should not increase more than linearly with N? I don't see how it could be the first, so I'm going to assume the second. If I further assume that the integers are of a fixed size (32-bit unsigned integers for example), then I can trivially write a function to bypass your constraints with the number of lookups varying linearly with N. If N has no upper limit in the problem, then technically I believe the trivial bypass becomes N*log(N). Please clarify, BUT
+ Show Spoiler +I think the problem can be solved using the XOR trick again like the other problem. In the other problem, numbers were in equal pairs, so XORing them canceled out all except the one without a pair. In this problem, every number has a pair (0, N), (1, N-1), (2, N-2), etc. If you invert all numbers greater than N/2 prior to XORing, then you have equal pairs again. By invert, I mean invert(x) = N - x. I think the remaining XOR sum will either be the missing number or its inverse (it depends on how many inversions you did while traversing the list). Of course, all of this is assuming I am allowed to trivially bypass your constraint 
|
On October 22 2013 07:05 waxypants wrote:Show nested quote +On October 19 2013 20:07 wherebugsgo wrote:On October 19 2013 16:33 spinesheath wrote:On October 19 2013 15:55 wherebugsgo wrote:
You're given an array of numbers such that every element in the array is duplicated except for one. Provide an efficient algorithm to determine the singleton element. Is that the exact wording of the question? Does "duplicated" mean that the duplicate and the original are in unrelated slots of the array, or are they adjacent? Can there be multiple sets of duplicates of the same number, as in 2, 4, 6 of the number? What range are the numbers from? Then there also is the question how one defines efficient. It's an inefficient use of programmer time if you don't just use some stupid algorithm that works and is easy to read and understand. Unless that piece of code is a performance bottleneck that needs to be faster. But I'm going to assume that low execution time is the goal here anyways. I paraphrased, but basically you can expect to encounter two of every element in the array except for one element. The array is unsorted and the duplicates can appear anywhere. There won't be multiple (read: more than 2) instances of the same number, though the answer would remain the same for even-number duplicates-i.e. you could have 4 of the same number and 2 of another and 6 of another and finding the singleton still works the same. There is no specification on the range of the numbers, though you can assume that you won't need multiple data structures to represent a single number. i.e. if it makes it easier for you, assume they are 32 bit ints or whatever. My first solution required O(nlogn) time, and O(1) space. I pretty quickly realized that the time complexity can be improved to O(n) time and there's a relatively simple way of doing that by adding a data structure that takes O(n) space, but the "brilliant" answer (as the interviewer described it-I'd call it elegant) requires no additional space and is also O(n) time. + Show Spoiler [my shitty answer] +Sort the array, then step through the array until you find that two consecutive elements are not the same. Sorting takes O(nlogn) time and stepping through the array takes O(n) time; O(nlogn + n) is in O(nlogn).
You could use radix sort and get an O(n) sort, I suppose. Instead of sorting the array, maintain a hash table and a second sum variable. Iterate through the array and for each integer, check if it's in the hash table. If it isn't, then add it to the sum, and store it. If it is, then subtract it from the sum. When we've gone through the entire array, the singleton is the only element we never subtracted, thus the sum variable is the singleton.
This works in O(n) time since hash accesses are O(1), and we need O(n) space for the hash table.
Just iterate through the array and XOR everything together. A[0] XOR A[1] XOR .... XOR A[n]. The result of this computation is the singleton element.
This works since XOR is commutative and associative. a XOR a is just 0, and 0 XOR a is a. Since all of the elements are duplicated except one of them, all the duplicates will XOR out to 0 and then the singleton will be left at the end.
This holds true also for arrays in which you have even multiples of elements, not just duplicates, though it fails when there are odd multiples.
If you guys like this sort of stuff or need interview practice, here's a few more interesting problems I encountered at career fairs/interviews and company visit sessions: 1. This problem is similar to the one I posed before, but it has a pretty major twist. The problem statement is to find the missing integer in the array with the following rules: a. An array A contains every integer from 0 to N except for one of them. b. The elements of the array A may appear in any order. c. We can't actually access an entire element of the array all at once. In other words if you index the array you won't get back the whole element. + Show Spoiler +in other words, normally if you access an array element at index i, you would call A[i] and you would be returned the element at the ith position in A. In this problem you can't do that. Instead, what you can do is ask for the jth bit of the ith element of the array. In other words, I could ask for the 4th bit of the first element of A, and I would be returned the bit in the 4th position of the element ordinarily given by A[0]. d. The algorithm must return the missing integer by looking through at most O(N) bits. 2. Give an approach (or code) to writing an equivalent of the C function atoi. + Show Spoiler +I've also been asked how to implement strlen If you're not a C programmer, atoi is a function that converts an ASCII string to an integer. Describe the limitations or shortcomings of your approch (or code) in as much detail as you can. 3. Suppose we have a function that computes rand2() (i.e. a fair coin toss-it outputs 1 or 2 with equal probability). Design an algorithm that uses this function to simulate a fair die roll, i.e. a function that should output a random number from 1 to 6 with equal probability. I don't really understand the bit lookup constraint on problem 1. What do you mean by "looking through at most O(N) bits". O(N) is not an amount, it's a complexity. So are you trying to say "at most N bits", or are you trying to say that the number of lookups should not increase more than linearly with N? I don't see how it could be the first, so I'm going to assume the second. If I further assume that the integers are of a fixed size (32-bit unsigned integers for example), then I can trivially write a function to bypass your constraints with the number of lookups varying linearly with N. If N has no upper limit in the problem, then technically I believe the trivial bypass becomes N*log(N). Please clarify, BUT + Show Spoiler +I think the problem can be solved using the XOR trick again like the other problem. In the other problem, numbers were in equal pairs, so XORing them canceled out all except the one without a pair. In this problem, every number has a pair (0, N), (1, N-1), (2, N-2), etc. If you invert all numbers greater than N/2 prior to XORing, then you have equal pairs again. By invert, I mean invert(x) = N - x. I think the remaining XOR sum will either be the missing number or its inverse (it depends on how many inversions you did while traversing the list). Of course, all of this is assuming I am allowed to trivially bypass your constraint
You cannot assume fixed size numbers, and you are correct in assuming the second understanding of O(N). But, to xor two numbers together, you must look at all of their bits, i.e. 2*logN bit accesses, which will lead you to O(NlogN) accesses total.
I solved the problem on the previous page if you're interested.
|
On October 22 2013 07:05 waxypants wrote:Show nested quote +On October 19 2013 20:07 wherebugsgo wrote:On October 19 2013 16:33 spinesheath wrote:On October 19 2013 15:55 wherebugsgo wrote:
You're given an array of numbers such that every element in the array is duplicated except for one. Provide an efficient algorithm to determine the singleton element. Is that the exact wording of the question? Does "duplicated" mean that the duplicate and the original are in unrelated slots of the array, or are they adjacent? Can there be multiple sets of duplicates of the same number, as in 2, 4, 6 of the number? What range are the numbers from? Then there also is the question how one defines efficient. It's an inefficient use of programmer time if you don't just use some stupid algorithm that works and is easy to read and understand. Unless that piece of code is a performance bottleneck that needs to be faster. But I'm going to assume that low execution time is the goal here anyways. I paraphrased, but basically you can expect to encounter two of every element in the array except for one element. The array is unsorted and the duplicates can appear anywhere. There won't be multiple (read: more than 2) instances of the same number, though the answer would remain the same for even-number duplicates-i.e. you could have 4 of the same number and 2 of another and 6 of another and finding the singleton still works the same. There is no specification on the range of the numbers, though you can assume that you won't need multiple data structures to represent a single number. i.e. if it makes it easier for you, assume they are 32 bit ints or whatever. My first solution required O(nlogn) time, and O(1) space. I pretty quickly realized that the time complexity can be improved to O(n) time and there's a relatively simple way of doing that by adding a data structure that takes O(n) space, but the "brilliant" answer (as the interviewer described it-I'd call it elegant) requires no additional space and is also O(n) time. + Show Spoiler [my shitty answer] +Sort the array, then step through the array until you find that two consecutive elements are not the same. Sorting takes O(nlogn) time and stepping through the array takes O(n) time; O(nlogn + n) is in O(nlogn).
You could use radix sort and get an O(n) sort, I suppose. Instead of sorting the array, maintain a hash table and a second sum variable. Iterate through the array and for each integer, check if it's in the hash table. If it isn't, then add it to the sum, and store it. If it is, then subtract it from the sum. When we've gone through the entire array, the singleton is the only element we never subtracted, thus the sum variable is the singleton.
This works in O(n) time since hash accesses are O(1), and we need O(n) space for the hash table.
Just iterate through the array and XOR everything together. A[0] XOR A[1] XOR .... XOR A[n]. The result of this computation is the singleton element.
This works since XOR is commutative and associative. a XOR a is just 0, and 0 XOR a is a. Since all of the elements are duplicated except one of them, all the duplicates will XOR out to 0 and then the singleton will be left at the end.
This holds true also for arrays in which you have even multiples of elements, not just duplicates, though it fails when there are odd multiples.
If you guys like this sort of stuff or need interview practice, here's a few more interesting problems I encountered at career fairs/interviews and company visit sessions: 1. This problem is similar to the one I posed before, but it has a pretty major twist. The problem statement is to find the missing integer in the array with the following rules: a. An array A contains every integer from 0 to N except for one of them. b. The elements of the array A may appear in any order. c. We can't actually access an entire element of the array all at once. In other words if you index the array you won't get back the whole element. + Show Spoiler +in other words, normally if you access an array element at index i, you would call A[i] and you would be returned the element at the ith position in A. In this problem you can't do that. Instead, what you can do is ask for the jth bit of the ith element of the array. In other words, I could ask for the 4th bit of the first element of A, and I would be returned the bit in the 4th position of the element ordinarily given by A[0]. d. The algorithm must return the missing integer by looking through at most O(N) bits. 2. Give an approach (or code) to writing an equivalent of the C function atoi. + Show Spoiler +I've also been asked how to implement strlen If you're not a C programmer, atoi is a function that converts an ASCII string to an integer. Describe the limitations or shortcomings of your approch (or code) in as much detail as you can. 3. Suppose we have a function that computes rand2() (i.e. a fair coin toss-it outputs 1 or 2 with equal probability). Design an algorithm that uses this function to simulate a fair die roll, i.e. a function that should output a random number from 1 to 6 with equal probability. I don't really understand the bit lookup constraint on problem 1. What do you mean by "looking through at most O(N) bits". O(N) is not an amount, it's a complexity. So are you trying to say "at most N bits", or are you trying to say that the number of lookups should not increase more than linearly with N? I don't see how it could be the first, so I'm going to assume the second. If I further assume that the integers are of a fixed size (32-bit unsigned integers for example), then I can trivially write a function to bypass your constraints with the number of lookups varying linearly with N. If N has no upper limit in the problem, then technically I believe the trivial bypass becomes N*log(N). Please clarify, BUT + Show Spoiler +I think the problem can be solved using the XOR trick again like the other problem. In the other problem, numbers were in equal pairs, so XORing them canceled out all except the one without a pair. In this problem, every number has a pair (0, N), (1, N-1), (2, N-2), etc. If you invert all numbers greater than N/2 prior to XORing, then you have equal pairs again. By invert, I mean invert(x) = N - x. I think the remaining XOR sum will either be the missing number or its inverse (it depends on how many inversions you did while traversing the list). Of course, all of this is assuming I am allowed to trivially bypass your constraint
+ Show Spoiler +
Also, I believe you can go through one bit at a time, XORing all of the bit 0s, then all of the bit 1s, bit 2s, etc. Based on the results of each (compared to what you expect the result to be IF all the numbers were present), you can figure out the missing bit 0, bit 1, bit 2, etc. This is N*log(N) lookups though, so I'm not sure if it qualifies.
|
I think the only appropriate solution to any of these problems, would be to reconsider why you would even run into them, since pretty much all of them are so absurd that they only should occur in terrible design.
|
On October 22 2013 07:15 gedatsu wrote:Show nested quote +On October 22 2013 07:05 waxypants wrote:On October 19 2013 20:07 wherebugsgo wrote:On October 19 2013 16:33 spinesheath wrote:On October 19 2013 15:55 wherebugsgo wrote:
You're given an array of numbers such that every element in the array is duplicated except for one. Provide an efficient algorithm to determine the singleton element. Is that the exact wording of the question? Does "duplicated" mean that the duplicate and the original are in unrelated slots of the array, or are they adjacent? Can there be multiple sets of duplicates of the same number, as in 2, 4, 6 of the number? What range are the numbers from? Then there also is the question how one defines efficient. It's an inefficient use of programmer time if you don't just use some stupid algorithm that works and is easy to read and understand. Unless that piece of code is a performance bottleneck that needs to be faster. But I'm going to assume that low execution time is the goal here anyways. I paraphrased, but basically you can expect to encounter two of every element in the array except for one element. The array is unsorted and the duplicates can appear anywhere. There won't be multiple (read: more than 2) instances of the same number, though the answer would remain the same for even-number duplicates-i.e. you could have 4 of the same number and 2 of another and 6 of another and finding the singleton still works the same. There is no specification on the range of the numbers, though you can assume that you won't need multiple data structures to represent a single number. i.e. if it makes it easier for you, assume they are 32 bit ints or whatever. My first solution required O(nlogn) time, and O(1) space. I pretty quickly realized that the time complexity can be improved to O(n) time and there's a relatively simple way of doing that by adding a data structure that takes O(n) space, but the "brilliant" answer (as the interviewer described it-I'd call it elegant) requires no additional space and is also O(n) time. + Show Spoiler [my shitty answer] +Sort the array, then step through the array until you find that two consecutive elements are not the same. Sorting takes O(nlogn) time and stepping through the array takes O(n) time; O(nlogn + n) is in O(nlogn).
You could use radix sort and get an O(n) sort, I suppose. Instead of sorting the array, maintain a hash table and a second sum variable. Iterate through the array and for each integer, check if it's in the hash table. If it isn't, then add it to the sum, and store it. If it is, then subtract it from the sum. When we've gone through the entire array, the singleton is the only element we never subtracted, thus the sum variable is the singleton.
This works in O(n) time since hash accesses are O(1), and we need O(n) space for the hash table.
Just iterate through the array and XOR everything together. A[0] XOR A[1] XOR .... XOR A[n]. The result of this computation is the singleton element.
This works since XOR is commutative and associative. a XOR a is just 0, and 0 XOR a is a. Since all of the elements are duplicated except one of them, all the duplicates will XOR out to 0 and then the singleton will be left at the end.
This holds true also for arrays in which you have even multiples of elements, not just duplicates, though it fails when there are odd multiples.
If you guys like this sort of stuff or need interview practice, here's a few more interesting problems I encountered at career fairs/interviews and company visit sessions: 1. This problem is similar to the one I posed before, but it has a pretty major twist. The problem statement is to find the missing integer in the array with the following rules: a. An array A contains every integer from 0 to N except for one of them. b. The elements of the array A may appear in any order. c. We can't actually access an entire element of the array all at once. In other words if you index the array you won't get back the whole element. + Show Spoiler +in other words, normally if you access an array element at index i, you would call A[i] and you would be returned the element at the ith position in A. In this problem you can't do that. Instead, what you can do is ask for the jth bit of the ith element of the array. In other words, I could ask for the 4th bit of the first element of A, and I would be returned the bit in the 4th position of the element ordinarily given by A[0]. d. The algorithm must return the missing integer by looking through at most O(N) bits. 2. Give an approach (or code) to writing an equivalent of the C function atoi. + Show Spoiler +I've also been asked how to implement strlen If you're not a C programmer, atoi is a function that converts an ASCII string to an integer. Describe the limitations or shortcomings of your approch (or code) in as much detail as you can. 3. Suppose we have a function that computes rand2() (i.e. a fair coin toss-it outputs 1 or 2 with equal probability). Design an algorithm that uses this function to simulate a fair die roll, i.e. a function that should output a random number from 1 to 6 with equal probability. I don't really understand the bit lookup constraint on problem 1. What do you mean by "looking through at most O(N) bits". O(N) is not an amount, it's a complexity. So are you trying to say "at most N bits", or are you trying to say that the number of lookups should not increase more than linearly with N? I don't see how it could be the first, so I'm going to assume the second. If I further assume that the integers are of a fixed size (32-bit unsigned integers for example), then I can trivially write a function to bypass your constraints with the number of lookups varying linearly with N. If N has no upper limit in the problem, then technically I believe the trivial bypass becomes N*log(N). Please clarify, BUT + Show Spoiler +I think the problem can be solved using the XOR trick again like the other problem. In the other problem, numbers were in equal pairs, so XORing them canceled out all except the one without a pair. In this problem, every number has a pair (0, N), (1, N-1), (2, N-2), etc. If you invert all numbers greater than N/2 prior to XORing, then you have equal pairs again. By invert, I mean invert(x) = N - x. I think the remaining XOR sum will either be the missing number or its inverse (it depends on how many inversions you did while traversing the list). Of course, all of this is assuming I am allowed to trivially bypass your constraint You cannot assume fixed size numbers, and you are correct in assuming the second understanding of O(N). But, to xor two numbers together, you must look at all of their bits, i.e. 2*logN bit accesses, which will lead you to O(NlogN) accesses total. I solved the problem on the previous page if you're interested.
Ok I will think more about it then.
|
On October 22 2013 07:17 Yoshi- wrote:
I think the only appropriate solution to any of these problems, would be to reconsider why you would even run into them, since pretty much all of them are so absurd that they only should occur in terrible design.
Boo! Hiss!
|
On October 22 2013 07:17 Yoshi- wrote:
I think the only appropriate solution to any of these problems, would be to reconsider why you would even run into them, since pretty much all of them are so absurd that they only should occur in terrible design.
Because they are fun and they stretch your brain a little bit? The process and analysis/comparison of different solutions are more important than the solution itself in terms of learning. Although, coming up with the cleverest/fastest solution is where the fun part comes in.
|
On October 22 2013 07:03 n0ah wrote:
Is there anything like a "light-weight" C compiler? I want to re-teach myself C in my free time, but I don't want to install a bunch of resource-heavy software. Any suggestions?
cygwin or install dualboot linux for gcc
|
On October 22 2013 07:03 n0ah wrote:
Is there anything like a "light-weight" C compiler? I want to re-teach myself C in my free time, but I don't want to install a bunch of resource-heavy software. Any suggestions?
GCC is your best bet. No C compiler is really that heavy, but the associated build tools and libraries can take up quite a bit of disk space. http://www.mingw.org/ is one of the best ports for Windows. Nearly every distro of Linux already has GCC installed.
If you want to relearn C, though, I would suggest picking up a 30$ arduino board and screwing around with hardware. It's fun and will probably teach you a bunch.
Edit: Or Cygwin works, but I file that under the "resource-heavy software" category.
|
A quick search turned up TCC (tiny c compiler). I downloaded it, it's a couple megs and compiled HelloWorld just fine on Windows! I imagine though that it has some quirks, so you're better off using MingW or gcc if you want to avoid a bloated install of MSVC with IDE. For the record, I've never used MingW, but I assume it's good and relatively lightweight.
|
Actually I do have an Arduino board... I buried it in my closet a long time ago haha... I guess I could pull that out and try some stuff... I just miss programming (I'm a computer engineer, not computer scientist). My programming skills were never excellent or anything, and I don't feel like I learned all of the concepts from my school so I wanted to go through it again in my free time.
Thanks for your replies guys.
|
On October 22 2013 07:46 waxypants wrote:
A quick search turned up TCC (tiny c compiler). I downloaded it, it's a couple megs and compiled HelloWorld just fine on Windows! I imagine though that it has some quirks, so you're better off using MingW or gcc if you want to avoid a bloated install of MSVC with IDE. For the record, I've never used MingW, but I assume it's good and relatively lightweight.
Yeah, TCC works as well as long as you stick to the standard C library, which is probably the case.
|
On October 22 2013 07:30 RoyGBiv_13 wrote:Show nested quote +On October 22 2013 07:03 n0ah wrote:
Is there anything like a "light-weight" C compiler? I want to re-teach myself C in my free time, but I don't want to install a bunch of resource-heavy software. Any suggestions? GCC is your best bet. No C compiler is really that heavy, but the associated build tools and libraries can take up quite a bit of disk space. http://www.mingw.org/ is one of the best ports for Windows. Nearly every distro of Linux already has GCC installed. If you want to relearn C, though, I would suggest picking up a 30$ arduino board and screwing around with hardware. It's fun and will probably teach you a bunch. Edit: Or Cygwin works, but I file that under the "resource-heavy software" category.
Imo, if you're going to spend $30, then the raspberry pi is a much more powerful tool
|
Hyrule19228 Posts
On October 22 2013 07:46 waxypants wrote:
A quick search turned up TCC (tiny c compiler). I downloaded it, it's a couple megs and compiled HelloWorld just fine on Windows! I imagine though that it has some quirks, so you're better off using MingW or gcc if you want to avoid a bloated install of MSVC with IDE. For the record, I've never used MingW, but I assume it's good and relatively lightweight.
mingw is great. There's a bit more hassle setting it up compared to Cygwin, and it can be weird to use, but the end product is better imo
|
guys. i want to google something but i dont know the keywords. what i want to do is that i want a checker that checks if my { ends with }.
is it too confusing? i forgot what that is called >.>
nvm. ctrl+f does the trick lol
|
|
|
|
|
|
EPT
