Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 2 vote

public class Solution {
    public String minWindow(String s, String t) { // s is the string and t is alphabet
        int[] map = new int[256];
        int begin=0,end=0; // for substring window
        int head = begin; // for getting the output substring
        
        for(int i=0;i<t.length();i++) { // fill the map with freq of chars in t
            map[t.charAt(i)]++;
        }
        
        int count = t.length(); // size of t as we have to have this count check
        int min=Integer.MAX_VALUE;
        
        while(end<s.length()) {
            // System.out.println(s.charAt(end) + "\t" + map[s.charAt(end)]);
            // System.out.println("Step 1\t"+count+"\t"+begin+"\t"+end+"\t"+head+"\t"+min);
            if(map[s.charAt(end++)]-->0) { // if it is present in map decrease count
                count--;
            }
            // System.out.println("Step 2\t"+count+"\t"+begin+"\t"+end+"\t"+head+"\t"+min);
            while(count==0) { // t is found in s
                if(end-begin<min) { // update min and head
                    min = end-begin;
                    head = begin;
                }
                if(map[s.charAt(begin++)]++==0) { // shrink the window
                    count++;
                }
            }
            // System.out.println("Step 3\t"+count+"\t"+begin+"\t"+end+"\t"+head+"\t"+min);
        }
        
        return min==Integer.MAX_VALUE ? "" : s.substring(head,head+min);
    }
}

- prathak07 January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isAlphabetChar(char a)
{
    return dict[a];
}

//time complexity of 2 * input size
//extra storage is input size
string shortestSub (string input)
{
    vector<bool> isAlphabet(input.size());
    
    for (int i=0; i< input.size(); i++)
    {
        if (isAlphabetChar(input[i]))
        {
            isAlphabet[i] = 1;
        }
    }
    
    //keeps track of shortest start index and shortest length
    int startIndex = 0;
    int length = input.size();
    
    //if in the middle of evaluating a string, set to true
    bool evalString = true;
    
    int currentLength = 0;
    int currentStart = 0;
    for (int i=0; i< isAlphabet.size(); i++)
    {
        if (isAlphabet[i] == 1)
        {
            if (evalString == false)
            {
                currentStart = i;
            }
            evalString = true;
            currentLength++;
            
        }
        else
        {
            if (evalString == true)
            {
                if (currentLength < length)
                {
                    length = currentLength;
                    startIndex = currentStart;
                }
            }
            
            evalString = false;
            currentLength = 0;
            currentStart = i;
        }
    }
    
    return input.substr(startIndex, length);
}

- julie January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 
The idea is to isolate all pair of (start,end) indices
such that : length is >= alphabet
sort ascending by length   
then find first match - that will ensure shortest.
There are other alternatives.
just find pairs, ignore all which are less than size of alphabet, and keep a min.
This avoids the sorting.   
*/
def find_min_alpha_sub_str( string , alphabet ){
  r = [0:size(string)]
  max_len = size(alphabet)
  pairs = join ( r , r ) :: { $.o.1 - $.o.0 + 1 >= max_len }
  fold( pairs , string ) :: {  
    s = string[$.o.0:$.o.1]
    // ignore when not a sub set or current size is >= min size 
    continue ( !( alphabet.value <= s.value && size(s) < size($.p) ) )
    $.p = s // got the min one 
  }
}
s = find_min_alpha_sub_str ( "abbcac", "abc" )
println( s )

- NoOne January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* @author prizkaboom
 */
public class ShortestSubstring {
    
  HashMap HashAlphabet;   
    
 
public ShortestSubstring()
{

}
  
  
 void resetAlphabet()
 {
 
  HashAlphabet = new HashMap();
    
 }   
    
