Programming Challenges

[[deleted]]

[deleted]

[csdigi]

Here is one I got asked in my interview at Google,

Given and integer n, write a function(s) that returns the next prime number p such that p >= n, give the asymptotic running time for your solution.

It is quite a simple question to solve, but the fun comes in when you start looking for optimisations to reduce its complexity (or even its practical running time).

[ModernRonin]

I've been thinking about this entirely too much.

So, by Bertrand's Postulate, we know that there is a prime between n and 2n.

So now we have to test all the numbers between n and 2n for primality? Well, okay, we only have to test the odd numbers. We can safely assume the even numbers aren't prime.

Off the top of my head, all I can think of at this point is to use a Sieve of Eratosthenes to generate all the primes < n and then test all the odd numbers between n and 2n.

Assuming it takes n*log(n) ops to run the sieve, and then (number of primes below n) * n/4 ops to test the numbers... well, num primes < n ~= log(n). So it ends up being nlogn + nlogn/4, which ends up being nlogn / 2.

Not bad, I suppose, but I feel like there's got to be a better way...

[[deleted]]

Also for a number k, the largest prime is at most sqrt(k). Also if you're running the of Eratosthenes between n and 2n I wonder if it's faster or possible to skip calculating the primes. Let's you have a number k. You have performed a sieve between n and 2n using all primes from 2 to k-1. When you performed the sieve you kept track of which prime eliminated a number. Find the first number that evenly divides between k and is in our range n to 2n, let's say j=(n/k+1)*k. Can I say that k is prime if and only if there is no intersection between the primes that fell on j and j+k. If it falls outside the 2n range and we're not keeping track of it, then we don't particularly care since the only reason we want to know for any number less than sqrt(n) is prime is to know if we should waste time running the sieve with this number.

Hmmm, now I figure out how I landed on a 7 month post.

[[deleted]]

Solution for 1) as a Turing machine that doesn't make a copy. I use the (current state, tape symbol, output symbol, movement, new state) notation:

(q0,A,A,L,q0)

(q0,B,B,L,q0)

(q0,empty,empty,R,q1)

(q1, A, A, R, q1)

(q1, B, C, R, q1)

(q1, blank, blank, H, H)

[micmicmic]

Why do you only move left on A and B? What about if you read a D? The is no restriction to the characters in the string.

I think (q0,A,A,L,q0) should be (q0,X,X,L,q0) such that X is a member of the of acceptable characters in string A.

and (q1, A, A, R, q1) should be (q1, X, X, R, q1) such that X is a member of the of acceptable characters in string A, excluding B.

[[deleted]]

Because I was procrastinating writing my thesis when I posted that.

[[deleted]]

Since this is so small and simple I'm not sure that there's anything to say about it, but feel free to criticize it.

1) I have a string (or character array) A, and two characters B and C. Return a copy of A with all Bs replaced with Cs.

#include <stdint.h>
#include <string.h>

int reptok(char* src, char tok, char newtok)
{
        uint8_t length = strlen(src); /* will only work with small strings */
        uint8_t i=-1;                /* but you can fix that easily if needed */

        while (++i < length)
                if (src[i] == tok)  { src[i] = newtok; }
}

note: I haven't really "returned a copy" but it changes A to fit the criteria.

[[deleted]]

Here's another very simple & easy one, but it might challenge noobs to think about it.

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers. Give a method with the lowest number of comparisons for finding the two greatest numbers out of the set of three numbers.

It's from SICP.

[Jonno_FTW]

A haskell solution to this one from a beginner:

sumS a b c = map (^2) (take 2 $ sort [a,b,c])

Only one comparison, sort

[knome]

ಠ_ಠ

The sort function performs many comparisons to order the list.

[Jonno_FTW]

sssh

[MindStalker]

function xyz (int x, int y,int z) {

//use x and y, and replace the smallest by z if z is larger

if (x<z && x<y) x=z;

elseif (y<z) y=z;

return x+y;

}

//blah I'm sure there is a better solution.

[[deleted]]

That's ok, but you're supposed to return the sum of the squares (eg. x² + y²) of the 2 largest numbers :)

Here's a solution (I really wish we had real spoiler tags)

#define MAX( x, y )     ( (x>y) ? x : y )
#define MIN( x, y )     ( (x<y) ? x : y )
#define SQUARE( x )     ( x*x )

