arturo
BAN USERHere'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[r1][c])
ChangePixels(matrix, 5, 5, r1, c);
if(r<rows1 && val == matrix[r+1][c])
ChangePixels(matrix, 5, 5, r+1, c);
if(c>0 && val == matrix[r][c1])
ChangePixels(matrix, 5, 5, r, c1);
if(c<cols1 && 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);
}

arturo
July 05, 2013 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.
 arturo July 01, 2013@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(AB)
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 data1) 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_;
};

arturo
June 16, 2013 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;
}

arturo
June 16, 2013
Repyahviross, translator at learnify
Dedicated EnglishMandarin Chinese translator with years of experience working in professional and scientific communities.Diverse translation work including proprietary scientific ...
RepLauraJOles, Android Engineer at A9
Hi i am Laura.I live in Us from my childhood and i love my country.My father he is ...
RepJe suis Hudson Will des ÉtatsUnis. Je travaille comme technicien dans une entreprise Éco Vannes. J'analyse et vérifie tous ...
Repellaiyer15, Content Writer at Precious Moments
Committed to producing exceptional and creative types of content, including articles, internet content, advertisements, commercials, brochures, and publications. Experienced in ...
Repabbyherza, Animator at ASAPInfosystemsPvtLtd
I am Viola .I am A public relations consultant, a communications specialist who works as an intermediary between the public ...
RepRobin has more than 26 years of experience working for state, city, university, and public entities as a fisheries ecologist ...
RepDonnaArvin, Analyst at Apple
Hii am from the United States. I work as a computer control programmer at Dynatronics Accessories. I am a social ...
Open Chat in New Window
 arturo July 11, 2013