CareerCup

use memory address

"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

Output fo above run

True
True
False
True
True

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?')

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 1-many 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 non-contiguity. 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

output is

[-1]
[-100, -1]
[-100, -1, 100]
[-1, 200, 100]
[-1, 200, 100]

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)

Choices - O(1) space + O(n**2) time OR O(n) in both

Again, 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

Space 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]

if(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.

O(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!

O(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.

In a binary tree, there is no way to avoid O(n^2)

I 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();
	}
}

Can you kindly explain why it would not work for 4 numbers adding to target?

no 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
}

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.

so is

java.security.InvalidParameterException

that's a crime

throw new NullPointerException

It'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)

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