## Interview Questions

#### 1. Implement negafibonacci function

Implement function that caculates n-th fibonacci number in a fibonacci sequence where n is a negative number

#### 2. Reverse double linked list

Reverse order of nodes in double linked list.

#### 3. Print all permutations of a string

Write a function that would print permutations of all charaters in the string.

#### 4. Return closest value from binary search tree

Given integer value k and binary search tree of integers, return value closest to value k from the tree.

#### 5. Link levels of the tree

Given binary tree, connect all nodes on each level of the tree. Each node has additional pointer "next" which you need to initialize to node on the same level.

#### 6. Find first shifted number.

Sorted array has been shifted. For example 4, 5, 7, 9, 1, 2. Find position of the first number in the shifted section of the array (in this case 1).

#### 7. Time periods

Write a function that as input takes two periods of time and returns first period minus the other one.

#### 8. Find common ancestor in tree

Each node in the tree has a pointer to parent and pointers to all children nodes. On input you received two nodes from the tree and your algorithm has to return closest common node between these two nodes.

#### 9. Reverse words in a string

Reverse words in a string.

#### 10. Find string in stream

Write a function that returns TRUE once it encounters string in a stream of characters. You can call "GetChar()" function which returns next character from the stream.

#### 11. Array pair sum

You are given array of integers and value k. Find all pairs of numbers from the input array which sum equals to k.

#### 12. Check if linked list has a loop

Create a function which returns true or false if given linked list contains a loop.

#### 13. Write any sort algorithm

Implement sorting algorithm of your choice and describe its pros and cons.

#### 14. Check if string is palindrome

Implement function that when given a string, check if string is palindrome.

#### 15. Implement Queue using Stack

Implement Queue using Stack.

#### 16. Tree successor

Given binary search tree and node in a tree, find next node (successor). Successor of a node is the next node in inorder traversal of the Binary Tree.

Create a copy of a linked list.

#### 18. Implement fibonnaci function

Explain performance of your solution when compared with recursive version.

#### 19. Clone a linked list with second pointer

Create a copy of a linked list in which node contains a second pointer which may point to other nodes in linked list.

#### 20. Longest common subset between two sets

Find longest common subset between two sets

Implement strcpy

#### 22. Atoi

Convert string to integer.

#### 23. Bitcount

Implement function that returns number of bits set in an integer.

Reverse order of nodes in singly linked list.

#### 25. N-Queens

Given a chess board NxN, place N queens in a configuration in which they are not attacking each other.

#### 27. Find values in sorted array

Given sorted array of 100000 integer values, write a function that will return number of occurrences of value k in the input array.

#### 28. Clone directed graph

Clone directed graph. The input to the algorithm is one of the nodes of the graph which contains a list of its adjacent nodes. Assume you can navigate visit all renaming nodes in the graph from the node that you are given. Your function has to return pointer to cloned graph.

#### 29. Delete a node from binary search tree

Given root to binary search tree and node "x". Delete "x" from tree.

#### 30. Find n-th last element in single linked list

Given single linked list, find n-th element from the end of the linked list