MrZipf
BAN USERA simple inorder traversal should work here. In the current implementation there are two methods with the same signature but different return types. I'm not a Java person but this looks like trouble.
This is what I lashed up in C++:
template <typename T>
struct Node
{
Node<T>* Left;
Node<T>* Right;
T Value;
};
template <typename T>
static const Node<T>*
GetKthSmallestWorker(const Node<T>* node, int& k)
{
const Node* found = nullptr;
if (node->Left)
{
found = GetKthSmallestWorker(node->Left, k);
}
if (nullptr == found)
{
if (--k == 0)
{
found = node;
}
else if (Node->right)
{
found = GetKthSmallestWorker(Node->Right, k);
}
}
return found;
}
template <typename T>
Node<T>*
GetKthSmallest(const Node<T>& node, int k)
{
return (k > 0) ? GetKthSmallestWorker(&node, k) : nullptr;
}
The observation looks correct from the Java API documentation. In .NET, ArrayList and it's generic descendent List<T> are backed by an array so would be O(n) overall. However, I'd say the point of this question is to show the interviewee understands pointers so using an array based data structure would not be a good start.
The pattern take from head of one list and push to head of another is classic for the question of reversing a singly linked list. Does the test case work for your answer?
Here's a C++/C implementation assuming you are implementing your own list.
typedef struct _NODE
{
struct _NODE* Next;
char Value;
} NODE, *PNODE;
// Swaps node pointed to by head with it's successor and updates the head
// pointer (it's a reference) to reflect the swap.
// Returns the new tail on success, nullptr when the swap not possible.
static PNODE
SwapPair(
PNODE& head
)
{
if (nullptr == head || nullptr == head->Next)
{
return nullptr;
}
PNODE newHead = head->Next;
PNODE newTail = head;
newTail->Next = newHead->Next;
newHead->Next = newTail;
head = newHead;
return newTail;
}
// Swaps elements in list in a pairwise fashion.
// Returns a pointer to the modified lists head.
static PNODE
SwapListPairs(
PNODE head
)
{
PNODE retval = head;
PNODE current = SwapPair(retval);
while (nullptr != current)
{
current = SwapPair(current->Next);
}
return retval;
}
If this were C++, the issue would be which of the changes affect the layout of the object. Code which uses the affected class will likely make inappropriate accesses when they access fields as they assume the old layout. Bugs from this will likely be very hard to diagnose.
Adding a data member typically changes the object layout though in some app compat cases people add a field and shrink another. This is not 100% safe, it depends on how the fields are accessed, so best to avoid.
If the class had no other virtual methods before adding a virtual destructor, then the addition a virtual method will change object layout to include a vtable pointer. It's an implementation detail, but this is typically at the start of the object so all fields shift by the vtable pointer size.
Adding new methods does not and the existing libraries can't call them.
Probably worth pontificating that you absolutely never want to ship out of date libraries, better to build everything against a known point.
Yes, you are absolutely right - this was a 2 minutes sketch during a lunch break. There is also a problem when other.name is null in the code - this.name always needs deleting.
Think it'd be fair feedback in the interview to point out that using C++ allocators with C strings is awkward, ie can't use strdup. There's also been a std::string class for 20 years that'd avoid :-)
- MrZipf December 17, 2014