The Big Programming Thread - Page 859

Prev 1 857 858 859 860 861 1032 Next

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.

Nesserev

Belgium2760 Posts

March 09 2017 22:03 GMT

#17161

--- Nuked ---

netherh

United Kingdom333 Posts

March 09 2017 22:30 GMT

#17162

On March 10 2017 07:03 Nesserev wrote:

Show nested quote +

I don't see how you could write any decent code under 5 minutes to solve this problem.

Yeah. Took me about 15 minutes to create a basic solution and realise it didn't work, 30 minutes of trying to remember how reverse_iterators work (yay C++), and another 15 minutes of fiddling around and fixing edge cases.

Googling shows there are better ways of doing this (and would be the first step anywhere other than interviews I guess...).

+ Show Spoiler +


#include <string>
#include <array>
#include <iostream>
#include <algorithm>
#include <cassert>

int main(int, char*[])
{
	auto input = std::array<std::string, 9u>{ "", "a", "ab", "abc", "aa", "cac", "aabbbabab", "aabbaa", "carracecar" };

	auto best = std::string();

	for (auto const& s : input)
	{
		if (s.size() < 2u)
			continue;

		// won't find a longer palindrome in a shorter or equal string
		if (s.size() <= best.size())
			continue;

		std::cout << "checking: " << s << std::endl;

		for (auto i = s.begin(); std::next(i) != s.end(); ++i)
		{
			using RIt = std::reverse_iterator<std::string::const_iterator>;

			// i is the start of a palindrome (e.g. the first 'a' in "aa")
			auto even = std::mismatch(std::next(i), s.end(), RIt(std::next(i)), s.rend());

			auto even_first = even.second.base();
			auto even_last = even.first;
			auto even_length = std::distance(even_first, even_last);

			assert(even_length >= 0);
			auto even_length_u = static_cast<unsigned int>(even_length);

			if (even_length_u > 1 && even_length_u > best.size())
				best = std::string(even_first, even_last);

			// i is the middle of a palindrome (e.g. the 'a' in "cac")
			auto odd = std::mismatch(std::next(i), s.end(), RIt(i), s.rend());

			auto odd_first = odd.second.base();
			auto odd_last = odd.first;
			auto odd_length = std::distance(odd_first, odd_last);

			assert(odd_length >= 0);
			auto odd_length_u = static_cast<unsigned int>(odd_length);

			if (odd_length_u > 1 && odd_length_u > best.size())
				best = std::string(odd_first, odd_last);
		}

		std::cout << "best so far: " << best << " " << best.size() << std::endl;
	}

	std::cout << "best: " << best << " " << best.size() << std::endl;
}

slmw

Finland233 Posts

March 09 2017 22:36 GMT

#17163

O(N^2) per word should be simple enough to do in five minutes for anyone with a bit of competitive programming practice. O(N) is quite a bit tougher with all the index fiddling and potential one off errors.

Khalum

Austria831 Posts

March 10 2017 01:18 GMT

#17164

5 minutes are more than enough for a trivial approach. It won't be pretty but it should work.

I'm curious why the string as well as the length are valid outputs. The approach is the same?

meatpudding

Australia520 Posts

March 10 2017 01:25 GMT

#17165

This took me 7 minutes and it still doesn't quite work. Basic idea is to "fan out" both ways from each character and stop when the palindrome ends. Store the longest palindrome word and print it.

def palin(s):
    longest_n = 0
    longest_start = 0
    start = 0
    end = 0
    for i in range(len(s)):
        start = i
        end = i
        while (s >= 0 and end < len(s)):
            if (s[start] == s[end]):
                n = end - start + 1
                if (n > longest_n):
                    longest_n = n
                    longest_start = start
            else:
                break
            start -= 1
            end += 1
        
    print longest_n, s[longest_start:longest_start + longest_n]


palin("carracecar")
palin("aabbaa")
palin("aabbbabab")

Output:

7 racecar
3 
5 abbba

I only just realised that this will only work for odd palindromes.

tofucake

Hyrule19260 Posts

March 10 2017 01:43 GMT

#17166

I just had an interview today with a palindrome question. In JS it takes about 30 seconds to read the instructions, think, then type out


function isPalindrome(possiblePalindrome) {
    return possiblePalindrome == possiblePalindrome.split('').reverse().join('').toString();
}

