CareerCup

Suppose we want to convert one string S1 to another string S2 using only 3 types of operations:
-Insert(pos,char) (costs 8)
-Delete(pos) (costs 6)
-Replace(pos,char) (costs 8)
Find the sequence of steps to convert S1 to S2 such that the cost to convert S1 to S2 is minimum.
Eg. 'calculate' to 'late' - the possible operations are
Delete(0)
Delete(1)
Delete(2)
Delete(3)
Delete(4)
and the above sequence of operations costs 30.

I used the following code(using levenshtein algorithm) to solve this. But I am not getting correct answer.

tuples=[]
ops=[]
s1=''
s2=''
def levenshtein(a,b):
    global s1,s2
    n, m = len(a), len(b)
    if n > m:
        a,b = b,a
        n,m = m,n
    s1,s2=a,b
    current = range(n+1)
    for i in range(0,len(current)):
        current[i]=current[i]*8
    tuples.append(current)
    for i in range(1,m+1):
        previous, current = current, [i*8]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+6, current[j-1]+8
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change=change+8
            current[j] = min(add, delete, change)
        tuples.append(current)
    return current[n]

print levenshtein('calculate','late')
for i in range(len(tuples)):
    stri=''
    for j in range(len(tuples[0])):
        stri+=str(tuples[i][j])+' '
i=len(tuples)-1
j=len(tuples[0])-1
ops=[]
while i>0:
    while j>0:
        minimum=min([tuples[i-1][j],tuples[i][j-1],tuples[i-1][j-1]])
        if minimum==tuples[i-1][j]:
            i=i-1
            if not tuples[i][j]==tuples[i-1][j]:
                ops.append([1,i])
        elif minimum==tuples[i][j-1]:
            j=j-1
            if not tuples[i][j]==tuples[i][j-1]:
                ops.append([2,i-1,j])
        else:

            ops.append([3,i-1,s1[i-1]])
            i=i-1
            j=j-1

Design a DS for storing browsing history.

Design a Calculator. Details about the class variables, datastructure to be used etc.

Generate a solution when multiple threads want to just read in their critical sections and when nobody is writing in the critical section.

How to print a variable 1000 times without using loops and recurssion

There is a 1.2G text file on the 1.5G hard drive and 300M memory, how can reverse these file in word unit.
please program with c language!
For example:
"Thank you for your help"
reversed:
"help your for you Thank"

Truth Table implementation: Write a function which takes integer as In put parameter (let's say n), print all True (T) , False (F) combinations n times. Here is the example:

for n = 1
Output :
T
F

for n = 2
Output :
T F
F T

For n = 3
Output :

T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F

Write a program to swap kth node from first and kth node from last in a linked list .

How do you remove duplicates from a dataset that does not fit into memory?

Find the merge point of two linked list.

3)Reverse individual words of a sentence.

Reverse an integer without using temp variable.

How to swap two bits in an integer.

What will be the output of the program ?

#include< stdio.h >
void fun(void *p);
int i;
int main()
{
void *vptr;
vptr = &i;
fun(vptr);
return 0;
}
void fun(void *p)
{
int **q;
q = (int**)&p;
printf("%d ", **q);
}

test(){
return 3;
}
void main(){
int i=2;
for(test();test();test();)
{
printf("2");
}

Output value or run-time error or compile time error ?

Given sorted arrays A and B of lengths n and m respectively,return an array C containing elements common to A and B. The array C should be free of duplicates.

Create a Session Manager class that iterates thru Session objects throw stale sessions out - How would you automatically purge Session objects that have not been active for 30 seconds or (n) seconds? The answer needs to handle millions of sessions.

I Got this Crazy Question on PHONE INTERVIEW AT GOOGLE:

Design and implement a class to generate random numbers in an arbitrary probability distribution given by an array of integer weights, i.e. for int[] w return a number, n, from 0 to w.length - 1 with probability w[n] / sum(w). Using an existing random number generator with a uniform distribution is permitted.

Example distribution:
w = 1, 2, 3, 2, 1

Example probabilities:
w / sum = 1/9, 2/9, 1/3, 2/9, 1/9

Example results:
n = 0, 1, 2, 3, 4

Documentation:

Class java.util.Random

public int nextInt(int n)

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.

Parameters:
n - the bound on the random number to be returned. Must be positive.
Returns:
the next pseudorandom, uniformly distributed int value between 0 (inclusive) and n (exclusive) from this random number generator's sequence
Throws:
IllegalArgumentException - if n is not positive

Given a mathematical expression, remove the redundant brackets from the expression.
e.g. input: (a + (b*c)) * (d * ( f * j) )
output should be: (a + b * c) *d * f * J

operations to support: +, -, /, *, ++, also ternary operators.

Write a function to populate the best (lowest cost) path in a 64x64 weighted grid from a given start cell to a destination cell.

You have unique ASCII characters. How you can sort them ?

Run time complexity of approach ?

You are given with space of binary codewords, and you have to come up with an algo to generate all subspace of size 2^1 , 2^2 ,2^3 . . .2^n of that set.
subspace is defined as:
1. it should have the 00..000 code word.
2. it should satisfy closure property. ie if we add any 2 codewords then result shud lie in the subspace.
Note: code words are to be added simply under modulo 2. no concept of carry is there.
ie. 1111 + 1010 = 0101

Reverse words in a sentence.
Ex:
Input: "reverse the word"
Output: "word the reverse"

How can you implement queue?
I told him about list, array, stack implementation of queue.

Find the most frequently occurring element in a BST. In this BST we can have leftnode<=rootnode<=rightnode.

//Q. Write an algorithm that will take two dates and tell you if they are more than a month apart, less than a month apart or exactly a month apart.

1. What is difference between override and overload
2. abstract. when will u use abstract
3. what is an interface
4. what is difference betwwen array and link list
5. what is a tree
6. what is a map\dictionary
7. Explain (orally) how would you implement a dictionary via a tree

There are different buildings in one environment, each with machines that can handle one request at a time. How would you design the request handling so that there is no single fail-point and is scalable.
Hint: It is ok if a request is sent to a machine that is already servicing another request. We can handle requests that come back from a machine. But he didnot want a lock on a single file that contained the data of empty machines
Follow up question was, lets say BLDG-A has 250 free machines, BLDG-B has 500 free machines, BLDG-C has 100 free machines and BLDG-D has 0. How would you assign requests? What if you had 850 requests at the same time? Why would you assign what you did?

Given a set of array of size n, return all possible subset of size k.
example: if arr = { 1,2,3,4,5,6} , k=2;
return result is: {1,2};{1,3};{1,4};{2,3};{2,4};{3,4}
or a single array {1,2,1,3,1,4,2,3,2,4,3,4}

When is that we we want to use "user virtual address" instead of "kernel virtual address"? List some situations when we cannot go with kernel virtual address.