revanthpobala
BAN USER- 2of 2 votes
AnswersFind the largest substring palindrome in a given string.
- revanthpobala in United States
ex: input: abbac output: abba
Solution: Use Hashmap| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm
iparens = iter('(){}[]<>\'')
parens = dict(zip(iparens, iparens))
closing = parens.values()
def balanced(astr):
stack = []
for c in astr:
d = parens.get(c, None)
if d:
stack.append(d)
elif c in closing:
if not stack or c != stack.pop():
return False
return not stack
def isprime(n):
"""Returns True if n is prime."""
if n == 2:
return True
if n == 3:
return True
if n % 2 == 0:
return False
if n % 3 == 0:
return False
i = 5
w = 2
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True
def minDifferenceBetweenTwoPrimeNumbers(array):
primeArray = []
for i in array:
if isprime(i):
primeArray.append(i)
return sorted(primeArray)[1] - sorted(primeArray)[0]
def maxConsequtiveOnes(String):
if String is None or String.strip() is "" :
return 0
_max = 0
_ones = []
for i in String:
if i == "1":
_max += 1
if i == "0":
_max = 0
_ones.append(_max)
return max(_ones)
Modified Trie??
- revanthpobala August 03, 2016def rotate(matrix,degree=90):
if abs(degree) not in [0, 90, 180, 270, 360]:
# raise error or just return nothing or original
if degree == 0:
return matrix
elif degree > 0:
return rotate(zip(*matrix[::-1]), degree-90)
else:
return rotate(zip(*matrix)[::-1], degree+90)
Use regex.and compile all the words in the dictionary. match those words to the given string. append all the words into a list and output the list.
- revanthpobala November 18, 2015I have used regular expression to match the words that are present in the dictionary with the string given. Here is my code and I believe that it takes less than O(n^2) time. Btw regex is very fast i believe.
import re
def getsegstring(S,word):
dictionary = ['hello','ate','a','an','ant','i']
legalwords = {}
finalwords= []
if len(S)>0:
for i in dictionary:
match =re.compile(i)
if len(re.findall(match,S))>0:
legalwords[re.findall(match,S)[0]] = len(re.findall(match,S)[0])
maxi = max(legalwords.values())
for k,v in legalwords.iteritems():
if v == maxi:
finalwords.append(k)
return boolval(finalwords,word)
else:
return False
def boolval(finalwords,word):
if word in finalwords:
return True
else:
return False
print getsegstring("iateanant","ant")
"""
Result : True
"""
I believe the complexity is O(n* time taken to build a DFA i.e regex)
- revanthpobala November 05, 2015Well, we can use tries as mentioned above. But I feel that regular expressions can also be used to solve this problem. If the dictionary L is fixed then I believe that this is useful.
Here is my code
import re
def inputs(stream,dicts):
outputs = []
str = ""
for i in dicts:
matchs = re.compile(i)
outputs.extend(re.findall(matchs,stream))
for i in outputs:
str = str+ " "+i
return str
L = ['ok','testing','one','try','trying']
print inputs('oktestingdonehereandtherejustgiveitatryandiamtryingtogetsolution',L)
#Result : ok testing one try try trying
I am just guessing. We can use Head and Tail commands to read the first and last lines from a file.
- revanthpobala November 05, 2015Could you explain the question in more detail.
- revanthpobala November 05, 2015Here is the following code.
package pray;
import java.util.HashMap;
import java.util.Map;
public class Trie{
public static class TrieNode{
char c;
HashMap <Character,TrieNode> children = new HashMap<Character,TrieNode>();
boolean isLeaf;
public TrieNode(){
}
public TrieNode(char c){
this.c = c;
}
}
private TrieNode root;
public Trie(){
root = new TrieNode();
}
public void insert(String word){
HashMap<Character,TrieNode> children = root.children;
for(int i=0; i<word.length();i++){
char c = word.charAt(i);
TrieNode t;
if(children.containsKey(c)){
t = children.get(c);
}else{
t = new TrieNode(c);
children.put(c,t);
}
children = t.children;
if(i==word.length()-1){
t.isLeaf = true;
}
}
}
public boolean search(String word){
TrieNode t = searchNode(word);
if(t!=null && t.isLeaf){
return true;
}else{
return false;
}
}
public boolean startsWith(String prefix){
if(searchNode(prefix)==null){
return false;
}else{
return true;
}
}
private TrieNode searchNode(String str) {
Map<Character, TrieNode> children = root.children;
TrieNode t = null;
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(children.containsKey(c)){
t = children.get(c);
children = t.children;
}else{
return null;
}
}
return t;
}
public static void main(String[] args){
Trie t = new Trie();
t.insert("get");
t.insert("hi");
t.insert("hello");
t.insert("computer");
t.insert("communication");
t.insert("communist");
System.out.println(t.startsWith("com"));
}
}
We can use Tries
- revanthpobala November 03, 2015For the above solution,I think you need to use BigInt library if you want to multiply.
- revanthpobala October 29, 2015Tarjan's Algorithm for strongly connected graphs
- revanthpobala October 28, 2015In Python. Just import the OrderedDict.
from collections import OrderedDict
def removedups(S):
maps ={}
str = ""
maps = OrderedDict((i,S.count(i)) for i in S)
for k,v in maps.iteritems():
str = str+k
return str
print removedups("abracadabra")
I did not check for all the possibilities but here is the code in python. I am assuming a predefined dictionary is present.
def indict(word):
diction = ['cat', 'bat', 'bet', 'bed', 'at', 'ad', 'ed', 'cat', 'cog', 'dog', 'cot']
if word in diction:
return True
else:
return False
def stepschange(word1, word2):
if not (len(word1)!= len(word2)) and indict(word1) and indict(word2):
breaking1 = [i for i in word1]
counter =0
for j in word2:
if j in breaking1:
counter = counter +1
return 1+len(word1)-counter
else:
return 0
print stepschange('bat' , 'bed'),"11"
print stepschange('bat' , 'cat'),"11"
print stepschange('cat' , 'bet'),"11"
print stepschange('cat' , 'bog'),"11"
Here is my code in python.
def longers(P,S):
maps = {}
str1 = ''
str2 =''
for i in S:
maps[str(i)] = str(ord(i))
for ij in P:
str1 = str1 + str(maps.get(ij))
print str1
for x in P:
str2 = str2+str(str(ord(x)))
print str2
if str1 == str2:
return True
else:
return False
print longers('NAGARRG', 'abcNjhgAhGjhfhAljhRkhgRbhjbevfhO')
Dude what if the array has negative values? If the stock market looses then there will be a negative value. If that's the case your code fails.
- revanthpobala October 27, 2015It is a Dynamic Programming question folks.
- revanthpobala October 27, 2015Here is my solution. But it is not O(1) complexity.
def sum(arr,x1,x2):
sum = 0
for i in range(x1,x2+1):
sum = sum+ arr[i]
return sum
print sum([1,6,5,4], 1, 3)
I have not included the case for return False. I will post it once I have a good algorithm.
- revanthpobala October 27, 2015I have written a python code for it. In this code, I am not checking for all combinations but I am randomly splitting the string and matching it with the pattern. If our luck is good then it will return in the first match itself else it will keep trying until the recursion depth exceeds. Hope that someone comes up with a solid algorithm. As mentioned above this is an NP-Hard problem. Please look at the code. Hope it helps.
import random
def ismatch(P, S):
parts = len(P)
collections = []
maps = {}
str = ""
counter = 0
collections = breaks(S,parts)
for i in collections:
if i == "":
collections = ismatch(P,S)
else:
pass
#map logic
if len(collections) == parts:
for i in P:
maps[i] = collections[counter]
counter = counter+1
#check pattern
for ij in P:
print maps.get(ij)
str= str+ maps.get(ij)
if str == S:
return True
else:
ismatch(P, S)
#Split the string at random character and put them in to the list
def breaks(S,parts):
if parts == 0:
return []
collecter = []
strlen = len(S)/parts
for x in range(parts):
rand = random.randint(0,parts)
collecter.append(S[strlen*x: strlen*rand])
return collecter
print ismatch("aba","doggoddog")
'''Result
dog
god
dog
True
'''
could you explain it?
- revanthpobala October 27, 2015Dictionary structure: {Element: [Start index, Final index]}
- revanthpobala October 26, 2015Python Solution: It will return the following
def getfirstlast(arr1):
first = {}
second = {}
for i in arr1:
first[i] =[arr1.index(i), arr1.count(i)]
for k,v in first.iteritems():
for j in v:
second[k] = [v[0],(v[0]+v[1]-1)]
return second
a =[1,2,3,4,5,5,5,5,6,7]
print getfirstlast(a)
''' Answer: {1: [0, 0], 2: [1, 1], 3: [2, 2], 4: [3, 3], 5: [4, 7], 6: [8, 8], 7: [9, 9]} '''
Python implementation. Time complexity O(n)
def twosets(s,t):
table =dict()
lis = []
q = s+t
point = 0
for i in t:
table[i] = s[point]
point = point +1
for i in table.iteritems():
lis.append(i)
return lis
A = ['C', 'D', 'E', 'F', 'G']
B = [4,3,1,0,2]
print twosets(A,B)
I have solved the question using bubble sort and hashmap. My complexity is O(n^3). I have passed 9 test cases out of 11 test cases.
- revanthpobala October 01, 2015
Neat solution. Used the above python code
- revanthpobala February 05, 2017