 public void getShortestSubstring(String stringToCheck, String Alphabet )
 {
   
       this.resetAlphabet();
       int initIndex=-1;
       int lastIndex=-1;
      
       for (int i = 0; i < stringToCheck.length(); i++)
      {
          char c = stringToCheck.charAt(i);        
          
          if(HashAlphabet.containsKey(c))
          {
             resetAlphabet();
             initIndex=i+1;
          }
          else
          {
          HashAlphabet.put(c,i);
          }
           System.out.println("Adding:"+c);
           
           
               
          if(HashAlphabet.size()==Alphabet.length())
              {
                
                   if(ContainsAlphabet(Alphabet))
                   {
                     lastIndex=i+1;
                     String subs=stringToCheck.substring(initIndex,lastIndex);
                      System.out.println("is:"+ subs);
                       printHashAlphabet();
                     return;
                   }
                   else
                   {
                   resetAlphabet();
                   initIndex=i+1;
                   }
                  
                  
              }
          if(HashAlphabet.size()>Alphabet.length())
          {
           resetAlphabet();
           initIndex=i+1;
          }
          
         
         
       
      }
       // printHashAlphabet();
      System.out.println("The alphabet:"+Alphabet+" is not contained on this string");
     // If the ford end but we arribe here if meas that the shortest alphabet is no  present
    
 }   
    
 boolean ContainsAlphabet(String Alphabet)
 {
     // Add of elements of the  Alphabet
   for (int i = 0; i < Alphabet.length(); i++)
    {
         char c = Alphabet.charAt(i);        
         if(!HashAlphabet.containsKey(c))
         {
         return false;
         }
          
      }
   
    
   return true;
    
   
 }   
 
 void printHashAlphabet()
{
    System.out.println("Map : " + HashAlphabet+ "This can track the position!!");
 
}

- prizkaboom January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Program
    {
        static void Main(string[] args)
        {
            string inputString = "aabbccba";
            char[] searchedCharacters = {'a','b','c'};
            string tempStr = "";
            int startingSize = 3;
            int maxLength = inputString.Length;

            bool found = true;

            while (startingSize <= maxLength)
            {
                for (int i = 0; i <= maxLength-startingSize; i++)
                {
                    tempStr = inputString.Substring(i, startingSize);
                    found = true;
                    foreach (char searchedChar in searchedCharacters)
                    {
                        if (tempStr.IndexOf(searchedChar) == -1)
                        {
                            found = false;
                            break;
                        }

                    }
                    if (found)
                    { 
                        Console.WriteLine(tempStr);
                        Console.Read();
                        return;
                    }
                }
                startingSize++;
            }

            
        }
    }
}

- veronica January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2)

public class ShortestSubstringWithAllAlphabets {
	
	public static void main(String[] args){
		
		String oStr = "aabbccba";
		char[] cArr = {'a', 'b', 'c'};
				
		String subStr=null;
		int min = Integer.MAX_VALUE;
		
		for(int i=0; i<oStr.length(); i++){
			
			for(int j=i+cArr.length-1; j<oStr.length(); j++){
				
				String sStr = oStr.substring(i, j+1);
				
				if(containAll(sStr, cArr)){
					
					if(sStr.length()<min){
						subStr = sStr;
						min = sStr.length();
					}
					
					break;
				}
			}
		}
		
		System.out.println(subStr+": "+min);
	}

	public static boolean containAll(String str, char[] cArr){
		
		boolean containAll = true;
		Set<Character> cSet = new HashSet<Character>();
		for(int i=0; i<str.length(); i++){
			cSet.add(str.charAt(i));
		}
		
		for(int j=0; j<cArr.length; j++){
			
			if(!cSet.contains(cArr[j])) return false;
			
		}
		
		return containAll;
	}
}

- yankeson2013 January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*I'm sure this can be optimized further but I'm pasting it for others to get ideas from
The idea here is finding segments in the master string that contain all the characters of the alphabet string(to remove) and then shrinking the master string 1 character at a time*/

class Program
{
static void Main(string[] args)
{
String str = "aabbccba";
String ab = "abc";
StringBuilder sbr = new StringBuilder(str);

//Console.WriteLine(str.Substring(0));

for (int i = 0; i < sbr.Length; i++)
{
FindSubstring(str.Substring(i), ab);
FindSubstring(str.Substring(0, str.Length - i),ab);
}
//FindSubstring(str, ab);
//sbr.Remove(1, 1);
Console.WriteLine("{0}", sbr.ToString());
Console.ReadLine();
}
public static void FindSubstring(String str, String ab)
{
StringBuilder sbr = new StringBuilder(str);
StringBuilder abSbr = new StringBuilder(ab);
int wordStart = 0;
for(int i = 0; i < sbr.Length; i++)
{
for(int x = 0;x<abSbr.Length;x++)
{
char iChar = sbr[i];
char xChar = abSbr[x];
if (iChar==xChar)
{
abSbr.Remove(x, 1);
break;
}
}
if (abSbr.Length == 0)
{
Console.WriteLine(sbr.ToString(wordStart, i - wordStart+1));
abSbr = new StringBuilder(ab);
wordStart = i;
}

}
}
}

