EK MACHCHAR
BAN USER 0of 0 votes
AnswersWrite a Javascript program for the following problem 
 EK MACHCHAR in United States
(Actually, any language is fine with me but it was a JS interview)
Given a large number of strings occurring on a web page, find the largest group of strings that are likely to be swapped with each other.
e.g mat, rat, groom, broom, cat
answer => mat, rat, cat and not groom, broom
I coded edit distance, got hopelessly lost beyond that.
As for hints, he said that it being a web page don't count on traversing a given string more than once. Report Duplicate  Flag  PURGE
TP SDE1 Algorithm JavaScript  0of 0 votes
AnswersGiven a sorted array find whether odd number of numbers exist s.t. sum is K. 0 is a permitted value in array. Negatives may not be permitted. But he was not conclusive there. He was expecting Javascript code and O(n) complexity.
 EK MACHCHAR in United States
e.g. [12, 2, 1, 4] , searching 1 => yes, 5 => no because 4+1 make the number of numbers even! Report Duplicate  Flag  PURGE
TP SDE1 JavaScript  0of 0 votes
AnswersGiven an array find the subsequence that needs to be removed so that the array becomes sorted. There can be many resultant sorted arrays. Need to find longest. Expected time complexity O(n).
 EK MACHCHAR in United States
e.g. 9 9 6 1 3 4 4 5 1 7 => 1 3 4 4 5 7 so need to remove 9 9 6 1 Report Duplicate  Flag  PURGE
TP Algorithm
"Arrays are harder to cause size changes, LLs easier "
Dont know what 'harder' means there, if you are talking about computational complexity, the amortized one remains the same.
So, what's the harm in just saying arraylist is an array based implementation of DLL abstract data type?
Start with the leftmost digit in y. If the digit exists in x, print it else print the next greatest.
y = 2410 x = 1234
2
4
1
3 // there is no zero, the next greatest unused digit is 3
Python code
def find(hayStack, needle):
i = 0
j = len(hayStack)  1
while i < len(hayStack) and j >= 0:
print i,j
if hayStack[i][j] == needle:
return True
if hayStack[i][j] > needle:
j = j  1
if hayStack[i][j] < needle:
i = i + 1
return False

EK MACHCHAR
May 16, 2013 And here is a simple dumb regex engine in python
def dumb_regex(str1, str2):
#print str1, str2
if str1 == str2:
return True
if str2 == '*':
return True
if len(str1) == 1 and str2 == '?':
return True
if str2[0] == '?':
return dumb_regex(str1[1:], str2[1:]) or dumb_regex(str1, str2[1:])
elif str2[0] == '*':
for i in range(len(str1)):
if dumb_regex(str1[i:], str2[1:]):
return True
else:
return False
elif str1[0] != str2[0]:
return False
return dumb_regex(str1[1:], str2[1:])
if __name__=="__main__":
print dumb_regex('abcd', 'a*b*c?')
print dumb_regex('abcd', 'a?b*c?')
print dumb_regex('xyz', 'a?b*c?')
print dumb_regex('xyzabcd', 'xy*')
print dumb_regex('xyz', 'xy?')

EK MACHCHAR
May 14, 2013 I really don't understand what's all this inspace thing all about.
Do you really believe that a site such as fb will be storing the relationship between entities totally in memory?
There would be a table POSTS, another USERS and LIKES.
There is a many to many rel between POSTS and USERS so there is a link table POSTS_USERS.
POSTS to LIKES is 1many so LINKS table would have things like USER_ID, POST_ID and of course ID.
Now memcached enters.
A user logs in, his details are queried from the db and put in cache.
Of course, this is a hashtable.
The method name is misleading. Should have named it break_iterative
When searching for just 2 substrings to be scanned in dictionary, the iterative is more intuitive than recursive.
Rachit, he was asking subsequence not substring. To me sequence implied noncontiguity. so, in your first example the answer is 12345. That's also the answer in (2)
Now, how to do it in linear time?
python code
def break_recursive(s):
for i in range(len(s)):
str1 = s[i:]
str2 = s[:i]
if str1 in words and str2 in words:
print str1, str2

EK MACHCHAR
May 10, 2013 output is
[1]
[100, 1]
[100, 1, 100]
[1, 200, 100]
[1, 200, 100]

EK MACHCHAR
May 10, 2013 Python code
import heapq
heap = []
def topK(i, k):
if len(heap) < k:
#simply insert
heapq.heappush(heap, i)
else:
if heap[0] < i:
heap[0] = i
heapq.heapify(heap)
print heap
if __name__ == "__main__":
topK(1,3)
topK(100,3)
topK(100,3)
topK(200,3)
topK(200,3)

