Tuesday, June 28, 2016

Convert array into Zig-Zag fashion


Given an array of distinct elements, rearrange the elements of array in zig-zag fashion in O(n) time. The converted array should be in form a < b > c < d > e < f.

Example: 
Input:  arr[] = {4, 3, 7, 8, 6, 2, 1}
Output: arr[] = {3, 7, 4, 8, 2, 6, 1}

Input:  arr[] =  {1, 4, 3, 2}
Output: arr[] =  {1, 4, 2, 3}


Arrange given numbers to form the biggest number

Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value.


Absolute distinct count in a sorted array

Given a sorted array of integers, return the number of distinct absolute values among the elements of the array. The input can contain duplicates values.
Input: [-3, -2, 0, 3, 4, 5]
Output: 5
There are 5 distinct absolute values
among the elements of this array, i.e.
0, 2, 3, 4 and 5)

Input:  [-1, -1, -1, -1, 0, 1, 1, 1, 1]
Output: 2

Input:  [-1, -1, -1, -1, 0]
Output: 2

Input:  [0, 0, 0]
Output: 1 
http://www.geeksforgeeks.org/absolute-distinct-count-array-sorted-absolute-values/


Count the number of possible triangles

Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles. For a triangle to be possible from 3 values, the sum of any two values (or sides) must be greater than the third value (or third side).

For example, if the input array is {4, 6, 3, 7}, the output should be 3. There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle.
As another example, consider the array {10, 21, 22, 100, 101, 200, 300}. There can be 6 possible triangles: {10, 21, 22}, {21, 100, 101}, {22, 100, 101}, {10, 100, 101}, {100, 101, 200} and {101, 200, 300}

Sunday, June 26, 2016

Minimum sum of two numbers formed from digits of an array

Given an array of digits (values are from 0 to 9), find the minimum possible sum of two numbers formed from digits of the array. All digits of given array must be used to form the two numbers.

Input: [6, 8, 4, 5, 2, 3]
Output: 604
The minimum sum is formed by numbers 
358 and 246

Input: [5, 3, 0, 7, 4]
Output: 82
The minimum sum is formed by numbers 
35 and 047 


Saturday, June 25, 2016

Find Union and Intersection of two sorted arrays. Modify it the same for two unsorted arrays

Union and Intersection of two sorted arrays

Given two sorted arrays, find their union and intersection.
For example, if the input arrays are: 
arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}. 

Find Union and Intersection of two unsorted arrays

Given two unsorted arrays that represent two sets (elements in every array are distinct), find union and intersection of two arrays.
For example, if the input arrays are:
arr1[] = {7, 1, 5, 2, 3, 6}
arr2[] = {3, 8, 6, 20, 7}
Then your program should print Union as {1, 2, 3, 5, 6, 7, 8, 20} and Intersection as {3, 6}. Note that the elements of union and intersection can be printed in any order.

pending


Design a recommendation system

Design a scalable web crawling system

Complete Design:
http://webpages.uncc.edu/sakella/courses/cloud09/papers/Mercator.pdf

Questions To Ask:
If you were designing a web crawler, how would you avoid getting into infinite loops?
http://stackoverflow.com/questions/5834808/designing-a-web-crawler
https://github.com/filipegoncalves/interview-questions/blob/master/systems_design/WebCrawler.md
http://baozitraining.org/blog/design-a-basic-web-crawler/
http://massivetechinterview.blogspot.in/2015/06/design-web-crawler.html

Final Design:
http://blog.gainlo.co/index.php/2016/06/29/build-web-crawler/
https://www.quora.com/How-can-I-build-a-web-crawler-from-scratch
http://flexaired.blogspot.in/2011/09/design-web-crawler.html


There are at least 3 components that are required. 
1. HTTP Request/Getting page.
2. HTML Parser
3. URL Tracker

The first component is to request a given URL and either download it to the machine or just keep it in memory. (Downloading will need design to store the web page for easy retreival)

HTML Parser - Removes the html tags and retains text of interest (I needed only part of the page based on some pattern) and URL s in the current page. A more generic webcrawler will have to save different components like image/sound etc

URL Tracker - URL tracker makes sure that no URL is visited twice within a set time frame( A simple mechanism is a hash table with a user-defined comparator function, some urls may still point to the exact same page eg www.abc.com and www.abc.com/index.htm)
Crawler basic algorithm
  1. Remove a URL from the unvisited URL list
  2. Determine the IP Address of its host name
  3. Download the corresponding document
  4. Extract any links contained in it.
  5. If the URL is new, add it to the list of unvisited URLs
  6. Process the downloaded document
  7. Back to step 1