- waged7 January 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Steps
1)get unique set of characters, using hash or simple arr[26]
2) Suppose N is the length of unique character set. Find sum1 of the unique char set, assuming a=1, b=2...so on.
3)Now , pick every N length set from input, get its sum2, and compare it with unique set sum1. If sum1!=sum2 , sum2=sum2-input[i]+input[i+N].. and proceed like a moving window.
4)if sum1==sum2, use an utility to compare if the two strings are anagram.
continue, till i==strlen(input)-N+1 or you find the answer.

- vivek January 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my solution.
I think it is O(n) time and O(n) space, but feedback is appreciated.

//Find shortest string with all chars in alphabet
//
//For BigO notation, these values are used
//a = length of alphabet
//b = length of input string
//c = number of alphabet letters in input string.  max is 'b' if only using alphabet chars
//
//Time
//O(a) + O(b * a) + O(a) + O(c * a) + O(a)
//a is fixed 1 to 26 for alphabet (or upper end of 256 if using entire ASCII char set)
//b is 1...n
//c is count of a in b, with upper bound of b, so 1...n
//
//= O(26) + O(n * 26) + O(26) + O(n * 26) + O(26)
//= O(2 (n * 26))
//= O(n)
//
//Space
//O(a) Hash table for alphabet
//O(c * a) Hash table for each alphabet letter in input string
//= O(26) + O(n * 26)
//= O(n)
public static string FindShortestStringWithAlphabet(string input, string alphabet)
{


    //Sample Input
    //  ADOBECODEBANC       <- Input string
    //  0123456789111       <- Input index
    //            012
    //
    //  ABC                 <- Input Alphabet

    //  A   0, 10           <- Index values of A, B, C in input string
    //  B   3, 9
    //  C   5, 12
            

    //Find minimum distance between A, B, C
    //
    // For each character in the alphabet, we need to find the nearest char for every other item in the alphabet
    // Then we find the difference between the minimum and maximum index for each item in the alphabet
    //
    // For example, the index of the alphabet input chars are below, along with the nearest A, B, C characters
    //
    //  0   3   5   9   10  12
    //  A   B   C   B   A   C
    //  |
    //  A   nearest B = 3 (index)
    //      nearest C = 5 (index)
    //      current A = 0
    //      total = 5-0 = 5     <-- Max(A, B, C) = Max (0, 3, 5) = 5
    //                              Min(A, B, C) = Min(0, 3, 5) = 0
    //                              = Abs(0 - 5) = 5
    //      |
    //      B   nearest A = 0
    //          nearest C = 5
    //          current B = 3
    //          total = 5-0 = 5
    //
    //          |
    //          C   nearest A = 0, 10
    //              nearest B = 3
    //              current C = 5
    //              total = 0 -> 3 -> 5 = 5 || 3 -> 5 -> 10 = 7 --> 5
    //
    //              |
    //              B  nearest A = 10
    //                 nearest C = 12
    //                 current B = 9
    //                 total = 9 - 12 = 3                           <--- Solution
    //
    //                  |              
    //                  A   nearest B = 9
    //                      nearest C = 12
    //                      current A = 10
    //                      total = 9 - 12 = 3                      <--- Solution  All 3 are the solution since they are different letters of the alphabet
    //
    //                      |
    //                      C   nearest A = 10
    //                          nearest B = 9
    //                          current C = 12
    //                          total = 9 - 12 = 3                  <--- Solution
    //
    //  Minimum substring length = 3
    //  Starting = 9
    //  Ending = 12
    //  return: BANC

    //charMap stores the index of the items in the alphabet
    Dictionary<int, Item> charMap = new Dictionary<int, Item>();

    //alphabetMap stores the characters in the alphabet for O(1) lookup to find if a character is in the alphabet
    //It also stores the last index of the character when scanning the input left to right or right to left
    Dictionary<char, int> alphabetMap = new Dictionary<char, int>();

    //charMapStack stores the order we find the items in the input so we can re-process them in reverse to find the closest
    //character that may appear after the character.  When processing left to right, we scan all elements.  But when we scan
    //right to left, we only have to look at alphabet elements, so we only have to look at the items in the stack
    Stack<int> charMapStack = new Stack<int>();


    // O(a)
    //Initalize the alphabetMap and set chars to -1 indicating no values have been seen
    for (int i = 0; i < alphabet.Length; i++)
    {
        if (alphabetMap.ContainsKey((alphabet[i])))
            continue;
        alphabetMap.Add(alphabet[i], -1);
    }

            
    //Itterate over the input from left to right
    //If the character is in the alphabet
    //  1.  add this index position to the charMap hash
    //  2.  set the alphabetMap last seen location for this character as the current index
    //  3.  copy the last location for each character into the charMap.nearestChar hash map
    //  4.  push the current index number onto the charMapStack for the return trip in processing right to left
    //      we use this so we don't have to process every character on the return trip.  we only have to process
    //      those that are in the alphabet

    //O(b)
    for (int x = 0; x < input.Length; x++)
    {
        if (alphabetMap.ContainsKey(input[x]))
        {
            charMap.Add(x, new Item(input[x], x));
            alphabetMap[input[x]] = x; //set this char as nearest

            //O(a)
            foreach (var i in alphabetMap.Keys)
            {
                //Add all keys, even if it is -1
                charMap[x].nearestChar.Add(i, alphabetMap[i]);
            }

            charMapStack.Push(x);
        }
    }
            
    //First pass is complete and the charMap.nearestChar is populated with the nearest character that occured before that
    //value in the index.  The next step is to go from right to left and populate the nearest characters going this direction
            
    //reset alphabetMap to -1 for return trip
    alphabetMap = new Dictionary<char, int>();
    //O(a)
    for (int i = 0; i < alphabet.Length; i++)
    {
        if (alphabetMap.ContainsKey((alphabet[i])))
            continue;
        alphabetMap.Add(alphabet[i], -1);
    }

    //Store solution index as minIndex
    int minIndex = -1;

    //O(c)
    //Pop an item off the stack and process it until the stack is empty
    while (charMapStack.Count > 0)
    {
        //x is the key value inside charMap.  It is not the index of the value in the input string unless
        //the input string only contains characters from the alphabet
        int x = charMapStack.Pop();
        char c = charMap[x].C;
        int index = charMap[x].Index;   //index is the actual index value inside the input string

        //Initialize charMap
        charMap[x].Size = 0;        //stores the final size (max index - min index)
        charMap[x].MinChar = index; //init minChar to current index
        charMap[x].MaxChar = index; //init maxChar to current index

        //update alphabetMap with current character and index position
        alphabetMap[c] = index;

        //O(a)
        foreach (char v in alphabetMap.Keys)
        {
            //Check to see if we have a value in the map
            if (alphabetMap.ContainsKey(v) && alphabetMap[v] != -1)
            {
                //if our current nearest is -1, or the new value is < current value, update it
                if (charMap[x].nearestChar[v] == -1 ||
                    alphabetMap[v] < charMap[x].nearestChar[v])
                {
                    charMap[x].nearestChar[v] = alphabetMap[v];
                }
            }

            //Check to see if this character is still -1
            //If so, then this alphabet character was not found in the forward or reverse
            //processing of the input, so the character does not exist.
            //Return empty string for failure
            if (charMap[x].nearestChar[v] == -1)
            {
                return string.Empty;
            }

            //At this point charMap.nearestChar[v] has been processed forwards and backwards and contains the closest
            //character for character 'v'
            //So, check to see if its index is the Min or Max for the nearest alphabet characters
            charMap[x].MinChar = Math.Min(charMap[x].MinChar, charMap[x].nearestChar[v]);
            charMap[x].MaxChar = Math.Max(charMap[x].MaxChar, charMap[x].nearestChar[v]);
        }

        //All chracters have been processed forwards and backwards and the Min and Max character is know
        //We can now calculate the size of the window using the Min and Max values
        charMap[x].Size = charMap[x].MaxChar - charMap[x].MinChar;

        //Check to see if we found a new minimum
        if (minIndex < 0)
            minIndex = x;
        else if (charMap[x].Size < charMap[minIndex].Size)
            minIndex = x;
    }
            
    //Finally find the min and max indexes in the solution set.
    int start = int.MaxValue;
    int end = int.MinValue;
    //O(a)
    foreach (var key in charMap[minIndex].nearestChar.Keys)
    {
        start = Math.Min(start, charMap[minIndex].nearestChar[key]);
        end = Math.Max(end, charMap[minIndex].nearestChar[key]);
    }

    //Create substring using min and max index values
    string ret = input.Substring(start, end-start+1);

    return ret;
}