EK MACHCHAR
May 10, 2013 Choices  O(1) space + O(n**2) time OR O(n) in both
 EK MACHCHAR May 10, 2013Again, there is no O(n) in time and O(1) in space algo.
You are not tracking lets say second most frequent item and then suddenly you have the second most frequent item a lot of times.
You dont know now how many times it has occurred in the past, so now what will your algo do?
hashmap will consume the same space as your recursive inorder
 EK MACHCHAR May 10, 2013Space is definitely not O(1)  you are doing recursive calls there.
If you really want a O(1) space solution, then it cant be achieved in O(n) time it will be n**2
You may even think in terms of augmented data structures, recursion, hashtable, there is no o(n) + o(1) solution
Python code
import heapq
def kLists(L):
heap = []
end = False
for l in L :
thisRange = max(l)  min(l)
heap.append(min(l))
heapq.heapify(heap)
while not end:
elem = heapq.heappop(heap)
print elem
for l in L :
if elem in l:
#print l
l.remove(elem)
#print l
if len(l) == 0:
end = True
break
heapq.heappush(heap,l[0])
print heap
def minL(l):
m = min(float(s) for s in l)
return m
def maxL(l):
m = max(float(s) for s in l)
return m
if __name__ == "__main__":
L = [
[4, 10, 15, 24, 26],
[0, 9, 12, 20],
[5, 18, 22, 30],
]
kLists(L)
output : [20, 24]
 EK MACHCHAR May 10, 2013if(head != NULL){
while( count < k ){
must change to
if(ref_ptr != NULL){
while( count < k ){
to deal with the pathological case you are checking. Just a way to avoid that extra if block.
 EK MACHCHAR May 10, 2013O(1) memory? how?
O(n) space for merge sort.
This can't be done in O(n) without extra space.
Down voting can't change the facts
Me, Me!
 EK MACHCHAR May 05, 2013O(n lgm) algo where m is the length of the shorter sorted array.
Maintain two pointers beginning at each array. Compare the two current values and insert the out of place value in the other array using binary search.
This is ridiculous. Tomorrow they will mandate that knowledge of kabbadi is essential for a coding interview.
 EK MACHCHAR May 05, 2013In a binary tree, there is no way to avoid O(n^2)
 EK MACHCHAR May 05, 2013I don't see any probability here. The % are fixed. Just maintain a counter to ensure the proportions.
70% of times A has to be retained => return A 7 out of 10 times using counter and remaining 3 times something else.
What has prob got to do here?
Standard question. Solved in chapter 11 CLR.
Best case complexity is still O(n), but you can optimize using two variables.
Contact is composed of other entities or properties. May be Contact has ph number, name etc.
Time to use command DP.
interface Searchable {
public SearchResult search();
}
class PhoneNumber implements Searchable {
// implement the method .....
}
class Contact implements Searchable {
// lots of layering :)
public SearchResult search() {
return phNumber.search();
}
}

EK MACHCHAR
May 04, 2013 Can you kindly explain why it would not work for 4 numbers adding to target?
 EK MACHCHAR May 04, 2013no need of O(n^2)
When the universe is finite you can always fall back on counting sort or a modification thereof.
O(n) + constant space
The question is a bit ambiguous. "Rewrite the behaviour"
Encapsulation is the only other option, but you will run into typing issues.
import A;
import B;
public class C {
A a; B b;
C() { a = new A();
b = new B();
}
methodA() {
a.methodA();
}
/// and so on
}

EK MACHCHAR
May 04, 2013 To find k largest numbers we definitely don't need to sort.
The problem is cut out for Min heap.
The point at which rotation has occurred can be found only in linear time. So the entire thing will take O(n), the same as finding min in any array.
 EK MACHCHAR May 04, 2013It's the same as finding (i,j) such that i < j and Arr[i] < Arr[j]
All such pairs can be found in linear time. We need the one where Arr[j]  Arr[i] is max.
O(n) time
Don't see the point in the question.
call run of B in run of A and so on. Seems a warm up question.
?
The question text doesn't say that order needs to be preserved. maintain three pointers  1 for vowel, consonant, text each. Start traversal and keep inserting at the appropriate head.
f(nth) = floor((1+sqrt(5))/2)^n / sqrt(5) +0.5)
 EK MACHCHAR May 04, 2013and last I checked Chess was not part of computer science.
Yeah, right. Keep down voting. Chess will still not be part of Computer Science.
Is it some kind of runtime exception that's getting thrown? In such a case the method call will not be executed at all.
Wonder what's the real intent of the question.
Proxy DP.
It works by creating runtime proxies to the target object and enhancing the functionality of the underlying.
use memory address
 EK MACHCHAR November 17, 2013