Categories
discuss

“Couldn’t upload. Try again.” error on Google Play Console

When I try to upload my Android App Bundle to the Google Play Console, I get this generic error message saying “Couldn’t upload. Try again.”.

I’ve already tried:

  • making sure my versionName and versionCode are unique among all uploaded artifacts
  • making sure that the .aab/.apk is signed with the proper key
  • re-uploading the .AAB file
  • re-uploading the .APK file
  • checking status of google services to make sure that there isn’t a mass outage
  • asking my senior Android dev what’s up

How do I resolve this error and upload my .AAB or .APK?

When I try to upload my Android App Bundle to the Google Play Console, I get this generic error message: Couldn't upload. Try again.

Answer

Google Chrome

Use a new Incognito window to upload the .aab or .apk (as mentioned in the comments).

Alternatively, clear the website data:

  1. going to: developer console (F12) > Application > Storage > Clear site data
  2. press F5 to refresh the page
  3. uploading the .apk/.aab again

Safari

Open Preferences >
Privacy > Manage Website Data > Remove All > Done

Categories
discuss

Vue 3 Composition API data() function

Reading the composition api documentation for Vue 3, I didn’t quite understand how the new Composition API works. Could you explain please where data() function has gone and if it is no longer used what to use instead?

Updated 23.10.2021: The documentation in the link has been updated and expanded to include a mention of the data() in the Composition API introduction, so this question is now deprecated.

Answer

Under the new Composition API, all of the variables that you previously defined in data() are just returned from your setup() function as normal variables with reactive values. For example, a Vue 2.0 component that had a data function like so:

data() {
  return {
    foo: 1,
    bar: { name: "hi" }
  }
}

becomes this setup() function in Vue 3:

setup() {
  const foo = ref(1);
  const bar = reactive({ name: "hi" });

  return { foo, bar }
}

The ref helper wraps a non-object value for reactivity, and reactive wraps an object. This is exposing the underlying principles of Vue more clearly than the old way, where the wrapping happened “magically” behind the scenes, but will behave the same otherwise. What I like about it personally is that your setup() function can build up your object on the go while keeping related things together, allowing it to tell a cohesive story and not require jumping around to different sections.

Categories
discuss

How can I write a extension function to instantiate a AndroidViewModel in Kotlin?

Somebody wrote two extension function (Code A2) for both Fragment and FragmentActivity to instantiate a ViewModel, it works well, you can see Code A1 and Code A3.

I hope to write two extension function (Code B2) for both Fragment and FragmentActivity to instantiate a AndroidViewModel, you can see Code B1 and Code B3, how can I do? Thanks!

Code A1

class HomeViewModel_A(private val mDBVoiceRepository: DBVoiceRepository) :  ViewModel() {

}

Code A2

inline fun <reified T : ViewModel> Fragment.getViewModel(noinline creator: (() -> T)? = null): T {
    return if (creator == null)
        ViewModelProvider(this).get(T::class.java)
    else
        ViewModelProvider(this, BaseViewModelFactory(creator)).get(T::class.java)
}

inline fun <reified T : ViewModel> FragmentActivity.getViewModel(noinline creator: (() -> T)? = null): T {
    return if (creator == null)
        ViewModelProvider(this).get(T::class.java)
    else
        ViewModelProvider(this, BaseViewModelFactory(creator)).get(T::class.java)
}

Code A3

class FragmentHome : Fragment() {
    private val mHomeViewModel_A by lazy {
        getViewModel {
            HomeViewModel_A(provideRepository(mContext))
        }
    }

}

Code B1

class HomeViewModel_B(application: Application,private val mDBVoiceRepository: DBVoiceRepository) :  AndroidViewModel(application)  {

}

Code B2

?

Code B3

class FragmentHome : Fragment() {
  private val mHomeViewModel_B by lazy {     
       ?      
  }
}

Answer

The Ktx Fragments library already has a function for concisely creating a lazy delegate to retrieve a view model: Fragment.viewModels() and FragmentActivity.viewModels().

These work for both ViewModel and AndroidViewModels with the default constructors (empty, or an Application parameter respectively), or you can use the trailing lambda to return a view model factory. You would use it like this:

