DataStructure_ps1

所需积分/C币:1 2017-03-26 14:10:03 419KB PDF

DataStructure_ps1
1 Problem Check brackcts in the codc Problem introduction II this problen you will immplement a feature for a text editor to find errors in the usage of brackets in the code Problem Description Task. Your friend is making a text editor for programmers. He is currently working on a feature that will find errors in the usage of different types of brackets. Code can contain any brackets from the set []O, where the opening brackets are [,t, and and the closing brackets corresponding to them are],, and For convenience, the text editor should not only inform the user that there is an error in the usage of brackets, but also point to the exact place in the code with the problematic bracket. First priority is to find the first unmatched closing bracket which cithcr doesnt havc an opening bracket bcforc it the wrong opening bracket, like j in ()[]. If there are llo such Inistakes, thenl it should find the first unmatched opening bracket without the corresponding closing bracket after it like( in 0([]. If there are no mistakes, text editor should inform the user that the usage of brackets is correct Apart froln the brackets, code call contain big alld sinall latin letters, digits and punctuation Marks More formally, all brackets in the code should be divided into pairs of Latching brackets, such that ill each pair the opening bracket goes before the closing bracket, and for any two pairs of brackets either one of them is nested inside another one as in(foo [bar]) or they are separate as in f(a, b)-glcl The bracket corresponds to the bracket ], i corresponds to ], and corresponds to Input Format. Input contains one string s which consists of big and small latin letters, digits, punctuation Illarks and brackets froIn the set []O Constraints. The length of s is at least 1 and at most 105 Output Format. If the codc in S uscs brackcts corrcctly, output"Succcss"(without the quotes). Otherwise output the 1-based index of the first unmatched closing bracket, and if there are no unmatched closing brackets, output. the 1-based index of the first unmatched opening bracket Time LiNits. C: 1 sec. C++: 1 seC, Java: 1 sec, Python: 1 sec. C#: 1.5 sec, Haskell: 2 seC, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec Memory limit, 512MB Sample 1 Input Output Success planation The brackets are used correctly: there is just one pair of brackets and I, they correspond to each other, the left bracket i goes before the right bracket ], and no two pairs of brackets intersect, because there is just one pair of brackets Sample 2 nput {}[] uccess Explanate The brackets are used correctly: there are two pairs of brackets- first pair of t and 3, alld second pair of and ] and these pairs do not intersect Sample 3 pU Output Success Explaination The brackets are used correctly: there are two pairs of brackets- first pair of and 1, and second pair of and)- and the second pair is nested inside the first pair Sample 4 Output Success Explanation Pairs with the same types of brackets can also be nested mple 5 {[]() Output Success Here there are 3 pairs of brackets, one of them is nested into another one, and the third one is separate n the first Sample 6 Input: Output Explanation The code doesnt use brackets correctly, because brackets cannot be divided into pairs(there is just one bracket). There are no closing brackets, and the first unmatched opening bracket is f, and its position is l, so we output 1 4 Sample 7. Input {[} Output Explanate The bracket y is unLatched, because the last unmatched openling bracket before it is and not t.It is the first unmatched closing bracket, and our first priority is to output the first unmatched closing bracket, and its position is 3, so wc output 3 Sample 8 foo(bar) Output Success Explanation: All the brackets are matching, and all the other symbols can be ignored Sample 9 pu foo (bar li) Output 10 )doesn't match [, so )is the first unmatched closing bracket, so we output its position, which is 10 Starter Files Thcrc arc starter solutions only for CI-I, Java and Python3, and if you usc other languages, you nccd to implement solution from scratch. Starter solutions read the code from the input and go through the code character-by-character and provide convenience methods. You need to implement the processing of the brackets to find the answer to the problem and to output the answer What to Do To solve this problem, you can slightly modify the IsBalanced algorithm from the lectures to account not only for the brackcts, but also for other characters in the codc, and return not just whcther the codc uscs brackets correctly, but also what is the first position where the code becones broken Need Help? Ask a question or see the questions asked by other learners at this forum thread 2 Problem: Compute tree height Problem introduction Trees are used to Illalipulate hierarchical data such as hierarchy of categories of a retailer or the directory structure on your computer. They are also used in data analysis and machine learning both for hierarchi- cal clustering and building complex predictive models, including some of the best-performing in practice algorithms like gradient boosting over Decision Trees and Random Forests. In the later modules of this course, we will introduce balanced binary search trees(BST)-a special kind of trees that allows to very efficiently store, manipulate and retrieve data. Balanced BsTs are thus used in databases for efficient storage and actually in virtually any non-trivial programs, typically via built-in data structures of the programming language at hand In this problem, your goal is to get used to trees. You will need to read a description of a tree from the input, implcment the trec data structurc, store the trec and compute its height Problem Description Task. You are given a description of a rooted tree. Your task is to compute and output its height. Recall that the height of a (rooted tree is the maximum depth of a node, or the maximum distance from a leaf to the root. You are given an arbitrary tree, not necessarily a binary tree Input Forinlat. The first line contains the nuInber of nodes n. The second line contains r integer llunlbers from -I to n-1- parents of nodes. If the i-th one of them(0sisn-1)is-1, node i is the root. otherwise it's o-based index of the parent of i-th node. It is guaranteed that there is exactly one root It is guaranteed that the input represents a tree Constraints. 1<n< 105 Output Format. Output the height of the tree Time Limits. C: 1 sec. C++: 1 sec, Java: 6 sec, Python: 3 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec Memory Limit 512MB Sample 1 Input 4-1411 Output Explanation: he input means that there are 5 nodes with numbers from 0 to 4, node 0 is a child of node 4, node 1 is the root nodc 2 is a child of nodc 4 nodc 3 is a child of nodc 1 and nodc 4 is a child of nodc 1. to see this, let us write numbers of nodes from 0 to 4 in one line and the numbers given in the input in t he second line underneath 01234 4-1411 Now we can see that the node number 1 is the root, because-1 corresponds to it in the second line Also. we know that the nodes number 3 and number 4 are children of the root node 1. also we know that thc nodcs numbcr 0 and numbcr 2 arc children of thc nodc 4 root The height of this tree is 3, because the number of vertices on the path from root 1 to leaf 2 is 3 Samplc 2 Input 5 10403 Output: Explanation The input means that there are 5 nodes with numbers from 0 to 4 node 0 is the root, node 1 is a child of node 0. node 2 is a child of node 4. node 3 is a child of node o and node 4 is a child of node 3. The height of this tree is 4, because the number of nodes on the path from root 0 to leaf 2 is 4 root Starter files The starter solutions in this problem read the description of a tree, store it in memory. compute the height in a naive way and write the output. You need to implement faster height computation. Starter solutions are available for C++, Java and Python3, and if you use other languages, you need to implement a solution from scratch What to do To solve this problem, change the height function described in the lectures with an implementation which will work for an arbitrary tree. Note that the tree can be very deep in this probleIll, so you should be careful to avoid stack overflow problems if you're using recursion, and definitely test your solution on a tree with the maximum possible height Suggestion: Take advantage of the fact that the labels for each tree node are integers in the range 0.m2-1 you can store cach nodc in an array whose index is thc labcl of the nodc. By storing the nodes in an array, you have o(1)access to any node given its labe Create an array of n nodes allocate nodes] for it0 to nm nodes=new Node Then, read each parent index for child inde t0 to n-1 read parent_index if parent_index==-1: root← child index lse nodes parent__inde c addchild(nodes child_indea) Oncc you'vc built the trcc, you'll then nccd to compute its height. If you don t usc rccursion, you nccdn't worry about stack overflow problems. Without recursion, you'll need some auxiliary data structure to keep track of the current state (in the breadth-first seach code in lecture, for example, we used a queue Need Help? Ask a question or see the questions asked by other learners at this forum thread 3 Advanced Problem: Nctwork packet processing simulation We strongly recommend you start solving advanced problems only when you are done with the basic problems (for some advanced problems, algorithms are not covered in the video lectures and require additional ideas to be solved; for somc othor advanced problcms, algorithms arc covcred in the lectures, but implemcnting them is a more challenging task than for other problems) Problem introduction In this problem you will implement a program to simulate the processing of network packets ProbleIn Description Task. You are given a series of incoming network packets, and your task is to simulate their processing Packets arrive in some order. For each packet number i, you know the time when it arrived Ai and the time it takes the processor to process it Pi(both in milliseconds). There is only one processor, and it processes the incoming packets in the order of their arrival. If the processor started to process some packet, it doesnt interrupt or stop until it finishes the processing of this packet, and the processing of packet i takes exactly Pi milliseconds The computer processing the packets has a network buffer of fixed size S. When packets ar rive, they are stored in the buffer before being processed. However, if the buffer is full when a packet arrives(there are s packets which have arrived before this packet, and the computer hasn't finished processing any of them), it is dropped and won't be processed at all. If several packets arrive at the Saille tine, they are first all stored in the buffer(soinle of thelll Inay be dropped because of that t hose which are described later in the input). The computer processes the packets in the order of their arrival, and it starts processing the next available packet from the buffer as soon as it finishes processing the previous one. If at some point the computer is not busy, and there are no packets in the buffer, the computer just waits for the next packet to arrive. Note that a packet leaves the buffer and frees the space in the buffer as soon as the computer finishes processing it Input Format. The first line of the input contains the size s of the buffer and the number n, of incoming network packets. Each of the next n lines contains two numbers. i-th line contains the time of arrival A i and the processing time Pi(both in milliseconds) of the i-th packet. It is guaranteed that the sequence of arrival times is non-decreasing (however, it can contain the exact same times of arrival in milliseconds- in this case the packet which is earlier in the input is considered to have arrived earlier) Constraints. All the numbers in the input are integers.1≤S≤105;1≤n≤105;0≤A;≤106 0≤P2≤103;A≤A1+1for1≤ 1 Output Format. For each packet output either the moment of time(in milliseconds) when the processor began proccssing it or-1 if the packct was dropped (output thc answers for the packets in the samc order as the packets are given in the input Time Limits. C: 2 sec, C++: 2 sec. Java: 6 sec, Python: 8 sec. C#: 3 sec, Haskell: 4 sec, JavaScript: 6 sec Ruby: 6 sec, Scala: 6 sec Memory Limit 512MB S ample put 10 Output xplanation If there are no packets, you shouldnt output anything Sample 2 Input 11 00 Output: Explanation: The only packet arrived at time 0, and computer started processing it immediately. Sanple 3 Input: 12 01 01 Output Explanation: The first packct arrived at timc 0. the sccond packct also arrived at timc 0, but was dropped, because the network buffer has size 1 and it was full with the first packet already. The first packet started processing at time 0, and the second packet was not processed at all Sample 4. Input 12 01 11 Output 0 xplanation: The first packet arrived at time 0, the computer started processing it immediately and finished at time 1. The second packet arrived at time 1, and the computer started processing it immediately Starter files The starter solutions for C-+, Java and Python in this problem read the input, pass the requests for processing of packets one-by-one and output. the results. They declare a. class that implements network buffer simulator. The class is partially implemented, and your task is to implement the rest of it. If you use other languages, you need to implement the solution from scratch What to Do To solve this problem, you can use a list or a queue(in this case the queue should allow accessing its last element, and such queue is usually called a deque). You call use the corresponding built-in data structure ill your language of choice

...展开详情
试读 17P DataStructure_ps1
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    DataStructure_ps1 1积分/C币 立即下载
    1/17
    DataStructure_ps1第1页
    DataStructure_ps1第2页
    DataStructure_ps1第3页
    DataStructure_ps1第4页
    DataStructure_ps1第5页
    DataStructure_ps1第6页

    试读已结束,剩余11页未读...

    1积分/C币 立即下载 >