CareerCup

There is a sorted array of integers (suppose sorted in "ascending order"). How will you find a specific element in an array? You can not use traditional iterative method to find a specific element in an array.

Add two integers which cannot be stored even in long long int.

write a program to serialize and deserialize a Binary tree

write a program to return the highest value from a binary tree (note: not BST)

write a program to validate a BST and state the complexity (assume payload is integer values)

Data-structure and algorithm used in Load Balancer??

Explaining algorithm write code for it

Function to reverse a c style sub-string
start - points to the first character to be reversed
end - points to character after the last character to be reversed
Note: STL not allowed
void reverse(char* start, char* end)

1. N-Petrol bunk problem: There are n petrol bunks located in a circle. We have a truck which runs 1 km per 1 liter (mileage 1kmpl). Two arrays are given. The distances between petrol bunks are given in one array. Other array contains the no of liters available at each petrol bunk. We have to find the starting point such that if we start at that point , you we would able to visit entire circle without running out of fuel. Initially truck has no fuel

write a code to print the second largest element in a list
Shortest possible complexity.

A List PARENTLIST which contains primitive type and List L, this List L further can have primitve type and List L and so on. Given a Root node calculate how many List it have

For a given number, print this number in words(in Indian style number system).
eg:
i/p 345 o/p: three hundred fourtyfive
i/p 3145 o/p: three thousand one hundred fourtyfive
i/p 314520 o/p: three lakh fourteen thousand five hundred twenty.


* http://en.wikipedia.org/wiki/South_Asian_numbering_system

If a function is der mostCommonChar(String str, int num) ,
1-.First input is Aabra Ka Daabra and second argument is 1 then the function should return first most repeated character in the string .Means in sorted descending .
2-> First input is Aabra Ka Daabra and second argument is 2
then the function should return second most repeated character in the string
like wise 3rd 4rth ....etc

Write a C program to find the number of shift required to convert one string to another. Check all the corner cases.

Eg: abc to acb o/p shd be 2 as 'b' shifted from 1st index to 2nd and 'c' shifted to 1st from second.

You have a very large file of integers which cannot be loaded into memory at once. How would you find the ten largest numbers of that file?

Let A be an array of size n, containing positive or negative integers, with A[1] < A[2] <...< A[n]. Design an efficient algorithm (should be more efficient than O(n)) to find an i such that A[i] = i provided such an i exists. What is the worst case computational complexity of your algorithm?

Problem statement
You are planning a big programming conference and have received many proposals which have passed
the initial screen process but you're having trouble fitting them into the time constraints of the day -- there
are so many possibilities! So you write a program to do it for you.
· The conference has multiple tracks each of which has a morning and afternoon session.
· Each session contains multiple talks.
· Morning sessions begin at 9am and must finish by 12 noon, for lunch.
· Afternoon sessions begin at 1pm and must finish in time for the networking event.
· The networking event can start no earlier than 4:00 and no later than 5:00.
· No talk title has numbers in it.
· All talk lengths are either in minutes (not hours) or lightning (5 minutes).
· Presenters will be very punctual; there needs to be no gap between sessions.
Note that depending on how you choose to complete this problem, your solution may give a different
ordering or combination of talks into tracks. This is acceptable; you don’t need to exactly duplicate the
sample output given here.
Test input:
Writing Fast Tests Against Enterprise Rails 60min
Overdoing it in Python 45min
Lua for the Masses 30min
Ruby Errors from Mismatched Gem Versions 45min
Common Ruby Errors 45min
Rails for Python Developers lightning
Communicating Over Distance 60min
Accounting-Driven Development 45min
Woah 30min
Sit Down and Write 30min
Pair Programming vs Noise 45min
Rails Magic 60min
Ruby on Rails: Why We Should Move On 60min
Clojure Ate Scala (on my project) 45min
Programming in the Boondocks of Seattle 30min
Ruby vs. Clojure for Back-End Development 30min
Ruby on Rails Legacy App Maintenance 60min
A World Without HackerNews 30min
User Interface CSS in Rails Apps 30min
Test output:
Track 1:
09:00AM Writing Fast Tests Against Enterprise Rails 60min
10:00AM Overdoing it in Python 45min
10:45AM Lua for the Masses 30min
11:15AM Ruby Errors from Mismatched Gem Versions 45min
12:00PM Lunch
01:00PM Ruby on Rails: Why We Should Move On 60min
02:00PM Common Ruby Errors 45min
02:45PM Pair Programming vs Noise 45min
03:30PM Programming in the Boondocks of Seattle 30min
04:00PM Ruby vs. Clojure for Back-End Development 30min
04:30PM User Interface CSS in Rails Apps 30min
05:00PM Networking Event
Track 2:
09:00AM Communicating Over Distance 60min
10:00AM Rails Magic 60min
11:00AM Woah 30min
11:30AM Sit Down and Write 30min
12:00PM Lunch
01:00PM Accounting-Driven Development 45min
01:45PM Clojure Ate Scala (on my project) 45min
02:30PM A World Without HackerNews 30min
03:00PM Ruby on Rails Legacy App Maintenance 60min
04:00PM Rails for Python Developers lightning
05:00PM Networking Event