making it support an array and finding the longest palindrome of the bunch is another 2 minutes :\

Hanh

146 Posts

March 10 2017 01:55 GMT

#17167

Still too long! Heh

 
let is_palindrome s = rev s = s

Deleted User 3420

24492 Posts

March 10 2017 02:24 GMT

#17168

This is what I did. took 15-20 min cuz i kept making stupid mistakes


    public static int find(ArrayList<String> words) {
       int size = 1;
       int total = 0;
       for(String w : words) {

           for(int i = 0; i < w.length() - 1; i++) {
               int front = 1, back = 1;
               while(((i - back >= 0) && (i + front <= w.length() - 1) && (w.charAt(i + front) == w.charAt(i - back)))) {
                    size += 2;
                    back++;
                    front++;
               }
               if (size > total) {
                   total = size;
               }
               size = 1;
           }
       }
       return total;
    }

pretty sure this is O(n) unless we are dealing with the longest strings of all time

I didn't record the actual string because blisse said I didn't have to. but I could if I needed to it would just be a very mildly painful addition

edit: I guess slmw was talking about beating O(n^2) per word, which makes more sense because why would you have to iterate through words more than once

So looking at the complexity of this per word... mmmm..
I really am not sure? I guess it's technically O(n^2) but it's like a really good O(n^2), and that's worst case.

maybe someone who is good at complexity could look at this and tell me what the complexity per word is?

slmw

Finland233 Posts

March 10 2017 02:37 GMT

#17169

Simplest O(N^2) per word implementation I could think of, very similar to your python solution. O(N) per word was quite a bit tougher to do and definitely over 5 minutes. :D

On March 10 2017 10:18 Khalum wrote:
I'm curious why the string as well as the length are valid outputs. The approach is the same?

It's just basically a matter of formatting the output.

On March 10 2017 10:43 tofucake wrote:
I just had an interview today with a palindrome question. In JS it takes about 30 seconds to read the instructions, think, then type out


function isPalindrome(possiblePalindrome) {
    return possiblePalindrome == possiblePalindrome.split('').reverse().join('').toString();
}

making it support an array and finding the longest palindrome of the bunch is another 2 minutes :\

You gotta still create all the substrings though so a bit more programming left to do!. Also this is O(N^3) per word!

On March 10 2017 11:24 travis wrote:
This is what I did. took 15-20 min cuz i kept making stupid mistakes


    public static int find(ArrayList<String> words) {
       int size = 1;
       int total = 0;
       for(String w : words) {

           for(int i = 0; i < w.length() - 1; i++) {
               int front = 1, back = 1;
               while(((i - back >= 0) && (i + front <= w.length() - 1) && (w.charAt(i + front) == w.charAt(i - back)))) {
                    size += 2;
                    back++;
                    front++;
               }
               if (size > total) {
                   total = size;
               }
               size = 1;
           }
       }
       return total;
    }

This is O(N^2) per word, but doesn't it work just for odd palindromes? https://ideone.com/ke4q0k

Deleted User 3420

24492 Posts

March 10 2017 02:38 GMT

#17170

oh duh of course it only works for odd palindromes

looking up i probably did whatever meatpudding was doing

tbh I never even realized it was a palindrome if it wasn't odd, lol. the problem would be a million times harder for me including even palindromes

basically I'd be writing all separate code to handle even palindromes

it'd still be O(n^2) though

WarSame

Canada1950 Posts

March 10 2017 05:11 GMT

#17171

Do any of you know a good place to go for code review? I want to have my git repo checked to see if there are better coding decisions I could have made. Is there some sort of dedicated area or site for that?

ShoCkeyy

7815 Posts

March 10 2017 05:57 GMT

#17172

WarSame depending on the language, you can ask some one in the freenode irc chat. I'm sure some one there or here would be willing to review.

Hanh

146 Posts

March 10 2017 06:05 GMT

#17173

On March 10 2017 11:38 travis wrote:
oh duh of course it only works for odd palindromes

it'd still be O(n^2) though

Don't worry too much about performance. Focus on correctness first. There is no point in returning a wrong result quickly.
Looking back at this thread, the people who talk about how easy the question is have yet to give a good answer.

Manit0u

Poland17850 Posts

March 10 2017 08:04 GMT

#17174

