Salesforce Interview Question: Find the first index of the s... | Glassdoor

Interview Question

Software Engineer Interview San Francisco, CA

Find the first index of the substring. Condition: Do not

  use java library function or regular expressions. And measure the performance of your implementation with the standard java library function. Examples: String 1: “abcdefg” String 2: “bcd” Should return 1 String 1: “abcdefg” String 2: “x” Should return -1
Answer

Interview Answer

14 Answers

1

public class ComputeSubString {

    String s1 = "abqqqqqqqbcdef";
    String s2 = "xbcd";
    boolean found = true;
    static int pos = -1;

    public static void main(String s[]) {
        new ComputeSubString().start();
        System.out.println(pos);
    }

    private void start() {
        for (int i = 0; i s1.length() || s1.charAt(index + i) != s2.charAt(i)) {
                return false;
            }
        }
        return true;

    }
}

Srikanth Puppala on May 22, 2012
1

Is this too naive? Why not KMP?

Ziming on May 27, 2012
2

Here's a more elegant solution:

public static void main(String[] args) {

        String m = "internet";
        String t = "net";
        int i, j = 0;

        for (i = 0; i < m.length() && j < t.length(); ++i)
        {
            if (m.charAt(i) == t.charAt(j))
            {
                ++j;
            }
            else
            {
                j = 0;
            }
        }

        if (j == t.length())
        {
            System.out.println(i+1-t.length());
        }

    }

fireHydrant on Oct 2, 2012
1

@fireHydrant:

In your case there will be a small logical error..
You code does not work in case of two string "internnet" and "net"
Since in your code you keep on checking next character if there is a match. Bur what if the string is not a complete match? It never checks first value again..

Example:

internnet and net:
when it comes to nnet part:

Your codes output:
i=5
m = n
t = n

i=6 // here is the catch
m = n
t = e

i=7
m = e
t = n

i=8
m = t
t = n

 I modified your code and the correct code is:

    public static void main(String[] args) {

        String m = "internnet";
        String t = "net";
        int i, j = 0;

        for (i = 0; i 0){
                j=0;
                i--;
            }
            else
            {

                j = 0;
                //i--;
            }

        }

        if (j == t.length())
        {
            System.out.println("Yes.. A match "+(i-t.length()));
        }

    }

Hope this clears doubt..

SAM on Oct 12, 2012
0

public static int indexOf(String str1, String str2)
    {
        for (int i = 0; i <= str1.length() - str2.length(); i++)
        {
            if (equals(str1, str2, i, 0))
            {
                return i;
            }
        }
        return -1;
    }

    public static boolean equals(String str1, String str2, int idx1, int idx2)
    {
        while (idx1 < str1.length() && idx2 < str2.length() && str1.charAt(idx1++) == str2.charAt(idx2++))
        {

        }
        return idx2 == str2.length();
    }

@rm on Oct 23, 2012
0

Find the answer here:
http://programmingpassionforjava.blogspot.com/2012/10/find-first-index-of-substring.html

Anonymous on Oct 24, 2012
0

static int ReturnFirstOccurance(string mainString, string subString)
        {
            int len = mainString.Length;
            for (int i = 0; i < len; i++)
            {
                if (mainString[i] == subString[0])
                {
                    if (mainString[i+1] == subString[1])
                    {
                        if (mainString[i + 1] == subString[1])
                        {
                            return i;
                        }
                    }
                }
            }
            return -1;
        }

Anonymous on Jan 10, 2013
0

for (i=0; i< s.length - s1.length; i++) {

    for (j=0; j<s1.length; j++) {
        if (s1.charAt(j) != s.charAt[i+j]) {
            break;
        }

        if (j == s1.length -1) {
            return i;
        }
    }
}
return -1;

Tommy on Feb 17, 2013
0

This one is neater:

for (i=0; i< s.length - s1.length; i++) {
    j = 0;
    while (j < s1.length && s1.charAt(j) == s.charAt[i+j]) j++;
    if (j == s1.length) return i;
}
return -1;

Tommy on Feb 17, 2013

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

0

this can be done either by recursion or by for loop.

for ForLoop:

public static int indexOf(String str, String subStr) {
        if (str == null || str.length() == 0 ||
                subStr == null || subStr.length() == 0) {
            return -1;
        }

        int i = 0, j = 0;
        while (i 0) {
                    i -= j;
                    j = 0;
                }
                ++i;
            }
        }

        if (j == subStr.length()) {
            return i - j;
        }

        return -1;
    }

the problem with the other implementation are that they will miss the following:
indexOf("internnntood", "nnt");

ham on Apr 19, 2014
0

public boolean strStr(String haystack, String needle) {
        char[] big = haystack.toCharArray();
        char[] small = needle.toCharArray();
        if (big.length == 0 || small.length == 0 || big.length < small.length) { return false; }
        char firstChar = small[0];
        //find the first character of needle in the haystack by doing linear scan
        for (int j = 0; j < big.length; j++) {
            if (big[j] == firstChar) {
                //check if remaining consecutive characters match continuously
                if (matchRest(big, small, j + 1)) {
                    System.out.println(j); // matched at position j
                    return true;
                }
            }
        }
        // sorry no match
        return false;
    }

    private boolean matchRest(char[] big, char[] small, int sBig) {
        int i, j;
        // always start from position 1 of needle since position 0 is guranteed to be matched
        // start with position passed for haystack and make sure to stop before either buffers runs out
        for (i = 1, j = sBig; (i < small.length) && (j < big.length); i++, j++) {
            if (big[j] != small[i]) { return false; }
        }
        // if tail of haystack has a subset of needle then its not a match
        if (j == big.length && i < small.length) {
            return false;
        } else {
            return true;
        }
    }

hivejin on Mar 14, 2016
0

int strStr(String haystack, String needle) {
    int l1 = haystack.length(), l2 = needle.length();
    if(l1 < l2)
        return -1;
    else if(l2 == 0)
        return 0;
    int threshold = l1 - l2
    for(int i = 0; i < threshold; i++) {
        if(haystack.substring(i, i + l2).equals(needle)) {
            return i;
        }
    }
    return -1;
}

hivejin on Mar 19, 2016
0

C# solution:

using System;
namespace StringPractice
{
    class Program
    {
        static void Main(string[] args) {
            //string a = "internenenenenet";
            //string b = "net";
            //string a = "abqqqqqqqbcdef";
            //string b = "xbcd";
            //string a = "internnet";
            //string b = "net";
            string a = "internnntood";
            string b = "nnt";
            Console.WriteLine(findFirstIndexOfSubString(a, b));
        }

        ///
        /// Function returns first index of the substring.
        ///
        /// source string where to search for substring
        /// sub string of superString
        /// starting index of superString, where subString started, otherwise -1
        public static int findFirstIndexOfSubString(string superString, string subString) {
            // Return -1 if either of a or b are null or empty string
            if(string.IsNullOrEmpty(superString) || string.IsNullOrEmpty(subString)) {
                return -1;
            }
            int i = 0, j = 0;
            // Loop through until end of superString.
            while (i<superString.Length) {
                // Track superString index where substring match started.
                int currentStartIndex = i;
                // Now go through comparision between superString and subString until reaches end of subString.
                while (superString[i++] == subString[j++]) {
                    // If matched substrings till end of subString, then return currentStartIndex.
                    if (j == subString.Length) {
                        return currentStartIndex;
                    }
                }
                // Else reset i to 1 + currentStartIndex to move to next start index and reset j back to 0 index.
                i = currentStartIndex+1;
                j = 0;
            }
            // return -1 here we haven't found the match.
            return -1;
        }
    }
}

This was simple question and has very simple solution below. Tried with 4 different strings &amp; works on Oct 21, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.