CareerCup

LinkedList Reverse

Given a string, find the longest substring with k distinct characters.

e.g - “aaaabbbb”, k = 2, “aaaabbbb”
“asdfrttt” k = 3, “asd”, “frttt”

[Telephonic Question]

input = 8
output =
1 1 1 1 1 1 1 2
3 2 2 2 2 2 2 2
3 3 3 3 3 3 3 4
5 4 4 4 4 4 4 4
5 5 5 5 5 5 5 6
7 6 6 6 6 6 6 6
7 7 7 7 7 7 7 8

import java.util.*;
class Test 
{
	int n;
	Scanner sc;
	void readNumber()
	{
	    sc=new Scanner(System.in);
            n = sc.nextInt();
	}
	void printPattern()
	{                  
	    // write your logic here 

	}
	public static void main(String[] args) 
	{
        Test t = new Test();
		t.readNumber();
		t.printPattern();
	}
}

Object Oriented Design Problem

--------------------------------

Design an OO parking lot. What classes and functions will it have. It should say, full, empty and also be able to find spot for Valet parking. The lot has 3 different types of parking: regular, handicapped and compact.


Use Case:

1. Customer are given a ticket that they can use to redeem to get their vehicle back 

2. Parking spots come in three sizes, small, med, large 

3. Thee types of vehicles, small[Two Wheeler], med[Car], large[Bus] 

    -a small vehicle can park in a small, medium, and large spot 

    -a medium vehicle can park in a medium and large spot 

    -a large vehicle can park in a large spot

4. There are multiple entry gate to park vehicle. So Vehicle should asign nearest posible parking spot

You are given an array of integers. Find the minimum difference between two prime numbers(Positive or negative) in the array when present with minimum time complexity and provide the test data to test the this code.

Remove 3 consecutive duplicates from string.
INPUT:aabbbaccddddc
OUTPUT:cdc

Situation - You have millions of records(Strings) and user is typing "abc" in search box . Your task is to display strings from records in the sequence.

e.g String in the record contain "abc" starting should appear first, then string which has "abc" in the second, should apprear later as below.

String - fabcsdf,asdfabc,dfadsfsdfabc,abckdf,ddfabc...

Displays suggestion like....
abckdf
fabcsdf
ddfabc
asdfabc
dfadsfsdfabc

Question - Which data structure you would use to stor this ?
And how will you implement to get this(shorted) result

Given 2 sorted linked lists, return a linked list that has all the elements and is sorted.

Given 3 strings "s" ssearch" and "sreplace", search string s for the substring ssearch and for every instance of ssearch you find, replace that part of the string with sreplace

Given an NxN Boolean matrix, find how many true regions there are in the matrixj

Create a basic minesweeper game that allows for board creation with custom height, width and number of mines. Create a <click> function that will take in a board location and return whether the user has won, lost, or the number of surrounding mines.

Given a string, print out all of the unique characters and the number of times it appeared in the string

Write a code for reversing letters of string in java.

Given a singly linked list of integers, write a function in java that returns true if the given list is palindrome, else returns false

Convert an unordered tree to a binary tree

merge two binary search trees

Create a RESTful microservice that implements a card shuffling algorithm, as defined below. Should have evidence of test-driven development with unit tests. Use best practices of interfaces and generics for abstraction, preferably implementing a strategy pattern for deploy-time dependency injection of a shuffling algorithm.
Requirements:
· Create a microservice that stores and shuffles card decks.
· A card may be represented as a simple string such as “5-heart”, or “K-spade”.
· A deck is an ordered list of 52 standard playing cards.
· Expose a RESTful interface that allows a user to:
· PUT an idempotent request for the creation of a new named deck. New decks are created in some initial sorted order.
· POST a request to shuffle an existing named deck.
· GET a list of the current decks persisted in the service.
· GET a named deck in its current sorted/shuffled order.
· DELETE a named deck.
· Design your own data and API structure(s) for the deck.
· Persist the decks in-memory only, but stub the persistence layer such that it can be later upgraded to a durable datastore.
· Implement a simple shuffling algorithm that simply randomizes the deck in-place.
· Implement a more complex algorithm that simulates hand-shuffling, i.e. splitting the deck in half and interleaving the two halves, repeating the process multiple times.
· Allow switching the algorithms at deploy-time only via configuration.

Programming Challenge Description:
Develop a service to help a client quickly find a manager who can resolve the conflict between two employees. When there is a conflict between two employees, the closest common manager should help resolve the conflict. The developers plan to test the service by providing an example reporting hierarchy to enable the identification of the closest common manager for two employees. Your goal is to develop an algorithm for IBM to efficiently perform this task. To keep things simple, they just use a single relationship "isManagerOf" between any two employees. For example, consider a reporting structure represented as a set of triples:

Tom isManagerOf Mary
Mary isManagerOf Bob
Mary isManagerOf Sam
Bob isManagerOf John
Sam isManagerOf Pete
Sam isManagerOf Katie

