Informatica Interview Question for iOS Developers

Team: interviews
Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
0
of 0 vote

Well, you could reformulate the problem as shortest path on a graph with edge weights 1, where each square on the board is a node, and its neighbours are all the nodes the knight can go to from there. If a part is cut, then obviously the node doesn't exist. The shortest path is simply given by BFS (since all edge weights are the same), so it should take O(nodes + edges ) time which is O(n^2 + 8(n^2)) which is O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 3

/*
coordinates of the map
-----------> X
|
|
|
|
|
Y
*/
struct Point{ //coordinate of a point
int y, x;
};
int N; //map's row and col size
char map[MAX][MAX+1]; //map's state
int prePos[MAX*MAX]; //prePos[i] is the previous position of i, i/N is row, i%N is col
const int step[][2] = { //8 kinds of steps of knight -> (dy, dx)
{-2,1},{-1,2},{1,2},{2,1},
{-2,-1},{-1,-2},{1,-2},{2,-1}
};

void markPath(int y, int x)
{
int now, pre;
for(now = y*N + x; (pre = prePos[now]) >= 0; now = pre){
map[pre/N][pre%N] = '@';
}
}

bool bfs()
{
int i;

//step 1: find start and destination
int sy, sx, dy, dx;
char* p;
for(i = 0; i < N; ++i){ //find start
if(p = strchr(map[i], '@')){
sy = i;
sx = p - map[i];
break;
}
}
if(p[1] && (p = strchr(p+1, '@'))){//if destination is at the same row
dy = i;
dx = p - map[i];
}
else{ //destination is at different row
for(++i; i < N; ++i){
if(p = strchr(map[i], '@')){
dy = i;
dx = p - map[i];
break;
}
}
}

//step 2: bfs to find the shortest path from start to destination
memset(prePos, 0xFF, sizeof(prePos));
Point now, nex;
int nowIndex, nexIndex;
queue<Point> q;

now.y = sy;
now.x = sx;
q.push(now);
while(!q.empty()){
now = q.front();
if(now.y == dy && now.x == dx){ //find path!
markPath(dy, dx); //mark path in the map
return true;
}
//get represent index of point now
nowIndex = now.y*N + now.x;
for(i = 0; i < 8; ++i){
nex.y = now.y + step[i][0];
nex.x = now.x + step[i][1];
if(nex.y < 0 || nex.y >= N || //y out of border
nex.x < 0 || nex.x >= N || //x out of border
map[nex.y][nex.x] == '#') continue;//it's a cut cell
//get represent index of point nex
nexIndex = nex.y*N + nex.x;
if(prePos[nexIndex] >= 0) continue; //already visited
//add nex point to position queue
prePos[nexIndex] = nowIndex;
q.push(nex);
}
}

return false;
}

int main()
{
int i;
//input map size
scanf("%d", &N);
while(getchar() != '\n');
//input each row
for(i = 0; i < N; ++i) gets(map[i]);
//bfs search path
if(bfs()){//can go
for(i = 0; i < N; ++i) puts(map[i]);
}
else puts("Impossible");

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <ctime>
using namespace std;

const int N = 8;
int map[N][N];

/* A utility function to check if i,j are valid indexes for N*N chessboard */
bool isSafe(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && map[x][y] == -1;
}

/* A utility function to print solution matrix sol[N][N] */
void printSolution() {
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
cout << map[x][y];
cout << endl;
}
}

/* A recursive utility function to solve Knight Tour problem */
bool knightsTourRecursive(int x, int y, int movei, int xMove[N], int yMove[N]) {
int nextX, nextY;

if (movei == N*N)
return true;

/* Try all next moves from the current coordinate x, y */
for (int k = 0; k < 8; k++) {
nextX = x + xMove[k];
nextY = y + yMove[k];

if (isSafe(nextX, nextY)) {
map[nextX][nextY] = movei;

if (knightsTourRecursive(nextX, nextY, movei+1, xMove, yMove)) // recursion
return true;
else
map[nextX][nextY] = -1; // backtracking
}
}
return false;
}

bool knightsTour() {
/* Initialization of solution matrix */
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
map[x][y] = -1;

/* xMove[] and yMove[] define next move of Knight.
xMove[] is for next value of x coordinate
yMove[] is for next value of y coordinate */
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

int initX = rand() % N;
int initY = rand() % N;

cout << "Starting at " << initX << " " << initY << endl;

// Since the Knight is initially at the first block
map[initX][initY] = 0;

/* explore all tours using solveKTUtil() */
if(!knightsTourRecursive(initX, initY, 1, xMove, yMove) ) {
cout << "Solution does not exist" << endl;
return false;
}
else
printSolution();

return true;
}

int main() {
srand( (unsigned) time(0));
knightsTour();

cin.get();
return 0;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.