In preparation for an interview I have with a certain Mountain View, California software company, I am reviewing and practicing all the basic data structures and algorithms that I learned in second year. I will be live-blogging this. Excited yet? Fuck ya.
Linked list:
Probably the simplest data structure. Used for lists of shit.
The basic structure is a node (in Java) with a
pointer reference to its next node.
class LinkedListNode
{
public LinkedListNode(String text)
{
data = text;
}
LinkedListNode next = null;
String data; // or whatever interesting thing the list holds
};
Some design considerations:
- Should there be a LinkedList class to perform insert/delete/retrieve operations, or should the LinkedListNode do these itself?
- Probably makes more sense from an OOP perspective to have a separate class absract these ops, so I will write that.
- I should be recording how long I am spending on this. So far it's been at least 15 minutes.
- Apparently I don't know Java that well because I've already fucked up how Java copies references, and had a typo and shit...
- Forgot to update the previous node's next node after deleting
- I forgot to update the root after deleting the root node
- Forgot case where deleting the tail...wait no that's handled automatically
- A lot (all) of these functions could have been written recursively, whatever.
public class LinkedList {
LinkedListNode _root = null;
public void insert(LinkedListNode node)
{
LinkedListNode current = _root;
if (_root == null)
{
_root = node;
return;
}
while (current != null && current.next != null)
{
current = current.next;
}
current.next = node;
}
public LinkedListNode find(String data)
{
LinkedListNode found = _root;
while (found != null && !found.data.equals(data))
{
found = found.next;
}
return found;
}
// Version 1. delete using 1 extra pointer
public void delete1(String data)
{
LinkedListNode found = _root;
LinkedListNode prev = null;
while (found != null && !found.data.equals(data))
{
prev = found;
found = found.next;
}
if (found != null)
{
if (prev != null)
{
prev.next = found.next;
}
else
{
_root = found.next;
}
}
}
// Version 2. delete without using 1 extra pointer
public void delete2(String data)
{
LinkedListNode found = _root;
// special case where the head is what we're looking for
if (found.data.equals(data))
{
_root = found.next;
//delete( found); (if we were using c/++)
return;
}
while (found != null)
{
if (found.next != null && found.next.data.equals(data))
{
found.next = found.next.next;
//delete( found); (if we were using c/++)
break;
}
found = found.next;
}
}
}
Insert: O(n). Access: O(n). Delete: O(n). Some variants are double-linked list (where nodes point back to their next and previous nodes, and circular, where the head points to the tail.
A popular interview question is to reverse a linked list. Here goes:
public void reverse()
{
reverseEx(_root, null);
}
private void reverseEx(LinkedListNode node, LinkedListNode prev)
{
if (node.next != null)
{
reverseEx(node.next, node);
}
else
{
_root = node;
}
node.next = prev;
}
The above took me a long time, and you can do it without recursion. For some reason I wasn't thinking about doing it moving forward in the list:
public void reverse2()
{
LinkedListNode current = _root;
LinkedListNode prev = null;
LinkedListNode next = null; // this is necessary, at first I thought it wasn't, i'm retarded
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
_root = prev; // i fucked this up, previously I had _root = current, but at this point, current == null. but then again, I just wrote it then debuged it...hopefully i would read it over a couple times in an interview!
}
Stacks
Stacks are the basic LIFO structure. You can create them with any data structure you like, but typically arrays or linked lists are used. The array implementation was obvious to me:
#define MAXSIZE 2
template
class Stack
{
int _size;
int _allocated;
t* _data;
public:
Stack::Stack() : _size(0), _data(new t[MAXSIZE]), _allocated(MAXSIZE)
{
}
t pop()
{
if (_size < 1)
{
throw new exception("stack underflow");
}
return _data[--_size];
}
void push(t d)
{
if (_allocated <= _size)
{
_allocated += MAXSIZE;
t* newData = new t[_allocated];
memcpy(newData, _data, sizeof(t) * _size);
delete _data;
_data = newData;
}
_data[_size++] = d;
}
Stack::~Stack()
{
delete [] _data;
}
};
- I wanted to try having dynamic memory for some reason, that could grow past whatever, to test I set the maxsize to 2 which is obviously way low
- also wanted to use templates
- when using a template function, it's just template <class t> void MyFunction(){..}
- but when using a template class, it's template <class t> class MyClass {...}
- also I played around with std::stuff, I can't believe Fekete doesn't use it! MFC sucks compared to it.
So of course you can also create a stack with linked list:
For tomorrow:
Linked lists stacks, queues, priority queues, trees, sorting! Basic shit motherfucker.
