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

revanthpobala
January 25, 2017 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]

revanthpobala
January 25, 2017 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)

revanthpobala
January 24, 2017 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]), degree90)
else:
return rotate(zip(*matrix)[::1], degree+90)

revanthpobala
February 07, 2016 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
"""

revanthpobala
November 11, 2015 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

revanthpobala
November 05, 2015 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"));
}
}

revanthpobala
November 03, 2015 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")

revanthpobala
October 28, 2015 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"

revanthpobala
October 28, 2015 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')

revanthpobala
October 27, 2015 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)

revanthpobala
October 27, 2015 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 NPHard 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
'''

revanthpobala
October 27, 2015 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]} '''

revanthpobala
October 26, 2015 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)

revanthpobala
October 26, 2015 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, 2015Open Chat in New Window
Neat solution. Used the above python code
 revanthpobala February 05, 2017