public class Item
{
    public char C { get; set; }
    public int Index { get; set; }
        
    public Dictionary<char, int> nearestChar { get; set; }

    public int MinChar { get; set; }
    public int MaxChar { get; set; }
    public int Size { get; set; }


    public Item(char c, int index)
    {
        C = c;
        Index = index;
        nearestChar = new Dictionary<char, int>();
    }
        
}

- lx January 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Sliding window concept
Slide a window over the string

abcbbad-->[WINDOW]-->abbbcaa

we build an array containing letters found in the window
store window start, end index in $windowStart and $windowEnd


If our window contain $minAlphabet contained in aLetterFound! Fabulous...
increase windowStart... if we have the same letter as previously (we have a shorter string)... drop the letter... 
increase windowEnd to get the missing letter
*/

$inputString="aabbccba";
$minAlphabet = ['a','b','c'];

$string = getShortestSubstring($inputString,$minAlphabet);
echo "Shortest string :".$string.PHP_EOL;


function getShortestSubstring($input,$minAlphabet)
{
	$aLetterFound = [];//array containing found letters
	$minSize = false;//the smallest substring
	$windowStart = 0;//Window position
	$windowEnd = 0;
	$len = strlen($input);//string length
	$bestString="";//best string found

	//termination condition
	while($windowStart<$len)
	{
		//index are the same... ok increase window size
		if($windowStart==$windowEnd)
		{
			if($windowEnd<$len-1)
				$windowEnd++;			
		}

		$currentLetterStart = $input[$windowStart];
		$currentLetterEnd = $input[$windowEnd];

		//same letter for start and end.... found letter unchanged... 
		//increase start index
		if($currentLetterStart==$currentLetterEnd){
			$windowStart++;
			continue;
		}

		//Ok, we have found a new letter (start of the window)
		if(!array_key_exists($currentLetterStart,$aLetterFound))
		{
			$aLetterFound[$currentLetterStart]=$windowStart;
		}
		//Ok, we have found a new letter (end of the window)
		if(!array_key_exists($currentLetterEnd,$aLetterFound))
		{
			$aLetterFound[$currentLetterEnd]=$windowEnd;
		}

		//Wo oh ! We have everything 
		if(count($aLetterFound) == count($minAlphabet))
		{
			//first substring found or we find an another...
			if($minSize===false || ($windowEnd-$windowStart)<$minSize){
				$minSize = $windowEnd-$windowStart;
				$bestString = substr($input,$windowStart,$minSize+1);
		
			}
			//drop the letter from start and shift our start window position
			unset($aLetterFound[$currentLetterStart]);
			$windowStart++;
			continue;
		}
		
		//We have nothing

		//at the end of our string => slide our window : start index
		if($windowEnd==$len-1)
			$windowStart++;

		//slide our window : end index
		if($windowEnd<$len-1)
			$windowEnd++;
			
			
	}
	return $bestString;
}

