• Anonymous slightly humbled Scheme weenie (unregistered)

    I think I win the incomprehensibility award for today since nobody has yet pointed out that my matching function was totally wrong, since the full original string was being passed in.

    The value of n from the outer function needed to be passed in as an offset, as shown below:

    (define (match-string str substr offset n)
     (if (= n (string-length substr))
       #t
      (if (char-ci=? (string-ref str (+ offset n)) 
                     (string-ref substr n))
        (match-string str substr offset (+ n 1))
        #f)))
    

    Also, the test in the outer function to stop execution and return the list should have been a strict greater than. This is easy to see from the case where the length of str and substr are the same.

  • KG (unregistered) in reply to Anonymous user who feels like a smug Scheme weenie today.
    Anonymous user who feels like a smug Scheme weenie today.:
    (define (match-string str substr n)
     (if (= n (string-length substr))
       #t
      (if (char-ci=? (string-ref str n) (string-ref substr n))
        (match-string str substr (+ n 1)
        #f)))
    

    (define (substring-indexes str substr) (let* ((laststrindex (- (string-length str) (string-length substr)) (recursive-substring-indexes (lambda (str substr n) (cond ((>= n laststrindex) '()) ((match-string str substr 0) (cons n (recursive-substring-indexes str substr (+ n 1))) (#t (recursive-substring-indexes str substr (+ n 1)))))))
    (recursive-substring-indexes str substr 0)))

    I don't think that's correct. Unless I'm mistaken, you're only ever testing if the beginning of your string matches the substring. Shouldn't the default case of your (cond) block be:

    (#t (recursive-substring-indexes
          (cdr str) substr (+ n 1)))
    

    Of course, then you'd need to revise the terminating condition of your algorithm.

    One thing I've always hated about LISP-style languages - they force you to use recursion when iteration would yield a much more elegant solution. Yes, recursion provides a nice abstraction at times, but leaving out iteration because recursion can replace it is like leaving out for-loops because while-loop can replace them, or leaving out swtich statements because if-elseif-elseif... chains can replace them.

  • notJoeKing (unregistered) in reply to RandomWTF
    RandomWTF:
    dpm:
    At least his question about changing positions of columns can be explained by simple ignorance. In this one, however, the error message is RIGHT THERE IN FRONT OF HIM; he is criminally guilty of being unable to develop code and should be moved over to Marketing immediately.

    Maybe he realizes that the '<' operator won't work, but has no idea how to compare dates in the language he is using. But he leaves that part in the code so that it is still clear what he is trying to do.

    I know that date/time functions can be horribly inconsistent between languages or platforms, and often takes a bit of time and research to figure it out.

    Regardless of language or platform, only an idiot would write the code "If Date.ToString < OtherDate" and then wonder what the compiler means when the error message clearly says "Hey stupid, you are trying to compare a date and a string, try again with 2 matching items.... like maybe a date and a date or a string and a string..."

  • KG (unregistered)

    How the heck did the formatting on my post get screwed up so badly? Well, the entire message is there at least (partly inside the "quote" tag), so I won't repost it.

  • Anonymous Coward (unregistered) in reply to Zolcos

    Addendum (2008-05-05 12:52): And by pre-increment, I meant add 3 or 5. LOL!

    while(fiz<=100&&buz<=100) std::cout << fiz<buz?((fiz+3)?"fiz":""):(buz<fiz?((buz+5)?"buz":""):(((fiz+3) + (buz+5)?"fizbuz":""))) << endl;</pre>[/quote]
    

    Though it still does not compile (even if you add the missing std:: to endl).

  • Small Distraction (unregistered)

    The code below fits the acceptance criteria, in O(n) time, but it fails where two possible substrings are next to each other (ie. PPolly)

    using System; using System.Collections.Generic;

    public class MyClass { public static void Main() { string text = "Polly put the kettle on, polly put the kettle on, polly put the kettle on we'll all have tea";

    	string[] tests = { "Polly", "polly", "ll", "x", "Polx" };
    	
    	try {
    		foreach (string test in tests) {
    			IList<int> results = FindSubstring(text, test);
    			DisplayResults(test, results);
    		}
    	
    	} catch (Exception ex) {
    		Console.WriteLine(ex.ToString());
    	}
    
    	Console.ReadLine();	
    }
    
    public static void DisplayResults(string subtext, IList<int> results) {
    	Console.Write("{0:1,20} : ", subtext);		
    	foreach (int i in results) {			
    		Console.Write(i + " ");
    	}
    	Console.WriteLine();
    }
    
    
    public static IList<int> FindSubstring(string text, string subtext) {
    	List<int> results = new List<int>();
    	
    	int j = 0;
    	for (int i = 0; i < text.Length; i++) {
    		
    		if (j == subtext.Length) {
    			results.Add(i - subtext.Length + 1);
    			j = 0;	
    		} else if ((j < subtext.Length) && (char.ToLower(text[i]) == char.ToLower(subtext[j]))) {
    			j++;
    		} else {
    			j = 0;
    		}
    		
    	}
    	
    	return results;
    }
    	
    

    }

  • Me. Mememememememememe. (unregistered) in reply to Zolcos
    Zolcos:
    Have a Fiz and Buz counter that increment by 3 and 5 respectively. Each iteration of the loop increments the lower counter and prints the corresponding string. When the two are equal, increment both and print "FizBuz". Runs in: ((n/3) + (n/5) - (n / (3+5))) operations. Maybe.

    I think this is O(n), but then I didn't major in Comp Sci.

    $ python
    >>> for i in range (1, 101):
    ...   out = "%3d " % i
    ...   if i/3 == i/3.0: out = out + "Fiz"
    ...   if i/5 == i/5.0: out = out + "Buz"
    ...   print out

    Counters?? Bah! :^)

    -- MHill

  • Anonymous slightly humbled Scheme weenie (unregistered) in reply to KG

    That's good that somebody else did notice where I went wrong. However, you can't use cdr directly on strings in Scheme; they're a type distinct from lists (unlike, for example, Elisp), though string->list is an available option.

    While you may be correct about Lisp-likes not providing iteration in general, Scheme is an exception as it does have several iteration constructs. The most general purpose and least transparent in how it looks is "do": http://schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx_138

    From there you have for-each, which can be considered an iterative semantic (same with map, filter, and fold), but to use it you have to start with a list. You can also define your own if you're so inclined.

  • johndoe (unregistered)

    yeah, i post teh c0de tkx

    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    
    int main(int ac, char** av)
    {
        char *text, *subtext;
        int i, j, res= 0, *result, subsz;
        if (ac != 3) printf("usage: %s [text] [subtext]\n", av[0]), exit(-1);
        text=av[1]; subtext=av[2];
        for (subsz=0;subtext[subsz];subsz++);
        for (i=0;text[i];i++);
        result = (int*)malloc(i*sizeof(int));
        for (i=0;text[i];i++) {
            j=0;
            while(j<subsz && ((subtext[j]&0xDF)==(text[i+j]&0xDF))) j++;
            if (j==subsz) { result[res]=i+1; res++; }
        }
        if (res) {
            for(i=0;i<res-1;i++) printf("%d, ", result[i]);
            printf("%d\n", result[res-1]);
        } else {
            printf("There is no output\n");
        }
        free(result);
    }
    </pre>
    
  • Peter (unregistered) in reply to Anon

    Not that I have any experience with this, but I would simply leave the questions unasked, then provide flags for the program (along with a man page) allowing you to account for any of those cases.

  • Mr. V (unregistered) in reply to The Enterpriser

    [Epic] Fail. Doesn't work for all capital letters (think: foreign languages), returns "`" for "@".

    It does remind me, though, the wonderful days of using an IBM machine with EBCDIC as a base charset, precisely because such a simple problem could not be solved in a similar way there. And EBCDIC is the True WTF, without a question.

  • Peter (unregistered) in reply to Me. Mememememememememe.

    Or in ruby... for(1..101) do |i| if((i/3)*3==i) print "Fiz" if((i/5)*5==i) print "Buz" puts end

    I'm pretty sure there's a for loop sort of way to only go over 3 and 5 to make it even more clever, but I don't remember it.

  • Yazeran (unregistered) in reply to ydrol
    ydrol:
    I always get nervous typing sql 'delete' statements, and when I remember I usually type 'select count(*)' instead and then replace it with 'delete' when I'm happy.
    Yep, quite a good approach, although I tend to use 'SELECT *' in order to actually SEE which rows will be affected and not just the number. But then again, I'm quite gun shy about any DELETE sql....

    Yazeran

    Plan: To go to Mars one day with a hammer.

  • Marc (unregistered) in reply to MyFACE

    TRWTF is that you guys actually have time to waste writing this :-/

    MyFACE:
    Thomas Winwood:
    I decided to write some code because I was bored and it was something to spend five minutes on. I've not tested it in "production", though I probably would if I was actually applying for the job.

    I'm using the Substring() and ToLower() methods, which doesn't seem to be against the rules (which only state that you're not allowed to use built-in methods which do the checking for you). If there's no matches then I return an empty list.

    List<int> StringIndex(string text, string subtext)
    {
        List<int> positionsFound = new List<int>();
    
        for (int pos = 0; pos < input.Length - 1; pos++)
        {
            if (text.ToLower().Substring(pos, subtext.Length) == subtext.ToLower())
            {
                positionsFound.Add(pos);
            }
        }
    
        return positionsFound;
    }

    I was under the impression that no calls to "substring" would be allowed? If it is allowed, that makes this significantly easier (not that implementing substring is that much more difficult). I wrote it assuming I couldn't, although I wrote it in C...

    void get_index_of( char* text, char* subtext, int* result )
    {
        // assumes result is big enough.
        textLen = strlen( text );
        subtextLen = strlen( subtext );
        bool found = false;
        int i = 0, j = 0, foundidx = 0;
    
        if( subtextLen > textLen )
            return; // do nothing.
    
        for( i = 0; i < textLen; i++ )
        {
            for( j = 0; j < subtextLen; j++ )
            {
                found = true;
                if( i + j >= textLen )
                {
                    found = false;
                    break;
                }
    
                if( tolower( subtext[ j ] ) != tolower( text[ i + j ] ) )
                {
                    found = false;
                    break;
                }
            }
    
            if( found )
                result[ foundidx++ ] = i;
        }
    }
    

    Note, I'm not sure if it even compiles as I'm sure I have typos and gross syntax errors but this ought to work.

    I have now proven that I am either incapable of implementing a simple function, or that I fit the stereotype of every other nerd on the internet that MUST solve any programming problem, no matter how trivial.

  • Matt (unregistered) in reply to Alex

    Everyone here who's posted a solution that involves something that takes a substring and an == during the iteration part

    e.g.

    int indexOf(string needle, string haystack){ for(int i=0, i<haystack.Length-needle.Length;i++){ if(haystack.Substring(i,needle.Length) == needle) return i; } return -1; }

    I would not hire, because this has exponential time AND memory cost. On the other hand, a better solution (which loses the exponential time cost):

    int indexOf(string needle, string haystack){ for(int i=0;i<haystack.Length-needle.Length;i++){ bool found = true; for(int j=0;j<needle.Length;j++){ if(haystack[i+j] != needle[j]){ found = true; break; } } if(found) return i; } return -1; }

    would be OK.

    An instant hire would be either an implementation or mention that there is a better method - the Boyer Moore algorithm - although I would not expect the candidate to memorize it.

  • Matt (unregistered) in reply to Matt

    Fixbuz in C#:

    class Program { const string Fiz = "Fizz"; const string Buz = "Buzz"; const string Fizbuz = "FizzBuzz"; const int start = 0, end = 400; static void Main(){ for(int i=start;i<end;i++){ string[] s = new string[end-start]; Parallel.For(start, end, i => s[i] = ((i%3==0 && i%5==0)? Fizbuz : ((i%3==0)? Fiz : ((i%5==0)? Buz : i.ToString()))); Console.Write(String.Join(", ", s)); }

  • Mike (unregistered)

    A solution in Java.

    /**
     * Returns a List of indexes in text that match subtext, 
     * or an empty List if there are no matches.
     * 
     * @throws NullPointerException if text or subtext are null
     */
    private static List<Integer> findMatches(String text, String subtext) {
    	List<Integer> matches = new ArrayList<Integer>();
    
    	final char[] textChars = text.toCharArray();
    	final char[] subtextChars = subtext.toCharArray();
    	final int n = textChars.length - subtextChars.length;
    
    	outer: 
    	for(int i = 0; i <= n; i++) {
    		for(int j = 0; j < subtextChars.length; j++) {
    			if(textChars[i+j] != subtextChars[j]) {
    				continue outer;
    			}
    		}
    		matches.add(i);
    	}
    
    	return matches;
    }
    
  • Andrew (unregistered) in reply to blindio
    blindio:
    Why not just skip the middle man, post the interview question directly on various internet help boards, then approach those who answer it with job offers. Should give about the same success rate.

    The ones who answer the questions on the help boards already have jobs.

  • Saaid (unregistered) in reply to Andrew
    Andrew:
    blindio:
    Why not just skip the middle man, post the interview question directly on various internet help boards, then approach those who answer it with job offers. Should give about the same success rate.

    The ones who answer the questions on the help boards already have jobs.

    And they spend their time on message boards.

  • Anon Fred (unregistered) in reply to ydrol
    ydrol:
    I always get nervous typing sql 'delete' statements, and when I remember I usually type 'select count(*)' instead and then replace it with 'delete' when I'm happy.
    MySQL has a mode where it will refuse your UPDATE or DELETE commands if they're missing an explicit WHERE clause.

    http://dev.mysql.com/doc/refman/4.1/en/mysql-tips.html#safe-updates

  • mot (unregistered)

    FizBuz is much simpler than you are making it. 15, 30,45, 60, 75, 90 are FizBuz. No others. So just type every third number into Notepad, type every 5th number into notepad, type in those special cases above, merge the notepad files, and you are done. Programming? Who needs it! Not every "programming" task is best done by a program.

  • someguy (unregistered) in reply to Alex
    Alex:
    So, I don't understand the limits of the request.. I just cannot use LastIndexOf?, would I get the job with this?:

    private void FindSubStringPos(string str, string substr) { int i = 0; int maxIndex = str.Length - substr.Length;

    while (i < maxIndex) { if (str.Substring(i, substr.Length).Equals(substr, StringComparison.OrdinalIgnoreCase)) { Console.WriteLine("Position: "+i); i += substr.Length; } else i++; } }

    This would fail when the substring repeats itself. "rerere" would contain only one instance of "rere" according to your code.

  • Sitten Spynne (unregistered)

    Most of you that are nitpicking about optimizations by caching this and avoiding calls to that are forgetting that modern compilers make these optimizations for you. Let's take a snippet in the most modern and advanced language on the planet, VB .NET 2008, for an example:

        Private Sub FindMatches(ByVal text As String, ByVal target As Integer)
            For i As Integer = 0 To text.Length
                Console.WriteLine(text(i))
            Next
        End Sub

    OH $DEITY IN THE NAME OF ALL THAT IS HOLY! I'm failing to cache the length of the text, so I'm invoking the horrible penalty of an extra call per loop... or am I? Let's look at the IL:

      IL_0000:  ldc.i4.0
      IL_0001:  ldarg.0
      IL_0002:  callvirt   instance int32 [mscorlib]System.String::get_Length()
      IL_0007:  stloc.1
      IL_0008:  stloc.0
      IL_0009:  br.s       IL_001b
      IL_000b:  ldarg.0
      IL_000c:  ldloc.0
      IL_000d:  callvirt   instance char [mscorlib]System.String::get_Chars(int32)
      IL_0012:  call       void [mscorlib]System.Console::WriteLine(char)
      IL_0017:  ldloc.0
      IL_0018:  ldc.i4.1
      IL_0019:  add.ovf
      IL_001a:  stloc.0
      IL_001b:  ldloc.0
      IL_001c:  ldloc.1
      IL_001d:  ble.s      IL_000b
      IL_001f:  ret

    The compiler caches it for me; notice how the loop starts at IL_000b, but get_Length() is called at IL_0002? The compiler recognizes this value is constant (in a single-threaded context) and simply pushes it on the stack. "Optimizing" the code by caching the text length actually adds an extra IL instruction and consumes more mempry; the code first gets the value, stores it in a local variable, then has to retrieve it so it can be pushed on the stack for the loop:

      IL_0000:  ldarg.0
      IL_0001:  callvirt   instance int32 [mscorlib]System.String::get_Length()
      IL_0006:  stloc.0
      IL_0007:  ldc.i4.0
      IL_0008:  ldloc.0
      IL_0009:  stloc.2
      IL_000a:  stloc.1
      IL_000b:  br.s       IL_001d
      IL_000d:  ldarg.0
      IL_000e:  ldloc.1
      IL_000f:  callvirt   instance char [mscorlib]System.String::get_Chars(int32)
    ...

    Write code that's easy for humans to read, and let computers make it easy for computers to read.

    The real WTF is why the code tag inserts extra line spacing.

  • Franz Kafka (unregistered) in reply to Saaid
    Saaid:
    Andrew:
    blindio:
    Why not just skip the middle man, post the interview question directly on various internet help boards, then approach those who answer it with job offers. Should give about the same success rate.

    The ones who answer the questions on the help boards already have jobs.

    And they spend their time on message boards.

    I guess when you're bored waiting for some code to compile...

  • BrokenBokken (unregistered) in reply to dpm

    Marketing? In many places that qualifies him as Management.

    captcha: vulputate

  • (cs)

    I wonder if the "drop tables" post is the reason why he is looking for a new job?

  • Kasper (unregistered) in reply to Otto

    I guess his boss did find out :-)

    (Look up Boyer-Moore, it's pretty fancy.) I would not expect anyone to come up with it for an interview question without cheating
    Would it be cheating if somebody happened to know the algorithm but didn't remember the name and had to spend a little bit of time working out some minor details of the algorithm, which they didn't remember off the top of their head?
  • Edward Royce (unregistered) in reply to Muppet
    Muppet:
    The filter works the other way too, as I'd be tempted to get up and leave when presented with that kind of busy-work.

    I'd be tempted to leave if presented with any work at all!

    Work? Me!? Are you completely mad??

  • G (unregistered)

    Ooh, ooh, I've got one!

    subs xs ys = elemIndices True $ map (xs `isPrefixOf`) (tails ys)
    

    It's even efficient and still correct when presented with an empty "xs" :)

  • (cs) in reply to Sitten Spynne

    please point me to the compiler where one can code up naive string matching and the compiler will "optimize" to boyer-moore!

  • PeterF (unregistered) in reply to Sad Bug Killer
    Sad Bug Killer:
    (...) The problem was something along the lines of: for every number from 1 to 100 print Fiz if it's divisible by 3, Buz if it's divisible by 5 and FizBuz if it's divisble by both 3 and 5. (...)
    How about this snippet? This displays the number itself and adds a newline for every number:
    for i in $(seq 1 100); do \
      echo -n $i: 
      if [ $(($i % 15)) -eq 0 ]; then 
        echo FizBuz
      elif [ $(($i % 3)) -eq 0 ]; then
        echo Fiz
      elif [ $(($i % 5)) -eq 0 ]; then
        echo Buz
      else
        echo ''
      fi
    done
    
    Depending on the size of your monitor it could also qualify as a one-liner. If you follow the instructions literally (with less than useful output if you ask me) it could look like this (takes a single line on my monitor; YMMV):
    for i in $(seq 1 100);do if [ $(($i % 15)) -eq 0 ];then echo FizBuz;elif [ $(($i % 3)) -eq 0 ];then echo Fiz;elif [ $(($i % 5)) -eq 0 ];then echo Buz;fi;done
    
    --Peter
  • Ravi Wallau (unregistered)

    My answer would be something like this:

    class Program {
        static void Main(string[] args) {
            string seq = "Polly put the kettle on, polly put the kettle on, polly put the kettle on we'll all have tea";
            PrintOccurrences(seq, "kettle");
        }
        static void PrintOccurrences(string source, string match) {
            if (source == null || match == null)
                return;
            int control = 0;
            char[] sourceArray = source.ToLower().ToCharArray();
            char[] matchArray = match.ToLower().ToCharArray();
            int matchSize = matchArray.Length;
            for (int i = 0; i < sourceArray.Length; i++) {
                if (sourceArray[i] == matchArray[control]) {
                    if (++control == matchSize) {
                        Console.WriteLine("" + (i + 2 - matchSize) + " ");
                        control = 0;
                    }
                } else {
                    control = 0;
                }
            }
        }
    }
    
  • James (unregistered) in reply to Anonymous user who feels like a smug Scheme weenie today.
    Anonymous user who feels like a smug Scheme weenie today.:
    (define (match-string str substr n)
     (if (= n (string-length substr))
       #t
      (if (char-ci=? (string-ref str n) (string-ref substr n))
        (match-string str substr (+ n 1)
        #f)))
    

    (define (substring-indexes str substr) (let* ((laststrindex (- (string-length str) (string-length substr)) (recursive-substring-indexes (lambda (str substr n) (cond ((>= n laststrindex) '()) ((match-string str substr 0) (cons n (recursive-substring-indexes str substr (+ n 1))) (#t (recursive-substring-indexes str substr (+ n 1)))))))
    (recursive-substring-indexes str substr 0)))

    Let me be the first to say: NEERRRRRRRDDDDD!

  • (cs) in reply to Anonymous Coward

    Quite right sir. That was the "you get what I mean" version. Here is the "actually tested and working" version:

    #include <iostream>
    int main(int argc,char** argv)
    {
    int fiz=0,buz=0;
    while(fiz<=100||buz<=100) std::cout << ((fiz<buz)?((fiz+=3)?"fiz":""):((buz<fiz)?((buz+=5)?"buz":""):((((fiz+=3) + (buz+=5))?"fizbuz":"")))) << std::endl;
    return 0;
    }
    
    </pre>
    
  • Edward Royce (unregistered) in reply to Matt
    Matt:
    Everyone here who's posted a solution that involves something that takes a substring and an == during the iteration part

    e.g.

    int indexOf(string needle, string haystack){ for(int i=0, i<haystack.Length-needle.Length;i++){ if(haystack.Substring(i,needle.Length) == needle) return i; } return -1; }

    I would not hire, because this has exponential time AND memory cost. On the other hand, a better solution (which loses the exponential time cost):

    int indexOf(string needle, string haystack){ for(int i=0;i<haystack.Length-needle.Length;i++){ bool found = true; for(int j=0;j<needle.Length;j++){ if(haystack[i+j] != needle[j]){ found = true; break; } } if(found) return i; } return -1; }

    would be OK.

    An instant hire would be either an implementation or mention that there is a better method - the Boyer Moore algorithm - although I would not expect the candidate to memorize it.

    Sorry but if the string is "cracker wanted by Polly" and the test string is "Polly" then your solution wouldn't find it.

    "i<haystack.Length-needle.Length"

    So your outer loop would end prematurely and would not detect the existence of the test string if it was at the end of the primary string.

    Of course I've got a massive headache right now so I could be talking totally out of my butt.

  • Edward Royce (unregistered) in reply to Sitten Spynne

    [quote user="Sitten Spynne"]... Let's take a snippet in the most modern and advanced language on the planet, VB .NET 2008 .../quote]

    Oh Sweet Baby Jesus! Now you've gone and done it!

  • metallic (unregistered)

    Here's a solution in PHP. I could probably eliminate the

    if ($needle[0] == $haystack[$i])
    but it's Monday and my mind is still asleep. Also, no clue why my code is being double spaced.

    <?php
    
    function match($needle, $haystack) {
       $matches = array();
       $match = true;
       $matchPos = -1;
    	
       $needle = strtolower($needle);
       $haystack = strtolower($haystack);
       if (strlen($needle) > strlen($haystack)) return $matches;
       for ($i = 0; $i < strlen($haystack); $i++) {
          if ($needle[0] == $haystack[$i]) {
    	 for ($j = 1; $j < strlen($needle);  $j++) {
    	    $offset = $i + $j;
    	    if (($offset >= strlen($haystack)) ||  
                    ($haystack[$offset] != $needle[$j])) {
    	       $match = false;
    	       $matchPos = $i;
    	       break;
                } else {
                   $match = true;
    	    }
    	 }
    			
    	 if ($match === true) {
    	    $matches[] = $i;
    	 }
          }
       }
    	
       return $matches;
    }
    
    $matches = match ("test", "test test test");
    print_r($matches); // 0, 5, 10
    
    ?>
    
  • (cs)

    Most interviewers will look at the FizBuz question with 4 possible outcomes:

    1. You have no idea what you're doing and can't come up with a decent solution.
    2. You are a novice and have three different cases. One for Fiz, one for Buz, and one for FizBuz.
    3. You are competent and only need to use the two cases.
    4. You are eloquent and come up with a solution, they don't quite understand but it seems to work.
  • cole (unregistered) in reply to Sad Bug Killer

    FIZBUZ??? I've never heard of that, but wouldn't this little chunk of code do just that? I spent a whole ten seconds thinking (waiting on notepad really) before I typed this out:

    #include <iostream>
    using namespace std;
    void main() {
    	int counter; //useful names, right?
    	for (counter = 0; counter < 101; ++counter)
    	{
    		if ((counter%3)==0) cout << "fiz";
    		if ((counter%5)==0) cout << "buz";
    		if ((counter%3)==0 || (counter%5)==0) cout << endl;
    	}
    }

    Granted, I didn't compile it, but I assume it works... I could even get it down to a few less lines, like moving the counter declaration to the first part of the for statement, but really. That's just overkill. Yeah, I did it in C++. Want it done in a different language?

    You mean people can't do this?

    -- So before I posted this, I read through the comments the rest of the way down, and found that there is an additional piece to the original request: Print all other numbers normally. Does that mean each on their own line? That would be too trivial. Perhaps a space between each? Okay, also trivial, so let's see ...

    #include <iostream>
    using namespace std;
    void main() {
    	for (int counter = 0; counter < 101; ++counter)	{
    		if ((counter%3)==0) cout << "fiz";
    		if ((counter%5)==0) cout << "buz";
    		if ((counter%3)>0 || (counter%5)>0) cout << counter;
    		cout << endl;	}  } 

    And for those looking at "that other problem", why are you printing "No output" or "No results found" or whatever, when the original problem said "IF THERE ARE NO MATCHES, NO OUTPUT IS GENERATED" (sorry, wanted to emphasize)???

  • mihi (unregistered) in reply to The Enterpriser
    The Enterpriser:
    toLower is a String method...

    private char myToLower(char c) { if(c > 63 && c < 91) return (char) (c + 32);

    return c; }

    Cheater!

    The world is not just ASCII (and ToLower is not either). The "proper" manual solution would be parsing UnicodeData.txt from the Unicode Consortium :)

    or use char.ToLower(c)

    mihi

  • cole (unregistered) in reply to akatherder
    akatherder:
    Most interviewers will look at the FizBuz question with 4 possible outcomes:
    1. You have no idea what you're doing and can't come up with a decent solution.
    2. You are a novice and have three different cases. One for Fiz, one for Buz, and one for FizBuz.
    3. You are competent and only need to use the two cases.
    4. You are eloquent and come up with a solution, they don't quite understand but it seems to work.
    How praytell do you do it in two? You have three test cases. 3, 5, 15 <- counts up to three cases in my book, so how do two tests determine if it's three states? Granted, my original reply also assumed that you don't return an endline after every test, only where you had a result in the first place. but I tried for simplicity rather than breakproof usage.
  • Bored Doing Homework (unregistered)

    FizzBuzz in Java: static void FizzBuzz() { For(int x=1;x<=100;x++) { if(x%3==0) { System.out.println("Fizz"); if(x%5==0) { System.out.print("Buzz"); } } else if(x%5==0) { System.out.println("Buzz"); } else { System.out.println(x);
    } } }

    There's probably an easier or more efficient way to do this, but I wanted to put "Fizz", "Buzz", "FizzBuzz", or the number on its own line.

  • rjmccall (unregistered) in reply to Matt
    Matt:
    Everyone here who's posted a solution that involves something that takes a substring and an == during the iteration part, e.g.

    int indexOf(string needle, string haystack){ for(int i=0, i<=haystack.Length-needle.Length;i++){ if(haystack.Substring(i,needle.Length) == needle) return i; } return -1; }

    I would not hire, because this has exponential time AND memory cost. On the other hand, a better solution (which loses the exponential time cost):

    (I've corrected your bounds check, both here and below)

    For needle length N and haystack size H, and assuming an array-copying substring implementation, this runs in O(HN) time with O(HN) memory churn and O(N) instantaneous memory load. Assuming a (much more likely) array-sharing substring implementation, churn drops to O(H) and load drops to O(1). None of these measures are exponential.

    Matt:
    int indexOf(string needle, string haystack){ for(int i=0;i<=haystack.Length-needle.Length;i++){ bool found = true; for(int j=0;j<needle.Length;j++){ if(haystack[i+j] != needle[j]){ found = false; break; } } if(found) return i; } return -1; }</div>
    Churn and load have dropped to O(1) here, but it still runs in O(HN) time. If you're going to criticize someone's algorithm, please learn the meaning of the word "exponential" first.

    As a style note, you could eliminate the 'found' variable with a labeled continue.

  • jimi (unregistered)

    For fun, in python!

    import string
    
    inputstr = "Polly put the kettle on, polly put the kettle on, polly put the kettle on we'll all have tea"
    
    tests = ['Polly','polly','ll','x','Polx']
    
    for test in tests:
      pos = 0
      while pos < len(inputstr) - len(test):
    is',inputstr[pos:pos+len(test)]
        if inputstr[pos:pos+len(test)].lower() == test.lower():
          print pos+1,
          pos += len(test)
        else: pos += 1
      print ""
    

    If you want to get really trivial (anal) about not using string functions, you could iterate through the input string and test cases and convert them to lowercase then.

  • jimi (unregistered) in reply to jimi
    jimi:
    For fun, in python!
    import string
    inputstr = "Polly put the kettle on, polly put the kettle on, polly put the kettle on we'll all have tea"
    tests = ['Polly','polly','ll','x','Polx']
    for test in tests:
      pos = 0
      while pos < len(inputstr) - len(test):
        if inputstr[pos:pos+len(test)].lower() == test.lower():
          print pos+1,
          pos += len(test)
        else: pos += 1
      print ""
    
    Whoops, had a little bit of garbage in there.
  • (cs) in reply to curtmack
    curtmack:
    For what it's worth, here's my solution to FizBuz, in C++
    #include <stdio>
    #include <iostream>
    
    using namespace std;
    
    int main (int nargs, const char* pszargs[]) {
      for (int i=1; i <= 100; i++) {
        cout << i << ": ";
        //don't ask why I made this next line the way I did
        //it's Monday
        cout << (i%3 ? "" : "Fiz") << (i%5 ? "" : "Buz");
        cout << '\n';
      }
      return 0;
    }

    EDIT: Err, semicolon on the return 0 might be helpful.

    Hey, who let the cage with the code monkeys open? Please stop that.

  • (cs) in reply to Fanguad
    Fanguad:
    I once got asked "given two points, how would you find the distance between them?"

    My brain went into overdrive trying to find the hidden meaning behind the question. Were they talking three-dimensional points? Are the points moving? Are they some sort of weird hyper-points?

    I hesitantly responded, "The square root of delta x squared plus delta y squared?" The interviewer nodded and told me, "You'd be amazed at how many people have trouble with that."

    Terrible question, and it seems like you realize why it's a terrible answer. The right answer is: "Depends on the metric d on the space -- once that is known, evaluate d(x,y)"

  • (cs) in reply to cole
    cole:
    akatherder:
    Most interviewers will look at the FizBuz question with 4 possible outcomes:
    1. You have no idea what you're doing and can't come up with a decent solution.
    2. You are a novice and have three different cases. One for Fiz, one for Buz, and one for FizBuz.
    3. You are competent and only need to use the two cases.
    4. You are eloquent and come up with a solution, they don't quite understand but it seems to work.
    How praytell do you do it in two? You have three test cases. 3, 5, 15 <- counts up to three cases in my book, so how do two tests determine if it's three states? Granted, my original reply also assumed that you don't return an endline after every test, only where you had a result in the first place. but I tried for simplicity rather than breakproof usage.

    Note that if a number is divisble by both 3 and 5, it is divisible by 15...

  • Ken B. (unregistered)

    No, no, no! The solution for Fizbuz is:

    1. Convert the number to text.
    2. If the last character is '5' or '0', it's divisible by 5.
    3. Sum the digits. Repeat until sum is less than 10. If the result is 3, 6, or 9, then it's divisible by 3.
  • (cs) in reply to cole
    cole:
    akatherder:
    Most interviewers will look at the FizBuz question with 4 possible outcomes:
    1. You have no idea what you're doing and can't come up with a decent solution.
    2. You are a novice and have three different cases. One for Fiz, one for Buz, and one for FizBuz.
    3. You are competent and only need to use the two cases.
    4. You are eloquent and come up with a solution, they don't quite understand but it seems to work.
    How praytell do you do it in two? You have three test cases. 3, 5, 15 <- counts up to three cases in my book, so how do two tests determine if it's three states? Granted, my original reply also assumed that you don't return an endline after every test, only where you had a result in the first place. but I tried for simplicity rather than breakproof usage.
    Just to repeat poopdeville, akatherder is pointing out that there are three input cases (%3 and %5 and not (%3 or %5)) and four output cases (%3 not %5, %5 not %3, %3 and %5, and not (%3 or %5)).

    I believe the point, such as it is, that we're all trying to make is that There is no Rule Six. Anybody who considers %15 to be a separate input case, even in a theoretical sense, fails. This is the great thing about understanding state systems.

    So, good try on nit-picking, but: well, just no.

    As for akatherder's[ fourth point, I'm looking forward to some obfuscated Scheme. It's all right: Haskell or Ocaml would do just as well...

Leave a comment on “Code examples and interviews”

Log In or post as a guest

Replying to comment #:

« Return to Article