Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Microsoft Job Interview Questions

asserttrue.blogspot.com

Post reply on HN
Print view View original

31–36 of 36 posts

Re: Microsoft Job Interview Questions

#31

Post by Locke1689 »

Zak wrote: post #7

Write code that returns the length of a string without using any built-in functions. It took me a while to realize that they're probably not counting infix operators that behave like functions except for the syntax. Accomplishing this task in Lisp or Haskell would be nearly impossible.

Doesn't seem all that tough to me

  my_len_acc :: [a] -> Int -> Int
  my_len_acc [] so_far = so_far
  my_len_acc (_:xs) so_far = my_len_acc xs $ so_far + 1
   
  my_len :: [a] -> Int
  my_len some_str = my_len_acc some_str 0

Re: Microsoft Job Interview Questions

#32

Post by th0ma5 »

ambition wrote: post #9
Zak wrote: post #7

Write code that returns the length of a string without using any built-in functions. It took me a while to realize that they're probably not counting infix operators that behave like functions except for the syntax. Accomplishing this task in Lisp or Haskell would be nearly impossible.

That's disingenuous. When they say "no built-in functions", they really only mean "don't use a library function that makes this task trivial." Which eliminates 'strlen' in C, 'length' in Haskell, 'len' in Python, etc.

sort of trivial in python with just statements: i=0 for x in thestring i+=1 print i

Re: Microsoft Job Interview Questions

#33

Post by Zak »

Locke1689 wrote: post #31
Zak wrote: post #7

Write code that returns the length of a string without using any built-in functions. It took me a while to realize that they're probably not counting infix operators that behave like functions except for the syntax. Accomplishing this task in Lisp or Haskell would be nearly impossible.

Doesn't seem all that tough to me my_len_acc :: [a] -> Int -> Int my_len_acc [] so_far = so_far my_len_acc (_:xs) so_far = my_len_acc xs $ so_far + 1 my_len :: [a] -> Int my_len some_str = my_len_acc some_str 0

$ and + are built-in functions being used with infix syntax.

Re: Microsoft Job Interview Questions

#34

Post by Zak »

msg wrote: post #29
Zak wrote: post #7

Write code that returns the length of a string without using any built-in functions. It took me a while to realize that they're probably not counting infix operators that behave like functions except for the syntax. Accomplishing this task in Lisp or Haskell would be nearly impossible.

(defun strlen (str) (loop for i from 0 for char across str finally (return i))) Works in my emacs... I (require 'cl).

I suppose everything you called is a special form. It should have occurred to me that the loop macro could do it. Is the Loop macro Turing complete?

Re: Microsoft Job Interview Questions

#35

Post by Locke1689 »

Zak wrote: post #33
Locke1689 wrote: post #31

Earlier quoted context omitted.

Doesn't seem all that tough to me my_len_acc :: [a] -> Int -> Int my_len_acc [] so_far = so_far my_len_acc (_:xs) so_far = my_len_acc xs $ so_far + 1 my_len :: [a] -> Int my_len some_str = my_len_acc some_str 0

$ and + are built-in functions being used with infix syntax.

Without such built-in functions like application or arithmetic this is impossible in every language.

Consider: without application you cannot consider such a language general recursive and therefore it is not Turing complete according to the Church-Turing thesis.

Re: Microsoft Job Interview Questions

#36

Post by Zak »

Locke1689 wrote: post #35
Zak wrote: post #33

Earlier quoted context omitted.

$ and + are built-in functions being used with infix syntax.

Without such built-in functions like application or arithmetic this is impossible in every language. Consider: without application you cannot consider such a language general recursive and therefore it is not Turing complete according to the Church-Turing thesis.

Hence my claim about the near-impossibility of the task.
Post reply on HN