On March 10 2017 14:11 WarSame wrote:
Do any of you know a good place to go for code review? I want to have my git repo checked to see if there are better coding decisions I could have made. Is there some sort of dedicated area or site for that?

What language? I love code reviews

Cynry

810 Posts

March 10 2017 08:56 GMT

#17175

Anyone here knows golang, and have used the mongodb official drivers (mgo) ?
I've been working for almost 2 years with mongo in js without an issue, but ever since I started go every single query that I have to do is a pain in the ass.

It's my first project in go, soooo todolist it is !
And here's the query that is driving me nuts lately:

func (u *User) getNextTask(date time.Time) (Task, error) {
	task := Task{}
	query := bson.M{
		"id":        bson.M{"$in": u.Tasks},
		"timestamp": bson.M{"$gte": date},
	}
	err := Tasks.Find(query).Sort("timestamp").Limit(1).One(&task)
	if err != nil {
		return task, err
	}
	return task, nil
}

Simply receives a date, get the tasks that have been created after, sort them by ascending order to get the next one, limit to one result, etc. It doesn't even get here anyway.
The query doesn't return anything, although everything I've checked is correct. I receive a proper date, u.Tasks does contain an array of bson.ObjectIds (the query works when I remove the timestamp part, so this is fine). There is at the moment of the tests, at least a task that has should match the query (same user, created after, can be checked if I do the same query without the timestamp part).
So it apparently comes from that very line

"timestamp": bson.M{"$gte": date},

but I can't see what's wrong with it. At this point I suspect a typo or something silly like that, but I seem to need an exterior look... So, anyone ?

Palindrome challenge: All I could come up in 5 minutes was some pseudo code that didn't work for odd palindromes... forgot about those ^^

Khalum

Austria831 Posts

March 10 2017 10:34 GMT

#17176

On March 10 2017 15:05 Hanh wrote:
[..]
Looking back at this thread, the people who talk about how easy the question is have yet to give a good answer.

Fair point! I had just come home from a night of drinking and would definately not have given a good answer then

Am still a bit drunk but I gave it a shot to put my money where my mouth was. My solution is probably not correct. I hacked it in 7 minutes (yes, more than 5...) so I guess I failed anyways. Now back to sleep.


int palindromeLength(string s)
{
    for (int i=0; i<s.length()/2; ++i)
    {
        if (s[i] != s[s.length()-1-i])
        {
            return 0;
        }
    }
    return s.length();
}

int getLongestPalindrome(string s)
{
    int maxLen = 0;
    for (string::iterator ita=s.begin(); ita<s.end()-maxLen-1; ++ita)
    {
        for (string::iterator itb=ita+maxLen+1; itb<s.end(); ++itb)
        {
            maxLen = max(maxLen, palindromeLength(string(ita,itb)));
        }
    }
    return maxLen;
}

[edit]
This is missing a function that calls getLongestPalindrome() with some strings to be tested and collects the max of these.

[edit2]
Fixed 2 errors. Yes, I cheat.

netherh

United Kingdom333 Posts

March 10 2017 13:42 GMT

#17177

Well there's this:

http://codereview.stackexchange.com/

I think you're supposed to include code in the question though, so depends on how large your repo is, or if you can extract specific bits of code.

Deleted User 3420

24492 Posts

March 10 2017 14:04 GMT

#17178

Situation in C:

I want to pass a char pointer to a function.
Then go through the memory, and find integers.
Store those integers into a character array.
And then return the pointer to the new character array (that only holds the integers).

But because my character array is local to the function it becomes garbage when my function ends, so this doesn't work
But I am not supposed to use dynamic memory allocation, and im not supposed to use global variables

so how do I do what I am describing?

edit: is what I need to do, to declare my character array before i call my function, and then pass a pointer to it to my function? god I hate C

slmw

Finland233 Posts

March 10 2017 14:17 GMT

#17179

If you allocate an array on the stack it gets cleaned up when you exit the function scope. If you allocate it on the heap, you're responsible for cleaning it up. If you need to do it on the stack, do everything before you exit the stack scope. It isn't that different from other languages.

waffelz

Germany711 Posts

March 10 2017 16:05 GMT

#17180

On March 09 2017 05:57 Nesserev wrote:

Show nested quote +

Have you checked out qemu yet? (http://www.qemu-project.org/)

I haven't, but I will check it out, Thanks for the suggestion.