This repository contains instructions and questions for IEEECS, VIT 2nd year selections 2016.
If you are new to github, click here
- Fork this repository.
- Solve the questions in a language of your choice. Extra points if you derive the complexity of your algorithm in asymptotic notation. ( Big-O notation )
- Commit and push your code. If you are not able to complete all the questions, submit a partial solution.
- Submit a link to your forked repository here
- any programming language can be used. Even bash or powershell scripts are fine. Extra points for using a functional programming language.
- Use only the standard library of said language. For example, in python, use only the the standard modules ( os, collections, math, sys etc. ).
- Plagiarism without proper citation will lead to disqualification.
- If you do use someone's code, cite the source.
- Correctness. Does your code meet the specifications ?
- Code quality. How well does your code adhere to your language's standards.
- Efficiency. Is your solution the best way to solve the problem ?
In a list of numbers, find the only element that occurs once. All other elements are guaranteed to only occur twice.
Example
Input: 2 5 7 6 5 7 2
Output: 6
Part 1. Implement Binary search.
Part 2. A certain binary search algorithm takes about 4.5 milliseconds to search a sorted array of 10,000 elements, and about 6 milliseconds to search 1 lakh ( 1,00,000 ) elements. How long would I expect it to take to search 1 crore ( 1,00,00,000 ) elements assuming I have sufficient memory to prevent paging.
Hint: What is the complexity of Binary search ?
Given 2 numbers compute the bit difference between them.
Bit difference of a pair (x, y) is the count of different bits at the same positions in binary representations of x and y. For example, bit difference for 2 and 7 is 2. Binary representation of 2 is 010 and 7 is 111 (first and last bits differ in two numbers).
Note: Extra points for finding a non brute force solution ( O(n) or O(logn) )
Example
Input: 2 7
Output: 2
Read the given HTML file and and print contents of all tags that have a particular class.
Hint: There are multiple ways to do this ( Regular Expressions, XML parsing, character by character processing and so on )
Ex. Input: index.html active
<!-- index.html -->
<!doctype html>
<html>
<body>
<button class="button active"> click me! </button>
<section>
<h2> Hello, World </h2>
<p class="active"> I am active. </p>
</section>
</body>
</html>
Output:
click me!
I am active.