CareerCup

Given N shop coordinates on a 2-d plane, Find the nearest shop from a man whose coordinates are given.

Give you a text file, remove duplicated lines.

A string consists of ‘0’, ‘1’ and '?'. The question mark can be either '0' or '1'. Find all possible combinations for a string.

Given two two integer arrays. Find the longest common subsequence.
eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]

Verify if S2 = {5,8,2} is a subset of S1 = {1,5,4,6,8,2} and S3 = {5,8,2,7} is not a subset of S1.

Verify if the given strings is an anagram.
Ex: Str1: LISTEN, Srt2: SILENT.
Alter the program if there is more than one letter that repeats in any one of the strings.

Write a code to return a value 'True' if the number '1' throughout the array appears consecutively. Ex: S = {1,1,1,0,0,3,4}.
Else, return 'False' if the array does not have the given number (char = '1' in this case) in the consecutive order. Ex: S = {1,1,0,0,1,3,4}

Given an integer 'n', create an array such that each value is repeated twice. For example

n = 3 --> [1,1,2,2,3,3]
n = 4 --> [1,1,2,2,3,3,4,4]

After creating it, find a permutation such that each number is spaced in such a way, they are at a "their value" distance from the second occurrence of the same number.

For example: n = 3 --> This is the array - [1,1,2,2,3,3]

Your output should be [3,1,2,1,3,2]

The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.

Return any 1 permutation if it exists. Empty array if no permutation exists.

Follow up: Return all possible permutations.

Given

colors = ["red", "blue", "green", "yellow"];

and a string

str = "Lorem ipsum dolor sit amet";

write a function that prints each letter of the string in different colors. ex. L is red, o is blue, r is green, e is yellow, m is red, after the space, i should be blue.

Given a List of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.

There is a queue which contains some data. There are multiple applications running as distributed systems. These application reads data from the queue and stores them in the DB. But it should store the data in the same order in which it is present in the queue.

Implement an iterator<WordAndCount> which takes iterator<String> and its next() method returns the count for same word in a row. I was also asked to implement hasNext method.

WordAndCount class had two properties:
1. Word
2. Count

I was asked to implement hasNext() and next() method which basically returns a WordAndCount object.

To make it clear, following is the example:

lets say Iterator<String> has following values:

{foo,foo,foo,bar,foo,bar,bar}

iterator<WordAndCount> next() method should return this:

{{foo,3},{bar,1},{foo,1},{bar,2}}

It seemed like an easy problem and because we ran out of time during coding i think interviewer didn't ask me the follow up question. Interviewer was nice and he told me he doesn't expect me to code in time limit but he only wants to see how i approach the problem.

it will gain you more knowledge,intensify your soft skills,strong work ethics and grow your network,what is it?

Given a nxn grid with 1's and 0's find the length of largest black square formed with 1's.

So for below example:

00000
11110
01111
01110

The largest square length is 3.

With dynamic programming it can be done in O(n^2) time

It was a technical screen but it was taken in person for an event.

;***************************************************************************
; Imagine you have received a binary to reverse and you stumbled upon this 
; function. What can you tell me about this function? Does anything stand 
; out that makes you want to take a closer look? 
;
; At a high level, explain what is going on. Then we will go into this code 
; in more detail
;***************************************************************************

Write a program to find the given new program can be scheduled or not?
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.

As the P4 overlaps with P1, So P4 cannot be scheduled.

Given movement of Robot -
G-GO one unit
L-Turn left
R-Turn right

Given an input of string have to find whether there exists a circle which the robot would traverse. Input of string is the set of G,L,R have to return yes or no.

Given a list of strings. Check whether any two strings, if concatenated will form palindrome or not.

There is a hierarchical structure in an organization. A party is to be organized. No two immediate subordinates can come to the party. A profit is associated with every person. You have to maximize the total profit of all the persons who come to the party.

Lonely Pixel
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))

Design a vending machine with following functionalities
Three types of Users : User, Operator, Admin
User can select and buy multiple items at a time. Money can be inputted multiple times (you will get the item if there is a time gap > 30 secs). He can also do window shopping (see only the prices of items and buy nothing)
Operator can load the items and mark the items as expired if needed, gets notified if a product goes out of stock.
Admin can own multiple vending machines, he should have a analytics report of the items purchased in a month. He can also change the prices directly and it should reflect in all the vending machines which he owns.
Exception handling in all the edge cases
Both HLD and LLD were expected.

You have been given a set of inter-dependent tasks along with the time taken to execute them. We have more number of parallel processors available than the number of tasks given. There could be multiple starting tasks. There could also be cyclic dependencies. Calculate the minimum time required to complete all the task.

Given unsorted array, find how many elements can be found using binary search
- ex : [5,4,6,2,8] -> Ans : 3 -> '6' and '8' and '5' can be found using binary search

Implement an api that let's users create multiple timers. You can only use one system timer in your implementation though. For example a user can write:

timer.startTimer(3, callback)
timer.startTimer(7, callback)
timer.startTimer(1, callback)

and the user will get three callbacks 1, 3, and 7 seconds later. In startTimer you only have one timer that you call like this:

System.startTimer(seconds, callback)

