Just by coincidence I surfed on the paypal job site. They are looking for
software engineers. If you want to apply you need to solve to problems. The
second one is a programming problem.
http://www.paypal.com/cgi-bin/webscr?cmd=p/gen/jobs-engineers-outside
The problem is:
"Write a function which reverses all the words in a string,
using no local storage.(Turn "this is a test" into "test a is this".)
I started thinking about this, how to do it in C, not too obvious but
that's another ng.
After a little while I thought about trying this in Lisp. With my very
limited Lisp experience I came up with this.
(defun reverse_str (string)
(reverse string))
It works, in a sence that it does convert "this is a test" to "test a is
this" but would it also qualify as a valid answer? Why/Why not?
Thanks.
-Jeroen-
--
Jeroen Valcke ······@valcke.com
ICQ# 30116911 Home page: http://www.valcke.com/jeroen
Phone +32(0)56 32 91 37 Mobile +32(0)486 88 21 26
There's no such thing as an infinite loop. Eventually, the computer will break.
- John D. Sullivan
"Jeroen Valcke" <······@valcke.com> wrote in message ····························@afrodite.telenet-ops.be...
> Just by coincidence I surfed on the paypal job site. They are looking for
> software engineers. If you want to apply you need to solve to problems. The
> second one is a programming problem.
> http://www.paypal.com/cgi-bin/webscr?cmd=p/gen/jobs-engineers-outside
> The problem is:
> "Write a function which reverses all the words in a string,
> using no local storage.(Turn "this is a test" into "test a is this".)
>
> I started thinking about this, how to do it in C, not too obvious but
> that's another ng.
> After a little while I thought about trying this in Lisp. With my very
> limited Lisp experience I came up with this.
>
> (defun reverse_str (string)
> (reverse string))
>
> It works, in a sence that it does convert "this is a test" to "test a is
> this" but would it also qualify as a valid answer? Why/Why not?
>
????
(reverse-string "this is a test")
"tset a si siht"
I assume you left out part of the definition when you posted.
I'm more curious what they mean by `no local storage'. In C, I
can't think of a way to do it if the only variable I have available
is the original char *. Best I can come up with requires a minimum
of two indicies to make it work. I think Lisp solution would
require around the same, it's more a question of how much them can
be hidden by the language itself.
Geoff
>>>>> "JV" == Jeroen Valcke <······@valcke.com> writes:
JV> I started thinking about this, how to do it in C, not too
JV> obvious but that's another ng.
I suspect they have the "swap with no temporaries" XOR trick in mind.
You cannot do that with characters in Common Lisp without
casting/coercing.
[...]
JV> (defun reverse_str (string) (reverse string))
JV> It works, in a sence that it does convert "this is a test" to
JV> "test a is this" but would it also qualify as a valid answer?
It does not work (try it).
cheers,
BM
Bulent Murtezaoglu wrote:
> It does not work (try it).
On my system it seems to work fine ???
In clisp on linux, this is what I get. Seems fine to me.
[1]>
(defun reverse_str (string)
(reverse string))
REVERSE_STR
[2]> (reverse_str '(this is a test))
(TEST A IS THIS)
[3]>
Jeroen Valcke <······@valcke.com> wrote:
+---------------
| Bulent Murtezaoglu wrote:
| > It does not work (try it).
|
| On my system it seems to work fine ???
| In clisp on linux, this is what I get. Seems fine to me.
|
| [1]>
| (defun reverse_str (string)
| (reverse string))
| REVERSE_STR
| [2]> (reverse_str '(this is a test))
| (TEST A IS THIS)
| [3]>
+---------------
Uh... Dude, you didn't give it a STRING, you gave it a list of SYMBOLS.
Of *course* it worked!! Now try it with a *STRING*:
> (reverse_str "this is a test")
"tset a si siht"
>
-Rob
-----
Rob Warnock, 31-2-510 <····@sgi.com>
SGI Network Engineering <http://reality.sgi.com/rpw3/> [until 8/15]
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: ·········@sgi.com and ········@sgi.com aren't for humans ]
····@rigden.engr.sgi.com (Rob Warnock) writes:
>
> Jeroen Valcke <······@valcke.com> wrote:
> +---------------
> | Bulent Murtezaoglu wrote:
> | > It does not work (try it).
> |
> | On my system it seems to work fine ???
> | In clisp on linux, this is what I get. Seems fine to me.
> |
> | [1]>
> | (defun reverse_str (string)
> | (reverse string))
> | REVERSE_STR
> | [2]> (reverse_str '(this is a test))
> | (TEST A IS THIS)
> | [3]>
> +---------------
>
> Uh... Dude, you didn't give it a STRING, you gave it a list of SYMBOLS.
> Of *course* it worked!! Now try it with a *STRING*:
>
> > (reverse_str "this is a test")
> "tset a si siht"
> >
Hey, maybe he just had the readtables screwed up a little.
Happens to me all the time. ;-)
@begin(style, kind="bad", recommended="no")
(let ((rt (copy-readtable *readtable*)))
(defun print-string (list) ;defines globally. just here for easy pasting
(write-char #\")
(when list (prin1 (car list)))
(loop for x in (cdr list) do (write-char #\Space) (prin1 x))
(write-char #\")
t)
(setf (readtable-case rt) :preserve)
(set-macro-character #\"
#'(lambda (stream char)
`',(loop for ch = (peek-char t stream t nil t)
until (when (eql ch #\") (read-char stream t nil t) t)
collect (read-preserving-whitespace stream t nil t)))
nil rt)
(let ((*readtable* rt))
(eval (read))))
(PRINT-STRING (REVERSE "this is a test"))
"test a is this"
@end(style)
"Kent M Pitman" <······@world.std.com> wrote in message
····················@world.std.com...
> ····@rigden.engr.sgi.com (Rob Warnock) writes:
> Hey, maybe he just had the readtables screwed up a little.
> Happens to me all the time. ;-)
>
> @begin(style, kind="bad", recommended="no")
>
> (let ((rt (copy-readtable *readtable*)))
> (defun print-string (list) ;defines globally. just here for easy pasting
> (write-char #\")
> (when list (prin1 (car list)))
> (loop for x in (cdr list) do (write-char #\Space) (prin1 x))
> (write-char #\")
> t)
> (setf (readtable-case rt) :preserve)
> (set-macro-character #\"
> #'(lambda (stream char)
> `',(loop for ch = (peek-char t stream t nil t)
> until (when (eql ch #\") (read-char stream t nil t) t)
> collect (read-preserving-whitespace stream t nil t)))
> nil rt)
> (let ((*readtable* rt))
> (eval (read))))
> (PRINT-STRING (REVERSE "this is a test"))
> "test a is this"
>
> @end(style)
Ya know, some people simply have TOO much time on their hands...
(Even so, thanks for the quick lesson in readtable macrology :-).
faa
Jeroen Valcke <······@valcke.com> writes:
> Bulent Murtezaoglu wrote:
> > It does not work (try it).
>
> On my system it seems to work fine ???
> In clisp on linux, this is what I get. Seems fine to me.
>
> [1]>
> (defun reverse_str (string)
> (reverse string))
> REVERSE_STR
> [2]> (reverse_str '(this is a test))
^^^^^^^^^^^^^^^^^^
You are definitly not talking about a String. This is a list and of
course reverse works on such a list.
Regards
Friedrich
"Jeroen Valcke" <······@valcke.com> writes:
> Just by coincidence I surfed on the paypal job site. They are looking for
> software engineers. If you want to apply you need to solve to problems. The
> second one is a programming problem.
> http://www.paypal.com/cgi-bin/webscr?cmd=p/gen/jobs-engineers-outside
> The problem is:
> "Write a function which reverses all the words in a string,
> using no local storage.(Turn "this is a test" into "test a is this".)
I don't think it's fair to ask this until their programmer is hired.
If anyone publishes an answer, it will be defeat paypal's ability to use
this as a useful test. Why not come back with the problem after they've
hired their employee?
> I started thinking about this, how to do it in C, not too obvious but
> that's another ng.
> After a little while I thought about trying this in Lisp. With my very
> limited Lisp experience I came up with this.
>
> (defun reverse_str (string)
> (reverse string))
>
> It works, in a sence that it does convert "this is a test" to "test a is
> this" but would it also qualify as a valid answer? Why/Why not?
No, it does not work. REVERSE both conses [which is the moral equivalent of
using local storage] and returns the wrong answer, "tset a si siht".
The right answer, should you want to look it up, is pretty much the same
algorithm as that explained in Steele's paper on how to reverse cdr-coded
lists.
Kent M Pitman wrote:
> I don't think it's fair to ask this until their programmer is hired.
> If anyone publishes an answer, it will be defeat paypal's ability to use
> this as a useful test. Why not come back with the problem after they've
> hired their employee?
Allright. I posted this out of curiosity not because I want to cheat on
their test.
Actually I'm not applying for this job neither.
So I apoligize if I'm for messing up the test.
Jeroen Valcke <······@valcke.com> writes:
> Kent M Pitman wrote:
> > I don't think it's fair to ask this until their programmer is hired.
> > If anyone publishes an answer, it will be defeat paypal's ability to use
> > this as a useful test. Why not come back with the problem after they've
> > hired their employee?
>
> Allright. I posted this out of curiosity not because I want to cheat on
> their test.
> Actually I'm not applying for this job neither.
> So I apoligize if I'm for messing up the test.
My observation was that anyone doing a web search would find the answer.
It affects not only you.
Aha!
Reverse all letters in the string and then reverse all reversed words in the
string individually.
Code
(defun reverse-chars-in-string (string start len)
(loop with swapchar = nil
for front = start then (1+ front)
for back = (+ start len -1) then (1- back)
if (< front back) do
(setf swapchar (elt string front)
(elt string front) (elt string back)
(elt string back) swapchar)
else return string))
(defun reverse-words-in-string (string)
(let ((spaces-exist
(loop for char across string
when (char= char #\space) return t
finally return nil)))
(unless spaces-exist (return-from reverse-words-in-string string))
;; reverse all letters
(setf string (reverse-chars-in-string string 0 (length string)))
;; reverse all words
(loop with len = 1
with start = 0
for char across string
if (char= char #\space) do
(reverse-chars-in-string string start (1- len))
(incf start len)
(setf len 1)
else do (incf len)
finally return
(progn
(when (> len 1) (reverse-chars-in-string string start (1- len)))
string))))
"Jeroen Valcke" <······@valcke.com> wrote in message
····························@afrodite.telenet-ops.be...
> Just by coincidence I surfed on the paypal job site. They are looking for
> software engineers. If you want to apply you need to solve to problems.
The
> second one is a programming problem.
> http://www.paypal.com/cgi-bin/webscr?cmd=p/gen/jobs-engineers-outside
> The problem is:
> "Write a function which reverses all the words in a string,
> using no local storage.(Turn "this is a test" into "test a is this".)
>
> I started thinking about this, how to do it in C, not too obvious but
> that's another ng.
> After a little while I thought about trying this in Lisp. With my very
> limited Lisp experience I came up with this.
>
> (defun reverse_str (string)
> (reverse string))
>
> It works, in a sence that it does convert "this is a test" to "test a is
> this" but would it also qualify as a valid answer? Why/Why not?
>
> Thanks.
> -Jeroen-
>
> --
> Jeroen Valcke ······@valcke.com
> ICQ# 30116911 Home page: http://www.valcke.com/jeroen
> Phone +32(0)56 32 91 37 Mobile +32(0)486 88 21 26
> There's no such thing as an infinite loop. Eventually, the computer will
break.
> - John D. Sullivan
"Wade Humeniuk" <········@cadvision.com> wrote in message
·················@news3.cadvision.com...
> Aha!
>
> Reverse all letters in the string and then reverse all reversed words in
the
> string individually.
>
> Code
>
> (defun reverse-chars-in-string (string start len)
> (loop with swapchar = nil
> for front = start then (1+ front)
> for back = (+ start len -1) then (1- back)
> if (< front back) do
> (setf swapchar (elt string front)
> (elt string front) (elt string back)
> (elt string back) swapchar)
> else return string))
>
> (defun reverse-words-in-string (string)
> (let ((spaces-exist
> (loop for char across string
> when (char= char #\space) return t
> finally return nil)))
> (unless spaces-exist (return-from reverse-words-in-string string))
> ;; reverse all letters
> (setf string (reverse-chars-in-string string 0 (length string)))
> ;; reverse all words
> (loop with len = 1
> with start = 0
> for char across string
> if (char= char #\space) do
> (reverse-chars-in-string string start (1- len))
> (incf start len)
> (setf len 1)
> else do (incf len)
> finally return
> (progn
> (when (> len 1) (reverse-chars-in-string string start (1-
len)))
> string))))
>
> "Jeroen Valcke" <······@valcke.com> wrote in message
> ····························@afrodite.telenet-ops.be...
> > Just by coincidence I surfed on the paypal job site. They are looking
for
> > software engineers. If you want to apply you need to solve to problems.
> The
> > second one is a programming problem.
> > http://www.paypal.com/cgi-bin/webscr?cmd=p/gen/jobs-engineers-outside
> > The problem is:
> > "Write a function which reverses all the words in a string,
> > using no local storage.(Turn "this is a test" into "test a is this".)
> >
> > I started thinking about this, how to do it in C, not too obvious but
> > that's another ng.
> > After a little while I thought about trying this in Lisp. With my very
> > limited Lisp experience I came up with this.
> >
> > (defun reverse_str (string)
> > (reverse string))
> >
> > It works, in a sence that it does convert "this is a test" to "test a is
> > this" but would it also qualify as a valid answer? Why/Why not?
> >
> > Thanks.
> > -Jeroen-
> >
> > --
> > Jeroen Valcke ······@valcke.com
> > ICQ# 30116911 Home page: http://www.valcke.com/jeroen
> > Phone +32(0)56 32 91 37 Mobile +32(0)486 88 21 26
> > There's no such thing as an infinite loop. Eventually, the computer will
> break.
> > - John D. Sullivan
>
Oops! That's what BM meant by the XOR trick. If it means anything,
`no local storage' certainly means no temporaries for a character.
It's an old trick, but a good one(byte-enabled languages only):
a<-a XOR b
b<-b XOR a
a<-a XOR b
In other words, swapchar is "Bad form, Cap'n Hook". :-)
OTOH, my idea of the algorithm for C was to reverse the words
in place, then reverse the string. Obviously you had it
.sdrawkcab
,dronF
? (-: ro )-: ,ffoeG
Geoffrey Summerhayes wrote:
> Oops! That's what BM meant by the XOR trick. If it means anything,
> `no local storage' certainly means no temporaries for a character.
> It's an old trick, but a good one(byte-enabled languages only):
> a<-a XOR b
> b<-b XOR a
> a<-a XOR b
> In other words, swapchar is "Bad form, Cap'n Hook". :-)
>
> OTOH, my idea of the algorithm for C was to reverse the words
> in place, then reverse the string. Obviously you had it
> .sdrawkcab
Understanding both hardware instructions and CL, I read "no temporary
storage" to prohibit use of the stack, which means no function calls.
No storage is more temporary than a lambda-bound variable.
Remember, Paypal is in the business of Web Programming, which from
my experience is entirely disjoint from programming. Sort of like
"Military Intelligence" being disjoint from "intelligence."
"Steven M. Haflich" <·······@pacbell.net> wrote in message ······················@pacbell.net...
>
> Understanding both hardware instructions and CL, I read "no temporary
> storage" to prohibit use of the stack, which means no function calls.
> No storage is more temporary than a lambda-bound variable.
>
> Remember, Paypal is in the business of Web Programming, which from
> my experience is entirely disjoint from programming. Sort of like
> "Military Intelligence" being disjoint from "intelligence."
Hmm, what would "clear specifications" qualify as?
Geoff
"Steven M. Haflich" <·······@pacbell.net> writes:
> Understanding both hardware instructions and CL, I read "no temporary
> storage" to prohibit use of the stack, which means no function calls.
> No storage is more temporary than a lambda-bound variable.
Right. But I don't think only in the extreme case could they mean
don't use O(1) storage variables in the main routine. Among other
things, if it takes you N more instructions to work around the
availability of M storage locations, where M < N, you've probably made
a bad trade (unless you have a different valuation function for the
amount of storage used in mutable data space than probably-read-only
code space). But, in general, you never get anything "for free"; that
is, the three laws of thermodynamics apply here, as anywhere: "you
can't win", "you can't break even", "you can't get out of the game".
"Jeroen Valcke" <······@valcke.com> ha scritto nel messaggio
····························@afrodite.telenet-ops.be...
> Just by coincidence I surfed on the paypal job site. They are looking for
> software engineers. If you want to apply you need to solve to problems.
The
> second one is a programming problem.
> http://www.paypal.com/cgi-bin/webscr?cmd=p/gen/jobs-engineers-outside
> The problem is:
> "Write a function which reverses all the words in a string,
> using no local storage.(Turn "this is a test" into "test a is this".)
>
> I started thinking about this, how to do it in C, not too obvious but
> that's another ng.
> After a little while I thought about trying this in Lisp. With my very
> limited Lisp experience I came up with this.
>
> (defun reverse_str (string)
> (reverse string))
>
> It works, in a sence that it does convert "this is a test" to "test a is
> this" but would it also qualify as a valid answer? Why/Why not?
Because it does not work.
Without allocating any storage it seems impossible. Perhaps they
mean to solve it in O(1) space?
If this is the case, here's a solution in CL:
CL-USER 4 > (parovesc "this is a test")
"test a is this"
My solution is slightly more complex than yours.
Cheers,
Pierpaolo
===============
(defun reverse-subs (stringa start end)
(do ((start start (1+ start))
(end (1- end) (1- end)))
((<= end start))
(rotatef (char stringa start) (char stringa end)))
stringa)
(defun search-start-of-word-bw (stringa cur)
(let ((pos (position-if #'whitespace-char-p stringa :end cur :from-end
t)))
(if pos (1+ pos) 0)))
(defun search-end-of-word-bw (stringa cur)
(1+ (position-if-not #'whitespace-char-p stringa :end cur :from-end t)))
(defun parovesc (stringa)
(nreverse stringa)
(loop for end = (length stringa)
then (and (plusp start)
(search-end-of-word-bw stringa (1- start)))
for start = (and end (search-start-of-word-bw stringa (1- end)))
while start
do (reverse-subs stringa start end))
stringa)
"romeo bernardi" <········@tin.it> wrote in message
·························@news1.tin.it...
>
>
> Without allocating any storage it seems impossible. Perhaps they
> mean to solve it in O(1) space?
It is not literally impossible. There are spaces in the string. Use the
spaces as temporary storage to swap letters. Swap starting from either end
working towards the middle.
Even in C you would need some stack variables for indexes and such. I am
unsure what they mean by local storage. Allocated storage or no char arrays
for copying on the stack?
Wade