The manager who should resolve the conflict between Bob and Mary is Tom(Mary's manager). The manager who should resolve the conflict between Pete and Katie is Sam(both employees' manager). The manager who should resolve the conflict between Bob and Pete is Mary(Bob's manager and Pete's manager's manager).

Assumptions:
There will be at least one isManagerOf relationship.
There can be a maximum of 15 team member to a single manager
No cross management would exist i.e., a person can have only one manager
There can be a maximum of 100 levels of manager relationships in the corporation

Input:
R1,R2,R3,R4...Rn,Person1,Person2 R1...Rn - A comma separated list of "isManagerOf" relationships. Each relationship being represented by an arrow "Manager->Person". Person1,Person2 - The name of the two employee that have conflict
Output:
The name of the manager who can resolve the conflict Note: Please be prepared to provide a video follow-up response to describe your approach to this exercise.

Test 1:
Test Input
Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie

Expected Output
Mary

Test 2:
Test Input
Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John

Expected Output
Mary

This questing was something related to parse trees. I really don't remember the semantics but needed to extract the complete sentences from the provided parse tress.

Input: A full sentence: (S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a) (NN boy)) (VP (VBG eating) (NP (NNS sausages))))))
Output: James is a boy eating sausages

Input: (NNS Sausages)
Output: Sausages

Input: (NP(DT a) (NN boy))
Output: a boy

For a given string sentence, reverse it.
Input : Hello World
Output : Dlorw Olleh

Input: How Are You Doing Today
Output: Yadot Ginod Uoy Era Woh

You will be given a sequence of passages, and must filter out any passage whose text (sequence of whitespace-delimited words) is wholly contained as a sub-passage of one or more of the other passages.

When comparing for containment, certain rules must be followed:

The case of alphabetic characters should be ignored

Leading and trailing whitespace should be ignored

Any other block of contiguous whitespace should be treated as a single space

non-alphanumeric character should be ignored, white space should be retained

Duplicates must also be filtered - if two passages are considered equal with respect to the comparison rules listed above, only the shortest should be retained. If they are also the same length, the earlier one in the input sequence should be kept. The retained passages should be output in their original form (identical to the input passage), and in the same order.

Input: For each test case a single line comprising the passages (strings) to be processed, delimited by | characters. The | characters are not considered part of any passage.

Output: A single line of filtered passages in the same |-delimited format.

Input1: IBM cognitive computing|IBM "cognitive" computing is a revolution| ibm cognitive computing|'IBM Cognitive Computing' is a revolution?

Output1: IBM "cognitive" computing is a revolution

Input2: IBM cognitive computing|IBM "cognitive" computing is a revolution|the cognitive computing is a revolution

Output2: IBM "cognitive" computing is a revolution|the cognitive computing is a revolution

There is a DNA Strand having values as A , T , C , G.
All combinations are present in the the file.

Write a method which takes starting mutation string , ending mutation string and string bank and calculates the minimum mutation distance required. But the condition is that either of the start or end must be present in the bank.

Input:
AATTGGCC is starting and TTTTGGCA is ending then mutation distance will be 3.
AATTGGCC - TATTGGCC - TTTTGGCC - TTTTGGCA as it takes three mustaion for start to reach the end string and for this , all intermediate string and final string must be present in the bank.


static int findMutationDistance(String start, String end, String[] bank) {


}

You have a string of phrases present. For your simplicity consider them to be integer length.

String s= " I am Tom"
will be stored in an interger array as [1,2,3] where each represents length of each word in the string.

Write a method to compute the longest subsequence such that it is less than given k value.

Input:
3 //length of array
1 //a[0]
2 //a[1]
3 //a[2]
4 // value of k

Output:
2

Input:
4 //length of array
3
1
2
1
4 //value of k

Output:
3


static int maximumLength(int[] a, int k) {


}

write default and parameterized constructor accepting two variables

You have a big .csv file (say the size is 3GB). How efficiently you can process it and put the records in database?

A program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35

Given a file (which can be considered as a String with comma delimiter for the complexity of the question) of usernames and a value k, find top k usernames (with number of logins) who logged into the system the most.

For example -
Input:
User (String) = user1, user4, user2, user1, user3, user1, user2, user3
k (int) = 2

Output:
user1 (3)
user2 (2)
user3 (2)

- Both user2 and user3 should be included since both has same number of logins

Write a java method to find the output with best time and space complexity.

Given a list of numbers ex:(2,15,8) as a string with out any delimiters like space or ',' as str = "2158"; is there a way to parse the string an identify which one is double digit or single digit number ?? like 2,8 are single digit number and 15 is a double digit number

Build an in-memory DB that supports many commands and transactions.
Similar to redis database (Redis.io)

OO design for implementing table tennis game between two players? I just want the class diagram not the whole implementation. Only the class/interfaces names will help.