CareerCup

A non DP solution.

Omit all the punctuation.


This is a test This is a programming test This is a programming test in any language




for(int i=0; i< TotalWordsInSentence; i++)

{

for(int j=i; j<TotalWordsInSentence; j++)

{

if(WordInSentence[j] is givenWord)

{

MarkFound(givenWOrd)

}


if(AllGivenWOrdFound())
{
Length = j - i;
start = i
end = j
}


if(Length < finalLen)
{
finalLen = Length
finalStart = start
finalEnd = end
}
}

}

print finalStart, finalEnd, finalLen

O(N^2) Complexity. Where N is Number of words in sentence.

1. Make a TRIE of all the words to be searched.
2. Now, find the first segment which contains all the words.Mark its length
3. Take two pointers, one pointing to the start of the above segment & other pointing to the end.
4. Increment the end pointer to point to the next word. Check whether both start & end pointer point to the same word. If yes, increment the start pointer to point to next word.[We will also perform the same while findin the first segment]
Now, remove all the extra words from the starting that are not in the TRIE.
5. Proceed above steps until EOF is not encountered, meanwhile also keep updating the minlength if length of the newly found segment is less.

If there are any issues, let me know.

Dude you are not supposed to paste questions, as contest is still going on.
Please remove this post asap

@manishs747
If this was an interview question then what kind of interview: phone or in-person? And was this question for fresh college grads?

here is my implementation in java

import java.util.*;
import java.io.*;
public class Solution
{
    public static void main(String[] args)
    {
        Map<String, Integer> needstofind = new TreeMap<String, Integer>();
        Map<String, Integer> hasfound = new TreeMap<String, Integer>();
        String final_result="";
        String result="";
        int begin=0;
        int end=0;
        String words[];
        String text_words[];
        String final_words[];
        String str_final;
        int begin_tmp=0;
        int end_tmp=0;
        int flag=0;
        int z=0;
        int len;
        int txt_len;
        int i;
        int count=0;
        int needstofind_size;
        int min=0;
        int final_length=0;
        Scanner in = new Scanner(System.in);
        String string = in.nextLine();
        string = string.replaceAll("[^a-zA-Z| |]", " ");
        string = string.replaceAll("  ", " ");
        str_final=string;
        string=string.toLowerCase();
        z = in.nextInt();
        words = new String[z+1];
        in.nextLine();
        for(i=0; i<z; i++)
        {
            words[i] = in.nextLine();
            needstofind.put(words[i],1);
        }
        text_words = string.split(" ");
        final_words=str_final.split(" ");
        len=hasfound.size();
        txt_len=text_words.length;
        i=0;
        needstofind_size=needstofind.size();
        begin=0;
        count=0;
        for(end=0; end<txt_len; end++)
        {
            if(needstofind.containsKey(text_words[end])==false)continue;
            hasfound.put(text_words[end],hasfound.get(text_words[end])==null?1:hasfound.get(text_words[end])+1);
            if(hasfound.get(text_words[end])<=needstofind.get(text_words[end]) )count++;
            if(count==needstofind_size)
            {
                flag++;
                while(needstofind.get(text_words[begin])==null || hasfound.get(text_words[begin])>1)
                {
                    if(needstofind.containsKey(text_words[begin]))
                    {
                        if(hasfound.get(text_words[begin])>1)
                            hasfound.put(text_words[begin],hasfound.get(text_words[begin])-1);
                    }
                    begin++;

                }
                if(flag>1 && end-begin+1>min)continue;
                result="";
                min=end-begin+1;
                for(int j=begin; j<=end; j++)
                    result=result+final_words[j]+" ";
                if(flag==1)
                {
                    final_result=result;
                    final_length=min;
                }
                else if(min<final_length && flag>1)
                {
                    final_result=result;
                    final_length=min;
                }
            }
        }
        if(flag>0)System.out.println(""+final_result);
        else System.out.println("NO SUBSEGMENT FOUND");
    }
}

A solution using hashmap and building a dp tree
This is a test This is a programming test This is a programming test in any language.
Explanation with ex:
Note the occurrence index in hashmap

This - 0,4,9
a - 2,6,11
test - 3,8,13
programming - 7,12

