Google Interview Question
Software Engineer / DevelopersCountry: Israel
Interview Type: In-Person
Code is correct. But we do not need two pointers i1 and i2. As both start at 0 and both increment at same time. So i1 and i2 always have same values.
int i1 = 0;
while(i1 < len && i1 < arr[i].length() && arr[0].charAt(i1) == arr[i].charAt(i1)){
i1++;
}
len = i1;
The same idea, more readable code with comments
public static String longestPrefix(String s) {
// get all words
String[] words = s.split(" ");
// initial prefix length is set to the length of the first word
int prefixLength = words[0].length();
// iterate through the remaining words checking the prefix
for(int i = 1; i < words.length; i++) {
// if the length of ith word is less then prefix so far,
// prefix cannot be longer then that
if(prefixLength > words[i].length())
prefixLength = words[i].length();
//check charachters one by one and break on differing charachter
for(int j = 0; j < Math.min(prefixLength, words[i].length()); j++) {
if(words[i].charAt(j) != words[0].charAt(j)) {
prefixLength = j;
break;
}
}
}
return s.substring(0, prefixLength);
}
I would refrain from using string.split() operation and would ask from the interviewer first. Also, interviewer might ask what is the complexity of split operation - which we should be ready with the answer. Also, this uses additional space. Otherwise a good solution.
public class HelloWorld{
public static String findLongestPrefix(String[] words){
String prefix=words[0];
for(int i=1;i<words.length;i++){
if(prefix.length()>words[i].length()) prefix=prefix.substring(0,words[i].length());
for(int j=0;j<prefix.length();j++){
if(prefix.charAt(j)!=words[i].charAt(j)){
prefix=prefix.substring(0,j);
break;
}
}
}
if(prefix.equals("")) return "";
return prefix;
}
public static void main(String []args){
System.out.println("Hello World new");
String[] words={
"akaleeee","akale","akalear","akaleaer","akalemoss"
};
System.out.println(findLongestPrefix(words));
}
}
/**
* K - prefix length
* N - strings count
* time: O(K*N)
* space: O(K)
*/
String findLongestPrefix(String[] arr) {
if (arr == null) {
throw new IllegalArgumentException();
}
if (arr.length == 0) {
return "";
}
StringBuilder prefix = new StringBuilder();
String firstStr = arr[0];
int firstStrLength = firstStr.length();
MAIN:
for (int charIndex = 0; charIndex < firstStrLength; charIndex++) {
char ch = firstStr.charAt(charIndex);
for (int i = 1; i < arr.length; i++) {
String otherStr = arr[i];
if ( otherStr.length() <= charIndex || otherStr.charAt(charIndex) != ch ) {
break MAIN;
}
}
prefix.append(ch);
}
return prefix.toString();
}
# To change this template, choose Tools | Templates
# and open the template in the editor.
# code is implemented in the ruby
class Test
def findSequence(number)
words = number.split(" ")
@@index = 0
for i in 0...words[0].length
for j in 1...words.size
# puts j;
if words[j][i] == words[0][i]
next
else
@@index = i
puts words[0][0,@@index]
return
end
end
end
end
end
@test = Test.new
@test.findSequence("ankifbvh sdcds sd sdcds")
This is brute force and not the best solution. Will post more later ...
public StringBuilder bruteForceLCP (String str) {
StringBuilder sub = new StringBuilder();
String[] words = str.split(" ");
for (String word : words) {
for (int i = 0; i< word.length(); i++) {
if (sub.length() >= word.length()) {
continue;
}
if (sub.length() > 0 && sub.length() > i) {
i = sub.length();
}
String c = word.substring(0, i+1);
boolean isSubstring = true;
for (String wrd : words) {
if (!wrd.startsWith(c)) {
isSubstring = false;
}
}
if (isSubstring) {
System.out.println("Prefix found : " + c);
sub.replace(0, (sub.length()), c);
}
}
}
System.out.println("*****Longest common sub prefix : " + sub);
return sub;
}
Initially assume first word is the longest common prefix. check if each character in the rest of the words is exactly same, if not return the substring of first word.
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0)
return "";
String lcp = strs[0];
for(int i =0; i < lcp.length(); i++)
{
for(int j =1; j <strs.length; j++)
{
if(i >= strs[j].length() || lcp.charAt(i) != strs[j].charAt(i))
return lcp.substring(0,i);
}
}
return lcp;
}
maybe sort it by length first, and start with the shortest and match with next one, find the common part and use it to match with next one and so on...
/// Find the longest sequence of prefix shared by all the words in a string.
/// "abcdef abcdxxx abcdabcdef abcyy" => "abc"
public void FindLongestSequenceOfPrefix(string sentence)
{
string[] array = sentence.Split(' ');
array = array.OrderBy(s => s).ToArray();
Dictionary<string, int> hash = new Dictionary<string, int>();
foreach (var s in array)
{
var str1 = s;
var index = Compare(array, s, 0, 0, ref str1);
if (!hash.ContainsKey(str1))
{
hash.Add(str1, index - 1);
}
}
}
int Compare(string[] array, string s, int index, int prevCount, ref string str1)
{
if (index >= s.Length)
return prevCount;
int count1 = 0;
foreach (var str in array)
{
if (str[index] == s[index])
{
count1++;
}
}
if (count1 < prevCount)
{
str1 = s.Substring(0, index);
return prevCount;
}
else
{
prevCount = count1;
return Compare(array, s, index + 1, prevCount, ref str1);
}
}
string longestCommonPrefix(vector<string> &strs) {
string result;
if(strs.empty()) //这是为空的情况
return result;
if(strs.size()==1) //这是大小为1的情况
return *(strs.begin());
//下面讨论的是至少大小为2的情况
int minLength,i=0;
vector<string>::const_iterator iter=strs.begin();
minLength=(*iter).size();
for(;iter!=strs.end();++iter)
if((*iter).size()<minLength)
minLength=(*iter).size();
while(i<minLength)
{
for(iter=strs.begin();iter!=strs.end()-1;++iter)
{
if(*((*iter).begin()+i)!=*((*(iter+1)).begin()+i))
break;
}
if(iter==strs.end()-1)
{
result+=*((*iter).begin()+i);
i++;
}
else
break;
}
return result;
}
string longestCommonPrefix(vector<string> &strs) {
string result;
if(strs.empty()) //这是为空的情况
return result;
if(strs.size()==1) //这是大小为1的情况
return *(strs.begin());
//下面讨论的是至少大小为2的情况
int minLength,i=0;
vector<string>::const_iterator iter=strs.begin();
minLength=(*iter).size();
for(;iter!=strs.end();++iter)
if((*iter).size()<minLength)
minLength=(*iter).size();
while(i<minLength)
{
for(iter=strs.begin();iter!=strs.end()-1;++iter)
{
if(*((*iter).begin()+i)!=*((*(iter+1)).begin()+i))
break;
}
if(iter==strs.end()-1)
{
result+=*((*iter).begin()+i);
i++;
}
else
break;
}
return result;
}
str1="abcdef abcdxxx abcdabcdef abcyy"
def getstr(str1,str2):
str=""
for i in range(0,len(str1)):
if i<len(str2):
if str1[i]==str2[i]:
str+=str1[i]
else:
break
return str
def func(str1):
str1=str1.split()
str=getstr(str1[0],str1[1])
for i in range(2,len(str1)):
str=getstr(str1[i],str)
return str
print func(str1)
public static string LongestPrefix(string str)
{
string[] arr = str.Split(' ');
string prefix = string.Empty;
string firstWord = arr[0];
for (int j = 0; j < firstWord.Length; j++ )
{
char c = firstWord.ElementAt(j);
bool common = true;
for(int i = 1; i < arr.Length; i++)
{
if(arr[i].ElementAt(j) != c)
{
common = false;
}
}
if (common)
prefix += c;
else
return prefix;
}
return prefix;
}
I am able to think of two solutions :
First one :
* Assume the first word is the common prefix.
* Let there be L pointing to second word and R pointing to last word.
* Let PC hold common prefix. So, its initial value will be the first word.
1. Next, find common prefix between PC and second word AND PC and last word.
2. Take the smallest prefix from above and set this in PC.
3. Increment L and decrment R.
4. Repeat 1 to 3 until L > R
Second one :
* Start scanning for words in sentence, and for each word found, add them to a suffix tree (compressed trie)
* From suffix tree, will get the common prefix.
Test cases :
* Empty sentence
* Sentence with single word or 2 words
* Sentence with significant number of words
* Sentence with no common prefix among words
Approach 1:
Let the words in the sentence be defined as w0, w1, ... , wn. Let prefix (LP) be defined as w0.
For each word wi in w1 ... wn {
LP = common_prefix(LP, wi)
if (LP.isEmpty())
return LP
}
return LP
==================================================
Now it all depends how we calculate common_prefix(). We can use trie to generate a structure once when LP is initialized and use the same data structure to find out the prefix. or we can use two pointers to get the common prefix strings each time in the function.
Approach 2:
This approach is slight modification of the approach 1.
Assuming that the words are delimited by space character, we will not find any words separately and then iterate over words. In fact, we will iterate over sentence and perform common_prefix() operation on the word within the string.
public static String findCommonSuffix(final String sentence) {
if (sentence == null) throw new NullPointerException("String is null");
if (sentence.length() == 0) return "";
// Initialize LP first
StringBuilder LP = new StringBuilder();
for (int i = 0; sentence.charAt(i) != ' '; i++) {
LP.append(sentence.charAt(i));
}
// Move the forward pointer to the next non-space character
int next = LP.length();
while (next < sentence.length()) {
int s = next;
while (s < sentence.length() && sentence.charAt(s) == ' ') s++;
if (s == sentence.length()) return LP.toString();
StringBuilder temp = new StringBuilder();
for (int j = 0; j < LP.length() && s < sentence.length() && sentence.charAt(s) == LP.charAt(j); j++, s++) {
temp.append(LP.charAt(j));
}
LP = null;
LP = temp;
if (LP.length() == 0) return LP.toString();
if (s == sentence.length()) return LP.toString();
while (s < sentence.length() && sentence.charAt(s) != ' ') s++;
next = s;
}
return LP.toString();
}
In Java
public static String longestPrefix(String str){
String[] arr = str.split(" ");
char[] firstStr = arr[0].toCharArray();
for (int i = 0; i < firstStr.length; i++) {
for (int j = 1; j < arr.length; j++) {
if (arr[j].length() <= i || firstStr[i] != arr[j].charAt(i)) {
return arr[0].substring(0, i);
}
}
}
return arr[0];
}
Split into words, then use a recursive approach on the list of words, taking off one letter at a time. First in Python (concise), then in "C" using pointers into the existing word for efficiency.
Python:
import sys
def find_longest_prefix(words):
if any(len(word) == 0 for word in words):
return ''
if all([word[0] == words[0][0] for word in words]):
return words[0][0] + find_longest_prefix([word[1:] for word in words])
return ''
if __name__ == '__main__':
print find_longest_prefix([word for word in sys.argv[1].split(' ') if word])
Same apparcoh in "C" for efficiency, allocating only an array of pointers to identify words, and space for the prefix to be stored.
#include <string>
#include <stdio.h>
#include <stdlib.h>
void find_prefix(char **words, char *prefix)
{
int i;
char *word = words[0];
if (!word[0])
{
return;
}
char prech = word[0];
for (i=0;;i++)
{
if (!words[i])
{
break;
}
if (words[i][0] != prech)
{
return;
}
words[i] = &words[i][1];
}
*prefix = prech;
find_prefix(words, &prefix[1]);
}
int main(int argc, char * argv[])
{
/* Split argv[1] into words, then find longest prefix */
/* First, identify spaces and NULL terminate them, keeeping */
/* an array of pointers to each word's start */
int i=0;
char *start = argv[1];
char *prefix = (char *) malloc(strlen(argv[1]));
/* worst case, need length of string / 2 + 1 pointers */
char **words = (char **)malloc(sizeof(char *) * (strlen(argv[1]) / 2 + 1));
memset(words, 0, sizeof(words[0]) * strlen(argv[1]) / 2 + 1);
words[0] = start;
while (*start++)
{
if (*start == ' ')
{
while (*start == ' ')
{
*start++ = '\0';
}
words[++i] = start;
}
}
prefix[0] = '\0';
find_prefix(words, prefix);
printf("%s\n", prefix);
free(words);
free(prefix);
}
std::string longest_prefix(const std::string& sentence) {
// split sentence into a vector of words...
std::istringstream iss(sentence);
std::vector<std::string> words(std::istream_iterator<std::string>{iss}, {});
unsigned n;
for (n = 0; n < words[0].size(); ++n) {
const char c = words[0][n];
const auto f = [=](const std::string& word) { return word[n] == c; };
// break if c is not the n-th letter of all words...
if (!std::all_of(words.begin(), words.end(), f))
break;
}
return sentence.substr(0, n);
}
public static void main(String[] args) {
System.out.println(new StringPrefix().printPrefix("abcdef abcdxxx abcdabcdef abcyy"));
}
public String printPrefix(String str){
String tempHead;
String[] strList = str.split(" ");
for (int i = 0; i< strList[0].length(); i++)
{
tempHead = strList[0].substring(0, i);
for (String s : strList)
{
int index = s.indexOf(tempHead);
if (index < 0)
{
return tempHead.substring(0, tempHead.length() - 1);
}
}
}
return "";
}
public static void main(String[] args) {
System.out.println(new StringPrefix().printPrefix("abcdef abcdxxx abcdabcdef abcyy"));
}
public String printPrefix(String str){
String tempHead;
String[] strList = str.split(" ");
for (int i = 0; i< strList[0].length(); i++)
{
tempHead = strList[0].substring(0, i);
for (String s : strList)
{
int index = s.indexOf(tempHead);
if (index < 0)
{
return tempHead.substring(0, tempHead.length() - 1);
}
}
}
return "";
}
public static void main(String[] args) {
System.out.println(new StringPrefix().printPrefix("abcdef abcdxxx abcdabcdef abcyy"));
}
public String printPrefix(String str){
String tempHead;
String[] strList = str.split(" ");
for (int i = 0; i< strList[0].length(); i++)
{
tempHead = strList[0].substring(0, i);
for (String s : strList)
{
int index = s.indexOf(tempHead);
if (index < 0)
{
return tempHead.substring(0, tempHead.length() - 1);
}
}
}
return "";
}
pre = ""
for i in range(len(str)):
if(str[i] != ' '):
pre = pre + str[i];
else:
break;
n = i+1
l = i-1;
x = 0;
while (n < len(str)):
print n, x;
if x <= l and str[n] == pre[x] :
x = x+1;
n = n+1;
continue;
else:
l = x-1;
x = 0;
while(n < len(str) and str[n] != ' ' ):
print n , x;
n = n+1;
n=n+1;
print pre[:l+1] , l;
One pass solution...
public class PrefixMatching {
public static void main (String []args) {
String s1 = "ABCDEF";
String s2 = "ABCDEFGH";
String s3 = "ABCDSAD";
String result = "";
int i=0, j=0, k=0;
while (i < s1.length() && j < s2.length() && k < s3.length()) {
if (s1.charAt(i) == s2.charAt(j) && s2.charAt(j) == s3.charAt(k)) {
result += s1.charAt(i);
i++;
j++;
k++;
}
else {
break;
}
}
System.out.println("Result: "+result);
}
}
public class LongestSequence {
public static String longestSequence(String s) {
String[] tokens = s.split(" ");
String prefix = "", next = "";
String reference = tokens[0];
for (int i = 1; i <= reference.length(); i++) {
prefix = reference.substring(0, i);
next = reference.substring(0, i+1);
for (String token : tokens) {
if (i >= token.length() || !token.startsWith(next)) {
return prefix;
}
}
}
return prefix;
}
public static void main(String[] args) {
System.out.println(longestSequence(args[0]));
}
}
Just need 3 ints and one pass over the string (plus iterating over the common prefix m times)
static int GetPrefixLength(string s)
{
int length = -1;
int prefixIndex = 0;
for(int i = 0; i < s.Length && length != 0; i++)
{
if (prefixIndex < length)
{
if (s[i] == s[prefixIndex])
prefixIndex++;
else
length = prefixIndex;
}
if (Char.IsWhiteSpace(s[i]))
{
prefixIndex = 0;
if (length < 0)
length = i;
}
}
return prefixIndex;
}
var input="abcdef abcdxxx abcdabcdef abcyy";
var words=input.split(" ");
words.sort(function(a,b){return a.length-b.length});
var result="";
for (var i=0;i<words[0].length;i++){
for (var j=1;j<words.length;j++){
if (words[0][i]!=words[j][i]){
break;
}
}
if (j==words.length) {
result+=words[0][i];
}
}
console.log(result);
Using regular expressions (O(n)) and exponential growth (log(m) where m<n is the length of the first word and <=n)
brings the total runtime to O(n*log(m))
Can be further optimized by picking the shortest word for m and scanning the words string minus that word.
import re
def max_prefix(words):
if not words:
return None
words = words.lstrip()
num = len(re.findall(r"\w+",words,re.I))
lim=len(words)
i=1
step=1
last_good=0
while i<lim:
if len(re.findall(r"\b"+words[:i],words))==num:
last_good=i
i+=step
step*=2
else:
lim=i
step=1
i=i/2+step
if last_good>0:
return words[:last_good]
else:
return None
package careerCupGoogle;
public class longestPrefixString
{
String[] testCases = {"abcdef abcdxxx abcyy abcdabcdef"};
public static void main(String[] args)
{
longestPrefixString obj = new longestPrefixString();
for(int i=0;i<obj.testCases.length;i++)
{
System.out.println("\nTest Case: "+i);
System.out.println("\tInput : "+obj.testCases[i]);
System.out.println("\n\tResult : "+obj.calculateFunction(obj.testCases[i]));
}
}
private String calculateFunction(String string)
{
int prefix_length = 0;
String[] words = string.split(" ");
int total_words = words.length;
//find the smallest word
String min_word = words[0];
int min_word_len = words[0].length();
for(int i=1;i<words.length;i++)
{
if(words[i].length()<min_word_len)
{
min_word = words[i];
min_word_len = words[i].length();
}
}
System.out.println(min_word);
for(int i=min_word_len-1;i>=0;i++)
{
int words_count_compliance = 0;
for(int j=0;j<words.length;j++)
{
if(min_word.charAt(i)==words[j].charAt(i))
words_count_compliance++;
}
if(words_count_compliance!=total_words)
{
prefix_length = i-1;
break;
}
}
return words[0].substring(0, prefix_length);
}
}
One pass solution.
std::string getLongestPrefix(const std::string& str) {
// Prefix of first word is whole first word.
int prefix = 0;
while (prefix < str.size() && str[prefix] != ' ') {
prefix++;
}
for (int pos = prefix+1; pos < str.size(); pos++) {
int word_prefix = 0;
while (pos < str.size() &&
word_prefix < prefix &&
str[pos] == str[word_prefix]) {
word_prefix++; pos++;
}
prefix = word_prefix;
while (pos < str.size() && str[pos] != ' ')
pos++;
}
return str.substr(0, prefix);
}
It is not needed, but here is a Trie-based working solution in C++.
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
struct Node{
int prefixOf;
Node *children[26];
};
Node *createNode(){
Node *node = new Node;
node->prefixOf = 0;
for (int i = 0; i < 26; i++)
node->children[i] = NULL;
return node;
}
void insert(Node *node, string s){
for (int i = 0; i < (int)s.size(); i++){
node->prefixOf++;
char c = s[i];
int idx = c - 'a';
if (node->children[idx] == NULL)
node->children[idx] = createNode();
node = node->children[idx];
}
}
string longestPrefix = "";
void traverse(Node *node, string s, int N){
if (node->prefixOf == N && (int)s.size() > (int)longestPrefix.size()){
longestPrefix = s;
}
for (int i = 0; i < 26; i++){
if (node->children[i] != NULL)
traverse(node->children[i], s + (char)(i + 'a'), N);
}
}
int main(){
vector<string> words;
int N;
cin >> N;
Node *root = createNode();
string s;
for (int i = 0; i < N; i++){
cin >> s;
insert(root, s);
}
traverse(root, "", N);
cout << longestPrefix << endl;
return 0;
}
#include<iostream>
#define SIZE 4
using namespace std;
int main(){
string str[SIZE] = {"abcdf", "abcdefx", "abcdefcdef", "abcdy"};
string str1 = str[0];
int minCount = 0;
int index = 0;
int prevIndex = 0;
for(int i=0; i< SIZE-1;i++){
string str1 = str[i];
string str2 = str[i+1];
index = 0;
for(int j=0, k=0 ; j<str1.length() && k<str2.length(); j++,k++){
if(str1[j] != str2[k])
break;
//cout<<j<<" ";
if(j>index)
index = j;
}
if(i==0)
prevIndex = index;
if(prevIndex < index)
index = prevIndex;
}
str1 = str[0];
for(int i=0; i<=index; i++)
cout<<str1[i];
cout<<endl;
return 0;
}
- Phoenix July 15, 2014