CareerCup

Given a list of n points in 2D space. Lets call them (X1,Y1), (X2,Y2) .... (Xn,Yn). Find the optimal way to retrieve the result of following query.

SELECT min(X) FROM (2D Points) WHERE Y between Ymin and Ymax.

Code to check if a given short string is a substring of a main string. Can you get a linear solution (O(n)) if possible?

Given a circular linked list, find the mid element of the linked list.

Design an algorithm to search for Anagrams of a word in a dictionary. The interviewer stressed on not processing all the words in the dictionary.

Sort an array which only has 0's and 1's. Do not use count sort.

Q1. What is inheritance
2. Polymorphism
3. Diff between Pure Virtual class and Virtual Class
4. Adv and dis-adv of C# and C++ over each other
5. Sequence in which constructors are called when a child class object is created and why is the order so.

Given a rotated sorted array, find the MIN of the array.

He pointed out a mistake in my
int middle = (begin+end)/2 which could overflow if the array size was INT_MAX.
Answer was:
middle = (end-begin)/2 + begin

Given a binary tree, print its perimeter:

node, left->most nodes from top to bottom, leaf nodes from left-> right, right->most nodes from bottom to top

----------------------------1
-----------------------2--------3
------------------4-----5-----6--------7
-------------8------9-----10------11-----12

should print:
1-2-4-8-9-5-10-11-12-7-3

5 because it doesn't have any children. 10 and 11 are children of 6 and 8 & 9 are children of 4.
Apologies for the messy diagram.

Given a Binary tree and a node, return it's post-order predecessor

Single Initialization :

Global variable x, initialized to 0.

Implement a function that can be called by multiple threads simultaneously or sequentially.
The value of x should be set to the current time only once. If it is already set, the value shouldn't be updated.

Make sure that the function doesn't become a bottleneck

Given a BT and 2 nodes, find LowestCommonAncestor

Find the Max sum subsequence in array

Given 'n' coins, print the number of ways to form an amount 'A' . This is a standard denomination problem with one small twist(We have only one coin of each type,not infinite number,if we choose one coin for making change we should not choose it again) . Can somebody give a code with explanation ?

Example:

Amount:3 coins : 1 2 3

There are only two ways (1,2)(3) not (1,1,1)(1,2)(3)

Write a program to calculate Sum of two singly linked lists.
e.g.

1-->2-->3
8->9->10
.
Result list should be 10-->2-->3

You are not allowed to make any change in input lists. Those are read only.

Given a BST find Ceiling value of given key

8
                  6     12
                2   4 11    14

key = 8 return 11
key = 1 return 2
key = 16 return Null

Iteration and Recursion both

Q:
Given a binary tree with nodes that have left, right pointers pointing to the left and right children respoectively. It also has a neighbor pointer that currently Points to null.
Write a function to make it point to its neighbor.

E.g

1
               2      3
            4     5 6     7

1.sibling should point to null
2.sibling should point to 3
3.sibling should point to null
4.sibling should point to 5
5.sibling should point to 6
6.sibling should point to 7
7.sibling should point to null

Iteration and Recursion both

4 men- each can cross a bridge in 1,3, 7, and 10 min.
Only 2 people can walk the bridge at a time. How many min. minutes would they take to cross the bridge.

The probability of a bus passing through a certain intersection in a time window of 20 min. is 0.9
What is the probability of the same bus passing through the same intersection in 5 min.

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

Implement a simple regex parser which, given a string and a pattern, returns a boolean indicating whether the input matches the pattern. By simple, we mean that the regex can only contain one special character: * (star). The star means what you'd expect, that there will be zero or more of any character in that place in the pattern. However, multiple consecutive stars are allowed. Some examples of valid input (and expected output):

f(a*b, acb) => true
f(abc*, abbc) => false
f(**bc, bc) => true

Design a class structure for an airport terminal, where your primary use case is allocating runway time to approaching aircraft. For example, an instance of a terminal may have only two runways of different lengths and must schedule these among five aircraft of different types requesting permission to land.

Write a service or services to support tic-tac-toe between two players, on an infinite board. Normal rules apply (i.e. three in a row to win), but the players are not limited to a 3X3 board and can choose to place an X or an O in any arbitrary, positive (i, j) position. Solution should be as space and time efficient as possible. Your service is only responsible for maintaining and updating the state of the board between two players, given their sequence of moves.

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

Given a sequence of numbers (or array).Find the maximum distance between all the same numbers.Like you have 1,2,3,4,1,1,7,4 so max(1)=5,max(2)=0 max(4)=4. etc.

Given an array of integers, find all sub-arrays whose elements sum zero.
1.-1,4,-4 has 3 such arrays 1 to -1, 1 to -4 and 4 to -4

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.

Design a task scheduler

Design a vending machine.

array of numbers are given. WAP to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Follow up: After writing program to return the largest sum modify it to return the start and end index of such a subarray.