Home /
Expert Answers /
Computer Science /
instagram-is-a-photo-and-video-sharing-social-network-in-which-users-can-choose-to-follow-other-use-pa619

Instagram is a photo and video sharing social network, in which users can choose to follow other users. There are n users on Instagram, and each of them has been given a unique ranking from 1 to n by InstaRankings.com1. You are given a list of followers for each of the n users. We say that a user x shadows a user y if there is a sequence of users u1, u2, . . . uℓ such that x follows u1 who follows u2 and so on, with uℓ following y. For each user u, you are asked to determine the rank of the highest ranked user (i.e. user with rank closest to 1) who shadows u. You can return this information in an array S, where S[u] is the rank of the highest ranked user who shadows user u. You may assume that nobody follows themselves, a user may not follow anyone, and that every user has at least one follower. (a) Describe an algorithm which solves this problem. You should attempt to design an algorithm which is as efficient as posisble (asymptotically). Solution: (b) Prove the correctness of your algorithm. Solution: (c) Analyze your algorithm’s worst-case running time. Solution: 1this is not a real website, CS 3000 is not responsible for any damages caused by attempting to check your Instagram rankings at this made-up page 4