InterviewStreet Find Strings Solution C++

InterviewStreet Find Strings Solution C++

Problem

https://www.interviewstreet.com/challenges/dashboard/#problem/4efa210eb70ac

Algorithm

Declare a set<string> which will contain strings lexicographically ordered.
For each input string
     generate all its substrings one by one and add them  to set
For each query
     move pointer to require index in set and return the string
     if query no is greater than size of set, print Invalid.

 

 Solution

If you know better solution please post it in comments section.
//4 out of 7 test cases passed
#include<iostream>
#include<set>
#include<string>
typedef unsigned long long int big;
using namespace std;

int main() {

int n,i;
cin >> n;

set<string> s;
set<string>::iterator it;

string s1,temp;
for(i=0;i<n;i++) {   
    cin >> s1;
    int len = s1.length();
    int j,k;
    for(j=0;j<len;j++)
        for(k=len-j;k>0;k--) {
            temp = s1.substr(j,k);
            s.insert(temp);
        }                      
}

it=s.begin();
int curr = 1;
int q;
cin >> q;
big k, len;
len = s.size();
cout << len;
for(i=0;i<q;i++) {
    cin >> k;
    if(k>len) {
       cout << "INVALID\n";
       continue;
    }
    if(curr+(len/2) < k) {
      it = s.end();
      it--;
      curr = len;
    }
    if(curr-(len/2) > k) {
       it = s.begin();
       curr = 1;
    }
    if(k>curr) {
        int j= k-curr;
        while(j) { it++; j--; }
        cout << *it << endl;
        curr = k;
    }
    else if(k<curr) {
        int j=curr-k;
        while(j) { it--; j--;}
        cout << *it << endl;
        curr = k;
    }
    else cout << *it << endl;
}

cin >> i;
}

Interviewstreet String Similarity Solution C++

Interviewstreet String Similarity Challenge

Problem Statement

String similarity of two strings is defined as length of longest prefix common to both strings. For example string similarity for abcd and abb is 2, length of ab. Calculate sum of similarities of a string with each of its suffixes.
Input: First line contains T, no of test cases and next T lines contain strings
Output: T lines contain answer.
Sample Input:                                                  Sample Output:
1                                                                       3
aa

Algorithm

1) calculate similarity value of string with each of its suffix, i.e if character at index i matches with 1st character calculate the similarity value for this suffix.
2) For calculating similarity value, start counter with 0 and keep counting until prefix of the given suffix matches with original string. if doesn't match break and return count.
3) Keep calculating sum by adding every count value returned.

If you have a different approach in mind, please share it in comments section.

Solution

#include<stdio.h>
#include<string.h>

int getSimilarity(char str[],int sub_ind,int st);

int main()
{
    int T,len=0,sum=0,i=0;
    char s[100001];
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        scanf("%s",s);
        int y=strlen(s);
        for(i=0;i<y;i++)
            if(s[i]==s[0])
            {
               
                sum=sum+getSimilarity(s,i,y);
            }
        printf("%d\n",sum);
    }
}

int getSimilarity(char str[],int sub_ind,int st)
{
    int g=sub_ind;
    int j, i=0;
    int count=0;
    for(i=g,j=0;i<st;i++)
        if(str[i]==str[j++])
        {
            count++;
        }
        else
            break;
    return count;  
}

Time Complexity
O(n*n), bcoz if first character of suffix matches with first character of original string then we calculate string similarity for this suffix with original string which takes O(n) time and there can be n such suffix matches.

Interviewstreet String Reduction Solution C++

Interviewstreet Challenge String Reduction

Problem Statement

You are given a string consisting of a, b, and c's and following operation is allowed: Take any two adjacent character and they can be replaced with third character. For ex: a and b with c, b and c with a. Find length of smallest string, the operation can be applied repeatedly.
Ex: for input bcab, bcab -> aab -> ac -> b the output will be 1

Input: T test cases and next T lines contain strings to start with.
Output: T lines containing length of smallest possible resultant strings after applying operations repeatedly and optimally.

Algorithm

Use brute force approach, For each string
1) If length of string is 1 return 1
2) if len is 2 and both character are same return 2
3) else try to find smallest possible string from all possible ways i.e for every two adjacent character replace it with third character and invoke reduce again on this new smaller string until smallest possible string is reached.
4) If the string achieved is smaller then previous possible smaller string store and update minimum length.

If you have a different approach in mind, please share it in comments section for our readers.

Solution

// all 10 test cases passed

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

int minimum=1;
int value=1;


