1. Given a string s[1...n] and a reverse function reverse(s, i, k) which reverses the character sequence from i to k (inclusive of both) in string s, determine what the following operations result in.
1<k<n

reverse(s, 1,  k)
reverse(s, k+1, n)
reverse(s, 1, n)

a) Reverses the string
b) Rotates the String left k positions
c) Rotates the String right k positions
d) None of the above


Answer: b)

2. If len is the length of the string and num is the number of characters printed on the screen. Give the relation between num and len.

void abc (char *s){
if(s[0]=='\0')
return;

abc(s+1);
abc(s+1);
printf("%c ", s[0]);

}

a) num=2^len
b )num=2^len-1
c) num=2*len-1
d) None of the above




Answer: b)




3. Which of the following numbers cannot be represented accurately in binary?
a) 0.1  b) 6.5 c) 1/16 d)1.32 e) 0.590625 (not sure abt option e)

1. a only
2. a and b
3. a, b and d
4. a, b and e




Answer: a) and d) should be the answer



4. A process doesn't require additional processors to carry out 40% of it's execution since 40% is mostly sequential. Determine how many processors are required to execute the process in 150s if
the process takes 300s to execute on a single processor.

a)5
b)8
c)6
d)7


Answer: c)

5. Time complexity of a function f(m) is O(m). If the array[i...n] contains either 1 or 0 in each of it's locations, determine the worst case time complexity of the following piece of code written in C-like
language.


counter=0;
for(i=0; i=n; i++){
if(a[i]==1)
counter++;
else{
f(counter);
counter=0;

}
}

* i=n was given in the condition of for loop
a) O(n^2)
b) O(n^2 logn)
c) O(nlogn)
d) O(n)




Answer: d) if assuming everything else to be alright.




6. Increasing the RAM increases the efficiency of the CPU. The reason
is
a) Virtual memory increases
b) Number of page Page faults decreases
c) Page segmentation decreases
d) Increasing the amount of memory increases the speed of fetching
data.


Answer: b)


7. If a dice is thrown three times, what is the probability that a "six" comes atleast once.
a) 125/216
b) 25/216
c) 91/216
d) 1/216

Answer: c)

Find lowest common ancestor of two given nodes in a Binary Search Tree.

Hint for a corner case : Instead of some trivial solutions please keep in mind that value of nodes can be same in a BST.

You are given an array of N numbers. Shuffle the numbers in the array such that all permutations have equal probability.

You are given a dictionary of say N words. Find all words having a given Prefix.

Write a function for a biased coin on the basis of a fair coin.

Find whether a string is palindrome or not. Given that string consists of punctuation marks as well.

Implement sqrt() function without using math.h header file.

You have a set of N numbers. Print all subsets out of these numbers that contains exactly k numbers.

Level Order Traversal of a Tree.


p.s. Solutions will be posted soon.

From now, I'll be posting interview questions for Computer Engineering of several companies that visit our campus at Institute of Technology, Banaras Hindu University. A collection kind of thing.

Please let me know about any question that you want to share at this place. Mail me at arvind.mohan.cse08@itbhu.ac.in

Be Curious!

In this article, I describe the Bellman-Ford algorithm for finding the one-source shortest paths in a graph, give an informal proof and provide the source code in C for a simple implementation.

The Problem

Given the following graph, calculate the length of the shortest path from node 1 to node 2.

It’s obvious that there’s a direct route of length 6, but take a look at path: 1 -> 4 -> 3 -> 2. The length of the path is 7 – 3 – 2 = 2, which is less than 6. BTW, you don’t need negative edge weights to get such a situation, but they do clarify the problem.
This also suggests a property of shortest path algorithms: to find the shortest path form x to y, you need to know, beforehand, the shortest paths to y‘s neighbours. For this, you need to know the paths to y‘s neighbours’ neighbours… In the end, you must calculate the shortest path to the connected component of the graph in which x and y are found.
That said, you usually calculate the shortest path to all nodes and then pick the ones you’re intrested in.

The Algorithm

The Bellman-Ford algorithm is one of the classic solutions to this problem. It calculates the shortest path to all nodes in the graph from a single source.
The basic idea is simple:
Start by considering that the shortest path to all nodes, less the source, is infinity. Mark the length of the path to the source as 0:




Take every edge and try to relax it:



Relaxing an edge means checking to see if the path to the node the edge is pointing to can’t be shortened, and if so, doing it. In the above graph, by checking the edge 1 -> 2 of length 6, you find that the length of the shortest path to node 1 plus the length of the edge 1 -> 2 is less then infinity. So, you replace infinity in node 2 with 6. The same can be said for edge 1 -> 4 of length 7. It’s also worth noting that, practically, you can’t relax the edges whose start has the shortest path of length infinity to it.
Now, you apply the previous step n – 1 times, where n is the number of nodes in the graph. In this example, you have to apply it 4 times (that’s 3 more times).












That’s it, here’s the algorithm in a condensed form:

void bellman_ford(int s) {
int i, j;

for (i = 0; i < n; ++i)
d[i] = INFINITY;

d[s] = 0;

for (i = 0; i < n - 1; ++i)
for (j = 0; j < e; ++j)
if (d[edges[j].u] + edges[j].w < d[edges[j].v])
d[edges[j].v] = d[edges[j].u] + edges[j].w;
}

Here, d[i] is the shortest path to node i, e is the number of edges and edges[i] is the i-th edge.
It may not be obvious why this works, but take a look at what is certain after each step. After the first step, any path made up of at most 2 nodes will be optimal. After the step 2, any path made up of at most 3 nodes will be optimal… After the (n – 1)-th step, any path made up of at most n nodes will be optimal.

The Programme

