CareerCup

#include <unordered_map>

using namespace std;

Node * CopyGraph(Node * node, unordered_map<Node*, Node*> &copied)
{
	if(node==NULL)
		return NULL;

	//First check if this node has already been copied
	unordered_map<Node*, Node*>::iterator it = copied.find(node);
	if(it!=copied.end())
		return it->second;

	//If not, then create a copy of the node
	Node * new_node = new Node;
	new_node->data = node->data;

	//Add the copied node to the Hash table
	copied[node] = new_node;

	//Copy the node's neighbors using recursive calls
	for(int i=0; i<node->neighbors.size(); i++)
		new_node->neighbors.push_back(CopyGraph(node->neighbors[i], copied));

	return new_node;
}

This is not a recursive solution to the problem!

Here's my implementation of the algorithm. I used the recursive approach since it's much easier to understand. It is important to change the value in cell (i,j) BEFORE diving into the recursive calls, because if not you can end up with infinite recursive calls. Here's the C++ implementation:

#include <iostream>

using namespace std;

void PrintMat(int ** matrix, int height, int width)
{
	for(int r = 0; r < height;r++)
	{
		for(int c = 0; c < width;c++)
			cout<<matrix[r][c]<<" ";

		cout<<endl;
	}
}


void ChangeColor(int & val)
{
	if(val==1)
		val = 0;
	else
		val = 1;
}

void ChangePixels(int ** matrix, int rows, int cols, int r, int c)
{
	if(r<0 || r >= rows || c<0 || c>=cols)
		return;

	int val = matrix[r][c];
		
	ChangeColor(matrix[r][c]);

	if(r>0 && val == matrix[r-1][c])
		ChangePixels(matrix, 5, 5, r-1, c);
	
	if(r<rows-1 && val == matrix[r+1][c])
		ChangePixels(matrix, 5, 5, r+1, c);
	
	if(c>0 && val == matrix[r][c-1])
		ChangePixels(matrix, 5, 5, r, c-1);
	
	if(c<cols-1 && val == matrix[r][c+1])
		ChangePixels(matrix, 5, 5, r, c+1);
}	

void main(void)
{
	int **matrix = new int*[5];
	int height = 5;
	int width = 5;


	int a[] = { 0, 1, 0, 0, 0};
	int b[] = { 0, 1, 0, 1, 1};	
	int c[] = { 1, 1, 0, 0, 1};	
	int d[] = { 0, 1, 1, 0, 1};	
	int e[] = { 0, 1, 0, 0, 1};	

	matrix[0] = a;
	matrix[1] = b;
	matrix[2] = c;
	matrix[3] = d;
	matrix[4] = e;

	ChangePixels(matrix, 5, 5, 2, 1);

	PrintMat(matrix, 5, 5);
}

So, as many said before, this problem can be easily implemented using a Circular Double Linked List, and guaranteeing a O(n) complexity. Specifically, the complexity of this implementation will be O(k*n), and because k is a constant, O(k*n)=O(n). Here's my C++ implementation. I think it's quite simple to understand:

struct Node
{
	Node* next;
	int v;
	Node* prev;
};

Node* GetLastNode(Node* node, int k)
{
	Node * tmp = node;

	while(tmp!= NULL)
	{
		for(int i = 0; i<k; i++)
			tmp = tmp->next;

		//Remove tmp node
		Node* to_remove = tmp;
		tmp->prev->next = tmp->next;
		tmp->next->prev = tmp->prev;

		//Update the Node pointer
		tmp = tmp->prev;

		//Check if we reached the last element
		if(tmp==tmp->prev) 
			break;

		delete to_remove;
	}

	return tmp;
}

Note: This implementation can run a little faster if we knew in advance the size of the circular list. Thus, instead of running the "for" loop for k iteration, we can run it in k%n iterations. Of course, in each of the While iteration, we must update the value of "n".

There is also an elegant solution using a Single Linked List. In this case, whenever we want to remove a Node A from the list, we simply copy to the node A the full content of its A->next (pointers and value) and then delete the A->next.

