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

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
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

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

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.