class FragmentHome : Fragment() {
  private val mHomeViewModel_B: MyViewModel by viewModels()
}

or

class FragmentHome : Fragment() {
  private val mHomeViewModel_B: MyViewModel by viewModels { getMyViewModelFactory() }
}

To get something equivalent to what you have in A2, you can wrap this function to have it build a factory for you:

@Suppress("UNCHECKED_CAST")
inline fun <reified VM : ViewModel> Fragment.viewModelFactory(crossinline creator: () -> VM): Lazy<VM> {
    return viewModels {
        object : ViewModelProvider.Factory {
            override fun <T : ViewModel?> create(modelClass: Class<T>): T {
                return creator() as T
            }
        }
    }
}
Categories
discuss

Problem with loading native admob ads. No ads config or Invalid Template error

I’m trying to load admob native ads but I just can’t. I can’t see what is the problem. Spent 3 days on search and dont know where the problem is… Here is code for loading an ads:

private void getNativeAds() {
    _nativeAdmobMutable = ViewModelProviders.of(this).get(MutableNativeADModel.class);

    AdLoader.Builder builder = new AdLoader.Builder(this, GlobalConstants.numberForNativeAdmob);
    adLoader = builder.forUnifiedNativeAd(
            new UnifiedNativeAd.OnUnifiedNativeAdLoadedListener() {
                @Override
                public void onUnifiedNativeAdLoaded(UnifiedNativeAd unifiedNativeAd) {
                    _nativeAds.add(unifiedNativeAd);
                    if (!adLoader.isLoading()) {
                        _nativeAdmobMutable.setAdmobNativeAd(_nativeAds);
                    }
                    if (isDestroyed()) {
                        unifiedNativeAd.destroy();
                        return;
                    }
                }
            }).withAdListener(
            new AdListener() {

                @Override
                public void onAdLoaded() {
                    super.onAdLoaded();
                }
                @Override
                public void onAdFailedToLoad(LoadAdError errorCode) {
                    Log.d("ERROR ", errorCode.getMessage());
                    if (!adLoader.isLoading()) {
                        _nativeAdmobMutable.setAdmobNativeAd(_nativeAds);
                    }
                }
            }).withNativeAdOptions(new NativeAdOptions.Builder()
                    .build())
            .build();

    adLoader.loadAds(new AdRequest.Builder().build(), 5);

}

this method is called after

