The Daily WTF: Curious Perversions in Information Technology

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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..."

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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).

2008-05-05 Reply Admin

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;
}

}

2008-05-05 Reply Admin

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

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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>

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

[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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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)); }

2008-05-05 Reply Admin

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;
}

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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...

2008-05-05 Reply Admin

Marketing? In many places that qualifies him as Management.

captcha: vulputate

Grimoire · 2008-05-05 Reply Admin

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

2008-05-05 Reply Admin

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?

2008-05-05 Reply Admin

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??

2008-05-05 Reply Admin

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" :)

jaamkie · 2008-05-05 Reply Admin

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

2008-05-05 Reply Admin

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

2008-05-05 Reply Admin

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;
            }
        }
    }
}

2008-05-05 Reply Admin

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!

Zolcos · 2008-05-05 Reply Admin

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>

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

[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!

2008-05-05 Reply Admin

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

?>

akatherder · 2008-05-05 Reply Admin

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

You have no idea what you're doing and can't come up with a decent solution.
You are a novice and have three different cases. One for Fiz, one for Buz, and one for FizBuz.
You are competent and only need to use the two cases.
You are eloquent and come up with a solution, they don't quite understand but it seems to work.

2008-05-05 Reply Admin

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)???

2008-05-05 Reply Admin

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

2008-05-05 Reply Admin

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

You have no idea what you're doing and can't come up with a decent solution.

You are a novice and have three different cases. One for Fiz, one for Buz, and one for FizBuz.

You are competent and only need to use the two cases.

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

2008-05-05 Reply Admin

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.

ounos · 2008-05-05 Reply Admin

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.

poopdeville · 2008-05-05 Reply Admin

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)"

poopdeville · 2008-05-05 Reply Admin

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

You have no idea what you're doing and can't come up with a decent solution.

You are a novice and have three different cases. One for Fiz, one for Buz, and one for FizBuz.

You are competent and only need to use the two cases.

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...

2008-05-05 Reply Admin

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

Convert the number to text.
If the last character is '5' or '0', it's divisible by 5.
Sum the digits. Repeat until sum is less than 10. If the result is 3, 6, or 9, then it's divisible by 3.

real_aardvark · 2008-05-05 Reply Admin

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

You have no idea what you're doing and can't come up with a decent solution.

You are a novice and have three different cases. One for Fiz, one for Buz, and one for FizBuz.

You are competent and only need to use the two cases.

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...

Code examples and interviews

Leave a comment on “Code examples and interviews”