CareerCup

Round 1-question 1 - given an array of stock prices for n days.Write an algorithm to maximize the profit of a customer such that he can buy and sell only once.
-Question 2
Prove that complexity for searching in arraylist is o(n)
and adding is o(1)

write java code to create the following pattern
*
* * *
* * * * *
* * * * * * *
* * * * * * * * *

Round 1-Question 1
1)Given an array of stock prices for 7 continuous days.Write an algorithm to maximize the profit for a customer who buys stock on any day and sells it later.Buying and selling can happen only once and selling should happen on any day after buying

I was asked to design a system on a whiteboard which simulate a executor.
This system has a method that is being triggered every second. I need to add logic to the method (i.e. run jobs).
There is also a method called job_arrived() that is called when a new job arrives.. I need to implement it as well.
I needed to implement a system which tries to run each job right when it is arrived (it has a return value that gets a success status from a black box service). if the job ran successfully that's the end of it..
if not I need to re-run it after 2 seconds (and if that fails as well - there will be no re-runs).
of course - more than one job can be accepted each second.
I was asked to describes the system (describe the classes and method) and consider the system to be large scale one (meaning.. threading is in order here..).
The answer I gave was apparently not multi threaded enough..
any idea to what I should have done?
Thanks guys

https://codejamanalysis.wordpress.com/2017/03/18/crossover-problem-super-stack/

Any Optimized Solution to avoid TLE for 4 test cases. I have tried by implementing Stack using Doubly Linked List.
Still not able to pass test cases!!!

There is a list of 20 words. 10 of them are good works, and 10 of them are bad words. Write a regex of not more than 25 characters which would tell if given word is good or bad. Input would only contain one of these 20 words.
Good words: papa, book, home, cars, jolly, sugar, friend, mother, father, bloomiest
Bad words: ache, slow, torn, slum, boom, rival, wrong, cholera, revenge, arrogant

Input: book
Output: Good

Input: boom
Output: bad

Write Java Code using regex pattern

1. There is a list of 20 words. 10 of them are good works, and 10 of them are bad words. Write a regex of not more than 25 characters which would tell if given word is good or bad. Input would only contain one of these 20 words.
Good words: papa, book, home, cars, jolly, sugar, friend, mother, father, bloomiest
Bad words: ache, slow, torn, slum, boom, rival, wrong, cholera, revenge, arrogant

Input: book
Output: Good

Input: boom
Output: bad

What is the issue with this Producer Consumer Problem. Can you fix it.

public class ProducerConsumerProb {

	public static void main(String[] args) {
		Container container = new Container();
		Turn turn = Turn.PRODUCER;
		Producer p = new Producer(container, turn);
		Consumer c = new Consumer(container, turn);
		Thread pro = new Thread(p);
		Thread con = new Thread(c);
		pro.start();
		con.start();
	}

	public static class Producer implements Runnable{
		Container container;
		Turn turn;
		public Producer(Container integer,Turn turn) {
			this.container = integer;
			this.turn = turn;
		}
		
		@Override
		public void run() {
			for(int i=0;i<10;i++){
				Turn temp = null;
				while(true){
					synchronized (turn) {
						temp = turn;
					}
					if(temp == Turn.PRODUCER){
						break;
					}
				}
				synchronized (turn) {					
					container.setI(i);
					turn = Turn.CONSUMER;
				}
			}
		}
	}
	
	public static class Consumer implements Runnable{
		Container container;
		Turn turn;
		public Consumer(Container integer,Turn turn) {
			this.container = integer;
			this.turn = turn;
		}
		
		@Override
		public void run() {
			for(int i=0;i<10;i++){
				Turn temp = null;
				while(true){
					synchronized (turn) {
						temp = turn;
					}
					if(temp == Turn.CONSUMER){
						break;
					}
				}
				synchronized (turn) {					
					System.out.println(container.getI());
					turn  = Turn.PRODUCER;
				}
			}
		}
		
	}
	
	public static class Container{
		Integer i = new Integer(0);
		

		public int getI() {
			return i;
		}

		public void setI(int i) {
			this.i = i;
		}
				
	}
	
	enum Turn{
		PRODUCER,CONSUMER;
	}
}

There are hierarchy of class like super class and sub class. Yo have to make sure only one object can be create for any class using new keyword. How you implement the class.

find the sum of bit wise OR of minimum and Maximum element of all the subsets whose length is greater than 2 of the given of set.

for ex:-

{1,2,3} is set
then possible subsets of length is{ 1,2},{1,3},{2,3}{1,2,3} answer 1|2 +1|3 +2|3 +1|3=12

Let’s say you have two input arrays with sorted elements. Find the union.

a[] = {2, 10, 14, 19, 51, 71}
b[] = {2, 9, 19, 40, 51}

