## Google Interview Question

Country: United States
Interview Type: Phone Interview

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

One approach, if we're assuming multiple accesses to the data (otherwise linear find is best) is to set up a Trie where the node is the start of each subsequent word. In the trie we store indexes that match the current pattern.

That way, for any given pattern we can quickly get the indexes that can match the pattern based on the start of the camelcased words and we perform an individual match on those.

``````private List<String> matchesCCPattern(String[] words, String pattern) {
CCTrieNode root = new CCTrieNode();
for (int i = 0; i < words.length; i++) {
root.insert(words[i], i);
}

List<String> matchingWords = new ArrayList<>();
for (int index : root.indexesForCCPattern(pattern)) {
if (matchesPattern(words[index], pattern)) {
}
}
return matchingWords;
}

private boolean matchesPattern(String word, String pattern) {
int wordIndex = 0, patternIndex = 0;
while (wordIndex < word.length() && patternIndex < pattern.length()) {
char wordChar = word.charAt(wordIndex), patternChar = pattern.charAt(patternIndex);
if (Character.isUpperCase(wordChar) || !Character.isUpperCase(patternChar)) {
if (wordChar != patternChar) return false;
patternIndex++;
}
wordIndex++;
}
return patternIndex == pattern.length();
}

private class CCTrieNode {
private CCTrieNode[] next = new CCTrieNode[26];
private List<Integer> matchesIndex = new ArrayList<>();

private void insert(String words, int index) {
if (words.isEmpty()) return;

CCTrieNode nextWord = next[words.charAt(0) - 'A'];
if (nextWord == null) {
nextWord = new CCTrieNode();
next[words.charAt(0) - 'A'] = nextWord;
}
int nextWordStart = 0;
while (++nextWordStart < words.length()) {
if (Character.isUpperCase(words.charAt(nextWordStart))) break;
}
nextWord.insert(words.substring(nextWordStart), index);
}

private List<Integer> indexesForCCPattern(String pattern) {
if (pattern.isEmpty()) return matchesIndex;
CCTrieNode nextWordNode = next[pattern.charAt(0) - 'A'];
if (nextWordNode == null) {
return Collections.emptyList();
}
int nextWordStart = 0;
while (++nextWordStart < pattern.length()) {
if (Character.isUpperCase(pattern.charAt(nextWordStart))) break;
}
return nextWordNode.indexesForCCPattern(pattern.substring(nextWordStart));
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````package com.gregrode.questions;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

public class CamelCaseNotation
{

private String[] camelCaseWords = { "HelloMars", "HelloWorld", "HelloWorldMars", "HiHo" };

public List<String> testCamelCase(final String pattern)
{
return Arrays.stream(camelCaseWords).filter(word -> isMatchingCamelCase(pattern, word)).collect(Collectors.toList());
}

private Queue<String> toQueue(final String word)
{
final Queue<String> queue = new ArrayDeque<>(word.length());
for (final char ch : word.toCharArray())
{
}
return queue;
}

private boolean isMatchingCamelCase(final String pattern, final String word)
{
if (pattern.length() > word.length())
{
return false;
}

final Queue<String> patternQueue = toQueue(pattern);
final Queue<String> wordQueue = toQueue(word);
String ch = patternQueue.remove();
while (!wordQueue.isEmpty())
{
if (ch.equals(wordQueue.remove()))
{
if (patternQueue.isEmpty())
{
return true;
}
ch = patternQueue.remove();
continue;
}

if (!Character.isUpperCase(ch.charAt(0)))
{
return false;
}
}
return false;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

If at all I understood the question correctly, then here is my answer is in Python language

``````def camelcase(string, substring):
flag = False
arr = []
if substring[-1].islower() or substring[0].islower():
return []
#return [i for i in string for j in substring if j in i]
for i in string:
for j in substring:
if j not in i:
flag = True
break
if flag == False:
arr.append(i)
flag = False
return arr

print camelcase(['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo'], 'HeWorM')``````

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

``````import java.util.*;
public class camelcaseGoogle {
public static void main(String args[]){
ArrayList<String> list = new ArrayList<String>();
ArrayList<String> patternList = new ArrayList<String>();
Scanner sc = new Scanner(System.in);
String pattern = sc.next();int flag =0;
for(int i=0;i<list.size();i++){
String s = list.get(i);
int len =0; int pattern_len = pattern.length()-1; int pat =0;

while((len!=s.length()-1 && pat !=pattern.length()-1) || flag !=1){
if(s.charAt(len)== pattern.charAt(pat)){
len ++;
if(pat<pattern_len){pat ++;}
else break;
}
else if(len!=0 && pat !=0 && len!=s.length()-1) len ++;
else flag =1;
}
if (flag == 0)
{
}
else flag = 0;
}

System.out.println(patternList);

}
}``````

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

``````import java.util.*;
public class camelcaseGoogle {
public static void main(String args[]){
ArrayList<String> list = new ArrayList<String>();
ArrayList<String> patternList = new ArrayList<String>();
Scanner sc = new Scanner(System.in);
String pattern = sc.next();int flag =0;
for(int i=0;i<list.size();i++){
String s = list.get(i);
int len =0; int pattern_len = pattern.length()-1; int pat =0;

while((len!=s.length()-1 && pat !=pattern.length()-1) || flag !=1){
if(s.charAt(len)== pattern.charAt(pat)){
len ++;
if(pat<pattern_len){pat ++;}
else break;
}
else if(len!=0 && pat !=0 && len!=s.length()-1) len ++;
else flag =1;
}
if (flag == 0)
{
}
else flag = 0;
}

System.out.println(patternList);

}
}``````

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

``````import java.util.*;
public class camelcaseGoogle {
public static void main(String args[]){
ArrayList<String> list = new ArrayList<String>();
ArrayList<String> patternList = new ArrayList<String>();
Scanner sc = new Scanner(System.in);
String pattern = sc.next();int flag =0;
for(int i=0;i<list.size();i++){
String s = list.get(i);
int len =0; int pattern_len = pattern.length()-1; int pat =0;

while((len!=s.length()-1 && pat !=pattern.length()-1) || flag !=1){
if(s.charAt(len)== pattern.charAt(pat)){
len ++;
if(pat<pattern_len){pat ++;}
else break;
}
else if(len!=0 && pat !=0 && len!=s.length()-1) len ++;
else flag =1;
}
if (flag == 0)
{
}
else flag = 0;
}

System.out.println(patternList);

}
}``````

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

Assuming a pattern is either valid camel case or an empty string.
Assuming the list is always an array.

Javascript:

``````function getMatchingElements(list, pattern) {
return list.filter(doesMatch(pattern));
}

function doesMatch(pattern) {
return function(element) {
var p = new String(pattern);
while(p.length > 0) {
var nextCapitalIndex = findNextCapitalIndex(p);
var subPattern = p.substr(0, nextCapitalIndex);
if(element.substr(0, subPattern.length) !== subPattern) {
return false;
}
p = p.substr(subPattern.length);
element = element.substr(findNextCapitalIndex(element));
}
return true;
}
}

function findNextCapitalIndex(str) {
for(var i = 1; i < str.length; i++) {
var c = str.charAt(i);
if(c === c.toUpperCase()) {
return i;
}
}
return Number.POSITIVE_INFINITY;
}``````

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

Here are the steps:
1) Loop for each word in the list, create a boolean[] wordsFlags = new boolean[256]
2) set true on those ASCI characters which are present in the word..
3) Get the pattern word and check each char of the pattern word is present in wordsFlag
4) if all characters are present then add that word to the list of matching words..
5) return all the matching words

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

