Domanda di colloquio di Bloomberg
- Languages: Different between Java and C++, garbage collector in java (how it work), static vs dynamic memory allocation
- Data structures: Linked lists, queues, stacks, heap, trees
- OOP: polymorphism, design patterns that I used before
- Algorithms: Sorting algorithms I know and there complexity, how to search for a number in an array (sorted and not sorted cases)
- Coding question: reverse a single linked list
Risposte di colloquio
# @param {ListNode} head
# @return {ListNode}
# iterative solution
def reverseList(self, head):
# base case
if head == None or head.next == None:
return head
prev = None
current = head
while current:
# save next current pointer
next = current.next
# reverse links
current.next = prev
# advance pointers
prev = current
current = next
return prev
The following Python code, does the reversing of a LinkedList making use of a stack in O(n) time and O(n) space. I used a node and reference approach (implementations of LinkedList and Node are not included), for any improvements, let me know in the comment section:
#Reverse LinkedList using stack
stack = Stack()
current = my_list.head
for x in range(my_list.getSize()):
stack.push(current.get_data())
current = current.get_next()
string = ""
for x in range(stack.size()):
string += str(stack.pop()) + " "
The following Python code, does the reversing of a LinkedList making use of a stack in O(n) time and O(n) space. I used a node and reference approach (implementations of LinkedList and Node are not included), for any improvements, let me know in the comment section:
#Reverse LinkedList using stack
stack = Stack()
current = my_list.head
for x in range(my_list.getSize()):
stack.push(current.get_data())
current = current.get_next()
string = ""
for x in range(stack.size()):
string += str(stack.pop()) + " "