The following programme just puts the bellman_ford function into context. It runs in O(VE) time, so for the example graph it will do something on the lines of 5 * 9 = 45 relaxations. Keep in mind that this algorithm works quite well on graphs with few edges, but is very slow for dense graphs (graphs with almost n² edges). For graphs with lots of edges, you’re better off with Dijkstra’s algorithm.
Here’s the source code in C (bellmanford.c):

#include 
typedef struct {
int u, v, w;
} Edge;

int n; /* the number of nodes */
int e; /* the number of edges */
Edge edges[1024]; /* large enough for n <= 2^5=32 */
int d[32]; /* d[i] is the minimum distance from node s to node i */

#define INFINITY 10000

void printDist() {
int i;

printf("Distances:\n");

for (i = 0; i < n; ++i)
printf("to %d\t", i + 1);
printf("\n");

for (i = 0; i < n; ++i)
printf("%d\t", d[i]);

printf("\n\n");
}

void bellman_ford(int s) {
int i, j;

for (i = 0; i < n; ++i)
d[i] = INFINITY;

d[s] = 0;

for (i = 0; i < n - 1; ++i)
for (j = 0; j < e; ++j)
if (d[edges[j].u] + edges[j].w < d[edges[j].v])
d[edges[j].v] = d[edges[j].u] + edges[j].w;
}

int main(int argc, char *argv[]) {
int i, j;
int w;

FILE *fin = fopen("dist.txt", "r");
fscanf(fin, "%d", &n);
e = 0;

for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j) {
fscanf(fin, "%d", &w);
if (w != 0) {
edges[e].u = i;
edges[e].v = j;
edges[e].w = w;
++e;
}
}
fclose(fin);

/* printDist(); */

bellman_ford(0);

printDist();

return 0;
}

And here’s the input file used in the example (dist.txt): 5 0 6 0 7 0 0 0 5 8 -4 0 -2 0 0 0 0 0 -3 9 0 2 0 7 0 0 That’s an adjacency matrix. That’s it. Have fun. Always open to comments.

A Java Program to solve 8-Puzzle Problem

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class EightPuzzle {

    Queue<String> agenda = new LinkedList<String>();    // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
    Map<String,Integer> stateDepth = new HashMap<String, Integer>(); // HashMap is used to ignore repeated nodes
    Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor

    public static void main(String args[]){

        String str="087465132";                                 // Input the Board State as a String with 0 as the Blank Space

        EightPuzzle e = new EightPuzzle();              // New Instance of the EightPuzzle
        e.add(str, null);                                                   // Add the Initial State

        while(!e.agenda.isEmpty()){
            String currentState = e.agenda.remove();
            e.up(currentState);                                       // Move the blank space up and add new state to queue
            e.down(currentState);                                     // Move the blank space down
            e.left(currentState);                                     // Move left
            e.right(currentState);                          // Move right and remove the current node from Queue
        }

        System.out.println("Solution doesn't exist");
    }

    //Add method to add the new string to the Map and Queue
    void add(String newState, String oldState){
        if(!stateDepth.containsKey(newState)){
            int newValue = oldState == null ? 0 : stateDepth.get(oldState) + 1;
            stateDepth.put(newState, newValue);
            agenda.add(newState);
            stateHistory.put(newState, oldState);
        }
    }

    /* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
      After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
     */
    void up(String currentState){
        int a = currentState.indexOf("0");
        if(a>2){
            String nextState = currentState.substring(0,a-3)+"0"+currentState.substring(a-2,a)+currentState.charAt(a-3)+currentState.substring(a+1);
            checkCompletion(currentState, nextState);
        }
    }

    void down(String currentState){
        int a = currentState.indexOf("0");
        if(a<6){
            String nextState = currentState.substring(0,a)+currentState.substring(a+3,a+4)+currentState.substring(a+1,a+3)+"0"+currentState.substring(a+4);
            checkCompletion(currentState, nextState);
        }
    }
    void left(String currentState){
        int a = currentState.indexOf("0");
        if(a!=0 && a!=3 && a!=6){
            String nextState = currentState.substring(0,a-1)+"0"+currentState.charAt(a-1)+currentState.substring(a+1);
            checkCompletion(currentState, nextState);
        }
    }
    void right(String currentState){
        int a = currentState.indexOf("0");
        if(a!=2 && a!=5 && a!=8){
            String nextState = currentState.substring(0,a)+currentState.charAt(a+1)+"0"+currentState.substring(a+2);
            checkCompletion(currentState, nextState);
        }
    }

    private void checkCompletion(String oldState, String newState) {
        add(newState, oldState);
        if(newState.equals("123456780")) {
            System.out.println("Solution Exists at Level "+stateDepth.get(newState)+" of the tree");
            String traceState = newState;
            while (traceState != null) {
                System.out.println(traceState + " at " + stateDepth.get(traceState));
                traceState = stateHistory.get(traceState);
            }
            System.exit(0);
        }
    }

}

A program to solve Crypt Arithmetic Problem

#include<iostream>

#include<math.h>

using namespace std;

int size;

char a[10],b[10],c[11],d[11];

int an,bn,cn;

int n[10];

int ct=0;

int maxchar;

void gen(int z,int avail[10]);

void check();

void calc()

{

    int i;

  if(maxchar>10)

  {

      cout<<"wrong input";

      return;

  }

  int avail[10];

  for(i=0;i<=9;i++)

    avail[i]=1;

  gen(0,avail);

}

int no[10];

void gen(int z,int avail[10])

{

    if(z<maxchar)

    {

    int i;

    for(i=0;i<10;i++)

    {

        no[z]=i;

        if(avail[i]==1)

        {

            avail[i]=0;

            gen(z+1,avail);

            avail[i]=1;

        }

    }

    }

    if(z==maxchar)

      check();

}

Read more »