- th3R3b3l January 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a java solution.

public static void main(String[] args)
	{
		String problem =  "aabbczxcbbca";
		String given = "abc";
		boolean answer = false;
		
		ArrayList<Integer> indexes = new ArrayList();
		int count = given.length();
		
		for(int i = 0; i < problem.length() ; i++)
		{
			String c = Character.toString(problem.charAt(i));
			System.out.println("Now comparing : " + c);
			if(given.contains(c))
			{
				if(indexes.contains(given.indexOf(c)))
				{
					indexes.clear();
					count = given.length();
					System.out.println("**CLEARING INDEXES (top)**");
				}
				indexes.add(given.indexOf(c));
				System.out.println("Adding to indexes: " + given.indexOf(c));
				count--;
				if(count == 0)
				{
					answer = true;
					break;
				}
			}
			else
			{
				indexes.clear();
				System.out.println("**CLEARING INDEXES**");
				count = given.length();
			}
		}
		
		
			System.out.println(answer);
		
	}

- Anonymous February 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static String shortestSubstring(String input, char[] alphabet) {
    Set<Character> usedChars = new HashSet<>();
    boolean hasSubstringFound = false;

    int start = 0, end = input.length();
    for (int i = 0; i < input.length(); i++) {

      for (; i < input.length() - 1 && input.charAt(i) == input.charAt(i + 1); i++) {
      }

      int j = i;
      for (; usedChars.size() < alphabet.length && j < input.length(); j++) {
        char current = input.charAt(j);
        usedChars.add(current);
      }
      if (usedChars.size() == alphabet.length && end - start > j - i) {
        hasSubstringFound = true;
        start = i;
        end = j;
      }
      usedChars.clear();
    }

    return hasSubstringFound ? input.substring(start, end) : null;
  }

