21–30 of 30 posts
Earlier quoted context omitted.
Your "every k steps" operation executes N / k times, which isn't O(k) so I don't think it meets the requirements given.
His "every k steps" operation doesn't dereference any pointers; 0 * N / k is indeed O(k).
As someone currently doing the technical interview tour, I really appreciate this link. Particularly that the author follows the general thought pattern of thinking of an inefficient way and then searching for better ways. Does anyone have any other favorite sites that have these types of questions with answers?
As someone currently doing the technical interview tour, I really appreciate this link. Particularly that the author follows the general thought pattern of thinking of an inefficient way and then searching for better ways. Does anyone have any other favorite sites that have these types of questions with answers?
One I got recently - and blanked on - write a function to generate all the permutations of a string. Recursion preferred.
def permute(string, prefix = ''):
if len(string) == 1:
print prefix + string
return
for x in range(0, len(string)):
new_prefix = prefix + string[x]
unused_chars = string[0:x] + string[x+1:]
permute(unused_chars, new_prefix)The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
What about going through the list once, put each node onto a stack, then pop n - 1 elements off the stack, and the nth last element will be on the top of the stack. Edit: uses too many pointers as cperciva points out below.
The author points out that a two-stage process consisting of 1. counting the number of elements in the list, and then 2. finding the right element, is quite inefficient -- but he then presents a different approach which uses two pointers instead of one, yet is equally inefficient -- almost every pointer is dereferenced twice. Challenge: Show how, using three pointers, you can find the k th last element from a linked…
(defun nthFromEnd (lst n)
(labels ((from-end-helper (lst n)
(if (null lst)
0
(let ((ret (from-end-helper (cdr lst) n)))
(if (eq ret n)
(throw 'answer (car lst))
(+ ret 1))))))
(catch 'answer
(when (from-end-helper lst n)
nil))))
CL-USER> (nthfromend '(1 2 3 4 5) 6)
NIL
CL-USER> (nthfromend '(1 2 3 4 5) 3)
2
CL-USER> (nthfromend '(1 2 3 4 5) 0)
5
As someone currently doing the technical interview tour, I really appreciate this link. Particularly that the author follows the general thought pattern of thinking of an inefficient way and then searching for better ways. Does anyone have any other favorite sites that have these types of questions with answers?
One I got recently - and blanked on - write a function to generate all the permutations of a string. Recursion preferred.
The existence of posts like this really highlights the uselessness of "Guess the answer I'm looking for" interview questions. It turns them into "Did you take the trouble to scour the Internet for tech interview questions?" That being said, if I ever have to interview another programmer who reads zero programming blogs or web sites... I am going to end it all and become a bike messenger.
Earlier quoted context omitted.
There are many situations where the cost of using a more sophisticated data structure outweighs the advantages of avoiding an occasional excessively slow operation.
We don't have enough information to know which situation this is. Hence, it's an "alternative" to consider.
Here's the whole thing starting from scratch:
# Optional values (also known as the "Maybe" type)
#
# The (absent) function represents a value that is absent.
# The (present value) function represents a value that is present.
\absent = (\absent\present absent)
\present = (\value \absent\present present value)
# Natural numbers.
#
# The (zero) function represents the number 0.
# The (succ n) function represents the number 1+n (the successor of n).
#
# A natural number is really just an optional predecessor,
# so the constructors are just synonyms for the Maybe type.
\zero=absent
\succ=present
# Lists.
\null = (\null\cons null)
\cons = (\head\tail \null\cons cons head tail)
# Subtraction of natural numbers. Computes z = x - y.
#
# Returns (present z) if x >= y.
# Returns absent if x