Start with the word with the least instance and move towards one greater instance.
Move to the next word and associate a instance
i)within the range
ii) if none within range associate closest greater than and closest lesser than it
for 7 in 'programming' to 'test'
7 - 3,7 and 7,8
for 12 in 'programming' to 'test'
12- 8,12 and 12,13
now add 'a' instance
3,7 -> 3,6,7 [ 6 is within range ]
7,8 ->6,7,8 and 7,8,11
8,12 -> 8,11,12 [ 11 is within range]
12,13 ->11,12,13
now add 'this' instance
3,6,7 ->3,4,6,7
6,7,8 ->6,7,8,9 and 4,6,7,8
7,8,11 -> 7,8,9,11
8,11,12 ->8,9,11,12
11,12,13 ->9,11,12,13
Now the leaf nodes are all the smaller segments containing the given words , the smallest of them[ smallest range] is the answer
3,4,6,7 - range 4
6,7,8,9 - range 3
4,6,7,8 - range 4
7,8,9,11 - range 4
8,9,11,12 - range 4
9,11,12,13 - range 4

Ans is 6,7,8,9

Use divider and conquer.
Collect all the words in the input string into a list inlist[left:right].
Start at the middle of the input list.

{{
subsegment(inlist[left:right], words)
from the mid move in steps of 1 to the left and right and check if the word is the search list. if it is there mark the positions
at the end of this step you should have mid segment which contains all the words.
If some words were not found return []
ls=subsegment(inlist[left:mid], words)
rs=subsegment(inlist[mid+1:right], words)
Now it is possible that all ls,ms,rs can contain the words or some of them or none of them.
return the subsegment with the min length
}}

I have written the code and it is working in Python. If you have any queries contact me

can someone provide good test cases . I'm getting only 6 cleared but i need test cases

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

bool isequals( char * a, char * b)
{
int sz = sizeof(a)/sizeof(char);
if ((sizeof(b)/sizeof(char)) != sz)
return false;

if (strcmp(tolower(a),tolower(b))!=0)
return false;
return true;
}
int main()
{
char str[]="This is a test. This is a programming test. This is a programming test in any language";

int test;
char **input;
scanf("%d",&test);
input=(char **)malloc(sizeof(char *)*test);

for(int i=0;i<test;i++)
{scanf("%s",input[i]);}
char * pch;
char **words;
words=(char **)malloc(sizeof(char *)*10000);
int i=0;

pch = strtok (str," ,.-");
while (pch != NULL)
{ words[i]=pch;
pch = strtok (NULL, " ,.-");
i++;
}


int count=0,k;
bool flag;

for( k=0;k<i;k++)
{

flag=false;
for(int j=0;j<test;j++)
{
if(isequals(input[j],words[k]))
{flag=true;}
}
if(flag)
{count++;}
else
{count=0;}
if(count==test)
{break;}

}

for(int j=test;j>0;j--)
{printf("%s ",words[j]);}





return 0;
}

import java.util.HashMap;
import java.util.Scanner;

public class SubSegment {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int strt=0, end=0, x=0, y=0;
		int len = 100000;
		String text = s.nextLine();
		int count = s.nextInt();
		HashMap<String, Integer> h = new HashMap<String, Integer>();
		for(int i=0; i<count; i++){
			h.put(s.next().toLowerCase(), 0);
		}
		text = text.replaceAll("[^a-zA-Z ]", "");
		String t = text;
		text = text.toLowerCase();
		String[] token = text.split(" ");
		for(y=0; y<=token.length; y++){
			if(!h.containsValue(0)){
				y--;
			}
			else{
				if(y< token.length && h.containsKey(token[y])){
					h.put(token[y], h.get(token[y])+1);
				}
			}			
			if(!h.containsValue(0)){
				if(len > y-x){
					len = y-x;
					strt = x;
					end = y;
				}
				if(h.containsKey(token[x])){
					h.put(token[x], h.get(token[x])-1);
				}
				x++;
			}
		}
		
		String[] token2 = t.split(" ");
		
		if(end > strt){
			for(int i=strt; i<=end; i++){
				System.out.print(token2[i]+" ");
			}
		}
		else
			System.out.println("NO SUBSEGMENT FOUND");
	}

}

import java.util.HashMap;
import java.util.Scanner;