- Mike L February 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int main() {
  string in, sub;
  cin >> in >> sub;
  unordered_map<char, int> char_count;
  queue<char> char_order;
  unordered_set<char> chars;
  for (int i = 0; i < sub.size(); ++i) chars.insert(sub[i]);
  int min_l = in.size();
  int start_pos = 0;
  for (int i = 0; i < in.size(); ++i) {
    const char ch = in[i];
    char_order.push(ch);
    auto it = char_count.find(ch);
    if (it != char_count.end()) {
      it->second++;
    } else if (chars.count(ch) > 0) {
      char_count[ch] = 1;
    }
    if (char_count.size() == chars.size()) {
      while (char_count.size() == chars.size()) {
        char top = char_order.front();
        char_order.pop();
        auto it = char_count.find(top);
        if (it != char_count.end()) {
          it->second--;
          if (it->second == 0) {
            char_count.erase(it);
          }
        }
      }
      if (min_l > char_order.size() + 1) {
        min_l = char_order.size() + 1;
        start_pos = i - min_l + 1;
      }
    }
  }
  cout << in.substr(start_pos, min_l) << endl;
  return 0;
}

- Naughty February 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String printString(String input, String alphabet)
{
String result = "";
int length = alphabet.length();

// ^ matches the start of the string
// (?: open a non capturing group
// ([alphabets]) The characters that are allowed the found char is captured in group 1
// (?!.*\\1) That character is matched only if it does not occur once more
// ){length} Defines the amount of characters
// $ matches the end of the string

String REGEX = "^(?:([" +alphabet + "])(?!.*\\1)){" + (length) +"}$";
Pattern p = Pattern.compile(REGEX);
int inputLength = input.length();
for(int i = 0 ; i < (inputLength - length + 2);i++)
{
result = input.substring(i, i+length);
if(p.matcher(result).find())
{
return result;
}
}
return result;
}

- Dhara Padia February 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution

def shortest_substring(inp, alphabet):
    start, end = 0, 1
    alphabet = set(alphabet)
    result = None
    while start < len(inp) and end < len(inp):
        current = inp[start:end]
        if set(current).issuperset(alphabet):
            if result is None:
                result = current
            else:
                result = min([result, current], key=len)
            start += 1
        else:
            end += 1
    return result

- yilmazhuseyin February 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution using 2 histograms with start and end pointer O(n+c)

sti = raw_input().strip()
dct = raw_input().strip()

h_dct = dict()
h_sti = dict()

# creating histogram for the dictionary (to compare)
for i in dct:
    h_dct[i] = 1 if i not in h_dct else h_dct[i]+1

# compare two histograms to validate using the dictionary as base
def checkwindow():
    global h_dct, h_sti
    for i in h_dct.keys():
        if i not in h_sti:
            return False
        if(h_sti[i]<h_dct[i]):
            return False
    return True

def histog_add(elem,v):
    global h_dct, h_sti
    if(elem not in h_dct):
        return
    if(v>0):
        h_sti[elem] = 1 if elem not in h_sti else h_sti[elem]+1
    else:
        if(elem in h_sti):
            h_sti[elem]-=1


i=0 # start pointer
j=0 # end pointer
lstr = ""
while( i < len(sti) ):    
    if(checkwindow()):
        lstr = sti[i:j]
        # move i pointer to the right
        histog_add(sti[i],-1)
        i+=1
        continue
    
    if(j<len(sti)): # move j pointer to the right
        histog_add(sti[j],1)
        j+=1
    else: # move i pointer to the right
        histog_add(sti[i],-1)
        i+=1
    print("->" + sti[i:j])