I think a brute force approach for this algorithm is, given a string str, generating all values in order starting from "a", incrementing a counter, until we find the string str and return the value of the counter. So, for the example "aez", we will need to iterate 441 times.

@ashwini, The look up will take O(1) time because we have stored in the hash table the position of each key in the array. So the hash table will have the following key and values :
Key(string)->(Value(int), Index in array(int))

@oOZz You're right. I didn't consider the Amortized analysis. In that case, the best solution, as you said, is using a Hash Table and a dynamic resizing array. Thanks for the information.

@oOZz Even if you use an array with dynamic resizing and shrinking, and control the load factor, the total work of managing the array is O(n), (unless you know in advance the maximum number of elements you're going to have) because every time you have to resize the array (in some insertions or deletions), you'll have an operation of O(n) complexity of moving elements from one array to another.

I have posted below a solution with expected constant complexity O(1) in every of the mentioned 4 operations, using 2 Hash Tables. Check it out and let me know what you think about it.

Both BFS and Dijkstra will work, but it is better to use Dijsktra in weighted graphs. This is not the case, since all edges have value 1.

BFS will work as long as you keep record of the parent of each node you are processing. Then, just reconstruct the path (from target position to initial pose) by following the chain of ancestors. Just use this simple recursive function:

find_path(int start, int end, int parents[])
{
	if ((start == end) || (end == -1))
		printf("\n%d",start);
	else {
		find_path(start,parents[end],parents);
		printf(" %d",end);
	}
}

I strongly recommend you to read the chapter 5.6 of Skiena's "Algorithm Design Manual".

With the "parent" array, you can get the shortest paths from the initial position of bishop to all positions of the board, so for repeated queries in which we maintain the initial position and change the target positions, having this "parent" array is great because it takes linear time to find the shortest paths. All of these decisions (using Graphs, keeping the parent array, etc.) depend on the requisites of the problem which you have to ask the interviewer (hey, he will even give you a bonus for asking these, because that is the way you have to do it in the real world: get to know the problem the best you can before attacking it).

However, for this specific problem, I think the best solution is using A*, because it converges a lot faster to the shortest path, even when there are pieces blocking the way. I have already defined a good heuristic in my previous post.

If I were in an 45 min interview I would have used a Graph Representation of the problem. So, I would have created a Graph in which each Node correspond to a single square (x,y) and two nodes A,B are connected if a bishop can directly move from A to B (and viceversa),ie, they are in the immediate diagonal of one another. So, in a chess board, this Graph will have 32 nodes because the Bishop can only move in half of the chess board (all whites or all blacks).

So, suppose the chess board is 4x4. The graph will look like this:

(0,0)		(0,2)
    \		/   \
      \	   /     \
      (1,1)      (1,3)
	 /     \       /
    /		\     /
(2,0)        (2,2)
 			 /     \    
            /       \
         (3,1)     (1,3)

After I have constructed the Graph, I would just use Bread First Search on the initial position of the Bishop until I find the target position.

I think the big advantage of this solution is that it is quite easy to understand and that you can reuse the Graph for multiply queries of "find the shortest path from A to B". Another big advantage is that in case there are pieces blocking the way, it's as easy as eliminating the node where these pieces are. The BFS will continue to work.

The big disadvantage is, however, the memory usage.

Note: For further improvements on the solution, instead of using BFS, we can use A*, where the Heuristic(A,B) =euclidean distance (A,B) or norm(A-B)

This is an implementation using two Hash Tables that has an approximate complexity of O(1) for every operation (Add, Remove, Search and Random) if the Hash Tables are well implemented (good hash function and load factor).

The Hash Tables are:
map1: Key(string)->(Value(int), Index of map2 (int))
map2: Key(int)-> Value(string)

The Key of map2 represents an index (from 0 to size of data-1) and its value maps with Key of Map1.

Below you can see the C++ implementation (I used STL <unordered_map> for Hash Table), and assumed the Key is a "string" and the value is an "int".

#include <unordered_map>
#include <string>
#include <array>

using namespace std;
class MyStruct
{
public:
	
	MyStruct() {size_of_data_=0;}

	virtual ~MyStruct(){}

	void Add(string str, int v){
		array<int,2> arr;
		arr[0] = v;
		arr[1]= size_of_data_;
		map1_[str] = arr;
		map2_[size_of_data_++]=str;
	}

	int Search(string str)
	{
		unordered_map<string,array<int,2> >::iterator it =
                map1_.find(str);

		if(map1_.find(str)!=map1_.end()) //Element found
			return it->second[0];
		else //Element not found
			return -1;
	}

	void Remove(string str)
	{
		unordered_map<string,array<int,2> >::iterator it = 
                 map1_.find(str);

		//If element to remove doesn't exist in our Data
		if(it==map1_.end()) 
			return;

		//Get the index element in the map2
		int map2_idx = it->second[1];
	
		//Get key (string) of last element in the map2
		string last_str = map2_[size_of_data_-1];

		//Replace with element to remove with the last element
		map2_[map2_idx] = last_str;

		//Update the map2_idx of last key of map2
		map1_[last_str][1] = map2_idx;

		//Erase element from map1
		map1_.erase(str);

		//Erase last element from map2
		map2_.erase(size_of_data_-1);

		//Decrement size_of_data
		size_of_data_--;
	}

	int Random()
	{
		//Generate big rand number - use your favorite randgen
		unsigned int rand_number = GetRandNumber();

		//If you want to return the value of the random element
		return map1_[map2_[rand_number%size_of_data_]][0];

		//If you want to return the key of the random element
		//uncomment next line
		//return map2_[rand_number%size_of_data];
	}

private:
	unordered_map<string, array<int,2> > map1_;
	unordered_map<int,string> map2_;
	int size_of_data_;
};

Instead of "map", you can use STL "unordered_map" that is implemented using a hash table. Easy as that.

Andrei, if you use an array, the insertion are not always O(1). I suppose that you are using a dynamical array (because of the push_back). Every time you run out of space, you have to increase its size and copy every element to a new array with a bigger size.

Since I read this problem, I had an idea very similar to yours on how to implement this DS. But instead of using a Hash Table + Array, used 2 Hash Tables. I have posted the implementation below. Check it out.

I have implemented an algorithm with complexity O(n) using a Hash Table (I used STL "unordered_map") that only has to iterate over the array once, and has onl a max of 6 accesses to the Hash Table per iteration.

I have implemented other working versions of this functions with complexity O(n) (one of them using a bitset), but this is the one I like the most. Here is the C++ implementation:

vector<int> findLongestSubset(int* arr, int size)
{
	unordered_map<int,int> mp;
	unordered_map<int,int>::iterator it;

	mp[arr[0]] = 1;	

	int max_seq = 1;
	int value_of_sequence = 0;
	int max_seq_first_elem = 0;
	int first_elem = 0;

	for(int i=1;i<size;i++)
	{	
		first_elem = arr[i];

		//Check if element is already in the map
		it = mp.find(arr[i]);
		if(it!=mp.end())
			continue;

		value_of_sequence = 0;
	
		//Check previous element in order by value if exists in map
		it = mp.find(arr[i]-1);
		if(it!=mp.end())
		{
			value_of_sequence = it->second;
			first_elem = arr[i]-value_of_sequence;
			//Update beginning of sequence
			mp[first_elem] = value_of_sequence+1;
		}
	
		value_of_sequence++;
		mp[arr[i]]=value_of_sequence;

		//Check next element in order by value if exists in map
		it = mp.find(arr[i]+1);
		if(it!=mp.end())
		{
			value_of_sequence = value_of_sequence+it->second;
			mp[first_elem] = value_of_sequence;
			mp[arr[i]+it->second] = value_of_sequence;
		}

		//Update max sequence and max sequence's first element
		if(value_of_sequence > max_seq)
		{
			max_seq = value_of_sequence;
			max_seq_first_elem = first_elem;
		}
	}

	vector<int> ret(max_seq); 

	for(int i=0; i<max_seq;i++)
		ret[i] = max_seq_first_elem+i;

	return ret;
}