public class SubSegment {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int strt=0, end=0, x=0, y=0;
		int len = 100000;
		String text = s.nextLine();
		int count = s.nextInt();
		HashMap<String, Integer> h = new HashMap<String, Integer>();
		for(int i=0; i<count; i++){
			h.put(s.next().toLowerCase(), 0);
		}
		text = text.replaceAll("[^a-zA-Z ]", "");
		String t = text;
		text = text.toLowerCase();
		String[] token = text.split(" ");
		for(y=0; y<=token.length; y++){
			if(!h.containsValue(0)){
				y--;
			}
			else{
				if(y< token.length && h.containsKey(token[y])){
					h.put(token[y], h.get(token[y])+1);
				}
			}			
			if(!h.containsValue(0)){
				if(len > y-x){
					len = y-x;
					strt = x;
					end = y;
				}
				if(h.containsKey(token[x])){
					h.put(token[x], h.get(token[x])-1);
				}
				x++;
			}
		}
		
		String[] token2 = t.split(" ");
		
		if(end > strt){
			for(int i=strt; i<=end; i++){
				System.out.print(token2[i]+" ");
			}
		}
		else
			System.out.println("NO SUBSEGMENT FOUND");
	}

}

Following code is passing 7 test cases but dont know what is wrong with other 3 test cases:

<?php
// read inputs
$line = trim(fgets(STDIN)); 						// reads paragraph
//$line = "This is a test. This is a programming test. a This is a  programming test in any language.";
//$line = file_get_contents('./input.txt', true);
if(strlen($line)> 200000) {
	die("Input paragraph is too long. It should be less than 200000");
}
$para = preg_split("/[\s]+/", $line);
foreach($para as $w) {
	if(strlen($w) >=15) {
		die("Word length should be in range 0 < word length < 15");
	}
}
$line1 = preg_replace("/[^a-zA-Z\s]/", "", $line);
$paragraph = preg_split("/[\s]+/", $line1);			// split paragraph in words

fscanf(STDIN, "%d\n", $number); 					// read number of words
//$number = 2;
if($number > count($paragraph)) {
	die("Number should be in range of 0 < Number <= " . count($paragraph));
}
for($i = 0; $i < $number; $i++) {
	$w = strtolower(trim(fgets(STDIN)));
	if(count($w) < 15) {
		$w = preg_replace("/[^a-zA-Z\s]/", "", $w);//strtolower(trim(fgets(STDIN)));
		$words[] = $w;
		$wordsAssoc[$w] = $w;
	} else {
		die("Word length should be in range 0 < word length < 15");
	}
}

// end reading inputs
$totalWords = count($words);
$totalPara = count($paragraph);
// create index map of required words
$alphaWords = array();
for($i = 0; $i < $totalPara; $i++) {
	$word = strtolower($paragraph[$i]);
	$alphaWords[] = $word;
}

$diff = array_diff($words, $alphaWords);

if(count($diff) > 0) {
	echo "NO SUBSEGMENT FOUND";
	exit;
}

$subStrLen = count($paragraph);
$min = 0;
$max = 0;
$found = array();
$result = array();
for($i = 0; $i < count($paragraph); $i++) {
	$word = strtolower($paragraph[$i]);
	if(isset($wordsAssoc[$word])) {
		if($totalWords == count($found)) {
			$found[$word] = $i;
			$values = array_values($found);
			$min = min($values);
			$max = max($values);
			//echo "$result[min] $result[max] $min $max \n";
			if($result['max'] - $result['min'] > $max - $min) {
				$result['min'] = $min;
				$result['max'] = $max;
			}
		} else {
			$found[$word] = $i;
			$values = array_values($found);
			$min = min($values);
			$max = max($values);
			$result['min'] = $min;
			$result['max'] = $max;
		}
	}
	if($totalWords == count($found) && $max - $min + 1 <= $totalWords) {
		// we have already found smallest substring
		break;
	}
}

for($i = $result['min']; $i <= $result['max']; $i++) {
	echo $paragraph[$i] . " ";
}

Can you explain your logic and where this question was asked.

I think we can have a HashTable where keys will be the 4 words and values will be by default false. Parse the text of string and check against the Hashtable to see if those values exists in the table. If yes, update value to True.... Now The words needs to be continuous. If not clear the HashTable and mark all False. Keep updating the table as per you parse the text,...and when you get all the values of the Table with TRUE at the same time words are continuous in the string, you get your answer right there !! Time complexity O(N), space will be O(1)..... give me ur thoughts on this... thanks !!

can any one tell me what will be the output of this case?

This is a test. This is a programming test. T!his is a programming test in any language.
4
this
a
test
programming

can we ignore "!" in "T!his" for the match?

after contest will over think lot of solution will be here...............till then wait.............!!!

guyz add extra test cases ... please !!!!!

This can be solved using DP.

I think you can use a Rabin Karp variant on this one