# Some popular programming questions for technical interviews

## Data Structures

### Arrays and Strings

1. Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
2. Given two strings, write a method to decide if one is a permutation of the other.
3. Implement a function in C/C++: void reverse(char *str), which reverses a null terminated string.
4. Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.
5. Assume you have a method called “isSubstring” which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only call to isSubstring. Example: “waterbottle” is a rotation of “erbotllewat”.

1. Write code to remove duplicates from an unsorted linked list. (Follow up: how would you solve this problem without a temporary buffer?)
2. Write code to partition a linked list around a value ‘x’, such that all nodes less than x come before all nodes greater than or equal to x.
3. Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node. Example, input: remove node c (a-b-c-d-e), result (a-b-d-e), nothing is returned.
4. Given two sorted linked lists, how can you combine them?

### Stacks & Queues

1. Implement a MyQueue class which implements a queue using two stacks
2. Write a program to sort a stack in ascending order (biggest items on top). You can use at most 1 additional stack to hold items but you cannot use any other data structures such as an array. The stack supports push, pop, peek, and isEmpty.

### Trees and Graphs

1. Implement a function to check if a binary tree is balanced. A balanced tree is defined to be a tree such that the heights of the two subtrees of any node differ by more than 1.
2. Given a sorted array, write an algorithm to create a binary search tree with minimal height.
3. Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth. Example, if you have a tree with depth of 5, you will have 5 linked lists.
4. You have two very large binary trees. T1 has millions of nodes. T2 has hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
5. Given a directed graph, perform a Breadth First Search algorithm.

## Concepts and Algorithms

### Object-Oriented Design

1. Design the data structures for an online book reader system.
2. Imagine you have a call centre with three levels of employees: respondent, manager, and director. An incoming telephone call must be first allocated to a respondent who is free. If the respondent can’t handle the call, he or she must escalate teh call to a manager. If the manager is not free or able to handle it, then the call should be escalated to a director. Design the classes and data structures for this problem. Implemented a method called ‘dispatchCall()’ which assigns a call to the first available employee.
3. Explain the data structures and algorithms that you would use to design an in-memory file system. Illustrate with an example in code where possible.
4. Design and implement a hash table which uses chaining (linked lists) to handle collisions.

### Recursion/Dynamic Programming

1. Suppose you have a robot sitting at coordinate 0,0 of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from 0,0 to X,Y?
2. Implement a recursive function that takes an integer and prints the hexadecimal representation.
3. Write a recursive binary search.
4. Given a string, find all its permutations.
5. Maximum subarray: Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

### Sorting/searching

1. Given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Example:
1. A: 1 3 5 8 _ _ _ _
2. B: 6 7 9 10
2. Imagine you have a 20GB file with one string per line. Explain how you would sort the file.

### Testing

1. How would test an umbrella?
2. Find mistakes with this code.
```unsigned int i;
for(i = 100; i >= 0; --i)
printf("%d\n", i);
```

## Knowledge based

### C++

1. How do virtual functions work in C++?
1. Follow up: why does a destructor in a base class need to be declared virtual?
2. What is the output of this program?
```        #include <iostream>

using namespace std;

class polygon

{

protected:

int width, height;

public:

void set_values (int a, int b)

{

width = a; height = b;}

};

class output1

{

public:

void output (int i);

};

void output1::output (int i)

{

cout << i << endl;

}

class rectangle: public polygon, public output1

{

public:

int area ()

{

return (width * height);

}

};

class triangle: public polygon, public output1

{

public:

int area ()

{

return (width * height / 2);

}

};

int main ()

{

rectangle rect;

triangle trgl;

rect.set_values (4, 5);

trgl.set_values (4, 5);

rect.output (rect.area());

trgl.output (trgl.area());

return 0;

}
```

### Databases

1. Write a SQL query to get a list of tenants who are renting more than one apartment.
2. Draw an entity-relationship diagram fro a database with companies, people, and professionals (people who work for companies).
3. Write a SQL query to get a list of all buildings and the number of open requests (Requests in whish status equals ‘Open’).