CareerCup

Write a new data structure, "Dictionary with Last"

Methods:
set(key, value) - adds an element to the dictionary
get(key) - returns the element
delete(key) - removes the element
last() - returns the last key that was added or read.

In case a key was removed, last will return the previous key in order.

Given a grid M x N cells having weight in each cell(any integer),
For every path from TOP-LEFT to BOTTOM-RIGHT, find the minimum weight you come across.(Minimum per path.)
Now from all those minimum weights, find the Maximum.
You can move in all 9 directions.

Is this a trick question?

Given an integer S, you have to count the total number of integral solutions of the equation a+b^2+c^3+d^4<=S, such that 0<=a,b,c,d<=10000 and 0<S<10^15

Edit: Here value can be less than or equal to S, so if input S= 2 ,then output=12
i.e we can consider 0,0,0,1 and 0,0,0,0 etc also as sum will be less than S(i.e 2)

Given two strings Y and Z , return True if y beats z or z beats y .
Beating Criteria : for i in [1,N] y[i]>=z[i] , if this condition is true for any of permutations of y for any of the permutations of z .

Get the sum of all prime numbers up to N. primeSum(N).
Follow-up: If primeSum(N) is frequently called, how to optimize it.

Find a pair that equals to the given target from the list of given two lists.
example:
input:
target = 7
list1= [[1,2],[2,4[,[3,6]]
list2 = [[1,2]]

Output:[[2,1]]

Explanation: There are only three combinations [1,1],[2,1] and [3,1], which use a total of 4,6, 8 respectively. Since 6 is the largest use that does not exceed 7, [2,1] is the only optimal pair.

Example 2:
Input :
target = 10
list1 = [[1,3],[2,5],[3,7],[4,10]]
list2 = [[1,2],[2,3],[3,4],[4,5]]

Output;
[[2,4],[3,2]]

How to divide a circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array.

For e.g If the array is as follow. [6 13 2 10] and k=2 then o/p should be 16(6+10)-15(13+2)=1. As array is circular 6,10 are contiguous element of array.

For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29

Prroblem: write an algorithm to calculate the minimum cost to add new roads between the cities such that all the cities are accessible from each other

int numTotalAvailableCities = 6;
int numTotalAvailableRoads = 3;
int[,] roadsAvailable = { { 1, 4 }, { 4, 5 }, { 2, 3 } };
int[,] costNewRoadsToConstruct = { { 1, 2,5 }, { 1,3,10 }, {1,6,2} ,{ 5, 6, 5 } };
int numNewRoadsConstruct = 4;

public class MinimumCostToConstructNewRoad
    {
        public static int getMinimumCostToConstruct(int numTotalAvailableCities,
            int numTotalAvailableRoads,
            int[,] roadsAvailable,
            int numNewRoadsConstruct,
            int[,] costNewRoadsConstruct)

        {
            int totalCost = 0;
            bool[] Visited = new bool[numTotalAvailableCities];
            int[] Keys = new int[numTotalAvailableCities];
            int[] Parent = new int[numTotalAvailableCities];

            int[,] AdjMatrix = GetAdjecencyMatrix(roadsAvailable, costNewRoadsConstruct, numTotalAvailableCities);


            for (int i=0;i< numTotalAvailableCities;i++)
            {
                Keys[i] = Int32.MaxValue;
            }

            Keys[0] = 0;
            Parent[0] = -1;

            for(int i=0;i< numTotalAvailableCities-1;i++)
            {
                var u = FindMin(Visited, Keys);

                Visited[u] = true;
                for(int v=0;v< numTotalAvailableCities;v++)
                {
                    if(Visited[v]==false && AdjMatrix[u, v]!=Int32.MaxValue && AdjMatrix[u,v]<Keys[v])
                    {
                        Parent[v] = u;
                        Keys[v] = AdjMatrix[u, v];
                    }
                }

            }

           for(int i=1;i< numTotalAvailableCities;i++)
            {
                totalCost = totalCost + AdjMatrix[Parent[i], i];
            }
            return totalCost;
        }


        private static int FindMin(bool[] Visited, int[] Keys)
        {
            int min = Int32.MaxValue; int index = -1;
            for (int i = 0; i < Keys.Length; i++)
            {
                if (Visited[i] == false && Keys[i] < min)
                {
                    min = Keys[i];
                    index = i;
                }
            }
            return index;
        }


        private static int[,]  GetAdjecencyMatrix(int[,] roadsAvailable, int[,] costNewRoadsConstruct,int numTotalAvailableCities)
        {
            int[,] AdjMatrix = new int[numTotalAvailableCities, numTotalAvailableCities];

            for (int i = 0; i < numTotalAvailableCities; i++)
            {
                for (int j = 0; j < numTotalAvailableCities; j++)
                {
                    AdjMatrix[i, j] = Int32.MaxValue;
                }
            }


            int count = 0;
            for (int i = 0; i < roadsAvailable.GetLength(0); i++)
            {
                int start = roadsAvailable[i, count]-1;
                int end = roadsAvailable[i,count+1]-1;
                AdjMatrix[start, end] = 0;
            }

            for (int i = 0; i < costNewRoadsConstruct.GetLength(0); i++)
            {
                int start = costNewRoadsConstruct[i, count]-1;
                int end = costNewRoadsConstruct[i, count+1]-1;
                int cost= costNewRoadsConstruct[i, count + 2];

                AdjMatrix[start, end] = cost;
            }

            return AdjMatrix;
        }
    }

Maximum Pairs

You are given N pencils. You have to make pairs of pencils.

The condition for making pairs is:
If(a,b) is any pair of pencils then b >= 2 * a. Here a and b are the sizes of pencils.

Now you have to find out the number of such pairs and the number of pencils which could not be paired with any pencils.

Note:

You need to pair the pencils in such a manner that the maximum number of pairs are formed.

Input Format:

The first line consists of number of test case T.
Each test case consist of:
- First line consists of a single integer N.
- Second line consists of N space-separated integers denoting the size of pencils Si.

Output Format:

For each test case, print two space-separated integers, first denoting the number of pairs formed and second denoting the number of unpaired pencils.
Answer for each test case should come in a new line.

Constraints
1<T<=10
1<=N<=10^5
0<=Si<=10^5

Sample Input

2
5
1 2 3 4 5
4
1 2 4 4

Sample Output

2 1
2 0

Explanation

In the first test case:-
we can form the following pairs:
(1, 3), (2, 4) and 5 remains unpaired hence maximum pairs are 2
In second test case:-
(1, 4), (2, 4) are two pairs hence no pencil left unpaired

public class Test {
    public static void main(String[] args) {
          }

    static int[] solve(int[] arr) {
        // the value at first index of array to be returned is number of pairs
        // formed and value at second index is unpaired swords.
           }
}

Given a target number and a single number, write a program to find the shortest path to calculate the target number by applying "+-*/" operations to the single number. No parentheses. For example, if we have target number=26 and single number=3 return 3 * 3 * 3 - 3 / 3.

Given a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles


Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it

how would you debug a tablet with a part of its touch screen is broken.

Given an arbitrary tree remove nodes which have data value 0.
As it stats arbitrary tree, I assumed n-ary tree.

Design a Google Sheet System?

Where do you store the data? sql or nosql
How do you maintain concurrency?
How do you display it in frontend, which can be inline editable?

* Build Offices
A company wants to develop an office park in an area that has been divided up into a grid where each cell represents a potential building lot. The goal is for the furthest of all lots to be as near as 1 possible to an office building. Determine the building placement to minimize the distance the 0 most distant lot is from an office building. Movement is restricted to horizontal and vertical, i.e. diagonal movement is not allowed.
For example, there are n = 3 office buildings to build on a grid that is w = 4 lots wide and h = 4 lots high. An optimal grid placement sets any lot within two units distance of an office building. In the distance grid below, offices are cells at distance 0.
1 0 1 2
2 1 2 1
1 0 1 0
2 1 2 1

That represents one optimal solution among several, this array rotated for example.

The function must return an integer that denotes the maximal value among shortest distances to the closest office for each cell.
findMinDistance has the following parameter(s): w: an integer, the width of the grid h: an integer, the height of the grid n: an integer, the number of buildings to place
Constraints:
wxh <= 28

In an interview this question has been asked :
How to fit four characters into an integer, implementation should be in C programming language.

For example, four characters, viz., 'a', 'b', 'c', and 'd' need to be fit into an integer.

I tried to answer this question using ASCII value of the characters.

Please suggest the correct solution.

Given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
and then another series [A != C, D != H, ..., F != A ]

Check whether the equations combined is valid.

For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.

A function receives a big array (about 1G).
after manipulations done on the array it's data
will be erased. What should you're attitude be to dealing with the array? (I didn't understand totally the interviewer's meaning

read the 5'th bit from a byte

Write a function which returns
the multiplication of two inputs,
without using "return"

Imagine you have a computer keyboard that has all the letters mismatched

example:
typing q gives you a
typing w gives you b

all 26 letters in the alphabet are there, but typing one letter will give you another one

you are asked to write an algorithm to find whatever word you tried to type and count how many cycles you did to find the word

a restriction was set you need to type the whole word every time, not go character by character

note: a graph was suggested to represent the letter mappings

Replace each number by its next bigger number from right side of current index. if no bigger number found print that number itself.

Eg: 2,5,9,6,3,4,8,15,12
OutPut : 3,6,12,8,4,8,12,15,12

Convert a binary tree to a doubly linked circular linked list.(Tree is binary and not BST).Hint: using Inorder Traversal

Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.

eg: coins(10, 15, 55)
print:
10
15
20
25
30
.
.
.
1000

You have an array of numbers. You have to give the range in which each number is the maximum element. For Example, If array is [1, 5, 4, 3, 6] The output would be

1 [1, 1]
5 [1, 4]
4 [3, 4]
3 [4, 4]
6 [1, 5]

Bonus question -5: Build all permutations of a char array

4. Find an algorithm for finding the longest ascending order sub-sequence in an unsorted array of integers.

Example: { 16, 4, 8, 22, 33, 7, 71} == > { 16, 22, 33, 71 }

3. Implement a descending and ascending sort by building a binary tree and traversing it.

2. Implement a double linked list

C test – 3 hours (see also other questions: 1 to 5
1. Write a function which compares two strings –
Int strcmp (char* S1, char* S2)