CareerCup

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

Defining a tree as such that the parent node always contains the sum of children nodes.

Coul be something like this):
private static int p_get_nodes_value_sum(TreeNodeCollection v_tree_original)
{
//TreeNodeCollection a_child = v_tree_original.ChildNodes;
//TODO:sum the child nodes

int a_suma = 0;

foreach (TreeNode a_child in v_tree_original)
{
if (a_child.ChildNodes.Count > 0)
a_suma += p_get_nodes_value_sum(a_child.ChildNodes);
else
a_suma += Convert.ToInt16(a_child.Value);

}

return a_suma;

}


public class TreeParentSum: TreeNode{

public TreeParentSum(TreeNode v_tree)
{
int a_sum = p_get_nodes_value_sum(v_tree.ChildNodes);

TreeNode a_node = new TreeNode("PARENTNODE", a_sum.ToString());
a_node.ChildNodes.Add(v_tree);

}
}

there are two arrays named A and B , both of them with k size, they are sorted in acsending order. could you find k-th smallest combinations of ai, bj -->(ai+bj) . 0<=i,j <k.
for example: a = {1, 3, 6} b = {4, 5, 6} then we will get 1 + 4 = 5, 1 + 5 = 6, and 1 + 6 = 7,the result is 5,6,7. does it make you understood? and could anybody do it with less time and space complexity.

Hi guys, thanks for all your suggestions and idea, and finally I get my answer and here are my c++ codes, time complexity is O(k*lgk), and space complexity is O(k):

#include<iostream>
using namespace std;

typedef struct node{
int row;
int col;
int data;
}Node, *PNode;

void swap(PNode &a, PNode &b) {
PNode temp = a;
a = b;
b = temp;
}
void adjust_min_heap(PNode *bin, int i, int k) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int min_index;
if(left < k && bin[left]->data < bin[i]->data) {
min_index = left;
} else {
min_index = i;
}
if(right < k && bin[right]->data < bin[min_index]->data) {
min_index = right;
}
if(min_index != i) {
swap(bin[i], bin[min_index]);
adjust_min_heap(bin, min_index, k);
}
}

void build_min_heap(PNode *bin, int k) {
for(int i = k / 2; i >= 0; i--) {
adjust_min_heap(bin, i, k);
}
}

int *get_k_th_minimum(int *a, int *b, int k) {
PNode *bin = (PNode*)malloc(sizeof(PNode) * k);
int *result = (int*)malloc(sizeof(int) * k);
memset(result, 0, sizeof(int) * k);
int i;
int count = 0;
for(i = 0; i < k; i++) {
bin[i] = (Node*)malloc(sizeof(Node));
bin[i]->row = i;
bin[i]->col = 0;
bin[i]->data = a[i] + b[0];
}
build_min_heap(bin, k);
while(count < k) {
result[count++] = bin[0]->data;
bin[0]->col += 1;
bin[0]->data = a[bin[0]->row] + b[bin[0]->col];
adjust_min_heap(bin, 0, k);
}
for(i = 0; i < k; i++) {
free(bin[i]);
}
free(bin);
return result;
}

void main() {
int a[] = {1, 2, 4};
int b[] = {5, 9, 11};
int k = 3;
int *p = get_k_th_minimum(a, b, k);
for(int i = 0; i < k; i++) {
cout << p[i] << " ";
}
free(p);
getchar();
}

WAP to compare string without library function in c??
1)Program should be designed using Pointers
2)Most efficient i.e lesser number of loops or comparisons??

If we have a very big text file which contains millions of lines of code. On every line there is a one word. We also have a random generator which returns a number between 0 and 1. When we have 1 - this will corresponds to the last line of the file. When we have 0 - to the first one. We want an algorithm which tells as the word (the line) which corresponds to the generated number.

Write an algorithm to check if a tree is binary search tree

Suppose you have some guests arriving at a party. For each guest, you are given the arrival and departure time. When a guest arrives he is given a wine glass and when he leaves he returns that wine glass (it becomes available to be given to another guest). Find the minimum number of wine glasses needed to serve all the guests. The arrival and departure team can only be between 1800 to 2359 hours.