Adding Very Large Numbers. Write clean code for it. please check all corner cases..

Number can be really really large

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)

Consider a city with 50 locations each numbered from 0 to 49. Mr. XYZ runs a taxi service in a city. He has 25 Taxi’s to service the passengers. When passenger needs a taxi he makes a call to Mr. XYZ and give details like his current location as a source, and where he is willing to travel as a destination. He also tells max time he can wait for a taxi. In return Mr. XYZ either allocate a taxi to the passenger or tell him request can’t be satisfied within the given max_waiting time. Allocated taxi travels from its current location to the passengers pick-up point i.e. the source. This travel is termed as non revenue travel. Mr. XYZ charge passenger only for the distance from source to the destination. After dropping passenger to the destination taxi waits for call from Mr. XYZ to serve next passenger.
Let’s assume we know all TaxiHireRequests in advance. We also know the distance and time to travel between any two locations in the city.


Write a program which will choose the taxi’s such that sum of non_revenue distance travelled by all the Taxi’s is minimum and the number of unsatisfied requests are minimized. Also print the total non_revenew distance and number of unsatisfied requests.


pseudo helper structures.
struct TaxiHireRequest{
int Time Of Request;//Number of seconds from 12AM
int Source; // an int from 0 to 49
int Destination;// an int from 0 to 49
int Maximum waiting time // in seconds;
}[200]


struct Taxi{
int location;//an int from 0 to 49
bool isHired//true or false
}[25]


int Distance[50][50];
int Time[50][50];
// Extend the structure whenever required.

You are on a point on Google Maps (longitude, latitude). You select a radius, and expect to get a list of all the places within that radius. How would you implement this?

How would you implement live search for people's names (only firstname and lastname, or lastname and firstname) like in facebook's search, retreiving the top 5, knowing a value between 0 and 1 for every one of them. If you are close friends then the value will be bigger. You should output the first 5 values in descending order.

0 1 1 T 1
T 1 1 1 1
0 0 T 1 2

Given this 2d matrix where 2 is the entry point, 1 is land and 0 is water. T stands for treasure whose value is 12.You have to get the maximum value by starting from 2 and coming back to 2.Every time you move in the land there will be a penality of -2.
So starting from [2,4] and traversing as below
2,4 -> 1,4->0,4->0,3->0,4->1,4->2,4
will give you points as:
-2-2-2-2-2-2+12 = 0
Any paths can be traversed any number of times but treasure can be collected only once.You can go to other treasure also provided that gives you maximum value.
What is the maximum value you can get from this 2d array if you start from starting point and end also at the starting point.

Given a sorted array consisting 0's and 1's. find the index of first '1'. write a complete program which takes less time complexity. and test all boundary conditions also.
Eg: If given array is 0,0,0,0,0,0,1,1,1,1 the out put should be 6.

There are lots of string in a file. Find the longest string that could be made from the other strings in the file.

Eg.
the
there
after
thereafter
reaf

ans.
thereafter

Given an integer N, populate an array of size N with the first N sum-of-squares. In other words, if you were given N=3, your array would be [1, 5, 14] (1^2, 1^2 + 2^2, 1^2 + 2^2 + 3^2).

How do you find the greatest 1000 elements in a list of a million elements? No other information given. What would be the runtime? Hint: You can do better than O(n log n). I didn't realize but it could be possible with Tree or Heaps.

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

function takes input x , y , A and N
returns true if
there are atleast N pairs of x and y satisfying
x^3 + y^3 = A;

all inputs are postive integer values

Code to create a file system.... Have classes like directory, file and all

please write the full code

In a BST, I want to replace all nodes with value which is the sum of all the nodes which are greater than equal to the current node.
5
2 10

Output -->
15
17 10