CareerCup

You are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge. Your task is to find the shortest path from a to b satisfying the above condition.

You are given a n x m grid consisting of values 0 and 1. A value of 1 means that you can enter that cell and 0 implies that entry to that cell is not allowed. You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) such that you can only move in the right or down direction from every cell. Your task is to calculate the total number of ways of reaching the target.
Constraints :-
1<=n, m<=10, 000

There is a meeting scheduled in an office that lasts for time t and starts at time 0. In between the meeting there are n presentations whose start and end times are given i.e. the ith presentation starts at s[i] and ends at e[i]-1. The presentations do not overlap with each other. You are given k, the maximum number of presentations that you can reschedule keeping the original order intact. Note that the duration of the presentation can't be changed. You can only change the start and end time. Your task is to maximize the longest time period in which there is no presentation scheduled during the meeting.
Constraints :-
1<=t<=1, 000, 000, 000
0<=k<=n
1<=n<=100, 000
e[i]<=s[i+1], 0<=i <n-1
s[i] < e[i] for 0<=i<=n-1

Given an array of integers find the maximum value of a[i] - a[j] + a[k]
with constraints i < j < k and a[i] < a[j] < a[k]

Implement following method of ScheduledExecutorService interface in Java

schedule(Runnable command, long delay, TimeUnit unit)
Creates and executes a one-shot action that becomes enabled after the given delay.

scheduleAtFixedRate(Runnable command, long initialDelay, long period, TimeUnit unit)
Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given period; that is executions will commence after initialDelay then initialDelay+period, then initialDelay + 2 * period, and so on.

scheduleWithFixedDelay(Runnable command, long initialDelay, long delay, TimeUnit unit)
Creates and executes a periodic action that becomes enabled first after the given initial delay, and subsequently with the given delay between the termination of one execution and the commencement of the next.

Write your own class for key value store which has four methods:
put(key,value)
get(key)
getRandom() this should return a random value with equal probability

deleteWithKey(key)


I was allowed to use hashmap internally to store data.

this was my second technical phone interview because they wanted to get some more idea about my technical skills.

At first Interviewer asked me to write a problem to solve sudoku and return error if sudoku is invalid.

I told him I already had seen the problem before and he said he really appreciates my honesty.

this was my second technical phone interview because they wanted to get some more idea about my technical skills.

Given an array of integers find all combination of numbers (regardless of length) that add up to a particular sum. (Subset sum problem)

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.

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.

Design payments system like Google Pay or Paytm.

Design QR code system for a grocery shop.

You have a bit pattern and an infinite stream of bits coming in. You need to raise an alarm whenever the given pattern comes. Storing the stream is not allowed.

Design a Notification Service. Notification can be sent to multiple devices.

Design a job workflow system wherein a job is defined as sequence of steps. This system will take jobs and execute as per the steps in job. The steps can be conditional(if this then do this else do that). This system should be able to handle multiple jobs, should be fault tolerant etc

Design and implement a Message broker which can handle high throughput and is fault tolerant.

Design a workflow system. You need to implement pause/continue operations of the workflow using your database. Essentially, the interviewer was looking completely manage workflow system using database.

Design a finite state machine

Design slack like collaboration tool

There is a notepad which accepts only four operations:
1. Character X
2. select all
3. copy
4. paste
Given n number of operations, provide the sequence of choices that gives maximum characters in the notepad.

Given two async streams -
Trip : {tripId, date, city}
Bill: {billId, tripId, date, amount}

Design a system to get real time aggregated view of following nature
City, TripCount, TotalAmount

Events in both streams can be out of sync or duplicate. But result needs to be accurate and realtime.

Design a Scheduler Service which can handle high throughput with minimal latency. Should be fault-tolerant and distributed.

Design a log4j style logging library for a high throughput multi threaded application.

How would you implement jQuery' s addClass and removeClass functions using vanilla JS? What other variations you can use? Can you pass multiple parameters for classnames ? How will you make these vanilla JS functions asynchronous? Make this component re-usable.

The implementation must respond to something like this:

$('#container')
.addClass('blue')
.addClass('bg-lime')
.addClass('bold')
.addClass('font-medium-italic')
.addClass('border-solid-pink');

In a Binary maze with 0 and 1, 0 is the valid cell to which we can travel and 1 means that the cell is blocked. Given source and destination. We have to find-
1. IF path exists, if yes, find shortest path.
2. If we are given a chance to toggle single cell from 1 to 0 , which cell you will toggle so that you will surely get the shortest path.

Design a system like HackerRank/Codechef.

Design a concurrent hashmap.

Please point me to the link if this has been discussed before.
They wanted design with code snippet of the classes.

Given lat long of cabs in a city(lat long keeps changing)
Implement a function getNearby(lat1,long1) which returns all cabs in a circle of radius R from lat1,long1.
Which datastructure will u use?
FollowUp qs: Hows it implemented using a database like MySQl or Postgres.

You have two arrays of strings, words and parts. Return an array that contains the strings from words, modified so that any occurrences of the substrings from parts are surrounded by square brackets [], following these guidelines:

If several parts substrings occur in one string in words, choose the longest one. If there is still more than one such part, then choose the one that appears first in the string.

Example

For words = ["Apple", "Melon", "Orange", "Watermelon"] and parts = ["a", "mel", "lon", "el", "An"], the output should be
findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"].

While "Watermelon" contains three substrings from the parts array, "a", "mel", and "lon", "mel" is the longest substring that appears first in the string.

Convert a string with digits into a literal representation of the number like: 1001 to one thousand one