Giter Site home page Giter Site logo

codepractice's Introduction

CodePractice

Code Interview Questions Implementation

Question1 --- Tree Decrement

Please see the latest version by the following shared Notion link.
https://www.notion.so/Tree-Decrement-e84e1514b19f4f819ff1916ee89a9ed1?pvs=4

Tree Decreasment

A tree can be represented as an unweighted undirected graph of $t$ nodes nodes numbered from $1$ to $t$ nodes and $t-1$ edges where the $i^{th}$ edge connects the nodes numbered t_from $[i]$ and t_to $[i]$.

A value $\text{val}[i]$ is associated with $i^{th}$ node. In a single operation, two nodes (could be the same node) can be selected, and their(its) value(s) can be decremented by 1 at a cost equal to the distance between the two nodes, i.e, the number of edges in the simple path between them. The distance between it and itself is 0.

Given the tree, $t$, and the values $\text{val}$, find the minimum cost to decrease the values of all the nodes to 0. It is guaranteed that the values of all the nodes can be decreased to exactly 0.

Example
Suppose $t$ = 3, t_from = [1, 1], t_to = [2, 3] and $\text{val} = [3, 1, 2]$.The optimal strategy is to choose nodes 1 and 2 at cost 1. The values become [2, 0, 2]. Now nodes 1 and 1, followed by 3 and 3, can be chosen, each with a cost of 0. Thus the total cost is 1 + 0 + 0 = 1.

Possible Solution:

To minimize the cost, we'd like to see the best secriano (all nodes have a even value, which implies that they can complete the decreasement with 0 cost in total).

Also, since the question gurantees that the given tree can be decreased to 0, which means there must be a "true" pair for each node

$$ V = \{1, \dots, t\}, E = \{e_1, \dots, e_{t-1}\}, P=\{(x_1,y_1), \dots, (x_n, y_n)\}\ \text{where } x_i, y_i \in V, $$

Question 2 -- Multi-dimensional Selection

Given a 2-d array arr of size n x m, a selection is defined as an array of integers such that it contains ateast ( m/ 21 integers from each row of arr. The cost of the selection is defined as the maximumdifference between any two integers of the selection. Suppose kis the minimum cost of all the possible selections for the given 2-d array. Find themaximum value of the product of k* the number of integers considered in the selection with theminimum cost.

Example

Suppose n = 3, m = 2, and arr = [[1, 2], [3, 4], [8, 9]] Some of the possible selections are [2, 3, 8], [1, 2, 3, 9], [1, 3, 4, 8, 9] etc. The cost of these selectionsare 8 - 2 = 6, 9 - 1 = 8, and 8 respectively. Here the minimum cost of all the possible selections is 6. The possible selections with the cost 6 are2, 4, 8] and [2, 3, 4, 8]. The maximum value of the required product is obtained using the latterselection i.e.6*4 = 24. Hence the answer is 24. Function DescriptionComplete the function getMaxProductin the editor below. getMaxProduct has the following parameter:int arrln][m]: the given 2-d array Returns int: the maximum possible product

codepractice's People

Contributors

chenyo34 avatar kyraaaaaaaa avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.