but it can only be called once it has finished with the previous timer.

Brace Expansion
Given a string, perfrom the brace expansion
For example,
Input: s = "a{d,c,b}e"
output: {ade , ace , abe}

Given a rectangle with width 'W' and height 'H', you have to fit a string 'S' in it with maximum possible font size
The font size ranges from 1 to 30
You are given two APIs getCharacterWidth(char c , int font_size) and getCharacterHeight(int font_size)
getCharacterWidth(char c , int font_size): returns the width of a character for a particular font size
getCharacterHeight(int font_size): returns the height of characters for a particular font size

How will you implement organizational chart? Implement two methods -
isPeer - Should return true if two employees have same managers.
isManager - should return true if manager is management chain of given employee.

Relation between 2 animals is given.
A is child of B
C is child of B
A is child of D

An animal can be child of 0 to 2 parents. With this given data, find out if two animals are related to each other.
Follow up question was - Maternal side animals, should not be related to patrernal side family.

You have a 3x3 grid. In each cell you can have two colors, white or black. At the beginning, the matrix has some cells painted white and others black.
If you change a color cell, that is, grid [i] [j] the cells grid [i-1] [j], grid [i + 1] [j], grid [i] [j-1] and grid [ i] [j + 1] also change (if these positions do not leave the 3x3 grid), that is, if they were white, they change to black.
Return, the minimum number of cells you have to flip for the 3x3 grid to be totally white. If you cannot do this, return -1!
Sample input/output - ibb.co/3Y0WVNR

Given array of integer, count number of distinct sub array such that it has at most k odd elements and two sub array differ if only when they have at least one member differ.

Example:
{3, 2, 3, 4}, k = 1;
output; 7
[ [3], [2], [4], [3,2], [2,3], [2,3,4],[3,4] ]; Note we did not count [3,2,3] since it has more than k odd elements.

Example 2:
{6, 3, 5, 8}, k = 1;
[ [6], [3], [5], [8] , [6,3], [5,8] ] = 6
We did not count [3,5] as it has > k odd elements

Example 2:
{2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12}
There are these many arrays ;
[2], [2] , [5], [6], [9] , [2], [11], [9], [2], [11], [12]
[2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 9] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [5, 6, 9] , [6, 9, 2] , [9, 2, 11] , [2, 11, 9] , [11, 9, 2] , [2, 11, 12] , [2, 2, 5, 6] , [2, 5, 6, 9] , [5, 6, 9, 2] , [6, 9, 2, 11] , [9, 2, 11, 9] , [2, 11, 9, 2] , [11, 9, 2, 11] , [9, 2, 11, 12] , [2, 2, 5, 6, 9] , [2, 5, 6, 9, 2] , [5, 6, 9, 2, 11] , [6, 9, 2, 11, 9] , [9, 2, 11, 9, 2] , [2, 11, 9, 2, 11] , [11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2] , [2, 5, 6, 9, 2, 11] , [5, 6, 9, 2, 11, 9] , [6, 9, 2, 11, 9, 2] , [9, 2, 11, 9, 2, 11] , [2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9] , [5, 6, 9, 2, 11, 9, 2] , [6, 9, 2, 11, 9, 2, 11] , [9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9] , [2, 5, 6, 9, 2, 11, 9, 2] , [5, 6, 9, 2, 11, 9, 2, 11] , [6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2] , [2, 5, 6, 9, 2, 11, 9, 2, 11] , [5, 6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9, 2, 11, 12]

But only 18 get qualified as there are duplicates like [9, 2, 11] etc.

Qualified arrays are
[2] , [5], [6], [9] , [11], [12] , [2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [6, 9, 2] , [2, 11, 12] , [2, 2, 5, 6]


MY finding so far;
we can use sliding window technique, such that we start counting all sub array of len = 1 to n such that each sub array are different and have at most k odd elements

Here is the code, that i've written for this approach O(n^2)

static int subArraysBrute(int arr[], int k) {


        int count = 0;
        Set<Integer> set = new HashSet<>();

        //Count single length
        for (int i = 0; i < arr.length; i++) {
            count += set.contains(arr[i]) ? 0 : 1;
            set.add(arr[i]);
        }

        int len = 2;
        int odd;

        Set<List<Integer>> setArray = new HashSet<>();
        while (len < arr.length) {

            setArray.clear();
            for (int i = 0; i < arr.length - len + 1; i++) {
                int j = i + len - 1;
                odd = 0;
                List<Integer> ar = new ArrayList<>();
                for (int x = i; x <= j; x++) {
                    if (arr[x] % 2 != 0)
                        odd++;
                    ar.add(arr[x]);
                }

                if (!setArray.contains(ar)) {
                    if (odd <= k) {
                        count++;
                        System.out.print(ar + " , ");
                    }


                }

                setArray.add(ar);
            }
            len++;

        }
        return count;

    }

Other findings;
1. We can't sort the array, as they will ruin the subarray property
2. We can't use simple sliding technique as they will mis so many sub arrays ( moving from left to right window) - I've tried this, this fails like any thing;

Probably, in second idea (sliding window), can be improve further such that once we counted sub arrays, we can run one more time and count those sub array which are left out.