|
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 March 22 2017 19:03 dsyxelic wrote:oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers I went with array cause that seemed simpler k then thinking of it now with some code
def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False
though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison. this function would run in O(log n) total O(m log n), m = size of string s for character comparison or O(|S| log n) with the way you expressed it
Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with.
|
On March 23 2017 03:33 Acrofales wrote:Show nested quote +On March 22 2017 19:03 dsyxelic wrote:oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers I went with array cause that seemed simpler k then thinking of it now with some code
def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False
though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison. this function would run in O(log n) total O(m log n), m = size of string s for character comparison or O(|S| log n) with the way you expressed it Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with.
If you binary search it character by character, you have to do log N comparisons for each character of the input string. That's O(M*log(N)).
|
On March 23 2017 03:50 slmw wrote:Show nested quote +On March 23 2017 03:33 Acrofales wrote:On March 22 2017 19:03 dsyxelic wrote:oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers I went with array cause that seemed simpler k then thinking of it now with some code
def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False
though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison. this function would run in O(log n) total O(m log n), m = size of string s for character comparison or O(|S| log n) with the way you expressed it Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with. If you binary search it character by character, you have to do log N comparisons for each character of the input string. That's O(M*log(N)).
No you don't. You start with the beginning of the string. Once you're in the part of the array where your bounds match the first X characters, you only compare the X+1st character onwards, etc. Don't feel like writing out the code, because it's finicky and you have to deal with lots of corner cases, but I'll sketch it:
Search string: abcd
Array (with color codes for what the binary search checks, and strikethroughs for parts of string that are skipped):
aaaa
aaab
aaac
abbb
abbc
abcd
abce
abdd
addd
adde
addf
bcde
cccc
cccd
ccde
cddd
cdff
daaa
daba
dabc
ddaa
ddbb
dddd
So we start in the middle:
addf > abcd. But a matched, so we remember that
Next up: middle between start and addf: abbc
abbc < abcd. So now we know that everything between abbc and addf starts with a, so we move the search index up. Moreover, the second char matches too: b matched as well. So we remember that, and from now on skip the first char, so next: bdd
bdd > bcd. b is matched, so we know everything between abbc and abdd matches the first two chars. We once again move the search index up. Next test: cd == cd. We are done.
Thus we don't have to check m characters log n times. We have to check a couple of characters log n times, but m characters at most twice.
|
Obviously in the uniformly distributed case it is O(log N) as was established earlier in this thread. However in these types of puzzles we're usually talking about the worst case (and the prevailing question in the thread was whether there is anything better than O(M*log N) for the worst case). Your solution is O(M log N) as well in the worst case. "Couple of characters" and "at most twice" certainly isn't true in the general case.
|
On March 23 2017 04:18 Acrofales wrote:Show nested quote +On March 23 2017 03:50 slmw wrote:On March 23 2017 03:33 Acrofales wrote:On March 22 2017 19:03 dsyxelic wrote:oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers I went with array cause that seemed simpler k then thinking of it now with some code
def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False
though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison. this function would run in O(log n) total O(m log n), m = size of string s for character comparison or O(|S| log n) with the way you expressed it Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with. If you binary search it character by character, you have to do log N comparisons for each character of the input string. That's O(M*log(N)). No you don't. You start with the beginning of the string. Once you're in the part of the array where your bounds match the first X characters, you only compare the X+1st character onwards, etc. Don't feel like writing out the code, because it's finicky and you have to deal with lots of corner cases, but I'll sketch it: Search string: abcd Array (with color codes for what the binary search checks, and strikethroughs for parts of string that are skipped): aaaa aaab aaac abbb abbcabcdabce abddaddd adde addfbcde cccc cccd ccde cddd cdff daaa daba dabc ddaa ddbb dddd So we start in the middle: addf > abcd. But a matched, so we remember that Next up: middle between start and addf: abbc abbc < abcd. So now we know that everything between abbc and addf starts with a, so we move the search index up. Moreover, the second char matches too: b matched as well. So we remember that, and from now on skip the first char, so next: bdd bdd > bcd. b is matched, so we know everything between abbc and abdd matches the first two chars. We once again move the search index up. Next test: cd == cd. We are done. Thus we don't have to check m characters log n times. We have to check a couple of characters log n times, but m characters at most twice.
I agree with you in the typical and average case, but the worst case would be O(m*log(n)).
Note that for you algorithm the worst case would be that the string you are looking for is first or last in the list.
|
On March 23 2017 05:30 meadbert wrote:Show nested quote +On March 23 2017 04:18 Acrofales wrote:On March 23 2017 03:50 slmw wrote:On March 23 2017 03:33 Acrofales wrote:On March 22 2017 19:03 dsyxelic wrote:oh then i misinterpreted the question :/ they didnt specify what kind of list it was so I guess we can assume it's either an array implementation or a list by pointers I went with array cause that seemed simpler k then thinking of it now with some code
def match(list, s):
start = -1
end = len(list)
while end-start>1:
p = (start+end)/2
if list[p] == s:
return True
if list[p] > s:
end=p
else:
start=p
return False
though of course the comparisons would only work if I had a some other function to compare the characters of the string or the value of the string for alphabetical comparison. this function would run in O(log n) total O(m log n), m = size of string s for character comparison or O(|S| log n) with the way you expressed it Pretty sure it's not O(m*log n) but rather O(m + log(n)). You only have to walk through the string length a constant number of times if you keep track of the part of the string that you've already matched on both "bounds" of your binary search. Usually string length is completely negligible in comparison to the number of strings you have to look through, and if it's not, you should use a different data structure (like a trie) to solve the problem, and not a sorted array. But given the question was phrased explicitly to include the string length as a parameter, O(m + log(n)) is the best I can come up with. If you binary search it character by character, you have to do log N comparisons for each character of the input string. That's O(M*log(N)). No you don't. You start with the beginning of the string. Once you're in the part of the array where your bounds match the first X characters, you only compare the X+1st character onwards, etc. Don't feel like writing out the code, because it's finicky and you have to deal with lots of corner cases, but I'll sketch it: Search string: abcd Array (with color codes for what the binary search checks, and strikethroughs for parts of string that are skipped): aaaa aaab aaac abbb abbcabcdabce abddaddd adde addfbcde cccc cccd ccde cddd cdff daaa daba dabc ddaa ddbb dddd So we start in the middle: addf > abcd. But a matched, so we remember that Next up: middle between start and addf: abbc abbc < abcd. So now we know that everything between abbc and addf starts with a, so we move the search index up. Moreover, the second char matches too: b matched as well. So we remember that, and from now on skip the first char, so next: bdd bdd > bcd. b is matched, so we know everything between abbc and abdd matches the first two chars. We once again move the search index up. Next test: cd == cd. We are done. Thus we don't have to check m characters log n times. We have to check a couple of characters log n times, but m characters at most twice. I agree with you in the typical and average case, but the worst case would be O(m*log(n)). Note that for you algorithm the worst case would be that the string you are looking for is first or last in the list.
Hmm, you're right. I guess if you have something like:
aaaa
and your array is:
aaaa
aaab
aaac
etc.
You have to check m characters log n times, because you can never establish the baseline. Didn't think that one through. You are completely right.
|
thanks yall
was pretty fun thinking about this problem the last 2 days and definitely learned alot. especially about learning to understand the question in the first place x.x
|
Going over quiz for wednesday. It has this question
+ Show Spoiler +What is wrong with the following code?
#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}
I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x?
I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?
|
On March 26 2017 23:20 travis wrote:Going over quiz for wednesday. It has this question + Show Spoiler +What is wrong with the following code?
#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}
I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x? I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?
Not sure, but:
Since it is a local variable, the moment the programm exists the function, the memory adress still holds the value but is no longer protected and could be used to store a differerent value by another programm and therefore could contain something completely different. Propably unlikely that this happens in the given example but anyways... I feel like there are a lot of coding questions that are just irrelevant as soon as you follow certain best practices... at least for my interview for an internship a while back it was.
|
On March 26 2017 23:20 travis wrote:Going over quiz for wednesday. It has this question + Show Spoiler +What is wrong with the following code?
#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}
I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x? I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?
I'm not even sure what this code is supposed to do. Why would you do some arithmetic with x and then only return x's adress? I can't make sense out of this program's intention.
If the code is intended to add 200 to y and return the result, then the mistake is that we're returning x's adress instead of its actual value 
|
On March 26 2017 23:38 beg wrote:Show nested quote +On March 26 2017 23:20 travis wrote:Going over quiz for wednesday. It has this question + Show Spoiler +What is wrong with the following code?
#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}
I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x? I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time? I'm not even sure what this code is supposed to do. Why would you do some arithmetic with x and then only return x's adress? I can't make sense out of this program's intention.
I don't think it's meant for practical application
ok how about this question:
". Name one advantage of initializing pointer variables to NULL?"
Is an advantage of doing this, that if you don't initialize them to null then if your code doesn't assign them to an address somewhere, and you try to grab the pointer, it may really mess up your program and be hard to debug?
I suppose also if your program is using memory allocation and you free the pointer, it will be no problem if the pointer was initialized to null, but a big problem if it was never initialized.
|
On March 26 2017 23:41 travis wrote:Show nested quote +On March 26 2017 23:38 beg wrote:On March 26 2017 23:20 travis wrote:Going over quiz for wednesday. It has this question + Show Spoiler +What is wrong with the following code?
#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}
I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x? I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time? I'm not even sure what this code is supposed to do. Why would you do some arithmetic with x and then only return x's adress? I can't make sense out of this program's intention. I don't think it's meant for practical application ok how about this question: ". Name one advantage of initializing pointer variables to NULL?" Is an advantage of doing this, that if you don't initialize them to null then if your code doesn't assign them to an address somewhere, and you try to grab the pointer, it may really mess up your program and be hard to debug?
Yes. This is just a way to minimise the risk of stupid errors. If you don't initialize them with NULL, they could point to pretty much anything and can make debugging a mess since it can lead to inconsistent crashes.
|
Yea definitely. Did you see the edit of my last post?
|
On March 26 2017 23:38 beg wrote:Show nested quote +On March 26 2017 23:20 travis wrote:Going over quiz for wednesday. It has this question + Show Spoiler +What is wrong with the following code?
#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}
I wasn't sure so I ran the code. Compiler gave me a warning that it returns the address of a local variable (though the program works anyways). I am guessing the correct way to do this, if you don't want to use a global variable, is to pass a pointer to whatever variable you want to return back? So, like, I would have defined int x in main, pass the pointer of x to the function along with y, and then return the address of x? I have another question as well. Why is this actually a problem? If we do "p = get_val(y);", is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time? I'm not even sure what this code is supposed to do. Why would you do some arithmetic with x and then only return x's adress? I can't make sense out of this program's intention. If the code is intended to add 200 to y and return the result, then the mistake is that we're returning x's adress instead of its actual value
Why is that a problem? P is a pointer.
I mean we could make P an int and change our function and it would probably make more sense, but I don't see why this is a mistake as is.
|
Well shit, I just realized I never fiddled around with pointers to funciton. Nevermind. I'm playing around with it now.
EDIT: Yea you explained it correct in the same post where you asked the question
|
On March 26 2017 23:20 travis wrote:
is it even possible for something to sneak in there and mess with the memory that held our local variable x in that time?
Imagine if you did something like this instead:
#include <stdio.h>
#include <stdlib.h>
int *get_val(int y) {
int x = 200;
x += y;
return &x;
}
int main() {
int *p, y = 10;
int *w;
p = get_val(y);
w = get_val(100);
printf("%d%d\n", *p, *w);
exit(0);
}
Pretty sure that will break and you can figure out why its bad.
|
Oh blitz that's an excellent example, thank you.
Just to make sure I am on the right page here, the poblem is that when we dereference p and w in our print statement, they are both going to print from the same address, which currently holds the result of get_val(100) ?
|
On March 27 2017 00:45 travis wrote:
Oh blitz that's an excellent example, thank you.
Just to make sure I am on the right page here, the poblem is that when we dereference p and w in our print statement, they are both going to print from the same address, which currently holds the result of get_val(100) ?
The real problem is undefined behavior. When you're programming you have an expected result and this program does not always return the expected result because you're referencing a pointer that is out of scope. Because the pointer is declared in the function call, it is out of scope after the function ends and can be overwritten.
In the example you provided the print statement was immediately done and it probably wasn't a issue (note that this is still bad, the fact that it could have been wrong is still a problem even though it likely never happens).
In my example, the value is overwritten and the wrong value is printed.
In another example, you could get that memory allocated to another process and cause a segfault by trying to access memory in another process.
Bottom line is that you don't want to write code that can have undefined behavior. You can't know what will happen because it will depend on how the operating system assigns memory when the program is run.
|
On March 27 2017 00:45 travis wrote:
Oh blitz that's an excellent example, thank you.
Just to make sure I am on the right page here, the poblem is that when we dereference p and w in our print statement, they are both going to print from the same address, which currently holds the result of get_val(100) ?
Travis, have you learnt about memory layouts and the call stack yet? This is essentially the underlying reason for why the given program results in undefined behaviour.
https://en.wikipedia.org/wiki/Call_stack
When you call a function, we increment the stack pointer to make room for several things, including local variables of the function. So in your example, we're going to have some address on the stack which points to the local variable 'x'.
When the function terminates, we're going to decrement the stack pointer to where it was before the function was called. Therefore, referring to any of the locals from the function after we've returned now results in undefined behaviour.
Depending on what the function is actually supposed to do, I think the following might have been what was desired:
+ Show Spoiler +
#include <stdio.h>
#include <stdlib.h>
int * get_val(int y)
{
static int x = 200;
x += y;
return &x;
}
int main()
{
int *p, y = 10;
p = get_val(y);
printf("%d\n", *p);
exit(0);
}
|
Regardless of what that code does and is supposed to do, that is some absolutely horrendous coding. I understand asking you general questions that require you to understand C code, but does it really have to be so incredibly shitty?
|
|
|
|
|
|
EPT