print lstr

- carlos de oliveira February 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find the occurrences of each character in the main string
2. Find the shortest path, between the occurrences, it will be the shortest subsequence/ substring.

- Raj February 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class SubStringLetters {
	public static void main(String[] args) {
		System.out.println(findSubString("aabbccba"));
		System.out.println(findSubString("abbcac"));
	}

	public static String findSubString(String input) {
		String result = input;
		Set<Character> set = new HashSet<Character>();
		char[] charArr = input.toCharArray();
		for (int i = 0; i < charArr.length; i++) {
			if (!set.contains(charArr[i])) {
				set.add(new Character(charArr[i]));
			}
		}
		int size = set.size();
		Character previous = null;
		for (int i = 0; i < charArr.length; i++) {
			Character current = new Character(charArr[i]);
			if (previous == null) {
				previous = current;
			} else if (!current.equals(previous)) {
				String subString = findSubStringFromI(charArr, i - 1, size);
				if (subString != null && subString.length() < result.length()) {
					result = subString;
				}
			}
		}
		return result;
	}

	public static String findSubStringFromI(char[] charArr, int k, int setSize) {
		StringBuilder sb = new StringBuilder("");
		Set<Character> set = new HashSet<Character>();
		for (int i = k; i < charArr.length; i++) {
			Character c = new Character(charArr[i]);
			if (set.size() < setSize) {
				set.add(c);
				sb.append(charArr[i]);
			} else {
				break;
			}
		}
		if (set.size() < setSize) {
			return null;
		}
		return sb.toString();
	}
}

class Occupied {
	int from;
	int to;

	Occupied(int from, int to) {
		this.from = from;
		this.to = to;
	}
}

- Mei Li February 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This approach applies run length encoding first and then seeks for all abc combinations in the end and stores the one which has minimal length.

s="aabbccba"

def runl(s):
	news=""
	count=1
	i=1
	while i<len(s):
		if s[i]==s[i-1]:
			count+=1
		else:
			news+=str(count)+s[i-1]
			count=1
		i+=1
	news+=str(count)+s[i-1]
	return news

def getstr(s):
	result=s
	i=1
	while i+4<len(s):
		temp=s[i]+s[i+2]+s[i+4]
		if temp in ["abc","acb","bac","bca","cab","cba"]:
			string=s[i]+s[i+2]*int(s[i+1])+s[i+4]
			if len(string)<len(result):
				result=string
		i+=2		
	return result
	
print getstr(runl(s))

- sharadboni February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String matchingString(String input, String alphabet) {
	if (TextUtil.isEmpty(input) || TextUtil.isEmpty(alphabet)) return “”;

	HashSet<String> hs = new HashSet<>();

	for (int i = 0; i < input.length(); i++) {
		if (hs.contains(input.charAt(i))) {
			hs = new HashSet<>();
		}

		hs.add(input.charAt(i));

		if (hm.size() == alphabet.length()) {
			return input.substring(i - alphabet.length(), alphabet.length());
		}
	}
}

- dora March 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Manjunath April 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. We can capture the indexes of each character in the pattern
2. then find the range with minimum difference between start and end of the range
- pick the first occurrence of each character pick the min and max
- drop the min and pick the next element from the queue it was dropped

repeat 2 until one of the source exhausts
3. return the range with minimum difference.