MobileAds.initialize(this, new OnInitializationCompleteListener() … etc

this are my dependencies

implementation fileTree(dir: 'libs', include: ['*.jar'])
implementation 'androidx.appcompat:appcompat:1.2.0'
implementation 'androidx.constraintlayout:constraintlayout:2.0.1'
implementation 'androidx.legacy:legacy-support-v4:1.0.0'
implementation 'com.google.android.exoplayer:exoplayer:2.10.4'
testImplementation 'junit:junit:4.12'
androidTestImplementation 'androidx.test:runner:1.3.0'
androidTestImplementation 'androidx.test.espresso:espresso-core:3.3.0'

implementation 'androidx.recyclerview:recyclerview:1.2.0-alpha05'
implementation 'com.intuit.sdp:sdp-android:1.0.6'
implementation 'com.google.android.gms:play-services-ads:19.4.0'
implementation 'androidx.lifecycle:lifecycle-extensions:2.2.0'
implementation 'com.google.code.gson:gson:2.8.5'
implementation 'com.squareup.picasso:picasso:2.71828'

Everytime onAdFailedToLoad callback is called with log:

I/Ads: Ad failed to load : 0
D/ERROR: Invalid template ID: -1

I also tried to load single ad like:

adLoader.loadAd(new AdRequest.Builder().build());

and then I get error No ads config. and I/Ads: Ad failed to load : 3

Does anyone have some idea what could be the problem here ? I also have implemented banner, interstitial and video reward, they work just fine (app is live for almost a year on GP). Ofcourse i’m using TEST ID for ads, not real one. Thanks in advance !

EDIT 1: Here is layout

<com.google.android.gms.ads.formats.UnifiedNativeAdView
android:id="@+id/ad_view"
android:layout_width="match_parent"
android:layout_height="wrap_content"
xmlns:android="http://schemas.android.com/apk/res/android">

    <LinearLayout
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_gravity="center"
        android:background="#FFFFFF"
        android:minHeight="50dp"
        android:orientation="vertical">

        <TextView
            android:id="@+id/ad_attribution"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:layout_gravity="left"
            android:textColor="#FFFFFF"
            android:textSize="12sp"
            android:text="Ad"
            android:background="#FFCC66"
            android:width="15dp"
            android:height="15dp"/>

        <LinearLayout
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:orientation="vertical"
            android:paddingLeft="20dp"
            android:paddingRight="20dp"
            android:paddingTop="3dp">

            <LinearLayout
                android:layout_width="match_parent"
                android:layout_height="wrap_content"
                android:orientation="horizontal">

                <ImageView
                    android:id="@+id/ad_icon"
                    android:layout_width="40dp"
                    android:layout_height="40dp"
                    android:adjustViewBounds="true"
                    android:paddingBottom="5dp"
                    android:paddingRight="5dp"
                    android:paddingEnd="5dp"/>

                <LinearLayout
                    android:layout_width="match_parent"
                    android:layout_height="wrap_content"
                    android:orientation="vertical">

                    <TextView
                        android:id="@+id/ad_headline"
                        android:layout_width="match_parent"
                        android:layout_height="wrap_content"
                        android:textColor="#0000FF"
                        android:textSize="16sp"
                        android:textStyle="bold" />

                    <LinearLayout
                        android:layout_width="match_parent"
                        android:layout_height="wrap_content">

                        <TextView
                            android:id="@+id/ad_advertiser"
                            android:layout_width="wrap_content"
                            android:layout_height="match_parent"
                            android:gravity="bottom"
                            android:textSize="14sp"
                            android:textStyle="bold"/>

                        <RatingBar
                            android:id="@+id/ad_stars"
                            style="?android:attr/ratingBarStyleSmall"
                            android:layout_width="wrap_content"
                            android:layout_height="wrap_content"
                            android:isIndicator="true"
                            android:numStars="5"
                            android:stepSize="0.5" />
                    </LinearLayout>

                </LinearLayout>
            </LinearLayout>

            <LinearLayout
                android:layout_width="match_parent"
                android:layout_height="wrap_content"
                android:orientation="vertical">

                <TextView
                    android:id="@+id/ad_body"
                    android:layout_width="wrap_content"
                    android:layout_height="wrap_content"
                    android:layout_marginRight="20dp"
                    android:layout_marginEnd="20dp"
                    android:textSize="12sp" />

                <com.google.android.gms.ads.formats.MediaView
                    android:id="@+id/ad_media"
                    android:layout_gravity="center_horizontal"
                    android:layout_width="250dp"
                    android:layout_height="175dp"
                    android:layout_marginTop="5dp" />

                <LinearLayout
                    android:layout_width="wrap_content"
                    android:layout_height="wrap_content"
                    android:layout_gravity="end"
                    android:orientation="horizontal"
                    android:paddingBottom="10dp"
                    android:paddingTop="10dp">

                    <TextView
                        android:id="@+id/ad_price"
                        android:layout_width="wrap_content"
                        android:layout_height="wrap_content"
                        android:paddingLeft="5dp"
                        android:paddingStart="5dp"
                        android:paddingRight="5dp"
                        android:paddingEnd="5dp"
                        android:textSize="12sp" />

                    <TextView
                        android:id="@+id/ad_store"
                        android:layout_width="wrap_content"
                        android:layout_height="wrap_content"
                        android:paddingLeft="5dp"
                        android:paddingStart="5dp"
                        android:paddingRight="5dp"
                        android:paddingEnd="5dp"
                        android:textSize="12sp" />

                    <Button
                        android:id="@+id/ad_call_to_action"
                        android:layout_width="wrap_content"
                        android:layout_height="wrap_content"
                        android:gravity="center"
                        android:textSize="12sp" />
                </LinearLayout>
            </LinearLayout>
        </LinearLayout>
    </LinearLayout>

</com.google.android.gms.ads.formats.UnifiedNativeAdView>

Loading ad i allready wrote above. This is how to connect layout

 public UnifiedNativeAdViewHolder(@NonNull View itemView) {
    super(itemView);
    adView = (UnifiedNativeAdView) itemView.findViewById(R.id.ad_view);

    // The MediaView will display a video asset if one is present in the ad, and the
    // first image asset otherwise.
    adView.setMediaView((MediaView) adView.findViewById(R.id.ad_media));

    // Register the view used for each individual asset.
    adView.setHeadlineView(adView.findViewById(R.id.ad_headline));
    adView.setBodyView(adView.findViewById(R.id.ad_body));
    adView.setCallToActionView(adView.findViewById(R.id.ad_call_to_action));
    adView.setIconView(adView.findViewById(R.id.ad_icon));
    adView.setPriceView(adView.findViewById(R.id.ad_price));
    adView.setStarRatingView(adView.findViewById(R.id.ad_stars));
    adView.setStoreView(adView.findViewById(R.id.ad_store));
    adView.setAdvertiserView(adView.findViewById(R.id.ad_advertiser));
}

and populate like this

        // Some assets are guaranteed to be in every UnifiedNativeAd.
    ((TextView) adView.getHeadlineView()).setText(nativeAd.getHeadline());
    ((TextView) adView.getBodyView()).setText(nativeAd.getBody());
    ((Button) adView.getCallToActionView()).setText(nativeAd.getCallToAction());

    // These assets aren't guaranteed to be in every UnifiedNativeAd, so it's important to
    // check before trying to display them.
    NativeAd.Image icon = nativeAd.getIcon();

    if (icon == null) {
        adView.getIconView().setVisibility(View.INVISIBLE);
    } else {
        ((ImageView) adView.getIconView()).setImageDrawable(icon.getDrawable());
        adView.getIconView().setVisibility(View.VISIBLE);
    }

    if (nativeAd.getPrice() == null) {
        adView.getPriceView().setVisibility(View.INVISIBLE);
    } else {
        adView.getPriceView().setVisibility(View.VISIBLE);
        ((TextView) adView.getPriceView()).setText(nativeAd.getPrice());
    }

    if (nativeAd.getStore() == null) {
        adView.getStoreView().setVisibility(View.INVISIBLE);
    } else {
        adView.getStoreView().setVisibility(View.VISIBLE);
        ((TextView) adView.getStoreView()).setText(nativeAd.getStore());
    }

    if (nativeAd.getStarRating() == null) {
        adView.getStarRatingView().setVisibility(View.INVISIBLE);
    } else {
        ((RatingBar) adView.getStarRatingView())
                .setRating(nativeAd.getStarRating().floatValue());
        adView.getStarRatingView().setVisibility(View.VISIBLE);
    }

    if (nativeAd.getAdvertiser() == null) {
        adView.getAdvertiserView().setVisibility(View.INVISIBLE);
    } else {
        ((TextView) adView.getAdvertiserView()).setText(nativeAd.getAdvertiser());
        adView.getAdvertiserView().setVisibility(View.VISIBLE);
    }

    // Assign native ad object to the native view.
    adView.setNativeAd(nativeAd);

Answer

Did you try to rebuild project?

Categories
discuss

How can I improve this search algorithms runtime?

I’m trying to solve an interview problem I was given a few years ago in preparation for upcoming interviews. The problem is outlined in a pdf here. I wrote a simple solution using DFS that works fine for the example outlined in the document, but I haven’t been able to get the program to meet the criteria of

Your code should produce correct answers in under a second for a 10,000 x 10,000 Geo GeoBlock containing 10,000 occupied Geos.

To test this I generated a CSV file with 10000 random entries and when I run the code against it, it averages just over 2 seconds to find the largest geo block in it. I’m not sure what improvements could be made to my approach to cut the runtime by over half, other than running it on a faster laptop. From my investigations it appears the search itself seems to only take about 8ms, so perhaps the way I load the data into memory is the inefficient part?

I’d greatly appreciate an advice on how this could be improved. See code below:

GeoBlockAnalyzer

package analyzer.block.geo.main;

import analyzer.block.geo.model.Geo;
import analyzer.block.geo.result.GeoResult;

import java.awt.*;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.time.format.DateTimeParseException;
import java.util.List;
import java.util.*;

public class GeoBlockAnalyzer {

  private static final DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd");
  private final int width;
  private final int height;
  private final String csvFilePath;
  private GeoResult result = new GeoResult();

  // Map of the geo id and respective geo object
  private final Map<Integer, Geo> geoMap = new HashMap<>();
  // Map of coordinates to each geo in the grid
  private final Map<Point, Geo> coordMap = new HashMap<>();

  /**
   * Constructs a geo grid of the given width and height, populated with the geo data provided in
   * the csv file
   *
   * @param width the width of the grid
   * @param height the height of the grid
   * @param csvFilePath the csv file containing the geo data
   * @throws IOException
   */
  public GeoBlockAnalyzer(final int width, final int height, final String csvFilePath)
      throws IOException {

    if (!Files.exists(Paths.get(csvFilePath)) || Files.isDirectory(Paths.get(csvFilePath))) {
      throw new FileNotFoundException(csvFilePath);
    }

    if (width <= 0 || height <= 0) {
      throw new IllegalArgumentException("Input height or width is 0 or smaller");
    }

    this.width = width;
    this.height = height;
    this.csvFilePath = csvFilePath;

    populateGeoGrid();
    populateCoordinatesMap();
    calculateGeoNeighbours();
    // printNeighbours();
  }

  /** @return the largest geo block in the input grid */
  public GeoResult getLargestGeoBlock() {
    for (final Geo geo : this.geoMap.values()) {
      final List<Geo> visited = new ArrayList<>();
      search(geo, visited);
    }
    return this.result;
  }

  /**
   * Iterative DFS implementation to find largest geo block.
   *
   * @param geo the geo to be evaluated
   * @param visited list of visited geos
   */
  private void search(Geo geo, final List<Geo> visited) {
    final Deque<Geo> stack = new LinkedList<>();
    stack.push(geo);
    while (!stack.isEmpty()) {
      geo = stack.pop();
      if (visited.contains(geo)) {
        continue;
      }
      visited.add(geo);

      final List<Geo> neighbours = geo.getNeighbours();
      for (int i = neighbours.size() - 1; i >= 0; i--) {
        final Geo g = neighbours.get(i);
        if (!visited.contains(g)) {
          stack.push(g);
        }
      }
    }
    if (this.result.getSize() < visited.size()) {
      this.result = new GeoResult(visited);
    }
  }

  /**
   * Creates a map of the geo grid from the csv file data
   *
   * @throws IOException
   */
  private void populateGeoGrid() throws IOException {
    try (final BufferedReader br = Files.newBufferedReader(Paths.get(this.csvFilePath))) {
      int lineNumber = 0;
      String line = "";
      while ((line = br.readLine()) != null) {
        lineNumber++;
        final String[] geoData = line.split(",");
        LocalDate dateOccupied = null;

        // Handle for empty csv cells
        for (int i = 0; i < geoData.length; i++) {
          // Remove leading and trailing whitespace
          geoData[i] = geoData[i].replace(" ", "");

          if (geoData[i].isEmpty() || geoData.length > 3) {
            throw new IllegalArgumentException(
                "There is missing data in the csv file at line: " + lineNumber);
          }
        }
        try {
          dateOccupied = LocalDate.parse(geoData[2], formatter);
        } catch (final DateTimeParseException e) {
          throw new IllegalArgumentException("There input date is invalid on line: " + lineNumber);
        }
        this.geoMap.put(
            Integer.parseInt(geoData[0]),
            new Geo(Integer.parseInt(geoData[0]), geoData[1], dateOccupied));
      }
    }
  }

  /** Create a map of each coordinate in the grid to its respective geo */
  private void populateCoordinatesMap() {
    // Using the geo id, calculate its point on the grid
    for (int i = this.height - 1; i >= 0; i--) {
      int blockId = (i * this.width);
      for (int j = 0; j < this.width; j++) {
        if (this.geoMap.containsKey(blockId)) {
          final Geo geo = this.geoMap.get(blockId);
          geo.setCoordinates(i, j);
          this.coordMap.put(geo.getCoordinates(), geo);
        }
        blockId++;
      }
    }
  }

  private void calculateGeoNeighbours() {
    for (final Geo geo : this.geoMap.values()) {
      addNeighboursToGeo(geo);
    }
  }

  private void addNeighboursToGeo(final Geo geo) {
    final int x = geo.getCoordinates().x;
    final int y = geo.getCoordinates().y;

    final Point[] possibleNeighbours = {
      new Point(x, y + 1), new Point(x - 1, y), new Point(x + 1, y), new Point(x, y - 1)
    };

    Geo g;
    for (final Point p : possibleNeighbours) {
      if (this.coordMap.containsKey(p)) {
        g = this.coordMap.get(p);
        if (g != null) {
          geo.getNeighbours().add(g);
        }
      }
    }
  }

  private void printNeighbours() {
    for (final Geo geo : this.geoMap.values()) {
      System.out.println("Geo " + geo.getId() + " has the following neighbours: ");
      for (final Geo g : geo.getNeighbours()) {
        System.out.println(g.getId());
      }
    }
  }
}

GeoResult

package analyzer.block.geo.result;

import analyzer.block.geo.model.Geo;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class GeoResult {

    private final List<Geo> geosInBlock = new ArrayList<>();

    public GeoResult() {
    }

    public GeoResult(final List<Geo> geosInBlock) {
        this.geosInBlock.addAll(geosInBlock);
    }

    public List<Geo> getGeosInBlock() {
        this.geosInBlock.sort(Comparator.comparingInt(Geo::getId));
        return this.geosInBlock;
    }

    public int getSize() {
        return this.geosInBlock.size();
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append("The geos in the largest cluster of occupied Geos for this GeoBlock are: n");
        for(final Geo geo : this.geosInBlock) {
            sb.append(geo.toString()).append("n");
        }
        return sb.toString();
    }
}

Geo

package analyzer.block.geo.model;

import java.awt.Point;
import java.time.LocalDate;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class Geo {

    private final int id;
    private final String name;
    private final LocalDate dateOccupied;
    private final Point coordinate;
    private final List<Geo> neighbours = new ArrayList<>();

    public Geo (final int id, final String name, final LocalDate dateOccupied) {
        this.id = id;
        this.name = name;
        this.dateOccupied = dateOccupied;
        this.coordinate = new Point();
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public LocalDate getDateOccupied() {
        return this.dateOccupied;
    }

    public void setCoordinates(final int x, final int y) {
        this.coordinate.setLocation(x, y);
    }

    public Point getCoordinates() {
        return this.coordinate;
    }

    public String toString() {
        return this.id + ", " + this.name + ", " + this.dateOccupied;
    }

    public List<Geo> getNeighbours() {
        return this.neighbours;
    }

    @Override
    public int hashCode() {
        return Objects.hash(this.id, this.name, this.dateOccupied);
    }

    @Override
    public boolean equals(final Object obj) {
        if(this == obj) {
            return true;
        }

        if(obj == null || this.getClass() != obj.getClass()) {
           return false;
        }

        final Geo geo = (Geo) obj;
        return this.id == geo.getId() &&
                this.name.equals(geo.getName()) &&
                this.dateOccupied == geo.getDateOccupied();
    }
}

Answer

The major optimization available here is a conceptual one. Unfortunately, this type of optimization is not easy to teach, nor look up in a reference somewhere. The principle being used here is:

It’s (almost always) cheaper to use an analytic formula to compute a known result than to (pre)compute it. [1]

It’s clear from your code & the definition of your problem that you are not taking advantage of this principle and the problem specification. In particular, one of the key points taken directly from the problem specification is this:

Your code should produce correct answers in under a second for a 10,000 x 10,000 Geo GeoBlock containing 10,000 occupied Geos.

When you read this statement a few things should be going through your mind (when thinking about runtime efficiency):

  • 10,000^2 is a much larger number than 10,000 (exactly 10,000 times larger!) There is a clear efficiency gain if you can maintain an algorithm that is O(n) as opposed to O(n^2) (in the expected case because of the use of hashing.)
  • touching (i.e. computing any O(1) operation) for the entire grid is going to immediately yield a O(n^2) algorithm; clearly, this is something that must be avoided if possible
  • from the problem statement, we should never expect O(n^2) geo’s that need to be touched. This should be a major hint as to what the person who wrote the problem is looking for. BFS or DFS is an O(N+M) algorithm where N,M are the number of nodes and edges touched. Thus, we should be expecting an O(n) search.
  • based on the above points, it is clear that the solution being looked for here should be O(10,000) for a problem input with grid size 10,000 x 10,000 and 10,000 geos

The solution you provided is O(n^2) because,

  1. You use visited.contains where visited is a List. This is not showing up in your testing as a problem area because I suspect you are using small geo clusters. Try using a large geo cluster (one with 10,000 geos.) You should see a major slow down as compared to say the largest cluster having 3 geos. The solution here is to use an efficient data structure for visited, some that come to mind are a bit set (unknown to me if Java has any available, but any decent language should) or a hash set (clearly Java has some available.) Because you did not notice this in testing, this suggests to me you are not vetting/testing your code well enough with enough varied examples of the corner cases you expect. This should of come up immediately in any thorough testing/profiling of your code. As per my comment, I would of liked to have seen this type of groundwork/profiling done before the question was posted.
  2. You touch the entire 10,000 x 10,000 grid in the function/member populateCoordinatesMap. This is clearly already O(n^2) where n=10,000. Notice, that the only location where coordMap is used outside of populateCoordinatesMap is in addNeighboursToGeo. This is a major bottleneck, and for no reason, addNeighboursToGeo can be computed in O(1) time without the need for a coordMap. However, we can still use your code as is with a minor modification given below.

I hope it is obvious how to fix (1). To fix (2), replace populateCoordinatesMap

  /** Create a map of each coordinate in the grid to its respective geo */
  private void populateCoordinatesMap() {
   for (Map.Entry<int,Geo> entry : geoMap.entrySet()) {
     int key = entry.getKey();
     Geo value = entry.getValue();
     int x = key % this.width;
     int y = key / this.width;  
     value.setCoordinates(x, y);
     this.coordMap.put(geo.getCoordinates(), geo); 
   }
  }

Notice the principle being put to use here. Instead of iterating over the entire grid as you were doing before (O(n^2) immediately), this iterates only over the occupied Geos, and uses the analytic formula for indexing a 2D array (as opposed to doing copious computation to compute the same thing.) Effectively, this change improves populateCoordinatesMap from being O(n^2) to being O(n).

Some general & opinionated comments below:

  • Overall, I strongly disagree with using an object oriented approach over a procedural one for this problem. I think the OO approach is completely unjustified for how simple this code should be, but I understand that the interviewer wanted to see it.
  • This is a very simple problem you are trying to solve, and I think the object orientated approach you took here confounds it so much so you could not see the forest for the trees (or perhaps the trees for the forest.) A much simpler approach could of been taken in how this algorithm was implemented, even using an object oriented approach.
  • It’s clear from the points above, you could benefit from knowing the available tools in the language you are working in. By this I mean you should know what containers are readily available and what the trade offs are for using each operation on each container. You should also know at least one decent profiling tool for the language you are working with if you are going to be looking into optimizing code. Given that you failed to post a profiling summary, even after I asked for it, it suggests to me you do not know of such a tool with Java. Learn one.

[1] I provide no reference for this principle because it is a first principle, and can be explained by the fact that running fewer constant time operations is cheaper than running many. The assumption here is that the known analytic form requires less computation. There are occasional exceptions to this rule. But it should be stressed that such exceptions are almost always because of hardware limitations or advantages. For example, when computing the hamming distance it is cheaper to use a precomputed LUT for computing the population count on a hardware architecture without access to SSE registers/operations.

Source: stackoverflow
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Privacy Policy, and Copyright Policy. Content is available under CC BY-SA 3.0 unless otherwise noted. The answers/resolutions are collected from stackoverflow, are licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 © No Copyrights, All Questions are retrived from public domain..