package com.gregrode.questions;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

public class CamelCaseNotation
{

private String[] camelCaseWords = { "HelloMars", "HelloWorld", "HelloWorldMars", "HiHo" };

public List<String> testCamelCase(final String pattern)
{
return Arrays.stream(camelCaseWords).filter(word -> isMatchingCamelCase(pattern, word)).collect(Collectors.toList());
}

private Queue<String> toQueue(final String word)
{
final Queue<String> queue = new ArrayDeque<>(word.length());
for (final char ch : word.toCharArray())
{
}
return queue;
}

private boolean isMatchingCamelCase(final String pattern, final String word)
{
if (pattern.length() > word.length())
{
return false;
}

final Queue<String> patternQueue = toQueue(pattern);
final Queue<String> wordQueue = toQueue(word);
String ch = patternQueue.remove();
while (!wordQueue.isEmpty())
{
if (ch.equals(wordQueue.remove()))
{
if (patternQueue.isEmpty())
{
return true;
}
ch = patternQueue.remove();
continue;
}

if (!Character.isUpperCase(ch.charAt(0)))
{
return false;
}
}
return false;
}
}

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

I used a trie with random pointers and a boolean attribute in each trie node to indicate if it's the start of a word in the initial list.

``````//Time Complexity: Tree building-O(NL) where N is the number of words to be added and L is the length of the longest word. Pattern Querying-O(P) where P is the length of the pattern.

public class Node{

Node[] arr;
ArrayList<String> ls;
boolean isWordStart;

public Node{
arr=new Node[128];
ls=new ArrayList<String>();
isWordStart=false;

for(int i=0;i<pointers.length;i++)
{
pointers[i]=new ArrayList<Node>();
}

}

}