private boolean reduce(String s1) {
char[] array=s1.toCharArray();
int len=array.length;
minimum =array.length;
boolean flag;
String cat;
if(len==1)
{
value=1;
return true;
}
else if(array[0]==array[1] && len == 2)
{
value=2;
return true;
}

for(int i=0;i<len-1;i++)
{
if(array[i+1]!=array[i])
{

String new_string

=Character.toString(array[i]).concat(Character.toString(array[i+1]));
char reduce =other(new_string);
String sub1="";
String sub2=Character.toString(reduce);
String sub3="";
if(i==1)
{
sub1=Character.toString(array[0]);
}else if(i>1)
{
sub1=s1.substring(0, i);
}
if(i+2<len-1)
{
sub3=s1.substring(i+2,len);
}else if(i+2==len-1)
{
sub3=Character.toString(array[i+2]);
}
cat=sub1+sub2+sub3;
flag=reduce(cat);
if(flag)
{
minimum=Math.min(minimum, value);
return flag;
}
}
}
return false;
}

private char other(String s1) {
char ret_value='b';
if (s1.equalsIgnoreCase("bc")|| s1.equalsIgnoreCase("cb")) {
ret_value='a';
}
else if (s1.equalsIgnoreCase("ab")|| s1.equalsIgnoreCase("ba")) {
ret_value='c';
}
return ret_value;
}
   
   
public static void main(String[] args) {
Scanner scan;
Solution obj = new Solution();
scan = new Scanner(System.in);
int T = scan.nextInt();
for (int i = 0; i < T; i++) {
String s1 = scan.next();
obj.reduce(s1);
System.out.println(obj.minimum);
}
}
       
}

Time Complexity

In a string of length n, there are n-1 2 character pairs, At max each of these pair would contain different character so for n-1 pairs we replace it with third character and call reduce again on new string of length n-1 which has n-2 pairs and so on....(n-1)*(n-2)*(n-3)..1 = (n-1)! times.
Surely it can be done in better way. If you find a better solution, update me.

find all anagrams of a word in a file, Java Code : Amazon Interview

Find all anagrams of a word in a file 

Amazon Interview (Dec 2011)

Problem Statement

Find all anagrams of a word in a file. Input -  only file name and word. Output - all set of word in file that are anagrams of word. Write production quality code.

Algorithm

1) Use a hashmap with string as key and list<string> as value where list of strings contain all anagrams of a key string.
2) For each word in the file, find beta string which is its sorted version ex abd is sorted version of bad, adb and dba. Put this word to that list whose key is this beta string. If it does not exist then create a new list with the beta string as key in map.
3) Finally print all strings from the list whose key is the input word(sorted/beta string).

If you have a different approach in mind, please share it in comments section for our readers.

Solution

import java.util.*;
import java.io.*;

public class Anagram {
    public static void main(String[] args) {
    String beta = args[1];

        try {

            Map<String, List<String>> m = 

                   new HashMap<String, List<String>>();

            Scanner s = new Scanner(new File(args[0]));
            while (s.hasNext()) {
                String word = s.next();
                String alpha = sorting(word);
                List<String> l = m.get(alpha);
                if (l == null)
                    m.put(alpha, l=new ArrayList<String>());
                l.add(word);
            }

         List<String> l = m.get(sorting(beta));
       Object[] arr = l.toArray();
           for (int i=0; i < arr.length; i++)
                System.out.println(arr[i]);

        }
    catch (Exception e) {
            System.out.println(e);
            System.exit(1);
        }

    }

    private static String sorting(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }
}

Time Complexity

O(n) for visiting each word in file once. You can't do it actually in O(n) if you consider the time complexity involved in sorting each word.
If you consider that time complexity involve with sorting also, then you should know that java uses quicksort algorithm to sort char array for which time complexity is O(mlogm) and I have applied sorting function in my code to each word of file .Therefore the time complexity would be O(n*mlogm), where longest word has length m.

Replace all spaces in a string by %20. Amazon Interview

Replace all spaces in a string by %20.

Amazon Interview (Jan 2012)

Problem Statement

Replace all spaces in a string by %20. Write production quality code in first attempt  

Algorithm

1) Move along the string and count no of spaces.

2) New string length would be old string length + 2*no of spaces.

3) Start transferring characters from old string to new string and where ever there is space replace it with %20 as asked in question else transfer character as it is to new string. 

4) Finally put a '\0' character in end  of the new string.

Solution

// Replace all spaces in a string by %20.
// Write production quality code in first attempt.

#include<stdio.h>
#include<string.h>

int main()
{

char str[100];
//syntax to scan string till new line in C
scanf("%[^\n]", str);

int len = strlen(str);
int i,count=0,k=0;
for(i=0;i<len;i++)
    if(str[i]==' ') count++;
   
char newstr[len+2*count];
for(i=0;i<len;i++)
{
    if(str[i]==' ') {
        newstr[k++] = '%';
        newstr[k++] = '2';
        newstr[k++] = '0';
    }
    else
        newstr[k++] = str[i];
}
newstr[k] = '\0';
printf("%s\n", newstr);

}