Design image sharing website ( Flickr / Instagram )

Design a Notification system

Design an online multiplayer game

Speed Up Webpage for Slow Connection

Suppose you are handling Amazon website and you have 10 MB size home page. Optimize the homepage for a customer who has 100 kbps internet connection.
Further he asked for the customer who has 100 mbps internet connection.


Design a Payment Gateway

Design a Payment Gateway

Design Facebook Timeline

Thursday, June 23, 2016

Implement classes in C

how you can actually implement class like functionalities from C structures ?

OOPs Concepts

The four basic concepts of OOP are: 
a.) Abstraction 
b.) Polymorphism 
c.) Inheritance
d.) Encapsulation

What is friend function?

- Friend function is a friend of a class. 
- It is allowed to access Public, private or protected data of that class. 
- It can be declared anywhere in the class declaration
- It doesn’t have any effect of access control keywords like private, public or protected.


What is the function of pure virtual functions?

Pure virtual function in object oriented programming is called as virtual method that acts as a function allowing its behavior to be overridden by the class that is inheriting the pure virtual function with the same signature. This is used in case of polymorphism. It is used when a base class is being driven by the derived class and an object of the derived class referred as base or derived class type. When a derived class overrides the base class method then the output or the behavior will be called as ambiguous. To use the virtual function a virtual keyword is used. This allows the function to be defined in every derived class and use the functionality of it.

Can we overload a static method in Java? 
Yes, you can overload a static method in Java. You can declare as many static methods of the same name as you wish provided all of them have different method signatures. See the answer for more detailed explanation and code example.


Can we override static method in Java? 
No, you cannot override a static method because it's not bounded to an object. Instead, static methods belong to a class and resolved at compile time using the type of reference variable. But, Yes, you can declare the same static method in a subclass, that will result in method hiding i.e. if you use reference variable of type subclass then new method will be called, but if you use reference variable of superclass than old method will be called.


Can we prevent overriding a method without using the final modifier? (answer)
Yes, you can prevent the method overriding in Java without using the final modifier. In fact, there are several ways to accomplish it e.g. you can mark the method private or static, those cannot be overridden.


Can we override a private method in Java? 
No, you cannot. Since the private method is only accessible and visible inside the class they are declared, it's not possible to override them in subclasses. Though, you can override them inside the inner class as they are accessible there.


What is covariant method overriding in Java? 
In covariant method overriding, the overriding method can return the subclass of the object returned by original or overridden method. This concept was introduced in Java 1.5 (Tiger) version and it's very helpful in case original method is returning general type like Object class, because, then by using covariant method overriding you can return more suitable object and prevent client side type casting. One of the practical use of this concept is in when you override the clone() method in Java.


Read more: http://java67.blogspot.com/2015/12/top-30-oops-concept-interview-questions-answers-java.html#ixzz4CQOK9xam

Find popular items

Find popular item in sorted array of natural numbers.
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.
This is actually a very interesting problem. Since the popular item is defined as the element is repeated more than 1 / 4 times, and since it is a sorted array, so it can only occurs on 0, n / 4, n /2 and 3n/4 index. And the rest is just do binary search and get the range.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class PopularNumber {
 public static void popular(int[] n){
  if(n == null || n.length == 0)
   return;
  int len = n.length;
  int[] check = {0, len / 4, len / 2, 3 * len / 4};
  for(int i = 0; i < 4; i++){
   if(i > 0 && n[check[i]] == n[check[i - 1]])
    continue;
   int l = check[i];
   int start = binarySearchStart(n, n[l]);
   int end = binarySearchEnd(n, n[l]);
   //need to be larger than the ceil in case len / 4.0 is not an integer
   if(end - start + 1 >= Math.ceil(len / 4.0))
    System.out.println(n[l]);
  }
 }
 private static int binarySearchEnd(int[] n, int target){
  int len = n.length;
  int start = 0;
  int end = len - 1;
  while(start + 1 < end){
   int mid = (start + end) / 2;
   if(n[mid] <= target)
    start = mid;
   else
    end = mid;
  }
  if(n[end] == target)
   return end;
  else return start;
 }
 private static int binarySearchStart(int[] n, int target){
  int len = n.length;
  int start = 0;
  int end = len - 1;
  while(start + 1 < end){
   int mid = (start + end) / 2;
   if(n[mid] >= target)
    end = mid;
   else
    start = mid;
  }
  if(n[start] == target)
   return start;
  else
   return end;
 }
 
 public static void main(String[] args) {
  //int[] n = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8};
  int[] n = {1, 1, 2, 3, 4};
  popular(n);
 }
}