CareerCup

Which will take less time to retrieve the data if numbers are present in hashmap and sorted array .

An array of zero and non zero integer are their having range 10000 (i.e length of array is 10,000)
Arrange the array in such a way that zero comes first and after that the non zero integer.

Find duplicates in infinite range .
Which data structure to be used to give efficient solution.?
I answered HashMap .

How to implement using boolean array.?

Given a sorted array which is rotated n number of times. Find out how many times the array is rotated. Time complexity should be less than O(n).

Given a Binary Search tree along with the parent pointer, find the next largest node for the given node. Give the time and space complexity. The node Structure is
class Node {
Int data;
Node left;
Node right;
Node parent;
}

Given a string in the form of a Linked List, check whether the string is palindrome or not. Don’t use extra memory. Give the time complexity. The node structure is
Class Node {
Char data;
Node next;
}

Add a number to array and if there is carry increase array size.
---------------------------
For example input = {7,3,5,3,9} convert this to number 73539, add 1 so it becomes 73540 and convert to array {7,3,5,4,0}.
Array can be of any length, so you can't always represent array in form of in-built number format. So you have to do this summation in-place. Also, how would you increase array size in-case input = {9,9,9} so output = (1,0,0,0}

Assume, all elements of arrays are between 0 and 9.

Write a Javascript program for the following problem -
(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.

Max distance between two nodes of binary tree. Distance is # of branches.

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.

Step 1: Write a Job Handler class that can handle multiple Requests that are trying to access a single Resource. Each Resource can only be allocated by one Requestor at a time. The requests should be handled in the order in which they are received by the Job Handler.
Step 2: Extend this class to handle multiple Resources.
Step 3: Do not allow the same Requestor to submit a Request for two Resources simultaneously.

Given 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).
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

Given a string, find the longest possible even palindrome (length of palindrome is even) from it.
Eg:
Input: abcicbbcdefggfed
Output: defggfed (length is 8)

Available palindromes are
1) bcicb - has odd length
2) cbbc - even length
3) defggfed - longest palindrome with even length

This question was asked in a telephonic interview for my friend. I will be posting his solution in a day.

Pairwise swap elements of a given doubly linkedlist.
Node has prev and next pointers.

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?