- Raj April 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void min_substring(string str, string mat) {
    unordered_set<char> os;
    for(int i = 0; i < mat.length(); i++) {
        os.insert(mat[i]);
    }
    stack<pair<int, string> > st;
    set<char> count_set;
    // now use the sliding window
    int start = 0;
    for(int i = 0`; i <str.length(); i++) {
        if(os.find(str[i]) != os.end()) {
            // match
            if (i != start && str[i] == str[start]) {
                // just expand the 
                start++;
            } else {
                // see it it completes the search characters
                if(count_set.find(str[i]) == count_set.end()) {
                    // new character
                    count_set.insert(str[i]);
                    if(count_set.size() == mat.length()) {
                        // found all the matching
                        if (st.top().first > (i-start+1)) {
                            st.pop();
                            st.push(pair<int, string>((i-start+1),
                                str.substr(start, i+1)));
                        }
                        count_set.erase(str[start]);
                        start++;
                        
                    }
                }// if already seen character, just increament i, keep starts
                // as it is
            }
        }
    }
    
    if(!st.empty()) {
        cout << "min string is " << st.top().second << " of length " << st.top().first;
    }
}

- ali.kheam July 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args)
    {
        String inputString = "aabbccba";
        char[] searchedCharacters = {'a','b','c'};
        int startingSize = searchedCharacters.length;
        int maxLength = inputString.length();
        int searchSize = startingSize;
        String tempStr = "";
        boolean found;


        while (startingSize <= maxLength)
        {
            for (int i = 0; i <= maxLength-searchSize; i++, startingSize++)
            {
                tempStr = inputString.substring(i, startingSize);
                found = true;
                for (char searchedChar:searchedCharacters)
                {
                    if (tempStr.indexOf(searchedChar) == -1)
                    {
                        found = false;
                        break;
                    }

                }
                if (found)
                {
                    System.out.println(tempStr);
                    return;
                }
            }

        }


    }

- Shalini October 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args)
    {
        String inputString = "aabbccba";
        char[] searchedCharacters = {'a','b','c'};
        int startingSize = searchedCharacters.length;
        int maxLength = inputString.length();
        int searchSize = startingSize;
        String tempStr = "";
        boolean found;


        while (startingSize <= maxLength)
        {
            for (int i = 0; i <= maxLength-searchSize; i++, startingSize++)
            {
                tempStr = inputString.substring(i, startingSize);
                found = true;
                for (char searchedChar:searchedCharacters)
                {
                    if (tempStr.indexOf(searchedChar) == -1)
                    {
                        found = false;
                        break;
                    }

                }
                if (found)
                {
                    System.out.println(tempStr);
                    return;
                }
            }

        }


    }

- Shalini October 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Lab {
static String s1 ="abc";
static String result="";
public static void main(String []args){
String s="abbcac";

int l=s1.length();
int i=0;
boolean b;
while(l<=s.length()){
String ss=s.substring(i, l);
b= check(ss);
i++;
l++;
}
System.out.println("Hello check"+"\t"+result);
}
public static boolean check(String s){
char ch[] =s1.toCharArray();
char ch2[] =s.toCharArray();
int count=0;
System.out.println(s);
boolean b=false;
for(int i=0;i<ch2.length;i++){
b=false;
for(int j=0;j<ch2.length;j++){
if(ch[i]==ch2[j]){
b=true;
}
}
if(b){
count++;
}
}
if(count==s.length()){
result=s;
}
return false;
}
}

- Anonymous November 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Lab {
static String s1 ="abc";
static String result="";
public static void main(String []args){
String s="abbcac";

int l=s1.length();
int i=0;
boolean b;
while(l<=s.length()){
String ss=s.substring(i, l);
b= check(ss);
i++;
l++;
}
System.out.println("Hello check"+"\t"+result);
}
public static boolean check(String s){
char ch[] =s1.toCharArray();
char ch2[] =s.toCharArray();
int count=0;
System.out.println(s);
boolean b=false;
for(int i=0;i<ch2.length;i++){
b=false;
for(int j=0;j<ch2.length;j++){
if(ch[i]==ch2[j]){
b=true;
}
}
if(b){
count++;
}
}
if(count==s.length()){
result=s;
}
return false;
}
}

- Saurabh Bind November 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

O(n), no extra space.

public static String shortest(String input) {
	if (input == "" || input == null) return "";

	int sequenceStart = -1;

	int minStart = -1;
	int minLength = Integer.MAX_VALUE;

	for (int current = 1; current < input.length(); current++) {
		if (input.charAt(current - 1) != input.charAt(current)) {
			if (sequenceStart == -1) {
				sequenceStart = current - 1;
			} else {
				int len = current - sequenceStart + 1;
				if (len < minLength && input.charAt(current) != input.charAt(sequenceStart)) {
					minStart = sequenceStart;
					minLength = len;
				}

				sequenceStart = -1;
				current--;
			}
		}
	}

	if (minStart == -1) 
		return "";
	else
		return input.substring(minStart, minStart + minLength);

}

- rbd January 26, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More