# Interview Questions 13

September 5, 2010 Leave a comment

1. You are in a maze(like a labyrinth), and you open your eyes so you don’t know your position. The maze has walls and you can move only in up, right, left and down directions. You can escape the maze when you find a ladder.

The following API is given:

bool TryMove(direction) – returns true when you don’t hit a wall;

bool HasLadder() – return true if you found the ladder.

Write a method bool Explore() that returns true if you can escape the maze, false otherwise. Also, provide test cases.

2. Given a MxN matrix, in how many ways can you go from top-left to bottom-right?

3. You have given a node of a tree. that node is defined as below:

struct Node {

int value,

struct Node *left;

struct Node *right;

struct Node *grandparent;

} node;

At the starting the grand parent node is null in the tree. you have to assign the grandparent node for all the nodes in the tree.

4. Write pattern matching algorithm.

i.e isMatch(String,Pattern)

Pattern can have ?(one character) and *(many characters).

ex. abbdef and a?b*f are a match

aaabab and a*ba are not a match

5. Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take. [Tricky :)]

6. Write a function to find the nearest link on a webpage given the mouse x,y coordinates.

If your algorithm just iterates through all the links, give an idea of how to make it faster.

7. In C++, write functions for:

string serialize(vector v);

vector deserialize(string s);

such that a string returned from ‘serialize’ can be passed into deserialize to get the original set of strings back.

8. There is a byte array which contains the character of one byte and two bytes. One byte character has range 0 to 127 and first character of 2 byte character is 128 to 255 and second byte character has range 0 to 255. Now, two pointers are given, one points to the start of the and another points to somewhere else.

Tell which character 2nd pointers points to?

9. You have a graph with and start point A and end point B. All edges have positive weights. Now the shortest path from A to B can be found using Djikstra.

a) Find the kth shortest path

b) Find the longest path

10. Many overlapping rectangles – want to return which (doesn’t matter which one, if it’s over several) rectangle the mouse is over.

## Recent Activity