Monday, September 17, 2018

Simplified Breadth-first Search

Simplified Breadth-first Search

Given a graph G = (V, E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to “discover” every vertex that is reachable from s. It computes the distance (smallest number of edges) from s to each reachable vertex. It also produces a “breadth-first tree” with root s that contains all reachable vertices. For any vertex reachable from s, the simple path in the breadth-first tree from s to corresponds to a “shortest path” from s to v in G, that is, a path containing the smallest number of edges. The algorithm works on both directed and undirected graphs.

Python

class Graph:
  def __init__(self, nodes):
      self.nodes = nodes
      self.edges = 0
      self.adj = [[] for i in range(self.nodes)]

  def addEdge(self, v, w):
      self.adj[v].append(w)
      self.edges += 1

  def bfs(self, startingNode):
      from queue import Queue
      seen = [False for i in range(self.nodes)]
      q = Queue()
      q.put(startingNode)
      while not q.empty():
          node = q.get()
          print(node, end=", ")
          seen[node] = True
          for neighbour in self.adj[node]:
              if not seen[neighbour]:
                  q.put(neighbour)


Tuesday, September 4, 2018

Disable All Diagnostic Information on your mobile (Android)

In my last post, you have seen how to disable Location History completely. 
In this post I will show you how to disable all the diagnostic logging across Google apps which in turn save you a lot of battery and make our planet less warmer.

There are lot of apps in your Android which might be recording lot of diagnostic information, though the apps are unlimited on play store doing this, however I will keep this list minimal.

Disable all Diagnostic Logging

Most surprising thing here is that most of the settings are enabled by default in most of the apps. You may or may not disable these settings, but there are reasons why you want to do that.
  1. Saves Battery, these tiny settings on different different apps can save you lot of battery and keep your mobile battery healthier.
  2. Privacy, it is a biggest concern you might have:
    1. Do you know what data is being uploaded ?
    2. Your data is stored by so many apps to hundreds of servers across the globe by each app.
    3. Despite lot of privacy rules like GDPR, still there are apps who refused to delete your account. 
  3. End User not as a subject, a mobile user should be an end user rather than interest for studies.

Chrome


  1. On your Android phone or tablet, open Chrome > Settings Privacy.
  2. Disable Security Reports "Automatically send some system information and page content to Google to help detect dangerous apps and sites".
  3. Tap Usage and crash reports "Automatically send usage statistics and crash reports to Google".
  4. Turn off.


Hangouts



  1. On your Android phone or tablet, open Hangouts > Settings.
  2. Tap your Account, do this for all the accounts shown.
  3. Under Improve Hangouts "Report additional diagnostics to help improve Hangouts".
  4. Turn off.


Maps



  1. On your Android phone or tablet, open Maps > Settings.
  2. Tap Commute settings.
  3. Disable Get commute notifications "Know about delays and disruptions before you go".
  4. Disable Get more accurate commute info "Let Maps improve your commute times accuracy by using your Location History".


Sky Map



  1. On your Android phone or tablet, open Sky Map > Settings.
  2. Disable Send usage statistics "Make Sky Map better by sending anonymous data to Google Analytics".

Translate



  1. On your Android phone or tablet, open Translate > Settings.
  2. Tap Data usage.
  3. Disable Improve camera input "Let Google retain images for use in product improvement".

Gboard



  1. On your Android phone or tablet, open Settings > Languages & input.
  2. Tap Virtual keyboard > Gboard. This will open Gboard settings.
  3. Tap Advanced.
  4. Under Improve Gboard.
  5. Disable Share usage statistics "Automatically send keyboard usage statistics to Google".
  6. Disable Share snippets  "Automatically share snippets of what and how you type in Google apps to improve Gboard".
  7. You may have locate the Gboard settings in your mobile.

Google Indic Keyboard settings



  1. On your Android phone or tablet, open Settings > Languages & input.
  2. Tap Virtual keyboard > Google Indic Keyboard. This will open keyboard settings.
  3. Tap Others.
  4. Disable Send usage statistics.


Saturday, August 18, 2018

Disable Google Location Tracking (Android+Web)

You are being tracked by the Amazon, Facebook and Google and most probably you don't even know it. The reason most of the people are not well versed with the intricacies of the mobile ecosystem. The option is enabled by default as soon you buy a new device or you are forced to.
Every place on earth you visit is stored on their servers.

If you think you are targeted for the sake of artificial intelligence or improving user experience and you do not want to be location tracked, then I will guide you through.


Delete your Location History

You can control what’s saved in your Location History, and you can delete your history at any time.

Turn Location History off

You can turn off Location History at the account level at any time and this is the time to do it. When you turn off Location History for your Google Account, it's off for all devices associated with that Google Account.

Android

  1. On your Android phone or tablet, open your device's Settings > Google Google Account.
  2. At the top, tap Data & personalization.
  3. Under "Activity controls," tap Location History.
  4. Turn Location History off for your account.
You have actually paused Location History, however your previous Location History still exists and it can be erased as well. See the next section.

Web

  1. Go to the Activity controls section of your Google Account. Sign in if required.
  2. Turn Location History off.
  3. Confirm the change. This setting will change for your Google Account and all devices associated with it.

Delete Location History

You can delete all of your Location History. If you delete your entire history, only you would be knowing where you had been.
IMPORTANT: Deleting your Location History in the Settings app is permanent. You can't reverse or undo it.

Android

  1. On your Android phone or tablet, open your device's Settings > Google Google Account.
  2. At the top, tap Data & personalization.
  3. Under "Activity controls," tap Location History.
  4. At the bottom, tap Manage Timeline. Your device will open Google Maps.
  5. Tap More > Settings Personal Content.
  6. Under "Location Settings", choose Delete all Location History.

Web

  1. Go to maps.google.com/locationhistory. Sign in if required.
  2. Click SettingsDelete all Location history.




Saturday, July 21, 2018

How to use “ok Google” hotword to work when the Screen is Off (root)

In this article, I will be showing you how to use google "ok google" hotword detection when screen is off. This amazing feature is only available for selected high end phones for eg Moto X.

This feature has the ability to listen to "ok google" when display is off so that it can listen to voice command. This feature comes very handy when you have to search anything in google but you are traveling in a car or you are doing something in which you can’t access your smartphone.

In General, you only can hotword detection feature if your device screen is On or your device is connected to the charger so the main thing is that you can’t use this feature when your mobile screen is Off. So basically, this guide will help you to use this feature even when your screen is Off or you aren’t connected to the charger.


How to force “ok google” hotword to work when the Screen is Off (root)


Requirements

  • Rooted phone 
                A rooted phone gives you full control of your own mobile and it comes with full responsibility.
                Enable Voice detection in Google Search app settings.
                Browse intents and import "Google Now Voice Search" intent.

All Set!!

Sunday, July 2, 2017

Remove all adjacent or consecutive duplicate characters

Remove all adjacent or consecutive duplicate characters


Input:  azxxzy
Output: ay
First "azxxzy" is reduced to "azzy". The string "azzy" contains duplicates, 
so it is further reduced to "ay".

Input: geeksforgeeg
Output: gksfor
First "geeksforgeeg" is reduced to "gksforgg". The string "gksforgg" contains 
duplicates, so it is further reduced to "gksfor".

Input: caaabbbaacdddd
Output: Empty String

Input: acaaabbbacdddd
Output: acac

Iterate through the characters and keep track of duplicates with start and end index, once you get a non matching character then delete the start to end characters and step back one more step and start again.

private static String removeAllAdjacentDuplicates(String s) {
StringBuilder sb = new StringBuilder(s);
int startIndex = -1;
int endIndex = -1;
char previousChar = '\0';
for (int i = 0; i < sb.length(); i++) {
if (previousChar == sb.charAt(i))
endIndex = i;
else {
if (endIndex > startIndex) {
sb.delete(startIndex, endIndex + 1);
i = --startIndex;
i = i < 0 ? 0 : i;
endIndex = -1;
}
startIndex = i;
previousChar = sb.charAt(i);
}
}
if (endIndex > startIndex)
sb.delete(startIndex, endIndex + 1);

return sb.toString();
}

Note: Deleting is a costly operation for that all the elements will be left shifted with their position.

Find the minimum element in a sorted and rotated array

Find the minimum element in a sorted and rotated array


Take an example
int[] a = { 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, };

We can find the minimum element in O(logn), so first we divide the array in two parts in which one is sorted and other one is sorted, this process is continued until low is equal to high.

There are some differences and similarities with binary search algorithm.

private static int min(int a[]) {
int low = 0;
int high = a.length - 1;
while (low < high) {
int mid = (low + high) >>> 1;
if (a[mid] < a[high])
high = mid;
else
low = mid + 1;
}
return a[low];
}

Monday, June 26, 2017

Longest increasing sub-sequence

Longest increasing sub-sequence


The longest increasing sub-sequence problem is to find a sub-sequence of a given sequence in which the sub-sequence's elements are in sorted order, lowest to highest, and in which the sub-sequence is as long as possible. The longest increasing sub-sequence is solvable in O(nlogn) time complexity and O(n) space complexity in worst scenario.

Example
In the first 16 terms of the binary Van der Corput sequence
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
a longest increasing sub-sequence is
0, 2, 6, 9, 11, 15.
This sub-sequence has length six; the input sequence has no seven-member increasing sub-sequences. The longest increasing sub-sequence in this example is not unique: for instance,
0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15
are other increasing sub-sequence of equal length in the same input sequence.

See the figure below as to how it is done.

We have similar approach in which we check the following condition before inserting an element in a sorted array 

Case 1

If next element is already greater than the last element of the sorted array. Add it in the last of the sorted array.

Case 2

If next element is less than the first element of the sorted array. then replace it with first element in the sorted array with this element.

Case 3

If A[i] is in between, we will find an index in list such that for every 0<=j<=n in the list, A[i]>list(j)
To find the index of an element in an sorted array with least index greater than A[i], we will use modified Binary Search.

public class LIS {

 public static void main(String[] args) throws FileNotFoundException {

    int a[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 13, 3, 11, 7, 15 };
    System.out.println(lis2(a));
    System.out.println(lis3(a));

 }

 /**
  * Arraylist version with nlogn time and <=n space, will take less space
  * than array version. Steps 1 Create an array of same size. 2 Check the
  * next element from the input 3. if it is greater than the last element in
  * our array then add it into the end of the list. 4. if it is less than the
  * first element in our array then replace the first element 5. if it can be
  * inserted into our list then find out where it can be inserted and insert
  * it by replacement.
  *
  * @param a
  * @return
  */
 private static int lis2(int[] a) {
    List<Integer> lis = new ArrayList<>();
    lis.add(a[0]);
    for (int i = 1; i < a.length; i++)
       if (a[i] > lis.get(lis.size() - 1))
          lis.add(a[i]);
       else if (a[i] < lis.get(0))
          lis.set(0, a[i]);
       else
          lis.set(binarySearch(lis, a[i]), a[i]);
    System.out.println(lis);
    return lis.size();
 }

 /**
  * Array version with nlogn time complexity and n space.
  *
  * @param a
  * @return
  */
 private static int lis3(int[] a) {
    int[] lis = new int[a.length];
    int lastIndex = 0;
    lis[lastIndex] = a[0];
    for (int i = 1; i < a.length; i++)
       if (a[i] > lis[lastIndex])
          lis[++lastIndex] = a[i];
       else if (a[i] < lis[0])
          lis[0] = a[i];
       else
          lis[binarySearch(lis, 0, lastIndex, a[i])] = a[i];
    return lastIndex + 1;
 }

 /**
  * O(n^2) log time, very slow performance.
  *
  * @param arr
  * @return
  */
 private static int lis(int[] arr) {
    int max = -1;
    int[] lis = new int[arr.length];
    lis[0] = 1;
    for (int i = 1; i < arr.length; i++)
       for (int j = 0; j < i; j++)
          if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
             lis[i] = lis[j] + 1;
             max = Math.max(max, lis[i]);
          }
    return max;
 }

 /**
  * least index greater than n
  *
  * @param a
  * @param n
  * @param low
  * @param high
  * @return
  */
 private static int binarySearch(int[] a, int low, int high, int key) {
    while (low <= high) {
       int mid = (low + high) >>> 1;
       int midVal = a[mid];
       if (midVal < key)
          low = mid + 1;
       else if (midVal > key)
          high = mid - 1;
       else
          return mid; // key found
    }
    return low; // key not found.
 }

 private static int binarySearch(List<Integer> a, int key) {
    int low = 0;
    int high = a.size() - 1;
    while (low <= high) {
       int mid = (low + high) >>> 1;
       int midVal = a.get(mid);
       if (midVal < key)
          low = mid + 1;
       else if (midVal > key)
          high = mid - 1;
       else
          return mid; // key found
    }
    return low; // key not found.
 }

}