public class Solution
{
Node rt;

public Solution(String[] arr)
{
rt=new Node();

buildTree(arr);

}

private void buildTree(String[] arr)
{
for(String s:arr)
{
rt.arr[(int)s.charAt(0)].isWordStart=true;
}
}

public ArrayList<String>query(String patt)
{
if(patt==null||patt.length()==0||rt==null)
{
return null;
}
return(findMatches(String p));

}

private ArrayList<String> findMatches(String p)
{
Node v=rt.arr[(int)p.charAt(0)]==null||!rt.arr[(int)p.charAt(0)].isWordStart?null:rt.arr[(int)p.charAt(0)];
ArrayList<String> ls=new ArrayList<String>();

for(int i=1;i<p.length();i++)
{
int idx=(int)p.charAt(i);
if(v[idx]==null)
{

v=null;
break;
}
v=v[idx];

}

if(v!=null)
{
}
return ls;

}

private void addToTree(Node r,String str)
{

int lastIdx=str.length();
for(int i=str.length()-1; i>=0;i--)
{
int idx=(int)str.charAt(i);
if(isUpperCase(str.charAt(i)))
{
lastIdx=i;
}
}
}

private boolean isUpperCase(char c)
{
return (int)(c-'A')==0;
}

private void addHelper(Node rt,String s,lastIdx)
{
if(rt.arr[(int)s.charAt(0)]==null)
{
rt.arr[(int)s.charAt(0)]=new Node();
}
Node v=rt.arr[(int)s.charAt(0)];
for(int i=1;i<s.length();i++)
{
int idx=(int)s.charAt(i);
if(v.arr[idx]==null)
{
v.arr[idx]=new Node();

}
if(lastIdx<s.length())
{
v.arr[(int)s.charAt(lastIdx)]=rt.arr[(int)s.charAt(lastIdx)];
}
v=v.arr[idx];

}
if(lastIdx<s.length())
{
v.arr[(int)s.charAt(lastIdx)]=rt.arr[(int)s.charAt(lastIdx)];
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
Can somebody make me understand if {{{HeWorM -> [HelloWorldMars] #contains caps and small letter}}} then why, {{{Ho -> [] # is not returning [HiHo]?????}}} What would happen if we are looking for {{{{{{HeWorMa -> [HelloWorldMars] # or [] empty list? }}} Anyways, if at all I have understood the question correctly, then here is my answer in Python {{{ def camelcase(string, substring): flag = False arr = [] if substring[-1].islower() or substring[0].islower(): return [] #return [i for i in string for j in substring if j in i] for i in string: for j in substring: if j not in i: flag = True break if flag == False: arr.append(i) flag = False return arr print camelcase(['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo'], 'HeWorM') }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote

My understanding is that the search string has to start with the first capital letter.

``````def check_a_string(s, d):

def nextup(d, di):
while d[di].islower():
di += 1
if di >= len(d):
return -1
return di

di = 0

#first char has to match
if s[0] != d[0]:
return False

for c in s[1:]:
if c.isupper():
di = nextup(d, di)
else:
di += 1

if (di == -1) or (c != d[di]):
return False

return True

def check(input, l):
for s in l:
if check_a_string(input, s):
yield s

l = ['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo']
search_strings = ["H", "HW", "Ho", "HeWorM"]

for t in search_strings:
result = list(check(t, l))

print(t)
print(result)``````

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

Why can't the following be the solution?

``````static void Main(string[] args)
{
string[] words = new string[] {"HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"};
string[] patterns = new string[] {"H", "HW", "Ho", "HeWorM" };

foreach (string pattern in patterns)
{
Console.Write(pattern + " -> [");
string comma = string.Empty;
foreach (string match in GetFilteredItems(words, pattern))
{
Console.Write(comma + match);
comma = ", ";
}
Console.WriteLine("]");
}
}

static IEnumerable<string> GetFilteredItems(IEnumerable<string> words, string pattern)
{
return from word in words
where IsMatch(word, pattern, 0, 0)
select word;
}

static bool IsMatch(string word, string pattern, int wordIndex, int patternIndex)
{
if (string.IsNullOrEmpty(pattern) || patternIndex >= pattern.Length)
return true;
if (string.IsNullOrEmpty(word) || wordIndex >= word.Length)
return false;

if (pattern[patternIndex] == word[wordIndex])
return IsMatch(word, pattern, wordIndex + 1, patternIndex + 1);
if (char.IsUpper(word[wordIndex]) || char.IsLower(pattern[patternIndex]))
return false;
return IsMatch(word, pattern, wordIndex + 1, patternIndex);
}``````

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

``````public class prac2 {
public static void main(String[] args) {
List<String> strList = new ArrayList<String>();
String pattern = "HW";
List <String> returnList = findClasses(strList,pattern);
System.out.print(returnList);
}
public static List<String> findClasses(List<String> strList, String pattern){
List<String> resultList = new ArrayList<String> ();
for(String str : strList){
String  substring[] = str.split("[^A-Z]+");
StringBuilder camelCaseStr = new StringBuilder();
for(String s : substring){
camelCaseStr.append(s);
}
if(camelCaseStr.toString().contains(pattern)){
}
}
return resultList;
}
}``````

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

In RUBY

``````def camel_case_notation(str_arr, patt)
if patt.nil? || patt.length == 0 || str_arr.nil? ||
str_arr.length == 0 || is_lower?(patt[0])
return []
end

patt_arr = break_pattern(patt)
result = []
str_arr.each do |str|
if fits_pattern(patt_arr, str)
result << str
end
end

result
end

def is_upper?(char)
char == char.upcase
end

def is_lower? char
char == char.downcase
end

def break_pattern(pattern)
temp = pattern[0]
pattern_arr = []
1.upto(pattern.length-1).each do |i|
if is_upper? pattern[i]
pattern_arr << temp
temp = pattern[i]
elsif is_lower? pattern[i]
temp << pattern[i]
else
raise 'Unknown character'
end
end
pattern_arr << temp
pattern_arr
end

def fits_pattern(pattern_arr, str)
p = 0
s = 0
while p < pattern_arr.length
pattern = pattern_arr[p]
if str.length >= s + pattern.length && pattern == str[s..s+pattern.length-1]
p += 1
s += pattern.length
while (s < str.length && is_lower?(str[s]))
s += 1
end
else
return false
end
end
true
end``````

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

``````def camel_case_notation(str_arr, patt)
if patt.nil? || patt.length == 0 || str_arr.nil? ||
str_arr.length == 0 || is_lower?(patt[0])
return []
end

patt_arr = break_pattern(patt)
result = []
str_arr.each do |str|
if fits_pattern(patt_arr, str)
result << str
end
end

result
end

def is_upper?(char)
char == char.upcase
end

def is_lower? char
char == char.downcase
end

def break_pattern(pattern)
temp = pattern[0]
pattern_arr = []
1.upto(pattern.length-1).each do |i|
if is_upper? pattern[i]
pattern_arr << temp
temp = pattern[i]
elsif is_lower? pattern[i]
temp << pattern[i]
else
raise 'Unknown character'
end
end
pattern_arr << temp
pattern_arr
end

def fits_pattern(pattern_arr, str)
p = 0
s = 0
while p < pattern_arr.length
pattern = pattern_arr[p]
if str.length >= s + pattern.length && pattern == str[s..s+pattern.length-1]
p += 1
s += pattern.length
while (s < str.length && is_lower?(str[s]))
s += 1
end
else
return false
end
end
true
end``````

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

``````#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool checkLowerCase(char& ch){    // ==========> each element of string has type char& (reference)
return (ch >= 'a' && ch <= 'z');
}

bool check(string givenString, string pattern){
int i = 0, j = 0;
while (i < (int)givenString.size() && j < (int)pattern.size()){
if (checkLowerCase(givenString[i]) || checkLowerCase(pattern[j]) || givenString[i] != pattern[j]) return false;
i++; j++;

while (i < (int)givenString.size() && j < (int)pattern.size() && checkLowerCase(givenString[i]) && checkLowerCase(pattern[j]) && givenString[i] == pattern[j]){
i++;j++;
};
if (j == (int)pattern.size()) {
//Last part to check in pattern

return true;
} else if (!checkLowerCase(pattern[j])) {
//Current part is satisfied, go to the next position in givenString
while (checkLowerCase(givenString[i]) && checkLowerCase(givenString[i])) i++;
} else {
return false;
}
}
return false;
}

vector<string> findMatchingStrings(vector<string> stringList, string pattern){
vector<string> res;

for (int i = 0; i < (int)stringList.size(); i++){

if (check(stringList[i], pattern)){
res.push_back(stringList[i]);
}
}
return res;
}

void printVector(vector<string> myVector){
cout << "Size of vector: "  << myVector.size() << endl;

for (int i = 0; i < (int)myVector.size(); i++){
cout << myVector[i] << " ";
}
cout << endl;
}

int main()
{
cout << "Hello World" << endl;
//['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo']

string st1("HelloMars");
string st2("HelloWorld");
string st3("HelloWorldMars");
string st4("Hiho");                                // ==========> init string (giong het ben duoi)

vector<string> stringList {st1, st2, st3, st4};    // ==========> init vector by vector<int> a {1,2,3}

string pt1("H");
string pt2("HW");
string pt3("Ho");
string pt4("HeWorM");
printVector(stringList);
printVector(findMatchingStrings(stringList, pt1));
printVector(findMatchingStrings(stringList, pt2));
printVector(findMatchingStrings(stringList, pt3));
printVector(findMatchingStrings(stringList, pt4));

return 0;
}``````

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

``````#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool checkLowerCase(char& ch){    // ==========> each element of string has type char& (reference)
return (ch >= 'a' && ch <= 'z');
}

bool check(string givenString, string pattern){
int i = 0, j = 0;
while (i < (int)givenString.size() && j < (int)pattern.size()){
if (checkLowerCase(givenString[i]) || checkLowerCase(pattern[j]) || givenString[i] != pattern[j]) return false;
i++; j++;

while (i < (int)givenString.size() && j < (int)pattern.size() && checkLowerCase(givenString[i]) && checkLowerCase(pattern[j]) && givenString[i] == pattern[j]){
i++;j++;
};
if (j == (int)pattern.size()) {
//Last part to check in pattern

return true;
} else if (!checkLowerCase(pattern[j])) {
//Current part is satisfied, go to the next position in givenString
while (checkLowerCase(givenString[i]) && checkLowerCase(givenString[i])) i++;
} else {
return false;
}
}
return false;
}

vector<string> findMatchingStrings(vector<string> stringList, string pattern){
vector<string> res;

for (int i = 0; i < (int)stringList.size(); i++){

if (check(stringList[i], pattern)){
res.push_back(stringList[i]);
}
}
return res;
}

void printVector(vector<string> myVector){
cout << "Size of vector: "  << myVector.size() << endl;

for (int i = 0; i < (int)myVector.size(); i++){
cout << myVector[i] << " ";
}
cout << endl;
}

int main()
{
cout << "Hello World" << endl;
//['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo']

string st1("HelloMars");
string st2("HelloWorld");
string st3("HelloWorldMars");
string st4("Hiho");                                // ==========> init string (giong het ben duoi)

vector<string> stringList {st1, st2, st3, st4};    // ==========> init vector by vector<int> a {1,2,3}

string pt1("H");
string pt2("HW");
string pt3("Ho");
string pt4("HeWorM");
printVector(stringList);
printVector(findMatchingStrings(stringList, pt1));
printVector(findMatchingStrings(stringList, pt2));
printVector(findMatchingStrings(stringList, pt3));
printVector(findMatchingStrings(stringList, pt4));

return 0;
}``````

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

``````bool check(string givenString, string pattern){
int i = 0, j = 0;
while (i < (int)givenString.size() && j < (int)pattern.size()){
if (checkLowerCase(givenString[i]) || checkLowerCase(pattern[j]) || givenString[i] != pattern[j]) return false;
i++; j++;

while (i < (int)givenString.size() && j < (int)pattern.size() && checkLowerCase(givenString[i]) && checkLowerCase(pattern[j]) && givenString[i] == pattern[j]){
i++;j++;
};
if (j == (int)pattern.size()) {
//Last part to check in pattern

return true;
} else if (!checkLowerCase(pattern[j])) {
//Current part is satisfied, go to the next position in givenString
while (checkLowerCase(givenString[i]) && checkLowerCase(givenString[i])) i++;
} else {
return false;
}
}
return false;``````

}

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

``asdasd``

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

An efficient solution in C++, does not need Regex nor extra space!

``````#include <iostream>
#include <vector>
#include <string>

void
getCCPatterns(std::vector<std::string>& A, std::string& P) {
for(int i = 0; i < A.size(); ++i) {
std::string E = A[i];
int c = 0;
for(int j = 0; j < E.size() && c < P.size(); ++j) {
if(islower(P[c]) && P[c] != E[j]) break;
if(E[j] == P[c]) c++;
}
if(c == P.length()) std::cout << E << std::endl;
}
}

int main() {
std::vector<std::string> A = {"HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"};
std::string P = "HeWorM";

getCCPatterns(A, P);
return 0;
}``````

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

``````public static List<String> test(String pattern, List<String> inputList){
List<String> result = new ArrayList<>();
if(inputList != null && pattern != "null"){
String[] splitedStrs = pattern.split("(?=\\p{Lu})");
String reg = "^";
for(String splitedStr : splitedStrs){
System.out.println(splitedStr);
reg += splitedStr+"[a-z]*";
}
System.out.println(reg);
Pattern pat = Pattern.compile(reg);

for(String input: inputList){
Matcher matcher = pat.matcher(input);
while(matcher.find()){
}
}
}
return result;
}``````

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

``````public static ArrayList<String> matchedList(String[] list, String pattern){
if(pattern.length() < 1 || pattern == null)
return null;
if(list.length < 1)
return null;
ArrayList<String> matchedPattern = new ArrayList<String>();
int flag = 0;
for( String str : list){
if(pattern.length() > str.length())
continue;
if(pattern.charAt(0) != str.charAt(0))
continue;
else
flag = 1;
int position = 0;
for(int i = 1; i < pattern.length(); i++){
for( int j = position + 1; j < str.length(); j++) {
if (pattern.charAt(i) == str.charAt(j)) {
position = j;
flag = 1;
break;
}
if (j == str.length() - 1 && pattern.charAt(i) != str.charAt(j)) {
flag = 0;
break;
}
}
}
if(flag == 1)
}

return matchedPattern;
}``````

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

``````import re

def camel_case(strings, pattern):
splitStrings = []
for s in strings:
splitStrings.append(re.findall('[A-Z][a-z]*', s))
splitPattern = re.findall('[A-Z][a-z]*', pattern)
for ss in splitStrings:
flag = True
for i in xrange(len(splitPattern)):
if i >= len(ss) or splitPattern[i] not in ss[i]:
flag = False
break
if flag == True:
print ''.join(ss)``````

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

``````import re

def camel_case(strings, pattern):
splitStrings = []
for s in strings:
splitStrings.append(re.findall('[A-Z][a-z]*', s))
splitPattern = re.findall('[A-Z][a-z]*', pattern)
for ss in splitStrings:
flag = True
for i in xrange(len(splitPattern)):
if i >= len(ss) or splitPattern[i] not in ss[i]:
flag = False
break
if flag == True:
print ''.join(ss)``````

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

``````import re

def camel_case(strings, pattern):
splitStrings = []
for s in strings:
splitStrings.append(re.findall('[A-Z][a-z]*', s))
splitPattern = re.findall('[A-Z][a-z]*', pattern)
for ss in splitStrings:
flag = True
for i in xrange(len(splitPattern)):
if i >= len(ss) or splitPattern[i] not in ss[i]:
flag = False
break
if flag == True:
print ''.join(ss)``````

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

``````int FindIndexOfChar(string str, char c, int index)
{
for(int i = index; i<str.Length; i++)
{
if(str[i] == c)
{
return i;
}
}
return -1;
}

List<String> FindMatchingStrings(List<string> stringList, string pattern)
{
List<string> matchingStrings = new List<string>();
if(pattern[0].ToString() != pattern[0].ToString().ToUpper())
{
return matchingStrings;//invalid pattern. Return empty stringlist
}
foreach (var str in stringList)
{
int index = 0;
int i = 0;
for (i = 0; i < pattern.Length; i++)
{
int newIndex = FindIndexOfChar(str, pattern[i], index);
if (newIndex == -1)
{
break;//pattern not found. go to next string.
}
else if (i == 0 && newIndex != 0)
{
break;//goto the next string in the list.
}
else if((pattern[i].ToString() == pattern[i].ToString().ToLower()) &&
newIndex != index+1)
{
break;//pattern not found. go to next string.
}
index = newIndex;
}
if (i == pattern.Length)
{
}
}
return matchingStrings;
}``````

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

``````function IsUpperCase(ch)
{
return ch >= 'A' && ch <= 'Z';
} // IsUpperCase

function VerifyCCNPattern(oClassNames, sPattern)
{
oRet = new Array();
var nNameInx, nPatternInx

for(var i=0; i<oClassNames.length; i++)
{
nNameInx = nPatternInx = 0

if(!IsUpperCase(oClassNames[i][0]))
continue;

while( nPatternInx < sPattern.length && nNameInx < oClassNames[i].length )
{
if(sPattern[nPatternInx] == oClassNames[i][nNameInx])
{
++nNameInx;
++nPatternInx;
continue;
}

if(IsUpperCase(sPattern[nPatternInx]) && !IsUpperCase(oClassNames[i][nNameInx]))
{
++nNameInx;
continue;
}

break;
} // while

if(nPatternInx == sPattern.length)
oRet.push(oClassNames[i])
} // while

return oRet;
}``````

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

``````public class Solution {

public static void main(String [] args) {

String [] words = {"HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"};

CamelCaseNotation ccn = new CamelCaseNotation(words);

System.out.println(ccn.getPattern("H"));
// TODO: it can not split HW
System.out.println(ccn.getPattern("HW"));
System.out.println(ccn.getPattern("Ho"));
System.out.println(ccn.getPattern("HeWorM"));
}

}

class CamelCaseNotation {

private List<CamelCaseString> list;

public CamelCaseNotation(String [] words) {
this.list = new ArrayList<>();

for (String str : words) {
}
}

public List<String> getPattern(String pattern) {
List<String> results = new ArrayList<>();

for (CamelCaseString ccs : list) {
if (ccs.isMatch(pattern)) {
}
}

return results;
}
}

class CamelCaseString {

private final String [] strings;
private final String initial;

public CamelCaseString(String string) {
this.initial = string;
this.strings = string.split("(?<!(^|[A-Z]))(?=[A-Z])|(?<!^)(?=[A-Z][a-z])");
}

public String getInitial() {
return initial;
}

public boolean isMatch(String string) {
String [] splited = string.split("(?<!(^|[A-Z]))(?=[A-Z])|(?<!^)(?=[A-Z][a-z])");

for (int i = 0; i < splited.length; i++) {
if (i == strings.length) {
return false;
}

if (!strings[i].startsWith(splited[i])) {
return false;
}
}

return true;
}``````

}

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

``````import java.util.ArrayList;

public class TrieNode {

char value;
ArrayList<TrieNode> children;
boolean isWord;

TrieNode(Character v) {
value = v;
children = new ArrayList<>();
}

void insert(String s) {
if (s == null || s.length() <= 0) {
isWord = true;
return;
}
char c = s.charAt(0);
for (TrieNode child : children) {
if (child.value == c) {
child.insert(s.substring(1));
return;
}
}
TrieNode newNode = new TrieNode(c);
newNode.insert(s.substring(1));
}

void match(String prefix, String word) {
if (prefix == null || prefix.length() <= 0) {
getWords(word);
return;
}
char c = prefix.charAt(0);
String s=(prefix.length()>1)?prefix.substring(1):"";
for (TrieNode child : children) {
if (child.value == c)
child.match(s, word + c);
}
if (Character.isUpperCase(c)) {
for (TrieNode child : children) {
if (Character.isLowerCase(child.value))
child.match(prefix, word + child.value);
}
}
}

void getWords(String word) {

for (TrieNode child : children) {
if (child.isWord) {
System.out.println(word + child.value);
}
child.getWords(word + child.value);
}
}

public static void main(String[] args) {
TrieNode root = new TrieNode('-');
root.insert("HelloMars");
root.insert("HelloWorld");
root.insert("HelloWorldMars");
root.insert("HiHo");
root.match("HH", "");
}

}``````

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

``````import java.util.ArrayList;

public class TrieNode {

char value;
ArrayList<TrieNode> children;
boolean isWord;

TrieNode(Character v) {
value = v;
children = new ArrayList<>();
}

void insert(String s) {
if (s == null || s.length() <= 0) {
isWord = true;
return;
}
char c = s.charAt(0);
for (TrieNode child : children) {
if (child.value == c) {
child.insert(s.substring(1));
return;
}
}
TrieNode newNode = new TrieNode(c);
newNode.insert(s.substring(1));
}

void match(String prefix, String word) {
if (prefix == null || prefix.length() <= 0) {
getWords(word);
return;
}
char c = prefix.charAt(0);
String s=(prefix.length()>1)?prefix.substring(1):"";
for (TrieNode child : children) {
if (child.value == c)
child.match(s, word + c);
}
if (Character.isUpperCase(c)) {
for (TrieNode child : children) {
if (Character.isLowerCase(child.value))
child.match(prefix, word + child.value);
}
}
}

void getWords(String word) {

for (TrieNode child : children) {
if (child.isWord) {
System.out.println(word + child.value);
}
child.getWords(word + child.value);
}
}

public static void main(String[] args) {
TrieNode root = new TrieNode('-');
root.insert("HelloMars");
root.insert("HelloWorld");
root.insert("HelloWorldMars");
root.insert("HiHo");
root.match("HH", "");
}

}``````

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

``````import java.util.ArrayList;

public class TrieNode {

char value;
ArrayList<TrieNode> children;
boolean isWord;

TrieNode(Character v) {
value = v;
children = new ArrayList<>();
}

void insert(String s) {
if (s == null || s.length() <= 0) {
isWord = true;
return;
}
char c = s.charAt(0);
for (TrieNode child : children) {
if (child.value == c) {
child.insert(s.substring(1));
return;
}
}
TrieNode newNode = new TrieNode(c);
newNode.insert(s.substring(1));
}

void match(String prefix, String word) {
if (prefix == null || prefix.length() <= 0) {
getWords(word);
return;
}
char c = prefix.charAt(0);
String s=(prefix.length()>1)?prefix.substring(1):"";
for (TrieNode child : children) {
if (child.value == c)
child.match(s, word + c);
}
if (Character.isUpperCase(c)) {
for (TrieNode child : children) {
if (Character.isLowerCase(child.value))
child.match(prefix, word + child.value);
}
}
}

void getWords(String word) {

for (TrieNode child : children) {
if (child.isWord) {
System.out.println(word + child.value);
}
child.getWords(word + child.value);
}
}

public static void main(String[] args) {
TrieNode root = new TrieNode('-');
root.insert("HelloMars");
root.insert("HelloWorld");
root.insert("HelloWorldMars");
root.insert("HiHo");
root.match("HH", "");
}

}``````

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

Swift 2.2

``````// Determines if a character is capitalized.
func isCapital(c:Character) -> Bool {
return ("A"..."Z").contains(c)

}

// Splits a CamelCaseNotation string into sections.
func getSections(camelCaseString: String) -> [String] {
var sections = [String]()
var section = ""
for character in camelCaseString.characters {
if (isCapital(character)) {
if (section.characters.count > 0) {
sections.append(section)

}
section = String(character)

} else {
section.append(character)

}

}
if (section.characters.count > 0) {
sections.append(section)

}
return sections

}

// Returns an array of CamelCaseNotation strings whos prefixes match
// the CamelCaseNotation of the key.
func camelCaseNotation(words:[String], key: String) -> [String] {
// Because SE-0003
var words = words
var keySections = getSections(key)

for i in (0 ..< words.count).reverse() {
var wordSections = getSections(words[i])

// Remove the word if it has less sections than the key.
if (wordSections.count < keySections.count) {
words.removeAtIndex(i)
continue

}

// Remove the word if its section doesn't match the key's corresponding section.
for j in 0 ..< keySections.count {
if (wordSections[j].hasPrefix(keySections[j]) == false) {
words.removeAtIndex(i)
break;
}

}

}
return words;

}

var words = ["HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"]
camelCaseNotation(words, key: "H") // ["HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"]
camelCaseNotation(words, key: "HW") // ["HelloWorld", "HelloWorldMars"]
camelCaseNotation(words, key: "Ho") // []
camelCaseNotation(words, key: "HeWorM") // ["HelloWorldMars"]``````

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

``````public static void main(String args[]) {

List<String> data = Arrays.asList("H", "HW", "Ho", "HeWorM");
List<String> details = Arrays.asList("HelloMars", "HelloWorld", "HelloWorldMars", "HiHo");
details.forEach(str -> {
data.forEach(curCamCase -> {
System.out.println(" cam case " + curCamCase + " compared to string " + str + " is "
+ isMatchCamelCase(curCamCase, str));
});
});

System.out.println("match?" + isMatchCamelCase("HelWorM", "HelloWorld"));
}

public static boolean isMatchCamelCase(String camelCase, String word) {
if (camelCase.length() > 0 && word.length() == 0) {
return false;
}
if (camelCase.length() == 0) {
return true;
}
if (Character.isUpperCase(camelCase.charAt(0))) {
if (Character.isUpperCase(word.charAt(0))) {
return camelCase.charAt(0) == word.charAt(0)
&& isMatchCamelCase(camelCase.substring(1), word.substring(1));
} else {
return isMatchCamelCase(camelCase, word.substring(1));
}
} else if (!Character.isUpperCase(camelCase.charAt(0))) {
return camelCase.charAt(0) == word.charAt(0) && isMatchCamelCase(camelCase.substring(1), word.substring(1));
}

return true;
}``````

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

Can we use RegEx?

``````public static void main(String[] args){

String[] camelCaseWords = { "HelloMars", "HelloWorld", "HelloWorldMars", "HiHo" };

String input = "HeW"; //'This is an Example';

StringBuilder sb = new StringBuilder();
sb.append(input.charAt(0));
for (int i=1; i< input.length(); i++){
char curr = input.charAt(i);
if (curr >= 'A' && curr <= 'Z'){ //capital letter
sb.append("[a-z]*" + curr);
}else{
sb.append(curr);
}
}
sb.append("[a-z]*");

for (String s : camelCaseWords){
if (s.matches(sb.toString())){
System.out.println(s);
}
}

}``````

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

``````def getCamelCase(string):
caps = range(65, 91)
if len(string) <= 1:
return [string]
else:
res = []
pos = [i for i, x in enumerate(string) if ord(x) in caps]
prev = 0
for x in pos:
if x == 0:
continue
res.append(string[prev:x])
prev = x
res.append(string[prev:])
return res

def identify(lst, pattern):
splits = getCamelCase(pattern)
matched = []
for x in lst:
if x.startswith(splits[0]):
matched.append(x)
filter = []
for y in matched:
flag = True
for x in splits[1:]:
if x not in y:
flag = False
if flag:
filter.append(y)
if len(filter)==1:
return filter[-1]
else:
res = []
for z in filter:
if len(splits)==len(getCamelCase(z)):
res.append(z)
if len(res)>1:
return res
elif len(res)==0:
return ''
else:
return res[-1]

lst = ['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo', 'FunnyWire', 'HelloW']
pattern = 'FWi'

print identify(lst,pattern)``````

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

``````def getCamelCase(string):
caps = range(65, 91)
if len(string) <= 1:
return [string]
else:
res = []
pos = [i for i, x in enumerate(string) if ord(x) in caps]
prev = 0
for x in pos:
if x == 0:
continue
res.append(string[prev:x])
prev = x
res.append(string[prev:])
return res

def identify(lst, pattern):
splits = getCamelCase(pattern)
matched = []
for x in lst:
if x.startswith(splits[0]):
matched.append(x)
filter = []
for y in matched:
flag = True
for x in splits[1:]:
if x not in y:
flag = False
if flag:
filter.append(y)
if len(filter)==1:
return filter[-1]
else:
res = []
for z in filter:
if len(splits)==len(getCamelCase(z)):
res.append(z)
if len(res)>1:
return res
elif len(res)==0:
return ''
else:
return res[-1]

lst = ['HelloMars', 'HelloWorld', 'HelloWorldMars', 'HiHo', 'FunnyWire', 'HelloW']
pattern = 'FWi'

print identify(lst,pattern)``````

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

private static void findCamelCase(List<string> wordlist, string pattern)
{
foreach (var word in wordlist)
{
int i = 0, p = 0;

while (p<pattern.Length && i<word.Length)
{

if (word[i] == pattern[p])
{
i++;
p++;
}
else
{
while (!char.IsUpper(word[i]) && i<word.Length-1)
i++;
if (word[i] == pattern[p])
{
i++;
p++;
}
else
{
Console.WriteLine(word + " is NOT adhering to the pattern " + pattern);
break;
}
}

}

if (p == pattern.Length)
{
Console.WriteLine(word + " is adhering to the pattern " + pattern);
}

}

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

``````private static void findCamelCase(List<string> wordlist, string pattern)
{
foreach (var word in wordlist)
{
int i = 0, p = 0;

while (p<pattern.Length && i<word.Length)
{

if (word[i] == pattern[p])
{
i++;
p++;
}
else
{
while (!char.IsUpper(word[i]) && i<word.Length-1)
i++;
if (word[i] == pattern[p])
{
i++;
p++;
}
else
{
Console.WriteLine(word + " is NOT adhering to the pattern " + pattern);
break;
}
}

}

if (p == pattern.Length)
{
Console.WriteLine(word + " is adhering to the pattern " + pattern);
}

}``````

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

Here is my answer for people who are familiar with Python.

``````import re

inputList = ['Hello', 'HelloWorld', 'HelloWorldMars', 'HiHo', 'WorldHello']
givenString = 'HeW'

def CamelCaseNotation(inputList, givenString):
if givenString[0].islower():
return None

# Split it based on capital letters
splitString = re.findall(r'[A-Z][a-z]*', givenString)

output = list()
for item in inputList:
splitWords = re.findall(r'[A-Z][a-z]*', item)
# loop on the substrings of both lists at the same time
i = 0
while i < min(len(splitString), len(splitWords)):
# as long as there is a match, continue to loop
if splitString[i] not in splitWords[i] :
break
i += 1
# if all substrings of the input string match with a word from the input list,
# we can add this word to the output list
if i == len(splitString) :
output.append(item)

return output

CamelCaseNotation(inputList, givenString)``````

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

``````#include <string>
#include <iostream>
#include <map>

using namespace std;
struct TrieNode;

struct TrieNode {
TrieNode* lNext[26];
TrieNode* uNext[26];

char ch;
bool isWord;

TrieNode(char c, TrieNode* p) :
ch(c),
lNext(),
uNext(),
isWord(false)
{
}
};

void insert(string str, TrieNode* root) {
size_t len = str.size();
for (size_t i = 0; i < len; ++i) {
bool upper = str[i] >= 'A' && str[i] <= 'Z';
TrieNode* next = NULL;
if (upper){
next = root->uNext[str[i] - 'A'];
if (!next) {
next = new TrieNode(str[i], root);
root->uNext[str[i] - 'A'] = next;
}
}
else {
next = root->lNext[str[i] - 'a'];
if (!next) {
next = new TrieNode(str[i], root);
root->lNext[str[i] - 'a'] = next;
}
}
root = next;
}

root->isWord = true;
}

void printLeafNodes(TrieNode* cur, string str) {
if (cur) {
str.push_back(cur->ch);
if (cur->isWord)
cout << str << endl;

for (int i = 0; i < 26; ++i) {
if (cur->lNext[i])
printLeafNodes(cur->lNext[i], str);

if (cur->uNext[i])
printLeafNodes(cur->uNext[i], str);
}
}
}

void findMatches(string pat, size_t index, TrieNode* cur, string res) {
if (index >= pat.size())
return;
char c = pat[index];
bool upper = c >= 'A' && c <= 'Z';
int cIndex = upper
? c - 'A'
: c - 'a';

TrieNode* next = upper
? cur->uNext[cIndex]
: cur->lNext[cIndex];

if (next) {
if (index == pat.size() - 1)
printLeafNodes(next, res);
else{
res.push_back(c);
findMatches(pat, index + 1, next, res);
}
}
else{
if (upper) {
for (int i = 0; i < 26; ++i) {
if (cur->lNext[i]) {
res.push_back(cur->lNext[i]->ch);
findMatches(pat, index, cur->lNext[i], res);
}
}
}
}
}

void main2() {
TrieNode* root = new TrieNode(NULL, NULL);
string arr[] = { "HelloMars", "HelloWorld", "HelloWorldMars", "HiHo" };
for (int i = 0; i < 4; ++i)
insert(arr[i], root);

string pat[] = { "H", "HW", "Ho", "HeWorM" };
for (int i = 0; i < 4; ++i){
cout << "Matches for " << pat[i] << ":" << endl;
findMatches(pat[i], 0, root, "");
cout << endl;
}
}``````

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.

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