Union = {2, 9, 10, 14, 19, 40, 51}

why we have a such long number value for object's hashcode in java.can we not have any small numbers or why java is giving that much large number for any object hash code ?

List<Integer> list=Arrays.asList(1,2,3,4,5,6);
Iterator it=list.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
The above code will iterate sequentially through 1 to 6. Can we iterate the same list alternatively so that it will print 1,3,5 without changing the while loop.

Given a number, rearrange the digits of that number to make a higher number, among all such permutations that are greater,one of them is the smallest, Find the smallest greater permutation (the next Permutation).

Examples:
next_permutation (12) = 21
next_permutation (315) = 351
next_permutation (583) = 835
next_permutation (12389) = 12398
next_permutation (34722641) = 34724126

Problem:

Insert + or – sign anywhere between the digits 123456789 in such a way that the expression evaluates to 100. The condition is that the order of the digits must not be changed.

e.g.: 1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100

I have below C solution - Can you please help me to convert to Java. I need this solution in Java.


#include<stdio.h>
#include<conio.h>
int findnumber(int i,int j)
{
int k;
int n;
for(k = 0; k < j; k++)
{
n = i % 3;
i = i / 3;
}
return n;
}
void main()
{
int i, j, k, current, result, operation;
clrscr();
for(i = 0; i < 19683; i++)
{
if(i%3 == 0)
continue;
current = 0;
result = 0;
for(j = 1; j < 10; j++)
{
k = findnumber(i,j);
if(k==0)
{
current = current * 10 + j;
}
else
{
result = result + (operation == 1 ? current : -current);
current = j;
operation = k;
}
}
result = result + (operation == 1 ? current : -current);
if(result == 100)
{
for(j = 1; j < 10; j++)
{
k = findnumber(i,j);
if(k==0)
printf("%d",j);
else
printf("%c%d",k==1?'+':'-',j);
}
printf("\n");
}
}
getch();
}

Need to design and develop java program for assigning rankings to “Premier League” players. To start with all the players would have zero points. After every game, points would be updated for players based on the performance. Design data structure and algorithm to print the player rankings after every game.



Sample input and outputs:

Input to program would be of the format “player Id, points from the game”. Example :

1 2

2 1

3 5

1 2

2 3

3 5

### Problem 3: Theatre Seating

You run a small theater and each month, you have patrons mail in requests for pre-sale tickets. You need to process these ticket requests and either tell them where their party will sit or explain to the patron why you can't complete their order.

You have a few rules that you need to follow when you fill the orders:
1. Fill as many orders as possible
2. Put parties as close to the front as possible.
3. If there are not enough seats available in the theater to handle a party, tell them "Sorry, we can't handle your party."
4. Each party must sit in a single row in a single section. If they won't fit, tell them "Call to split party".

Your program must parse a theater layout and a list of ticket requests and produce a list of tickets or explanations in the same order as the requests.

The theater layout is made up of 1 or more rows. Each row is made up of 1 or more sections separated by a space.

After the theater layout, there is one empty line, followed by 1 or more theater requests. The theater request is made up of a name followed by a space and the number of requested tickets.


Sample input:
```
6 6
3 5 5 3
4 6 6 4
2 8 8 2
6 6

Smith 2
Jones 5
Davis 6
Wilson 100
Johnson 3
Williams 4
Brown 8
Miller 12
```

Your program must produce results to standard output in the same order as the requests, with the name of the person who requested the ticket and either the row and section of the ticket or the explanations "Sorry, we can't handle your party" or "Call to split party."


Sample output:

```
Smith Row 1 Section 1
Jones Row 2 Section 2
Davis Row 1 Section 2
Wilson Sorry, we can't handle your party.
Johnson Row 2 Section 1
Williams Row 1 Section 1
Brown Row 4 Section 2
Miller Call to split party.

Write a program that controls the traffic signals for a four-way intersection. Initially, we consider traffic flowing in straight lines only, no turns. The four directions are S(outhbound) and N(orthbound) on Snell Rd; and W(estbound) and E(astbound) on Weaver Rd. The traffic lights should obey the following rules:

1. Cars arrive in each direction on both roads (Snell and Weaver) at the rate of 1 car per second. That is, 4 cars approach the intersection each second.

2. Only one road (Snell or Weaver) can have a "green" light at one time.

3. It is acceptable for both roads to have the "red" light at the same time. Of course, traffic backs up on both roads if this happens.

4. Start by turning on the traffic on Snell Rd "green" in both directions for 3 seconds; then turn it "red" for one second; then turn Weaver "green" for 3 seconds; and then red for one second.

5. When the light turns from red to green at any intersection, it takes the first car 2 seconds to start moving and cross the intersection. Subsequent cars take 1 second each.

6. At the instant the light turns from "green" to "red", a car may not start moving to cross the intersection; whether that car just arrived at the intersection or was waiting at that intersection.

7. The output should be the number of cars that are waiting at the intersection in each direction at each second, for the first 20 seconds. Do not make the program wait 20 seconds to produce the output: this is only a simulation, so print the output when it's ready.

8. Expected output
```
0: N = 0; S = 0; E = 0; W = 0
1: N = 0; S = 0; E = 1; W = 1
2: N = 0; S = 0; E = 2; W = 2
3: N = 0; S = 0; E = 3; W = 3
4: N = 1; S = 1; E = 4; W = 4
5: N = 2; S = 2; E = 5; W = 5
6: N = 3; S = 3; E = 5; W = 5
7: N = 4; S = 4; E = 5; W = 5
8: N = 5; S = 5; E = 6; W = 6
```

Denver International Airport has decided to give an automated baggage system another shot. The hardware and tracking systems from the previous attempt are still in place, they just need a system to route the baggage. The system will route baggage checked, connecting, and terminating in Denver.
You have been asked to implement a system that will route bags to their flights or the proper baggage claim. The input describes the airport conveyor system, the departing flights, and the bags to be routed. The output is the optimal routing to get bags to their destinations. Bags with a flight id of “ARRIVAL” are terminating in Denver are routed to Baggage Claim.
Input: The input consists of several sections. The beginning of each section is marked by a line starting: “# Section:” ``` Section 1: A weighted bi-directional graph describing the conveyor system. Format: <Node 1> <Node 2> <travel_time>
Section 2: Departure list Format: <flightid> <flightgate> <destination> <flighttime> Section 3: Bag list Format: <bagnumber> <entrypoint> <flightid> ```
Output: The optimized route for each bag `
The output should be in the same order as the Bag list section of the input.
Example Input: ```
Section: Conveyor System
ConcourseATicketing A5 5 A5 BaggageClaim 5 A5 A10 4 A5 A1 6 A1 A2 1 A2 A3 1 A3 A4 1 A10 A9 1 A9 A8 1 A8 A7 1 A7 A6 1
Section: Departures
UA10 A1 MIA 08:00 UA11 A1 LAX 09:00 UA12 A1 JFK 09:45 UA13 A2 JFK 08:30 UA14 A2 JFK 09:45 UA15 A2 JFK 10:00 UA16 A3 JFK 09:00 UA17 A4 MHT 09:15 UA18 A5 LAX 10:15
Section: Bags
0001 ConcourseATicketing UA12 0002 A5 UA17 0003 A2 UA10 0004 A8 UA18 0005 A7 ARRIVAL ```
Example Output: `
0001 Concourse_A_Ticketing A5 A1 : 11 0002 A5 A1 A2 A3 A4 : 9 0003 A2 A1 : 1 0004 A8 A9 A10 A5 : 6 0005 A7 A8 A9 A10 A5 BaggageClaim : 12

Given an array of n elements return true if 3 of the sum of 3 elements is equal to a constant c

Example array a[6,2,3,4] constant c = 9

if a[1] + [2] + [3] == c return true

The size of the array is n

If any set of 3 elements is equal to the constant c, then return false

Longest increasing subsequence, Number of Island, Basic SQL questions like joins, select statement etc, Code for finding the Name in the document. Like based on the property of name (which cannot be written in small case). Find its frequency.

A number of islands. All the rounds had basic DB questions

Number of islands. Big(O).

In the doc file the "Name" without any dictionary. Like finding the property of the name as Starts with the capital letter. Then find the frequency of only names present in the doc. Whiteboard coding

Longest Increasing Subsequence

Given: Collection of sorted (ascending) iterators which return integer value.
Implement hasNext() and next() methods in SuperIterator class that next() method should return sorted values from all iterators.
Note that we can't load all iterators to memory, because they might get values from big file (1TB for instance) and it will lead to OutOfMemoryError.

/*
    iter1: 1,  4,  5, 20, ...
    iter2: 2, 10, 12, 50, ...

    SuperIterator.next() method should return: 1, 2, 4, 5, 10, 12, 20, 50, ...
*/

interface Iterator {
    boolean hasNext();
    int next();
}

class SuperIterator {
    public SuperIterator(Collection<Iterator> iters) {
        
    }
    
    boolean hasNext() {
        //TODO
    }
    
    int next() {
        //TODO
    }
}

Given a string "L*&EVe)))l", write a method which will determine if the input is a palindrome. Ignore all special characters. Uppercase/lowercase should be considered as same.

Imagine a room full of people, with only 1 celebrity in the room. Celebrity is defined as a person who does not know anyone, but everyone knows him/her. Write a method who will take array of people and a person as input and return boolean if the person is a celebrity or not.

Find the missing letters from a string if it doesn't create a pangram.

https://leetcode.com/problems/word-search/description/

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.