Time Complexity

O(2n) <==> O(n) since we move pointer along string twice.

Longest substring without repeating characters

Longest sub-string without repeating characters

Common Interview Question

Problem Statement

You are given a string. You need to find the length of "longest substring with unique characters" in O(n) time.
Ex: For Hackertohacker it is 8, hackerto

Solution

#include<stdio.h>
#include<string.h>

int longestSubString(char *str);

int main()
{

char str[] = "hackertohacker";
int len = longestSubString(str);
printf("%d",len);
getchar();
}

int longestSubString(char *str)
{

int visited[256];
int i;
for(i=0;i<256;i++)
    visited[i]=-1;

int curr_len=1;
int max_len=1;
int len=strlen(str);

visited[str[0]]=0;
int prev;

for(i=1;i<len;i++)
{
    prev = visited[str[i]];
   
    if(prev == -1 || i-prev > curr_len)
        curr_len++;
    else {
        if(max_len < curr_len)
          max_len=curr_len;
        curr_len=i-prev;
    }
   
    visited[str[i]]=i;
}

if(max_len < curr_len)
    max_len = curr_len;

return max_len;
}       

//If you have a different approach in mind, please share it in comments section for our readers.


Time Complexity: O(n)


If you find this blog somewhat helpful, please share it and Keep Visting...:)

Compress a string aaabbbcc into a3b3c2 : O(n) C code

Amazon Interview: String Compression

Problem Statement

Given a string "aaabbbcc", compress it, = "a3b3c2" . Given that output string's length is always smaller than input string, you have do it inplace. No extra space like array should be used.

Solution

#include<stdio.h>
#include<string.h>

void compress(char *str,int len, int act);
char str[100];
int length;

int main()
{
scanf("%s",str);
length=strlen(str);
//compression
//we need a recursive sol so that
//cases like abbbccc or abcccc are also taken care of
compress(str,0,0);
printf("%s",str);
scanf("%d",&length);

}

//recursive code - prefered
void compress(char *str,int len, int act) {

if(len<length) {
    int k=len;
    int count=0;
    int c, n;
    while(str[k]==str[len]){
        len++; count++;
    }
    n = 0;
    c=count;
    do {
        c /= 10;
        n++;
    } while (c != 0);
   
    compress(str,len,act+n+1);
   
    str[act]=str[k];
    if(k+count==length)
       str[act+n+1]='\0';
    for(c=0;c<n;c++) {
        str[act+n-c]=(count%10)+48;
        count=count/10;
    }

}
return;
}


Time Complexity:  O(n)


If you found this blog somewhat helpful, please share it and Keep Visiting.....:)

Find Longest Palindrome in a string : O(n*n) C code

  Given a string S, find the longest palindromic substring in S.

For example,
S = “caba".

The longest palindromic substring is “aba”.

Algorithm:

1. Palindrome mirrors around center and there are 2N-1 such centers in string. The reason is center of palindrome can be in between two letters(for even length string) or the letter itself (for odd length string).
2. Expand a palindrome around its center in both direction and look for maximum possible palindrome (O(n) time).
3. If the length of string is odd, the center would be letter, therefore repeat the step 2 for each letter and update maximum palindrome on the way.
   
4. If the length of string is even, the center would be between two letters, therefore repeat the step 2 for each such center and update the maximum palindrome on the way.
5. Since there are O(N) such centers, time complexity would be O(n²).

// O(n*n) time complexity and O(1) space algorithm
#include<stdio.h>
#include<string.h>

void longestpalindrome(char *str);

int main()
{
char *str = "abacba";
int i;
longestpalindrome(str);
scanf("%d", &i);
}

void longestpalindrome(char *str) {

int length = strlen(str);
printf("%d\n", length);
int i,j,k;
int start,end,max=0,curr;

if(length == 0) {printf("string null"); return;}

if(length%2!=0) { //if string is of odd length
    for(i=0;i<length-1;i++) {
        j=k=i;
        while(j>0 && k<length-1 && str[--j]==str[++k]); 
        curr = k-j+1;
        if(curr > max) {
           max = curr;
           start = j;
           end = k;
        }
    }
    for(i=start;i<=end;i++) printf("%c", str[i]);
    printf("\n");
}
else { //if string is of even length
    for(i=0;i<length-1;i++) {
        if(str[i]==str[i+1]) {
            j=i;
            k=i+1;
            while(j>=0 && k<=length-1 && str[j--]==str[k++]);
                    curr = k-j-1;
                    if(max < curr) {
                       max = curr;
                       start = j+1;
                       end = k-1;
                    }
        }
        for(i=start;i<=end;i++) printf("%c", str[i]);
        printf("\n");
    }
}
}
  
                         
           

// Time Complexity: O(n²)

// Space Complexity: O(1)