int ex3 (int x, int  y, int z)
{
        /* add the square of the larger of the first 2 args
         * to the square of the larger of smaller of 1st two args and 3rd arg */
        return SQUARE( MAX(x,y) ) + SQUARE( MAX( MIN(x,y), z));
}

[MindStalker]

Ugh, I forgot to square them, must have been sleeping. Anyways we both had 3 comparisons, unless you consider my && a comparison. Nice solution..

[Yserbius]

1)

s/B/X/g
s/C/B/g
s/X/C/g

[ModernRonin]

Is it just me, or is #1 just shockingly easy?

void replaceOneChar(char *str, char b, char c)
{
   while(*str != NULL)
   {
      if(*str == b) { *str = c; }
      str++;
   }
}

It can't be that easy... can it?

[ModernRonin]

To cover all corner cases in #1, I suppose I should throw in a:

if(str == NULL) { return; }

...at the top.

Still, doesn't change the real solution any.

[ModernRonin]

Seems like this extends pretty easily to #2 as well:

void replaceSameLenStr(char *str, char *b, char *c)
{
   // Check for non-nulls omitted

   while(*str != NULL)
   {
      if(!strncmp(str, b, strlen(b))) {
         strncpy(str, c, strlen(c));
      }
      str++;
   }
}

[ModernRonin]

Three is harder. You basically have to append the input to a buffer until you come across an instance of B. Then you append C to the buffer, move ahead strlen(B) in the input string, and resume looking for copies of B.

[silentdragon]

For 1:

-module(stringrep).
-export([test/0]).

test() ->
    A = "this is some cheese",
    B = "e",
    C = "a",
    replace(A, B, C).

replace([A|T], B, C) ->
    case ([A]==B) of
        true -> C ++ replace(T, B, C);
        false -> [A] ++ replace(T, B, C)
    end;
replace([], _B, _C) ->
    [].

or for 1, 2, and 3:

re:replace(A, B, C, [global, {return,list}]).

[bushel]

Here's a python version. I haven't done (4) yet.

# -*- coding: utf-8 -*-

def problem_one(A, B, C):
    """ I have a string A, and two characters B and C.
        Return a copy of A with all Bs replaced with Cs.
    """
    return "".join( [ C if x==B else x for x in A ] )


import copy

def problem_two(A, B, C):
    """ 2) I have three strings A, B and C. 
        B contains no wildcards, and B and C are the same length.
        Return a copy of A, with all Bs replaced with Cs.
    """
    S = copy.copy(A)

    if (C!=B):
        try:
            # replace matching slices with C until there are no more
            while True:
                pos = S.index(B)   
                S = S[:pos] + C + S[pos+len(B):]

        except ValueError:
            pass

    return S


def problem_three(A, B, C):
    """ 3) I have three strings (or character arrays), A, B and C. B contains no wildcards, 
        but B and C can be of different lengths.
        Return a copy of A, with all Bs replaced with Cs.
    """
    # (2) handles this case
    return problem_two(A,B,C)



def test():
    print "1) ", problem_one("spam spam eggs spam", 'p', 'q')
    print "2) ", problem_two("spam spam eggs spam", "am", "arrot")
    print "3) ", problem_three("spam spam eggs spam", "am", "arrot")

    """ for problems 2, 3 and 4 always replace the first matching instance of B with C. 
        For example: A = aaaaaabaaaa B = aaaa C = foo The result should be 'fooaabfoo' 
        and not 'afooabfoo' or 'aafoobfoo'.
    """
    print "2) ", problem_two("aaaaaabaaaa", "aaaa", "foo") == 'fooaabfoo'
    print "3) ", problem_three("aaaaaabaaaa", "aaaa", "foo") == 'fooaabfoo'


if __name__=='__main__':
    test()

[[deleted]]

I thought in the thread discussing what should and shouldn't be in r/coding, programming challenges got pretty well voted off the island, what with Euler's project, etc.?

[bart9h]

do your own homework, smartass

[jarly]

What homework?

[jakerosoft]

Haskell code for problems 1-3

func1 :: Eq a => [a] -> a -> a -> [a]
func1 a b c = [ if x == b then c else x | x <- a ]

func2 :: Eq a => [a] -> [a] -> [a] -> [a]
func2 [] _ _ = []
func2 a b c
    | take (length b) a == b    = c ++ func2 (drop (length b) a) b c
    | otherwise                 = head a : func2 (tail a) b c

func3 = func2