CareerCup

A prefix of a string S is any leading contiguous part of S. A suffix of the string S is any trailing contiguous part of S. For example, "c" and "cod" are prefixes, and "ty" and "ity" are suffixes of the string "codility". For simplicity, we require prefixes and suffixes to be non-empty and shorter than the whole string S.
A border of a string S is any string that is both a prefix and a suffix. For example, "cut" is a border of a string "cutletcut", and a string "barbararhubarb" has two borders: "b" and "barb".
We are looking for such borders of S that have at least three non-overlapping occurrences; that is, for some string that occurs as a prefix, as a suffix and elsewhere in between. For example, for S = "barbararhubarb", the only such string is "b".
In this problem we consider only strings that consist of lower-case English letters (a−z).
Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns the length of its longest border that has at least three non-overlapping occurrences in the given string. If there is no such border in S, the function should return 0.
For example, given a string S as follows:
if S = "barbararhubarb" the function should return 1, as explained above;
if S = "ababab" the function should return 2, as "ab" and "abab" are both borders of S, but only "ab" has three non-overlapping occurrences;
if S = "baaab" the function should return 0, as its only border "b" occurs only twice.
Assume that:
N is an integer within the range [0..1,000,000];
string S consists only of lower-case letters (a−z).
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

You have 100 coins which needs to be distributed among 3 beggars A, B, C. In how many ways you can distribute these 100 coins to all the 3 beggars. Constraint: A cannot have more than 75 coins, B cannot have more than 50 coins, C cannot have more than 25 coins. Write complete code covering all the edge cases. Also suggest test cases.

Given a string T of length n, partition it in n' "phrases" (p1, p2, ..., pn'), such that
pi = pj + c, for some j<i, where + is string concatenation and c is a character

p0 = ''
p1 = pj + c where j < 1


T = p1 + p2 + ... + pn'

For example:
T = aababcabcd = a + ab + abc + abcd
p1 p2 p3 p4

This was the question of two buckets of 3 and 5 litres each. Now measure four litre. I had given 2 solutions but still he wanted 3 solution.
1st soln: fill 3 litre and then interchange in various ways to get 4 litre.
2nd soln: fill 5 litre and then interchange in various ways.

do you have any soln other than this.

Given life time of different animals. Find period when maximum number of animals lived. ex [5, 11], [6, 18], [2, 5],[3,12] etc. year in which max no animals exists.

You have two threads one printing even numbers in order and other odd numbers. Design an algorithm so that it prints numbers in natural order

There are exactly N advertising boards on the highway. Now a company want to advertise on some of these advertising boards (each advertising board costs some money).

Company strategy is that, they want at least 'K' advertisement should be there among M consecutive advertising boards. But at the same time Company want to pay minimum for its advertisement.

Now, what is the total number of ways Company can advertise meeting its minimum cost strategy.

Also 1 <= K <= M <= 50 and M <= N <= 10^9

As for Example: N = 3, M = 2, K = 1 ==> there is only one way for minimum cost, ie. 0C0 , where '0' denotes No company advertisement, and 'C' denotes company advertisement board.

Similarly, for N = 4, M = 2, K = 1 ==> there are 3 possible ways, ie. C0C0, 0C0C, 0CC0.

What is stale object in Java? How will you handle it? For example: You have a Class A as shown below
public class A{
A(){
// code for database connection

}
// code for other method
}
Now,you are trying to create a object A by its constructor. To initialize constructor it throws some exception to create database connection.

A obj = new A().
obj.amethod() ;

If obj.amethod() ; will be executed successfully or not ?

How will you stop your code not to use obj?

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

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.

write a class which exposes only 20 of its Objects containing two methods borrowObject and returnObject .Code must be thread safe.Also write a method to get the number of Live Objects(Objects currently in use by other classes).

C program to convert little endian to big endian. Implement htons. ?
Also convert little to big endian using UNIONS ?

Data for various stocks is coming from various stock exchange continuously. Which data structure is suitable to store these data? Later I was told that if stocks are unique means only one data is there for each stock, then which data structure would you be choosing?

There is large set of sorted data where number of data is not known. How could a given number be find efficiently?

Given an array of integers, find Pythagorean triplets.

i.e. find a,b and c which satisfies a^2 + b^2 = c^2

Integers could be positive or negative.

XML Flat tree goes like this :

