1.I need to store countries, its states and cities in a data structure.
The following queries might be used to fetch details

  1. find list of states for a country.
  2. find list of cities for a state.
  3. find the name of the country and state for a city.

eg:

  1. India -> Gujarat, UP, MP
    MP -> Bhopal, Indore
    Gujarat-> Surat, Ahmedabad, Baroda
  2. USA -> Texas, California.. and so on.

Which is the best data structure that can be used to store these details?
Solution: Linked Lists should be fine.

  1. A linked list of countries, where each node has two pointers
    1. One that points to a linked list of states.
    2. The other pointing to the next country node.
  2. Each node in the state linked list will have 3 pointers
    1. One pointing back to the it’s country node.
    2. Another pointing to a linked list of cities
    3. The third pointing to the next state node.
  3. Each city node will have 2 pointers
    1. One that points back to it’s state node
    2. The other pointing to the next city node.

Queries 1 and 2 can be addressed in O(n) where n is the size of the country/state/city list. Query 3 can be addressed in O(1) time.

2. Write a function to check whether the two strings are rotation of each other or not.
Example: str1=”Password” str2=”ordPassw”
Solution:

#include<stdio.h>
void fn(char * str1, char * str2)
{
int i=0, j=0,flag=0;
while(str2[i])
{
   if(str2[i]== *str1)
   {
      flag=1;
      break;
   }
i++;
}
if(!flag)
{
   printf("2nd String is not a rotation of other\n");
   return;
}
j=i;
while(str2[i])
{
   if( !(str2[i]==*str1))
   {
      printf("2nd String is not a rotation of other\n");
      return;
   }
   i++;
   str1++;
}
i=0;
while(i<j)
{
   if( !(str2[i]==*str1))
   {
      printf("2nd String is not a rotation of other\n");
      return;
   }
   i++;
   str1++;
}
if(*str1=='\0')
   printf("String are rotation of each other\n");
else
   printf("2nd String is not a rotation of other\n");
}
int main()
{
char * str1="Password";
char * str2="ordPassw";
fn(str2, str1);
return 0;
}

3.Given a string we have to find first non-repeating character in the string.
Example: str=”aabbbccccddeffffgg”;
Answer is : e
Solution:

char FindFirstNonRepeatChar(const char* s)
{
int asc[128][2]={0};
int size=strlen(s);
unsigned char first=-1;
for(int i=0;i<size;i++)
{
   asc[s[i]][0]++;
   asc[s[i]][1]=i;
}
for(int i=0;i<128;i++) 
{ 
   if(asc[i][0]==1) 
   { 
      if(first=-1) 
      { 
          first=i; 
      } 
      else if(asc[first][1]>asc[i][1])
      {
          first=i;
      }
   }
}
return first;
}

4.There is an array {1,2,3,4,5,6,7,8}. Divide the array in two subarrays such that the difference between sum of the elements of individual subarrays is minimum.
Lets say u divide the arrays in a1 and a2. Then sum of elements of a1 – sum of elements of a2 should be minimum if u divide the array in other way possible.
Solution:

// first sort the array in descending order then apply the function 
void divide(int a[20]) 
{ 
int i=0,sumb=0,sumc=0,j=0,k=0,b[10],c[10]; 
sumb=b[j++]=a[0]; 
sumc=c[k++]=a[1]; 
for(i=2;i<limit;i++)  
{  
   if(sumb>sumc) 
   { 
      sumc+=(c[k++]=a[i]); 
   } 
   else 
   { 
      sumb+=(b[j++]=a[i]); 
   } 
} 
// for(i=0;i<limit;i++) 
// printf("\n%d\n",a[i]); 
printf("sum b=%d nd sum of c %d",sumb,sumc); 
} 

void main() 
{ 
int i=0,a[20]; 
for(i=0;i<limit;i++) 
   scanf("%d",&a[i]); 
sortDesc(a); 
divide(a);
}

5. Data for various stocks is coming from various stock exchange continuously. Which data structure is suitable to store these data? Later I was told that if stocks are unique means only one data is there for each stock, then which data structure would you be choosing?
Solution:
For this types of questions, Its a biggest mistake to jump to solution directly. Its very necessary to ask right set of questions before committing any solution. As an example, here lot of things are unknown

  1. Data are coming from stock exchange but where they are going, is it some centralized place where all the exchanges are sending the data
  2. What is data here, is it just stock name, price, time stamp
  3. how frequently data is sent and is it in some batches like 100 stock data per second ?
  4. what if two stock exchanges same same data, do we need to merge them
  5. what kinds of operations we want to do, do we just need to consolidate the data set
  6. can stock exchanges are wired to the place where they are sending data, if not we might need to go for File system storage and the later transfer them.
  7. is stock data are real time stock value or historical data,
  8. are all stock exchanges reside in same time zone, what if stock exchange A is NYSE and stock exchange B is Bombay stock exchange

Once u get clarity for all these open questions, you should jump on for solution.
HashMap<Exchange,Set> should be the right option.

6.Given a matrix of -1’s and 0’s, display a matrix which contains minimum distance to reach nearest 0 for that particular position.
Example:
Input: -1 0 -1
-1 -1 -1
-1 -1 -1
Output:
1 0 1
2 1 2
3 2 3
Solution:

/* Check the condition, if we have find the minimum distance as 0 for any node, we don't need to travel the loop any more. */ 
if (min == 0) 
   break;
