You are here:

C++/C SOLUTION

Advertisement


Question
recently i came across this question in our campus interview. which i dint clear. they dint gave the solution also for this one.
question :

input:
T X B X
X I S X
C D M D
S W Q E

search string : TIME

output : TIME (1,1,SE)
where 1,1 signify the 1st row and 1st column and SE represents the direction south east.

sir, can you help me out to clear this problem.

Answer
"Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy." - Rob Pike

"When in doubt, use brute force." - Ken Thompson

using brute force:

#include <algorithm>
#include <string>
#include <iostream>

enum { ROWS = 4, COLS = 4 } ;

enum direction { N, NE, E, SE, S, SW, W, NW } ;

const char* const direction_string[] =
         { "N", "NE", "E", "SE", "S", "SW", "W", "NW" } ;

const std::pair<int,int> increment[] =
{
   std::make_pair(0,-1), std::make_pair(+1,-1), std::make_pair(+1,0),
   std::make_pair(+1,+1), std::make_pair(-1,0), std::make_pair(-1,+1),
   std::make_pair(-1,0), std::make_pair(-1,-1)
};

inline bool apply_increment( int& a, int& b, const std::pair<int,int>& incr )
{
    a += incr.first ;
    b += incr.second ;
    return ( a >= 0 ) && ( a < ROWS ) && ( b >= 0 ) && ( b < COLS ) ;
}

void find_it( const char (&grid) [ROWS] [COLS], const std::string& word )
{
  for( int i = 0 ; i < ROWS ; ++i )
      for( int j = 0 ; j < COLS ; ++j )
      {
         for( direction dir = N ; dir <= NW ; dir = direction( dir+1 ) )
         {
         std::string str ;
         int x = i ;
         int y = j ;

         do str += grid[x][y] ;
         while( apply_increment( x, y, increment[dir] ) );

         if( str.find( word ) != std::string::npos )
         {
         std::cout << word << '(' << i+1 << ',' << j+1 << ','
         << direction_string[dir] << ")\n" ;
         return ;
         }
         }
      }
}

int main()
{
   const char grid[ROWS][COLS] =
   {
       { 'T', 'X', 'B', 'X' },
       { 'X', 'I', 'S', 'X' },
       { 'C', 'D', 'M', 'D' },
       { 'S', 'W', 'Q', 'E' }
   } ;
   find_it( grid, "TIME" ) ;
}  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.