<?xml version="1.0" encoding="utf-8"?>
    <?xml-stylesheet type="text/xsl" href="Stack.xsl"?>
    <Items>
        <Item>
            <Id>1</Id>
            <ParentId>0</ParentId>
            <Name>1</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>2</Id>
            <ParentId>1</ParentId>
            <Name>1.1</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>3</Id>
            <ParentId>1</ParentId>
            <Name>1.2</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>4</Id>
            <ParentId>1</ParentId>
            <Name>1.3</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>5</Id>
            <ParentId>1</ParentId>
            <Name>1.4</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>6</Id>
            <ParentId>0</ParentId>
            <Name>2</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>7</Id>
            <ParentId>6</ParentId>
            <Name>2.1</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>8</Id>
            <ParentId>6</ParentId>
            <Name>2.2</Name>
            <SortOrder>0</SortOrder>
        </Item>
        <Item>
            <Id>10</Id>
            <ParentId>3</ParentId>
            <Name>1.2.1</Name>
            <SortOrder>0</SortOrder>
        </Item>
    </Items>
    </XML>

and to display the output like below

1
       1.1
       1.2
             1.2.1
       1.3
       1.4
    2
       2.1
       2.2

Assuming the XML parsing is done and now is in some data structure in memory
and write a C or C++ program to display the output as above...

I pressume that interview was expecting which data structure I may use to store
XML elements values and how do I retrieve the same.

I tried using Binary search tree however it needs to have max of 2 children
for each node. again thought of using array, which i thought is a bit
complicated compare to tree..

guess array would be one of the solutions like a[i][j][k]

for(i=0;i<m;i++
     {
      print (a[i] n );
      for (j=0;j<n;j++);
      print(a[i][j] n);
      for(k=0;k<p;k++)
      print(a[i][j][k] n);
     }

I feel tree would be more efficient way for programming this kind of
problems however I could find other than Binary search tree for programming
this again that is not a solution for this

find the length of integer array using array pointer and remove the redundant element from the list using pointer ?

user inputs values which must be stored. The duplicates must be ignored without scanning the array/list. is there a method to do this?

Escape strings. Convert special ASCII characters to form of ‘\ooo’, where ‘ooo’ is oct digit of the corresponding special character.
The ascii characters that smaller than space are regarded as special characters.

How can you tell if your system is little endian or big endian?

white your own printf() function in c ?

Using two threads you should print "Hello World Hello World Hello World Hello World Hello World Hello World ".

In two threads one should print "Hello: and another thread "World".

Find whether there is a loop in a given liked list or no?
Solved it using two pointer. He wanted me to prov using mathematics, which I don't know :(.

According to the story, four prisoners are arrested for a crime, but the jail is full and the jailer has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed.

The jailer puts three of the men sitting in a line. The fourth man is put behind a screen (or in a separate room). He gives all four men party hats (as in diagram). The jailer explains that there are two red and two blue hats; that each prisoner is wearing one of the hats; and that each of the prisoners is only to see the hats in front of them but not on themselves or behind. The fourth man behind the screen can't see or be seen by any other prisoner. No communication between the prisoners is allowed.
If any prisoner can figure out and say to the jailer what colour hat he has on his head all four prisoners go free. If any prisoner suggests an incorrect answer, all four prisoners are executed. The puzzle is to find how the prisoners can escape, regardless of how the jailer distributes the hats?

Puzzle : There will be two sticks, if you burn each sticks from one side both will burn for an hour. You don't have any watch or stop watch, How you will measure 1 n half our and 45 min?

Find wether there is a loop in a given liked list or no?

I solved it using two pointers. But they were not satisfied as I knew this solution before. They wanted me to solve using Single pointer.

Print 'n' elements of fibonacci series.

public int fibonacci(int n) {
	if ((n == 1) || (n==2)) {
		System.out.print("\t" + 1);
		return 1;
	}
	int temp = fibonacci (n-1) + fibonacci (n-2);
	System.out.println("\t" + temp);
	return temp;

We Have 5 balls And We have to find it out in 2 ways that which 1 is havier or lesser..

How can we implement a geo location plugin on any browser

Write the following function
void drawLine(byte[] img, int len, int wid, int r, int x1, int x2)
such that you draw a line from x1 to x2 at row r.
len is the length and wid is the width of the image/canvas.
Setting a pixel on to draw the line is to set the corresponding bit on the img array
Each byte corresponds to 8 pixels, that is each pixel is a bit in the array