#include <iostream>
#include <math.h>
using namespace std; 
int main() 
{ 
int m,n;
cin>>m>>n; 
int **A=new int*[m]; 
for(int j=0;j<n;j++) 
{ 
   A[j]=new int[n]; 
} 
for(int i=0;i<m;i++) 
for(int j=0;j<n;j++)  
   cin>>A[i][j];
int *zeroi=new int[m*n]; 
int *zeroj=new int[m*n]; 
int k=0; 
for(int i=0;i<m;i++) 
{ 
   for(int j=0;j<n;j++) 
   if(A[i][j]==0) 
   { 
       zeroi[k]=i; 
       zeroj[k]=j; 
       k++; 
   } 
} 
for(int i=0;i<m;i++) 
{ 
   for(int j=0;j<n;j++) 
   { 
       int min=m+n; 
       for(int z=0;z<k;z++)  
       {  
           int dist=(abs(i-zeroi[z])+abs(j-zeroj[z]));  
           if(min>dist) 
               min=dist; 
           if (min == 0)
               break;
       } 
       A[i][j]=min; 
   } 
} 
for(int i=0;i<m;i++) 
{ 
   for(int j=0;j<n;j++) 
      cout<<A[i][j]<<" "; 
   cout<<"\n";	
} 
}

7. Give the output of the below code snippet :-

public class ParentTest 
{
public int x = 0;
public void print() 
{
   System.out.println("In Parent");
}
}

public class ChildTest extends ParentTest 
{
public int x = 1;
public void print() 
{
   System.out.println("In Child");
}
public static void main( String args[] )
{
   ParentTest s = new ChildTest();
   System.out.println(s.x);
   s.print();
}
}

Solution: Dynamic polymorphism is applicable to methods but not to variables. So the output will be “0: and :In Child”
ParentTest s = new ChildTest();
is evaluated as
ParentTest s ;
s= new ChildTest();

even though the variable s refers an instance of class ChildTest, the s.x still evaluates to “0”. Because variables names in Java are resolved by the reference type (it is ParentTest in this code), not the object they are referencing. This is known as Shadowing in Java. ChildTest extends ParentTest and overrides its print() method and when we call print() method from a reference variable of type ParentTest, it doesn’t call print() method from ParentTest class instead it calls print() method from ChildTest subclass because object referenced by ParentTest type is a ChildTest object. This resolution happens only at run time because object only created during run time and called dynamic binding in Java AKA Dynamic Method Dispatch.

8.Given three strings str1, str2 and str3; complete the function to find the smallest subsequence in str1 which contains all the characters in str2 (in any order) and not those in str3. For example,
Sample Input:
str1: spqrstrupvqw
str2: sprt
str3: q
Sample Output: strup
Explanation: In the given string str1, the smallest subsequence that contains the characters in str2 ( ‘s’ , ‘p’ , ‘r’ , ‘t’ ) and does not contain the character in str3 ( ‘q’ ) is ‘strup’.
Solution: 

Algorithm:

  1. Split the str1 with each character of the str3.
  2. Now iterate all the words and check the constraint that word contain all the characters of str2. Checking can be skipped by comparing string lengths.
  3. Return the minimum length string which satisfies point 2.

Implementation

public static void findShortestSubString() {
String s1 = "spqrstrupvqw";
String s2 = "sprt";
String s3 = "q";
Set<String> results = new HashSet<String>();
// 1. split the s1 with s3
// 2. sp rstrupv wrpts
// 3. find the shortest word that has s2 in it.
// -- if word's length >= s2.length --> find the shortest word sequence containing s2
String[] stringsToFind = s1.split(s3);
for(String stringToFind : stringsToFind)
{
   // ignore shorter strings
   if( stringToFind.length() < s2.length() )
   {
       continue;
   }

   // ignore the words that don't have every characters present in s2
   if( !stringHasAllLetters(stringToFind, s2))
   {
       continue;
   }

   boolean subStringFound = false;
   int offset = 0;
   int i = 0;

   // start with the exact length
   while( !subStringFound )
   {
      /* start to find all characters of s2 within equal length of words in stringToFind, if not found, increase length each time */
      for(i=0; i <= (stringToFind.length() - s2.length() - offset); i++ )
      {
          String currentSegment = stringToFind.substring(i, i + s2.length() + offset);
          if( stringHasAllLetters(currentSegment, s2) )
          {
              results.add(currentSegment);
              subStringFound = true;
              break;
          }
      }
      if( !subStringFound )
      {
          i = 0;
          offset++;
      }
   }
}
System.out.println(results);
}

private static boolean stringHasAllLetters(String stringToFind, String letters)
{
   boolean allLettersPresent = true;
   for(char c : letters.toCharArray())
   {
      if(stringToFind.indexOf(c) == -1)
      {
         allLettersPresent = false;
         break;
      }
   }
   return allLettersPresent;
}

9. How to add a more memory dynamically to an array without deleting the old memory, means, expanding an aray without deleting the old one?
Solution: You can have custom linked list with each element of the link list would be array of specific size. Once the number of elements reached to the size of array, it would add another link list element containing another array. It will require little complex algorithm to locate the linked list element based on [array_size]%index = linked list element
Remainder of above would then be the indexed element inside the array of the linked list element. It is somewhat similar to tiling in parallel programming.